Hashtable源码分析
基于Java8
Hashtable.class的说明：
This class implements a hash table, which maps keys to values.
Any non-null object can be used as a key or as a value.
To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
什么是hash table
- table
table很好理解，table（表）如数据库表或者Excel表格，这个数据结构的特征是键值对的形式（K-V），通过唯一的key（对象）可以得到对应的数据（对象）。
如下面的一个简单的表格：
| id | value |
|---|---|
| 1 | one |
| 2 | two |
| 3 | three |
这一个简单的线性表，它的映射关系很简单：位置（序号）映射到元素。
- hash
那么hash是什么呢？如果上面的线性表叫做LinerTable，类比起来，HashTable的hash可能也是数据的排列或者说存取方式。
百科上的定义：
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
那么看来就是使用hash函数来得出某个值，然后再使用这个值来映射到table的元素，而不是简单的加入序号。
Hashtable原理
- 结构
查看Hashtable的源码不难看出，Hashtable底层是一个对象数组：
// 核心构造器
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity 数组的初始容量，默认是11
* @param loadFactor 动态扩容的系数，默认0.75f
* @exception IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive.
*/
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);
}
可以看出Hashtable是一个Entry数组。那么这个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类的属性和构造器可以看出，它聚合了一个Entry对象作为next，显然，它是一个单向链表元素的实现类，多个Entry关联起来便是一个单向数组。那么至此Hashtable的结构就很清晰了，它是一个链表和数组的组合结构。即Hashtable是一个数组，数组的元素是单向链表元素类型。
hashtable.PNG
那么，元素的位置（数组的index）是怎么决定的呢？很明显这里会用到hash而不是按添加顺序来排了（按顺序那和list有什么区别）。
hash用在了何处：
- 数据存储
put方法
/**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this hashtable. Neither the key nor the
* value can be <code>null</code>. <p>
*
* The value can be retrieved by calling the <code>get</code> method
* with a key that is equal to the original key.
*
* @param key the hashtable key
* @param value the value
* @return the previous value of the specified key in this hashtable,
* or <code>null</code> if it did not have one
* @exception NullPointerException if the key or value is
* <code>null</code>
* @see Object#equals(Object)
* @see #get(Object)
*/
// 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;
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;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
int index = (hash & 0x7FFFFFFF) % tab.length;这句就是设置元素存储的index，即数组下标。对数组长度取余运算很好理解，那么hash & 0x7FFFFFFF是什么意思呢，0x7FFFFFFF==0b0111 1111 1111 1111 1111 1111 1111 1111 1111,按位与把hash值的最高位（符号位）置0，意义在于确保取余运算的结果是正数（符号位0：正数，1：负数）。所以hash在这里扮演的角色就是寻址（数组下标）。
确定了下标后就是把value设置到对应位置了。这个时候会做hash碰撞的检查，如果将要加入的位置已经有元素，说明二者的hash值一样，会先判断key是否相同，相同就更新旧值位新值，否则就把旧值设置为新值的next，也就是说新加的value是table[index]的链表的第一个元素，这也很好地处理了原先table[index]是null的情况。
看下addEntry代码片段：
// Creates the new entry.
//旧值，可能是null也可能是相同hash但是不同key的其他元素；
Entry<K,V> e = (Entry<K,V>) tab[index];
// 把旧值设置为新值的next
tab[index] = new Entry<>(hash, key, value, e);
count++;
- 数据读取
再看根据key取value是怎么实现的。实际上看了上面的分析，Hashtable的结构已经非常清晰了，取key对应的value也就是先计算key的hash拿到index，再看情况处理hash碰撞。看代码：
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;
}
- 自动扩容
在上文的构造器里应该注意到几个私有属性：initialCapacity，loadFactor，threshold,initialCapacity很好理解，是Entry数组的初始大小，默认是11。threshold=loadFactor * Capacity(这个capacity开始的时候是initialCapacity，后面会改变)，是进行自动扩容的阈值，也就是当table中的元素数量达到 threshold时，会进行自动扩容。（源码里面的方法是rehash）。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
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;
}
}
}
从代码中可以看出，扩容的策略是在没有达到最大容量前，事宜int newCapacity = (oldCapacity << 1) + 1;即2n+1的策略来扩充的。逻辑是创建新的数组，把旧的数组元素重新hash后转移到新的数组里，所以元素的位置可能每次扩容后都是变化的。
在转移数据的代码里面，这段for循环很有意思：
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;
}
}
一般我们写for循环要么是foreach类型的，要么是for(int i= oldCapacity;i>0;i++),这里写的是for (int i = oldCapacity ; i-- > 0 ;)，涨了知识。
然后在内层for循环中，这个for循环等价于for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; old=old.next;)（不能写成for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; （old=old.next） != null ; )这样会少了第一个），在内部重新hash，放到nerMap中去。
Hashtable最核心的实现基本就以上的内容，另外需要注意的是hashtable是线程安全的。HashMap的实现和Hashtable很相似，底层可以说是一样的，不过HashMap不是线程安全的。
关于hash寻址的方法，不同jdk不完全一样，HashMap和HashTable也不一样（HashMap的寻址方法简直不要太6），具体可以查看jdk源码。可以参考大神的一篇文章了解更多内容： 全网把Map中的hash()分析的最透彻的文章，别无二家。
最后膜拜jdk源码作者。
网友评论