1. 概述
上次讨论了HashMap的结构,原理和实现,本文来对Map家族的另外一个常用集合HashTable进行介绍。HashTable和HashMap两种集合非常相似,经常被各种面试官问到两者的区别。
对于两者的区别,主要有以下几点:
synchronized
)保护,在多线程环境下没有安全问题。但是锁保护也是有代价的,会对读写的效率产生较大影响。null
的,Entry.key
和Entry.value
均可以为null
。但是HashTable中是不允许保存null
的。Iterator
)是fail-fast迭代器,但是Hashtable的迭代器(enumerator
)不是fail-fast的。如果有其它线程对HashMap进行的添加/删除元素,将会抛出ConcurrentModificationException
,但迭代器本身的remove
方法移除元素则不会抛出异常。这条同样也是Enumeration和Iterator的区别。
2. 原理
HashTable类中,保存实际数据的,依然是Entry
对象。其数据结构与HashMap是相同的。
HashTable类继承自Dictionary
类,实现了三个接口,分别是Map
,Cloneable
和java.io.Serializable
,如下图所示。
HashTable中的主要方法,如put
,get
,remove
和rehash
等,与HashMap中的功能相同,这里不作赘述,可以参考另外一篇文章HashMap原理和底层实现
3. 源码分析
HashTable的主要方法的源码实现逻辑,与HashMap中非常相似,有一点重大区别就是所有的操作都是通过synchronized
锁保护的。只有获得了对应的锁,才能进行后续的读写等操作。
1. put方法
put方法的主要逻辑如下:
synchronized
锁。null
值,如果发现是null
,则直接抛出异常。key
的哈希值和indexaddEntry
方法增加节点。addEntry
方法中,如果需要则进行扩容,之后添加新节点到链表头部。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;
}
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++;
}
2. get方法
get方法的主要逻辑如下
synchronized
锁。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;
}
3.rehash扩容方法
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;
}
}
}
4.remove方法
remove方法主要逻辑如下:
e
表示待删除节点,pre
表示前驱节点。如果不存在,返回null
。next
,指向e
的next。返回待删除节点的value值。4. 总结
HashTable相对于HashMap的最大特点就是线程安全,所有的操作都是被synchronized
锁保护的