[源码]Hashtable源码解析
前言
HashMap被问过无数次。数据结构与算法之前也看过关于Hash的章节(其里面的复杂程度很高),也看过很多关于HashMap的分析以及自己也去看过HashMap的源码。但面对别人的询问时，HashMap里面的内容也总道不清说不明。这次一定要把HashMap撩清楚。但在撩HashMap之前，先撩撩Hashtable。
Hashtable
最为常见的能够对比的就是Hashtable，这是个历史遗留的类。
“
Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换
”【1】
线程安全
"并且是线程安全的，任一时间只有一个线程能写Hashtable"：这句话如何在代码中体现。如果去看Hashtable的源码很容易就能发现，那就是synchronized。如下Hashtable的get方法
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修饰,修饰方法意味着对当前的Map对象的同步锁，必须得当前方法执行完成后释放锁才能进行其他操作。所以“并且是线程安全的，任一时间只有一个线程能写Hashtable”意义就是如此。
这么做的好处是安全但是并发性能却很低，因为所有的对map的操作都是串行的了
数据结构
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);
initialCapacity = 1;
this.loadFactor = loadFactor;
//初始化节点数组
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
- 链表
//链表的节点
protected Entry(int hash, K key, V value, Entry<K,V> next) {
//hash的为key的hash值
this.hash = hash;
this.key = key;
this.value = value;
//下一个节点对象
this.next = next;
}
操作
- 新增节点
总结:超过阈值则扩容，每次扩容都是讲新节点放头部并放在数组桶中，节点放新节点Next。
private void addEntry(int hash, K key, V value, int index) {
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++;
modCount++;
}
- 判断是否存在
总结：hashCode与0x7FFFFFFF与并与tab长度做余计算table位置，然后对节点遍历判断
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//通过hashCode与0x7FFFFFFF与并与tab长度做余计算位置
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 true;
}
}
return false;
}
- 扩容
总结：到达阈值后原容量乘2+1，然后遍历重新计算位置
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
//原容量乘2+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;
}
}
总结
先看过的HashMap再来看HashTable的源码，发现原来确实做的很原始。很多地方的效率没有HashMap高。至于效率与改进在HashMap做分析。
还有一个地方重要的区别是value不允许为null
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
//...