HashMap 基础

1

transient Node<K,V>[] table;

1
2
3
4
5
6
7
8

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 当前节点中Key的hash值，注意不是hashCode()的返回值，具体是什么会在扩容中介绍
    final K key; // 键
    V value; // 值
    Node<K,V> next; // 下一个结点
 
    ...
}

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

 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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 当数组为空或者数组长度为0的时候，延迟初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 此时，resize将使用16作为初始容量，创建初始数组，n = size = 16，threshold = 16 * 0.75 = 12
        n = (tab = resize()).length;
    // 2. 将hash映射到数组长度内，得到索引值，并判断tab在该处是否已经有Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 若没有Node，则表明此次插入的Node为tab[i]这个桶上的第一个Node，直接将该Node赋值给tab[i]
        tab[i] = newNode(hash, key, value, null);
    // 3. 数组不为空，且当前桶处已有其他Node
    else {
        Node<K,V> e; K k;
        // 判断待插入的key与桶中的第一个Node的key是否相等，若相等，则稍后直接覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果是红黑树结构，则进行红黑树的put操作
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 如果是链表结构
        else {
            // 遍历链表，直到找到元素，或者到达表尾
            for (int binCount = 0; ; ++binCount) {
                // 到达表尾，没有找到与传入的key相等(hash和equals判断)的Node，则插入新结点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 若插入新结点后，当前桶中的链表结点数超过了8个，则转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 在链表中找到了与传入key相等的Node，则直接退出遍历，并在稍后将值直接覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 4. e不为空表示HashMap中已有相同key的Node，直接将旧值替换成新值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 修改后，这个值递增，确保fast-fail机制
    ++modCount;
    // 5. size自增，若此时size的值大于threshold，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1
2
3
4
5
6
7
8

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if (...) {
        ...
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

/**
* The default initial capacity - MUST be a power of two. 默认初始容量-必须为2的幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
...
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
 
    // tableSizeFor()方法将返回大于等于initialCapacity的2的整数幂，并将这个返回值赋值给threshold
    // 在第一次调用resize()方法时，会将这个threshold作为初始容量创建数组，这个地方用法比较特殊
    // 后续操作中threshold将一直作为判断是否扩容的标准，它的值为capacity*loadFactor
    this.threshold = tableSizeFor(initialCapacity);
}

1
2
3
4

... n = tab.length ...
...
if ((p = tab[i = (n - 1) & hash]) == null)
...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// put方法调用了putVal方法，putVal方法的第一个参数使用了hash方法，因此实际上传入putVal方法的hash值其实是经过处理的hashCode()
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
// hash方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 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
90
91
92
93
94
95
96
97
98
99

final Node<K,V>[] resize() {
    // 扩容前的数组
    Node<K,V>[] oldTab = table;
    // 扩容前的容量，因为这个方法在第一次put的时候也会被调用，它需要考虑到为null的情况
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 扩容前的扩容阈值threshold
    int oldThr = threshold;
    // 扩容后的新容量和新阈值
    int newCap, newThr = 0;
    // 如果旧的容量大于0，表示不是第一次put元素，HashMap中已有数据
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 1. 容量翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 // 如果旧容量比16小，则使用后面的方式计算新扩容阈值
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 同时，新的容量阈值为旧容量阈值的两倍(因为新的容量翻倍了)
            newThr = oldThr << 1; // double threshold
    }
    // 上文提到过，当使用带int参数的HaspMap构造方法时，就在这个地方将threshold作为初始化数组的大小
    // 注意此处没有指定newThr，则时候稍后的方法进行计算
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 同样在上文提到过，当使用无参数的HashMap构造方法时，就在这里指定默认的初始数组大小
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 针对上文中没有计算newThr的情况，统一在这进行计算
    if (newThr == 0) {
        // newThr的值为capacity * loadFactor
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 将计算后的新阈值赋给threshold，表示扩容后的阈值
    threshold = newThr;
    // 2. 创建大小为新容量的数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 将HashMap中的数组替换为新数组
    table = newTab;
    // 将旧数组中的Node往新数组中搬
    if (oldTab != null) {
        // 遍历旧数组中的各个桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果桶中只有一个Node，则使用(length - 1) & hash的方法，直接将这个Node存到新数组的相应位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是红黑树，则进行红黑树相关操作
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 3. 如果是链表，则遍历链表中的所有结点，确定其在新数组中的位置
                else { // 4. preserve order
 
                    // 5. 将旧桶中的链表结点分成两类，分别组成两个链表，然后分别插入到新数组的特定桶中
                    Node<K,V> loHead = null, loTail = null; // 低位置的链表，记为lo
                    Node<K,V> hiHead = null, hiTail = null; // 高位置的链表，记为hi
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 骚操作，表示e所指向的结点在新数组中的下标和旧数组中的下标相同，把这些Node放到lo链表中，原因还是因为数组容量为2的整数幂
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 否则，表示e所指向的结点在新数组中的下标是旧数组中下标加上旧数组的容量，把这些Node放到hi链表中
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 分别将两个链表插入到低位和高位桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

 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

class TestKey {
    private String id;
    private int number;

    public TestKey(String id, int number) {
        this.id = id;
        this.number = number;
    }

    /**
     * 故意写个冲突的hashCode
     * @return 返回固定的hashCode
     */
    @Override
    public int hashCode() {
        return 5;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TestKey testKey = (TestKey) o;
        return number == testKey.number &&
                id.equals(testKey.id);
    }
}

public class HashMapDemo {
    private static final int COUNT = 500_000;
    public static void main(String[] args) {
        HashMap<TestKey, Integer> testMap = new HashMap<>();
        Integer testValue = -1;
        TestKey key = null;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < COUNT; i++) {
            key = new TestKey("test", i);
            testMap.put(key, i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("插入耗时:" + (endTime - startTime));
    }
}

1

插入耗时:4875921

1
2
3
4
5
6
7

class TestKey implements Comparable<TestKey> {
    ...
    @Override
    public int compareTo(TestKey o) {
        return number - o.number;
    }
}

1

插入耗时:155

 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

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        ...
        }
    }
}