集合框架

集合框架

HashMap

putVal()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 {
           ....
        }
        ...
}
  • 如果表格是 null,resize负责初始化 — tab = resize()

    resize()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    final Node<K,V>[] resize() {
        // ...
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACIY &&
                    oldCap >= DEFAULT_INITIAL_CAPAITY)
            newThr = oldThr << 1; // double there
           // ... 
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {  
            // zero initial threshold signifies using defaultsfults
            newCap = DEFAULT_INITIAL_CAPAITY;
            newThr = (int)(DEFAULT_LOAD_ATOR* DEFAULT_INITIAL_CAPACITY；
        }
        if (newThr ==0) {
            float ft = (float)newCap * loadFator;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
        }
        threshold = neThr;
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newap];
        table = n；
        // 移动到新的数组结构 e 数组结构 
       }

  • 门限值等于（负载因子）x（容量），如果构建 HashMap 的时候没有指定它们，那么就是依据相应的默认常量值。
  • 门限通常是以倍数进行调整 （newThr = oldThr << 1），我前面提到，根据 putVal 中的逻辑，当元素个数超过门限大小时，则调整 Map 大小。
  • 扩容后，需要将老的数组中的元素重新放置到新的数组，这是扩容的一个主要开销来源。

HashMap的树化