java.util.Hashtable使用synchronized关键字实现线程安全,value不可以为空,

1
2
3
if (value == null) {
throw new NullPointerException();
}

key也不可为空,计算key的哈希值时会调用它的hashCode方法

1
2
3
4
private int hash(Object k) {
// hashSeed will be zero if alternative hashing is disabled.
return hashSeed ^ k.hashCode();
}

默认情况下hashSeed为0,即不使用alternative hashing,可以设置容量达到特定阀值时开始使用alternative hashing,这时,

1
hashSeed = sun.misc.Hashing.randomHashSeed(this);

Hashtable整体为数组tab,每个数组元素为Entry链表,使用put方法添加新的键值对时,首先计算key的哈希值,根据哈希值确定数组下标,

1
int index = (hash & 0x7FFFFFFF) % tab.length;

接着遍历index处的Entry链表,通过下面的比较逻辑确定key是否存在,

1
2
3
if ((e.hash == hash) && e.key.equals(key)) {
//...
}

如果已存在,更新其对应的value;如果未存在,根据键值对新建Entry对象,插入到当前Entry链表的首位。使用get方法获取键对应的值时,类似地确定数组下标,遍历链表,比较确定key是否存在,如果存在返回对应的value;不存在返回null

容量大于设定的阀值时会调用rehash方法扩容,这时会重新计算每个键值对的数组下标及位置。

java.util.HashMapHashtable类似,区别在于无synchronized关键字,HashMap中key、value可以为空,key为null的键值对保存在数组的0下标处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

HashMap中确定key是否存在的比较逻辑,

1
2
3
4
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
//...
}