HashMap源码分析 —— put与get（四）

链接

上一节 : HashMap源码分析 —— put与get（三）

2.6 resize()扩容操作

    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);
    if (loTail != null) {
      loTail.next = null;
      newTab[j] = loHead;
    }
    if (hiTail != null) {
      hiTail.next = null;
      newTab[j + oldCap] = hiHead;
    }

不难看出，loHead和loTail两个节点分别记录不需要移动的链表的头部和尾部，hiHead和hiTail分别记录需要移动的链表头部和尾部.

假设在扩容的时候某个数组下有这样一个链表 :

image

其中，假设天蓝色部分的不需要挪动，红色部分的需要挪动

第一步 : 建立loHead loTail hiHead hiTail四个节点

第二步 ：

image

第三步 :

image

...

第N步 :

image

最后一步 :

把以loHead为首的链表放到数组的原位置，把以hiHead为首的链表放到原位置+oldCap的位置，这就是链表的扩容操作

下面图片是美团技术团队的put函数的流程总结 :

image

2.7 脚步加快 —— get()函数

相对于put()函数 get()函数要简单的多 ：

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    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;
    }

首先看下条件 :

// 数组不能是空的 数组的长度必须要大于0 数组当前索引有节点存在
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);

}

2.8 HashMap的最后一个构造函数

最后一个构造函数如下 ：

public HashMap(Map<? extends K, ? extends V> m) {
   // 加载因子直接设置成默认的
   this.loadFactor = DEFAULT_LOAD_FACTOR;
   putMapEntries(m, false);
}

注意形式参数中的泛型

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            // 其实构造函数时 table是null
            if (table == null) { // pre-size
                // 初始化数据的容量
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            // 遍历要插入的map中的每一个节点 并把它们插入到调用它的map中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

其实除了构造器中调用了putMapEntries函数之外，还有putAll()函数调用了它

下一节 ： HashMap源码分析 —— put与get（总）