前面学习的集合都是非线程安全的，这次学习的集合它的方法都加了同步，使得它是线程安全的。
简介
- 基于hash表实现，存放key-value对，通过单链表解决hash冲突
- 当容量超过闸值时，会进行扩容
- 实现Serializable、Cloneable接口，支持克隆和序列化
- 线程安全，可用于多线程中
源码
构造方法
//存放单链表，用于解决冲突，每个HashtableEntry实际是单链表
private transient HashtableEntry<?,?>[] table;
// Hashtable中的元素个数
private transient int count;
//闸值，用于判断是否扩容
private int threshold;
//加载因子
private float loadFactor;
// Hashtable的操作次数
private transient int modCount = 0;
//序列号
private static final long serialVersionUID = 1421746759512286392L;
//指定初始容量和加载因子
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException(“Illegal Capacity: “+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException(“Illegal Load: “+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new HashtableEntry<?,?>[initialCapacity];//初始化数组
// Android-changed: Ignore loadFactor when calculating threshold from initialCapacity
// threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1);//选定闸值
}
//指定大小
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
//默认构造函数
public Hashtable() {
this(11, 0.75f);
}
//指定Map
public Hashtable(Map<? Extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}方法
public synchronized Enumeration<K> keys() {
//获取Key的枚举对象
return this.<K>getEnumeration(KEYS);
}
public synchronized Enumeration<V> elements() {
//获取Value的枚举对象
return this.<V>getEnumeration(VALUES);
}
public synchronized boolean contains(Object value) {
//是否包含值为value的元素
if (value == null) {
throw new NullPointerException();
}
HashtableEntry<?,?> tab[] = table;
//遍历HashTable中的所有元素
for (int I = tab.length ; i-- > 0 ;) {
for (HashtableEntry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
public synchronized oolean containsKey(Object key) {
//是否包含key的元素
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;//先计算出在数组的索引
for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
//遍历判断是否key又=有存在
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}
public synchronized V get(Object key) {
//获取key对应的Value
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;//计算出在数组中的索引
for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
//遍历
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
private void addEntry(int hash, K key, V value, int index) {
//添加元素
modCount++;
HashtableEntry<?,?> tab[] = table;
if (count >= threshold) {
//如果当前大小大于闸值
// Rehash the table if the threshold is exceeded
rehash();//调整数组大小
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;//计算得到索引
}
//将新元素插进到对应链表的表头
@SuppressWarnings(“unchecked”)
HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
tab[index] = new HashtableEntry<>(hash, key, value, e);
count++;
}
protected void rehash() {
//调整HashTable的长度
int oldCapacity = table.length;
HashtableEntry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;//新的长度为:旧长度*2+1
if (newCapacity – MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)//如果原来的长度已经是限定的最大值，则无需创建新的HashTable
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;//限定不能超过元素最大值
}
HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);//重新确定闸值
table = newMap;
for (int I = oldCapacity ; i-- > 0 ;) {
//将所有元素复制到新的HashTable
for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
HashtableEntry<K,V> e = old;
old = old.next;
//重新计算hash值
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
//将节点放到链头
e.next = (HashtableEntry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
public synchronized V put(K key, V value) {
//添加新元素，如果存在key和hash相同则更换对应元素原本的Value
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings(“unchecked”)
HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
//说明元素存在，替换值
V old = entry.value;
entry.value = value;
return old;
}
}
//如果不存在则添加进去
addEntry(hash, key, value, index);
return null;
}
public synchronized V remove(Object key) {
//删除key对应的元素
HashtableEntry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;//得到在hashTable的索引
@SuppressWarnings(“unchecked”)
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
//保留前一个节点，能够有效地删除
for(HashtableEntry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
//找到对应的元素的位置
modCount++;
if (prev != null) {
//不在链头，从链表中摘除
prev.next = e.next;
} else {
//在链头，直接将第二个元素覆盖到链头
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;//返回删除元素对应的值
}
}
return null;
}
public synchronized void putAll(Map<? Extends K, ? extends V> t) {
//将整个Map添加
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())//遍历逐个添加
put(e.getKey(), e.getValue());
}
public synchronized void clear() {
//将HashTable中的所有链头置空
HashtableEntry<?,?> tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;
count = 0;
}
//获取枚举类对象，如果长度为0则返回一个空枚举，否则返回一个正常枚举对象
private <T> Enumeration<T> getEnumeration(int type) {
if (count == 0) {
return Collections.emptyEnumeration();
} else {
//type表示要得到什么类型的枚举类
return new Enumerator<>(type, false);
}
}
//获取一个迭代器，逻辑与以上方法相同
private <T> Iterator<T> getIterator(int type) {
if (count == 0) {
return Collections.emptyIterator();
} else {
return new Enumerator<>(type, true);
}
}
private transient volatile Set<K> keySet;//key集合，没有重复
private transient volatile Set<Map.Entry<K,V>> entrySet;//节点集合，没有重复
private transient volatile Collection<V> values;//Value集合，可重复
public Set<K> keySet() {
//获取一个Key集合
if ( keySet == null)
//synchronizedSet目的是给KeySet的所有方法都添加synchronized
ketSet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() { return getIterator(KEYS); }
public int size() {
return count; }
public boolean contains(Object o) {
return containsKey(o); }
public boolean remove(Object o) {
return Hashtable.this.remove(o) != null; }
public void clear() { Hashtable.this.clear();}
}
public Set<Map.Entry<K,V>> entrySet() {
//获取所有元素的集合
if (entrySet==null)
entrySet = Collections.synchronizedSet(new EntrySet(), this);
return entrySet;
}
//元素集合类
private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return getIterator(ENTRIES);
}
public oolean add(Map.Entry<K,V> o) {
return super.add(o);
}
//判断是否存在的标准是节点的hash、key和value都相等
public oolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
Object key = entry.getKey();
HashtableEntry<?,?>[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
//遍历判断
for (HashtableEntry<?,?> e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
return false;
}
//删除的逻辑为：找到目标节点，然后具体逻辑与前面的remove一样（实际就是单链表删除元素）
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
HashtableEntry<?,?>[] tab = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings(“unchecked”)
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
for(HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
modCount++;
if (prev != null)//说明要元素不在链头
prev.next = e.next;
else//说明要删除的元素在链头
tab[index] = e.next;
count--;
e.value = null;
return true;
}
}
return false;
}
public int size() {
return count; }
public void clear() {Hashtable.this.clear();}
}
public Collection<V> values() {
//获取所有元素值的集合
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(),this);
return values;
}
//值集合的实现类
private class ValueCollection extends AbstractCollection<V> {
public Iterator<V> iterator() {
return getIterator(VALUES);
}
public int size() {
return count;
}
public oolean contains(Object o) {
return containsValue(o);
}
public void clear() {
Hashtable.this.clear();
}
}
//HashTable的比较，若两个集合的key-value都相等则两个相同
public synchronized boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<?,?> t = (Map<?,?>) o;
if (t.size() != size())
return false;
try {
Iterator<Map.Entry<K,V>> I = entrySet().iterator();
while (i.hasNext()) {
Map.Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(t.get(key)==null && t.containsKey(key)))
return false;
} else {
if (!value.equals(t.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
public synchronized int hashCode() {
//重写：获取hash值；如果当前实际元素为0或者加载因子小于0,则直接返回0
//否则返回table数组中所有元素的hash值的总和
int h = 0;
if (count == 0 || loadFactor < 0)
return h; // Returns zero
loadFactor = -loadFactor; // Mark hashCode computation in progress
HashtableEntry<?,?>[] tab = table;
for (HashtableEntry<?,?> entry : tab) {
while (entry != null) {
h += entry.hashCode();
entry = entry.next;
}
}
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
}
Entry
//HashTable的节点，实际是一个单链表
private static class HashtableEntry<K,V> implements Map.Entry<K,V> {
// END Android-changed: Renamed Entry -> HashtableEntry.
final int hash;//hash值
final K key;//Key值
V value;//Value值
HashtableEntry<K,V> next;//下一个节点
protected HashtableEntry(int hash, K key, V value, HashtableEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings(“unchecked”)
protected Object clone() {
return new HashtableEntry<>(hash, key, value,
(next==null ? null : (HashtableEntry<K,V>) next.clone()));
}
public K getKey() {
return key; }
public V getValue() {
return value; }
//设置Value，若Value为null则抛出异常
public V setValue(V value) {
if (value == null)//说明HashTable的Value不能为null
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
//比较的是key和value都要相等
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() { return hash ^ Objects.hashCode(value); }
public String toString() { return key.toString()+”=”+value.toString();}
}
枚举类
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
HashtableEntry<?,?>[] table = Hashtable.this.table;
int index = table.length;//初始化下标
HashtableEntry<?,?> entry;//当前entry
HashtableEntry<?,?> lastReturned;//随后返回的entry
int type;//指定的迭代器类型
boolean iterator;/是否为迭代器
protected int expectedModCount = modCount;//用于fast-faild机制
//指定要返回的是什么类型的数据（key/value/entry）和是否为迭代器
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}
//判断是否还有存在没有遍历的元素
//1.先从后遍历table数组中的元素
//2.向后遍历每个单链表，直到链表结束，再继续遍历table
public boolean hasMoreElements() {
HashtableEntry<?,?> e = entry;
int I = index;
HashtableEntry<?,?>[] t = table;
/* Use locals for faster loop iteration */
//从当前所有（index）向前找到第一个不为null的节点，找不到则返回false
//如果当前的entry不为null则不用去寻找
while (e == null && I > 0) {
e = t[--i];
}
entry = e;
index = I;
return e != null;
}
@SuppressWarnings(“unchecked”)
public T nextElement() {
//获取到下一个元素
HashtableEntry<?,?> et = entry;
int I = index;
HashtableEntry<?,?>[] t = table;
//从当前所有（index）向前找到第一个不为null的节点
//如果当前的entry不为null则不用去寻找
while (et == null && I > 0) {
et = t[--i];
}
entry = et;
index = I;
if (et != null) {
HashtableEntry<?,?> e = lastReturned = entry;
entry = e.next;
//根据指定的类型返回
return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
}
throw new NoSuchElementException(“Hashtable Enumerator”);//找不到元素
}
// Iterator methods
public boolean hasNext() {
return hasMoreElements();
}
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
}
public void remove() {
if (!iterator)//如果没有指定为iterator，则不能进行删除操作
throw new UnsupportedOperationException();
if (lastReturned == null)//如果连续执行删除操作则抛异常
throw new IllegalStateException(“Hashtable Enumerator”);
if (modCount != expectedModCount)//fast-faild机制
throw new ConcurrentModificationException();
synchronized(Hashtable.this) {
//进行删除操作
HashtableEntry<?,?>[] tab = Hashtable.this.table;
int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;//找到在table数组中的索引
@SuppressWarnings(“unchecked”)
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index];
for(HashtableEntry<K,V> prev = null; e != null; prev = e, e = e.next) {
if (e == lastReturned) {
//找到节点并从链表中删除
modCount++;
expectedModCount++;
if (prev == null)
tab[index] = e.next;
else
prev.next = e.next;
count--;
lastReturned = null;
return;
}
}
throw new ConcurrentModificationException();
}
}
}
总结
- 内部结构：数组（存放表头）+链表（节点为hash+key+value+next）
- 构造函数：有4个构造方法，默认大小为11，加载因子为0.75，扩容时为原来长度的两倍+1，重新计算hash值和确定闸值（Math.min(加载因子*新的长度,MAX_ARRAY_SIZE + 1)）
- key和value都不允许为null
- 用模运算确定在table数组中的索引：(hash&0x7FFFFFFF)%table.length，这样操作的目标是为了可以将负值的hash转为正值
- 线程安全，每个方法都进行同步，但是效率相对HashMap会低一些。
文章评论