HashTable是Map接口线程安全实现版本,数据结构和方法实现与HashMap类似。
HashTable类层级关系图:
主要成员变量:
// 内部采用Entry数组存储键值对数据,Entry实际为单向链表的表头
private transient Entry<?,?>[] table;
// HashTable里键值对个数
private transient int count;
// 扩容阈值,当超过这个值时,进行扩容操作,计算方式为:数组容量*加载因子
private int threshold;
// 加载因子
private float loadFactor;
// 用于快速失败
private transient int modCount = 0;
Entry代码如下:
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
......
}
Entry为单向链表节点,HashTable采用数组加链表的方式存储数据,不过没有类似于HashMap中当链表过长时转换为红黑树的操作。
初始化HashTable
时,都会直接进行容量初始化。
//
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
// 设置指定容量和加载因子,初始化HashTable
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)
// 容量最小为1
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
// 初始扩容阈值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// 设置指定容量初始HashTable,加载因子为0.75
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 手动指定数组初始容量为11,加载因子为0.75
public Hashtable() {
this(11, 0.75f);
}
put(K key, V value)
添加指定键值对,键和值都不能为null:
// 方法synchronized修饰,线程安全
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
// 得到key的哈希值
int hash = key.hashCode();
// 得到该key存在到数组中的下标
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 得到该下标对应的Entry
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 如果该下标的Entry不为null,则进行链表遍历
for(; entry != null ; entry = entry.next) {
// 遍历链表,如果存在key相等的节点,则替换这个节点的值,并返回旧值
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 如果数组下标对应的节点为空,或者遍历链表后发现没有和该key相等的节点,则执行插入操作
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
// 模数+1
modCount++;
Entry<?,?> tab[] = table;
// 判断是否需要扩容
if (count >= threshold) {
// 如果count大于等于扩容阈值,则进行扩容
rehash();
tab = table;
// 扩容后,重新计算该key在扩容后table里的下标
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
// 采用头插的方式插入,index位置的节点为新节点的next节点
// 新节点取代inde位置节点
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
// count+1
count++;
}
get(Object key)
获取指定key对应的value:synchronized修饰,线程安全。
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 根据key哈希得到index,遍历链表取值
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
rehash
扩容操作:
protected void rehash() {
// 暂存旧的table和容量
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// 新容量为旧容量的2n+1倍
int newCapacity = (oldCapacity << 1) + 1;
// 判断新容量是否超过最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0) {
// 如果旧容量已经是最大容量大话,就不扩容了
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
// 新容量最大值只能是MAX_ARRAY_SIZE
newCapacity = MAX_ARRAY_SIZE;
}
// 用新容量创建一个新Entry数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
// 模数+1
modCount++;
// 重新计算下次扩容阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
// 将新Entry数组赋值给table
table = newMap;
// 遍历数组和链表,进行新table赋值操作
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
remove(Object key)
删除指定key,返回对应的value:synchronized修饰,线程安全。
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 获取key对应的index
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 遍历链表,如果找到key相等的节点,则改变前继和后继节点的关系,并删除相应引用,让GC回收
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<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;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。