主要内容：
- Hashtable与HashMap比较
- 继承关系、关键属性、构造函数
- 插入、查找元素
- 扩容
Hashtable概述
一般提到Hashtable会将它与HashMap进行比较，下面先简要说下两者的联系。
-
相同点：基于哈希表的Map接口的实现，存储的是键值对。
以Key-Value键值对的形式存储数据。 -
不同点：Hashtable继承了
Dictionary，而HashMap继承了AbstarctMap；Hashtable不允许key、value值为null，而HashMap允许key、value值为null；Hashtable线程安全，HashMap线程安全；扩容时Hashtable数组扩大一倍+1，HashMap扩大一倍。
源码分析
继承关系
Hashtable继承关系.png
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
- 继承Dictionary抽象类，定义了对键值对的操作
关键属性
//Entry类型的数组，以键值对形式存储
private transient Entry<K,V>[] table;
//实际元素的数量
private transient int count;
//下次扩容的临界值，size>=threshold时会进行扩容，threshold=capacity * loadFactor
private int threshold;
//加载因子
private float loadFactor;
//被修改的次数，实现fail fast机制
private transient int modCount = 0;
构造函数
//使用指定的容量大小以及加载因子构造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);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
initHashSeedAsNeeded(initialCapacity);
}
//使用指定容量大小和默认加载因子0.75构造Hashtable
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
//使用默认初始容量大小11和默认加载因子0.75构造Hashtable
public Hashtable() {
this(11, 0.75f);
}
//构造一个指定map的HashMap，使用默认加载因子0.75
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
插入
方法是同步的。
public synchronized V put(K key, V value) {
//key为null，抛出异常
if (value == null) {
throw new NullPointerException();
}
//Hashtable已存在对应key的键值对，新值替换旧值
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
//Hashtable不存在对应key的键值对
modCount++;
if (count >= threshold) {//若实际容量>阈值
rehash();//扩容
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
//创建新的节点
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);//创建新节点，插入到Hashtable数组的index处，下一个元素指向e
count++;
return null;
}
查找
方法同步，根据键值key查找对应的值。
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
扩容
当实际元素占分配容量的75%时进行扩容。数组大小扩大一倍+1，然后重新计算每个元素在数组中的位置。
protected void rehash() {
int oldCapacity = table.length;
Entry<K,V>[] 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<K,V>[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {//遍历旧的Hashtable
Entry<K,V> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;//重新计算槽位index
e.next = newMap[index];
newMap[index] = e;
}
}
}
