Java
Java, 集合
Source
Edit
History

HashMap

Catalogue
  1. 1. 存储结构
  2. 2. 实现
    1. 2.1. hash算法
    2. 2.2. put方法
    3. 2.3. 扩容

存储结构

HashMap内部采用数组+链表+红黑树来实现。如下图所示。

hashMap

Node是HashMap的内部类，用来表示一个键值对，实现了Map.Entry接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

几个重要字段

1
2
3
4
5
6
int threshold;      // 所能容纳的key-value对极限 
final float loadFactor;  // 负载因子，默认为0.75
// 内部结构发生变化的次数，迭代器遍历时若发生变化会抛出ConcurrentModificationException异常
int modCount;
int size; // 实际存的键值对数量
Node<K,V>[] table  // 数组

当 size > (threshold = table.length * loadFactor)时，就要对数组进行扩容，数组扩容后的大小是原来的两倍。

实现

hash算法

1
2
3
4
5
6
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 来定位哈希桶数组索引位置
tab[i = (n - 1) & hash]

通过key的hashCode()的高16位异或低16位来计算hash，使得高低bit都参与到hash计算来。计算hash后，需要根据hash值确定键值对在数组中的位置。一般通过对数组取模h%length来确定，这里通过(n - 1) & hash同样达到了取模的目的，但是效率更高。下面证明下：

X % 2^n = X & (2^n – 1)

2^n表示成2进制就是1000…0(n个0)。2^n - 1为0111..11(n个1)。

此时X & (2^n – 1) 就相当于取X的2进制的最后n位数。

从2进制角度来看，X / 2^n相当于 X >> n，即把X右移n位，此时得到了X / 2^n的商，而被移掉的部分(后n位)，则是X % 2^n，也就是余数。

put方法

put方法流程如下图

hashMap 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
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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不扩容了
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 重点在这下面，上面是确定容量的，这里进行数组转移，以一个新数组替换原来的
    @SuppressWarnings({"rawtypes","unchecked"})
    // 构建新的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍历老数组的Node
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 便于GC
                oldTab[j] = null;
                // 链表就一个元素，直接放到新数组
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 是红黑树节点，节点数超过8
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 正常链表
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        // 循环遍历链表的节点
                        next = e.next;
                        // 分为两种情况，链表上节点会分到两个桶下面
                     	// 这里进行链表的拆分
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将链表放入新数组中，Node的先后顺序没有变
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // e.hash * old_n == 1 的放在新数组[j+old_n]位置处
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

前面说了通过(n - 1) & hash来确定Node在数组中的位置，扩容后n变为原来的2倍。也就是说n-1与扩容前相比其位标志上左边多出一位为1，这时候与hash进行与计算，则计算结果取决于该位上hash是0还是1，如果是0，则计算结果与扩容前一致，如果是1，则该位结果为1，即为原来的值+扩容前的n值。

在Java7中，链表在转移的时候顺序会被导致，多线程resize的时候会形成环形链表导致put时出现死循环，Java8已经没这个问题了。