java hashmap

hashmap结构

数组下标计算

当数组长度正好是 2的n次方时。

即,当数组长度正好是 2的n次方时,%运算可以转换为 & 运算,效率更高。

hash函数

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

hash冲突

当key1和key2 hash值相等时(hash冲突),导致下标一样，这时hashmap采用尾插法将key2插入到key1的尾部

image.png

put流程

image.png

hashmap链表转红黑树时机

 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//链表长度大于等于 TREEIFY_THRESHOLD
                            treeifyBin(tab, hash);
                        break;

    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)
//桶数组容量大于等于 MIN_TREEIFY_CAPACITY
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

参考：
https://tech.meituan.com/2016/06/24/java-hashmap.html