Hashtable

/ Java / 没有评论 / 352浏览

今天我们来分析一下Hashtable的底层实现。提到Hashtable可能对于有些人来说会比较陌生,因为不经常使用。这是因为Hashtable是很早就有的集合类了,因为它是在JDK1.0版本中存在的。HashMap集合是在Hashtable集合之后才有的。也可以理解为HashMap集合是优化后的Hashtable。所以它们底层的实现方式几乎是一样,但它们也有些不同的地方要注意,并且它们都是用哈希表的方式存储的。既然我们已经掌握了HashMap的底层实现,那么我们在分析Hashtable时会比较容易,所以本篇中将直接分析Hashtable的底层源码,将不在介绍哈希表的相关知识了。还是和其它集合一样,我们还是先看Hashtable的初始化。

public Hashtable() {
this(11, 0.75f);
}
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);
}
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;
}

@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}

public K getKey() {
return key;
}

public V getValue() {
return value;
}

public V setValue(V value) {
if (value == null)
throw new NullPointerException();

V oldValue = this.value;
this.value = value;
return oldValue;
}

public boolean equals(Object o) {
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();
}
}

上面源码是Hashtable集合初始化时所调用的方法,也就是我们通过默认无参的构造方法创建Hashtable对象时,就会执行上述代码。因为我们已经分析过HashMap中的源码了,所以在这里我们将不做过多的解释了。我们将重点分析一下Hashtable初始化与HashMap初始化有何不同。

我们在HashMap这篇文章中分析过,在通过无参的构造方法创建HashMap对象时,只会设置HashMap中的加载因子为默认的0.75,并不会执行底层数组的初始化。而在Hashtable中,不但设置了默认的加载因子为0.75,并且已经将底层的数组初始化了。默认初始化的数组大小为为了11。

下面我们看一下Hashtable中的put方法的底层实现逻辑。

public synchronized V put(K key, V value) {
if (value == null) {
throw new NullPointerException(); // 如果添加的元素的value值为null则直接抛出异常,这就说明,在Hashtable中不能保存value为null的元素
}

Entry<?,?> tab[] = table; // 定义一个Entry类型的数据保存数据
int hash = key.hashCode(); // 获取key的hash code,也就是调用Object对象中默认的hashCode方法 因为是直接调用hashCode方法,所以在Hashtable中key也不能为空,否则此出将抛空指针异常
int index = (hash & 0x7FFFFFFF) % tab.length; // 确认数组中要添加元素的位置
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index]; // 获取数组中上面hash code对应的索引位置的Entry类型数据
for(; entry != null ; entry = entry.next) { // 循环遍历索引位置的链表数据
if ((entry.hash == hash) && entry.key.equals(key)) { // 判断链表中Entry类型数据的hash code及key与新添加元素的key和hash code是否相同,如果相同则用新元素中的value覆盖原链表中的Entry类型中的value,并返回原链表中Entry类型的value值
V old = entry.value;
entry.value = value;
return old;
}
}

addEntry(hash, key, value, index); // 如果在链表中没有检索到相同的key则将新元素添加到链表中
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;

Entry<?,?> tab[] = table; // 获取底层数组
if (count >= threshold) { // 判断是否需要将底层数组进行扩展,也就是执行再散列
rehash(); // 执行再散列的方法

tab = table; // 将散列后的数组重新赋值给tab
hash = key.hashCode(); // 计算新元素key的hash code
index = (hash & 0x7FFFFFFF) % tab.length; // 重新确认散列后数组中的添加元素的位置
}

@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index]; // 返回数组中当前索引位置的Entry对象
tab[index] = new Entry<>(hash, key, value, e); // 创建一个Entry对象保存新添加元素的数据并设置当前Entry对象的后继节点为原数组索引中返回的Entry对象
count++;
}
protected void rehash() {
int oldCapacity = table.length; // 获取原数组的长度
Entry<?,?>[] oldMap = table; // 保存原数组的数据   
int newCapacity = (oldCapacity << 1) + 1; // 计算重新扩容后的数组大小 ,按上面执行的算法每次扩容时新数组的大小都为原大小的2倍加1
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; // 重新初始化新的数组

modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); // 计算下次扩容时的参数值
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;
}
}
}

通过对上面源码的分析,我们可以得出以下Hashtable的特性。