Website Logo. Upload to /source/logo.png ; disable in /source/_includes/logo.html

舞乐 VOLER

舞动我人生

对Hashtable和HashMap的补充解释

Feb 26, 2016

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)))) {
  //...
}