【java源码系列】HashMap

历史

  • java 1.0 中没有HashMap,有HashTable
  • java 1.2 引入HashMap
  • java 7 基于哈希表的实现
  • java 8 采用的

hash

数据结构

1
2
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;

hash过程

流程

  1. 对key计算hashcode
  2. 将hashcode映射到有限bucket空间
  3. 在相应的bucket内,存储或查询相应的key

计算hashcode

java7

1
2
3
4
5
6
7
8
9
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k); // 麻蛋
}
h ^= k.hashCode(); // 按位异或
h ^= (h >>> 20) ^ (h >>> 12); // “扰动函数”。Java 8中这步已经简化了,只做一次16位右位移异或混合,而不是四次,但原理是不变的。
return h ^ (h >>> 7) ^ (h >>> 4); // >>> 无符号右移运算符
}

基础知识:

  1. hashSeed 随机数的种子,详见..
  2. ^ 按位异或。作用:
  3. >>> 无符号右移运算符
    左移的规则:丢弃高位,0补低位
    右移的规则:丢弃低位,高位的空位补符号位,即正数补零,负数补1

右移的偏移量20,12,7,4是怎么来的呢?因为Java中对象的哈希值都是32位的,所以这几个数应该
就是把高位与低位做异或运算,

分配hashcode到bucket

hashcode的取值空间太大,不能作为直接存储地址。因此要把hashcode分配到一定数量的bucket中,取值[0, capacity‐1]

为了使每个key都能在冲突最小的情况下映射到[0,capacity),通常有两种做法:

  1. capacity为素数,index = hashCode(key) mod capacity
  2. capacity为2的倍数,index = hashCode(key) & (capacity‐1)

java7中

1
2
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
index = hashCode(key) & (capacity‐1); // 映射到0,capacity-1之间(类似mod)

普通的哈希算法(也称硬哈希)采用简单取模的方式,将机器进行散列,这在cache环境不变的情况下能取得让人满意的结果,但是当cache环境动态变化时,这种静态取模的方式显然就不满足单调性的要求(当增加或减少一台机子时,几乎所有的存储内容都要被重新散列到别的缓冲区中)。

存储或查询 (get put)

java7的get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

java7的put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}

rehash

java7的rehash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void resize(int newCapacity) {
Entry[] newTable = new Entry[newCapacity]; // 创建新的entry array
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// Transfers all entries from current table to newTable.
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

复杂度?

一致性?

其他

1
2
3
4
 //  默认的平衡因子为0.75。过高的因子会降低存储空间但是查找的时间就会增加。
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
int MAXIMUM_CAPACITY = 1 << 30; // 哈希表容量(也就是buckets或slots大小)
float DEFAULT_LOAD_FACTOR = 0.75f;

NUll keys always map to hash 0, thus index 0

横向对比

  • Hashtable
  • LinkedHashMap
  • TreeMap
  • EnumMap

VS Hashtable

HashMap 不是线程安全的

HashMap 是 HashTable 的轻量级实现,他们都完成了Map 接口,主要区别在于 HashMap 允许 null key 和 null value,由于非线程安全,效率上可能高于 Hashtable。

VS

revisit

设计

参考

思考题

  • hashcode的计算?
  • Null key的处理?为什么
  • 常量
    • modCount的作用?
    • loadFactor的作用?
    • 为什么容量必须为2的指数倍(默认为16)?
    • 超容后,reshash的复杂度是多少?怎样降低复杂度?怎样保证一致性?
    • 容量超过Integer.MAX_VALUE怎么办?
    • hashSeed的影响?
  • 并发的影响?见
  • 如何做到key的排序?见

答案在文中寻找