在之前学习HashMap的时候,我们知道在JDK8中HashMap是采用Node数组+链表+红黑树的方式实现的。那么HashTable又是怎样的?
字面上看应该还是利用的Hash表来处理的。那么我们基于这样一点知识来学习一下HashTable的设计和实现过程。
从结构上看,HashTable的结构也没有HashMap那么复杂。所以实现起来应该还是比较简单吧。从类的静态变量看,基本和HashMap没有什么差别。
比如table、threshold、loadFactor,似乎说明HashTable也仅仅是HashMap的小弟弟。那么是这样吗?咋从初始化方法看起。
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 Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
在初始化方法中,和HashMap类似有4个方法。当传入的初始化容量为0,那么就就初始化为1,否则如果是正常的数字,那么就直接做为容量了。看来是和HashMap不一样哦。然后计算了扩容上限。在默认的重载因子还是和hashMap一样0.75,如果传入的是一个map,那么就把容量的2倍与11做比较,然后取最大值。这里为什么要选择11而不是12呐?而且看的出来Hashtable相比与HashMap还是相当的保守呀。
那么在添加元素的时候,hashtable又是如何做的呐?是否和hashmap一样?
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的hashCode作为hash值,这和hashMap的二次计算有所不同 int hash = key.hashCode(); //和hashMap的下标计算类似 int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<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; } private void addEntry(int hash, K key, V value, int index) { modCount++;
Entry<?,?> tab[] = table; if (count >= threshold) { //扩容 // Rehash the table if the threshold is exceeded rehash();
tab = table; hash = key.hashCode(); //扩容之后计算下标 index = (hash & 0x7FFFFFFF) % tab.length; }
// Creates the new entry. @SuppressWarnings("unchecked") //拿到数组的下标,然后进行赋值 Entry<K,V> e = (Entry<K,V>) tab[index]; tab[index] = new Entry<>(hash, key, value, e); //对容量进行添加 count++; }
我们看到添加的方法用了synchronized修饰,说明是线程安全的。那么这里的扩容也显然是安全的。那么它是如何进行扩容的?
protected void rehash() {
//拿到容量
int oldCapacity = table.length;
//缓存老的数据
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//用老的容量左移1位,然后加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;
newCapacity = MAX_ARRAY_SIZE;
}
//开辟新的数组空间
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
//重新计算扩容上限
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//从后向前遍历
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;
}
}
}
可以看到这里的reshash就是对扩容,然后通过hash值与0x7FFFFFFF的与运算,然后得到新的地址空间。感觉这块还是比较绕的。但是感觉经过扩容之后就没有链表了。但好像上边也没有往链表中放数据。
在方法putIfAbsent中
@Override
public synchronized V putIfAbsent(K key, V value) {
Objects.requireNonNull(value);
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//遍历链表
for (; entry != null; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
if (old == null) {
//对链表赋值
entry.value = value;
}
return old;
}
}
//添加元素
addEntry(hash, key, value, index);
return null;
}
那么获取元素怎么?
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
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;
}
获取元素的时候也是加的synchronized,那么也是线程安全的。首先计算下标,然后遍历链表。