【Source Code】HashMap

通过 HashMap 的 field 和 method(hash(), put(), get(), resize())入手了解了一下 Java 中 HashMap 的设计。

存储结构-字段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;

...

/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;

/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;

/**
* The number of key-value mappings contained in this map.
*/
transient int size;

/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;

/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
  • DEFAULT_INITIAL_CAPACITY,默认 HashMap 的大小
  • MAXIMUM_CAPACITY,最大的 HashMap 的大小
  • DEFAULT_LOAD_FACTOR,默认的负载因子的大小
  • TREEIFY_THRESHOLD,将链表升级成红黑树的 threshold
  • UNTREEIFY_THRESHOLD,当 HashMap 删除元素后,红黑树退化成链表的 threshold
  • MIN_TREEIFY_CAPACITY,升级成红黑树的最小容量,表示 HashMap 达到这个容量之后,一定会升级成红黑树或者 resize。 (但是我没在别人的博客里看到过这个。。我只是按照注释理解了一下。。这个东西下面没用到)
  • table[],存放数据的数组,每个元素是一个内部类 Node
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
    }

    public final K getKey() { return key; }
    public final V getValue() { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
    V oldValue = value;
    value = newValue;
    return oldValue;
    }

    public final boolean equals(Object o) {
    if (o == this)
    return true;
    if (o instanceof Map.Entry) {
    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    if (Objects.equals(key, e.getKey()) &&
    Objects.equals(value, e.getValue()))
    return true;
    }
    return false;
    }
    }
    • hash 就是 hash 值
    • key 是存放的 key 值
    • value 是存放的 value 值
    • next 是指向下一个 Node 的引用,生成链表时用的,如果升级成红黑树,会用 TreeNode (也是一个内部类) 代替 Node
  • size,HashMap 的 size
  • modCount,表示 HashMap 的 structural modified 次数 (比如,添加删除元素,或者 resize 都算,但是如果仅仅是值的改变不算) 。当迭代操作或者序列化操作时,操作前后需要比较 modCount 是否相等,不相等就 Fail-Fast,抛出 ConcurrentModificationException。
  • threshold,resize 的大小,等于 (capacity * load factor) ,达到 threshold 的时候就会扩容 (会 rehash,复制数据等操作,比较消耗性能)
  • loadFactor,负载因子

功能实现 - method

hash()

1
2
3
4
5
6
static final int hash(Object key) {   //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取 hashCode 值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  1. 取 key 的 hashCode 值
  2. 高位运算
  3. 取模运算

这个有一个点,就是 HashMap 中桶的个数 capacity 设计成 2 的幂次(一般都是设计成素数的)。之所以这样设计是为了在取模扩容时做优化:

  • 取模可以直接优化成了 and 位运算。
  • 扩容时重新计算元素位置时取模更快了,而且扩容时可以直接根据 mask 位置上的新增位数是 0 还是 1 来确定当前元素是在【当前位置】,还是在【当前位置 * 2】的位置上。

但是这样设计也带来了一些问题,取模后的哈希值是有可能出现很差的哈希分布的,在 capacity 比较小的时候,hash 值高位 Bit 的信息完全丢失了。所以做了一个高位运算逻辑右移 >>> 16 位(逻辑右移,左边全部使用 0 填充),减少高位 Bit 信息的丢失。

put()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
  • 判断当前 table 是否未初始化,未初始化就初始化一波
  • 根据 hash 值定位到具体的 bin,如果这个 bin 为空,直接新建一个 bin 放入这个 Node,然后返回
  • 判断 key 是否和当前结点的 key 相等,相等就直接替换 Node (或者 key 都为 null 的时候,HashMap 允许 key 为 null,顺便再插一句,HashMap 中 null 无法计算其 hash 值,默认都是放到下标为 0 的 上)
  • 如果当前结点是 TreeNode 红黑树结点,就按红黑树的方法插入 (具体就不展开了)
  • 如果是链表,就遍历链表,找到相同的 key 的 Node 就可以直接替换 Node,如果没找到就 newNode() (这个方法会在对应的 bin 中插入 Node)
  • 统一替换 Node (即 e 不为空)
  • modCount 自增
  • 判断是否需要 resize

get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
  • 判断 table 是否未初始化,未初始化或者定位到的 bin 为空的话,直接返回 null
  • 判断第一个 Node/TreeNode 的值是否为查询的 key,是的话直接返回 (always check first node) ,若不匹配就下一步
  • 判断为 TreeNode,查找红黑树
  • 判断链表,遍历链表查找

resize()

扩容 (resize) 就是重新计算容量,向 HashMap 对象里不停的添加元素,而 HashMap 对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然 Java 里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。所以扩容就涉及到哈希值的重新计算,复制元素等操作,是很消耗性能的,如果能在开始就能确定好元素的个数,建议在一开始就设置好。

当插完元素后,size > threshold = capacity * Load factor,扩容就开始了。

1
2
3
4
5
6
7
8
9
10
11
12
13
void resize(int newCapacity) {   //传入新的容量
Entry[] oldTable = table; //引用扩容前的 Entry 数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大 (2^30) 了
threshold = Integer.MAX_VALUE; //修改阈值为 int 的最大值 (2^31-1),这样以后就不会扩容了
return;
}

Entry[] newTable = new Entry[newCapacity]; //初始化一个新的 Entry 数组
transfer(newTable); //!!将数据转移到新的 Entry 数组里
table = newTable; //HashMap 的 table 属性引用新的 Entry 数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}

transfer() 方法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable) {
Entry[] src = table; //src 引用了旧的 Entry 数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的 Entry 数组
Entry<K,V> e = src[j]; //取得旧 Entry 数组的每个元素
if (e != null) {
src[j] = null;//释放旧 Entry 数组的对象引用(for 循环后,旧的 Entry 数组不再引用任何对象)
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记 [1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个 Entry 链上的元素
} while (e != null);
}
}
}

可以看出来复制的时候,链表是用头插法的方式复制的,所以原来的链表会被 revert 一下。在多线程场景,在两个线程 resize 的时候,可能会出现环形链表。

扩展问题

1. Hash 时取模一定要模质数吗?

好的 hash 算法期望是 hash 值在取模后能尽可能均匀地分布。不模 prime number 的话,很容易会有分布不均匀的情况产生。

假设需要放入长为 m 的 hash 表的数是 n,取模函数是: $f(n) = n \% m$ , $f(n)$ 为需要放置在 hash 表中的位置的下标。

取 m 为质数的目的是:让 m 和 n 的最大公约数为 1,也就是: $gcd(m, n)=1$ 。因为在 m 为质数时,除非 n 恰好是 m 的倍数,否则他们的最大公约数都为 1。

$$ f(n) = n \% m $$

$$ \Rightarrow a \times m + f(n) = n(a = 0, 1, 2,3…) $$

$$ \Rightarrow f(n) = n - a \times m $$

$$ \Rightarrow f(n) = gcd(m, n) *( \frac{n}{gcd(m,n)} - \frac{a \times m}{gcd(m,n)}) $$

也就是我们算出来的 hash 值只可能是为 $gcd(m, n)$ 的倍数的那些值,倘若数据特别一点,全都是 gcd 的倍数,这样会让分布很不均匀。

2. 为什么 java 在计算 hashcode 时使用 31 作为乘数?

确实很奇怪。。感觉是个 magic number。把这个搞成了一个类似 31 进制的数字。看了很多说法,stackoverflow 上说:

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

是因为 31 是个奇素数,并且可以直接优化成位运算提高性能。偶数的话,相当于 shift 运算,会丢失信息,但是奇数因为在 shift 后在加上原数,所以比偶数好。之所以用素数是因为 traditional。。(我看到有的会用 33 来做,据说和 31 差不多)。

有个答案提到是根据实验得出发现 31 的,根据字典跑数据跑出的结果。(但是我看那个数据也是英文字典,ascii 字符,要是非 ascii 字符的实验结果呢?)

参考