HashMap 详细解析

HashMap

HashMap 是 Java 的一种键值对容器，该容器的核心方法是 putVal 方法，为了提高查询稳定性，Java 团队向该类引入了红黑树结构，为了减少碰撞概率引入了扰动函数，在对象的哈希值相同时又调用了 equals 方法进行二次检测

泊松分布

* 树形节点的大小是普通节点的两倍
* 桶的数量和节点的数量的关系呈泊松分布
* 树化阈值 8 解树化阈值 6 初始容量为 16 是经验的选择
* 默认情况下，当 HashMap 中的元素个数超过其容量的 3/4 便会触发扩容
* 初始容量为 16 第一次扩容后 32 第二次扩容后 64， λ 分别为 12 24 48

* 横坐标代表初始容量，纵坐标代表发生冲突的概率，面积代表桶中元素的个数（与 capacity 无直接联系）。
* λ 与 冲突概率 P(K) 和柱状图的面积呈正比
* λ 的初始值为 0.75 初始 capacity 为 16 是容量大冲突概率小的均衡选择
* λ = loadFactor * capacity 当 HashMap 超过此数时，就会触发 HashMap 的扩容操作

* 红黑树最好 O(logn) 最坏 O(logn)
* 链表 + 数组最好 O(1) 最坏 O(N)
* 为了保证系统查询的稳定性 Java 在 JDK 1.8 中使用了 数组 + 链表 <-----> 红黑树的结构

允许为空

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

* 为什么只允许一个 key 为 null 的对象？
    当 key 为 null 时 HashMap#hash 只会返回 0

* 为什么可以允许多个 key !=null 但 value == null 的键值对？
    HashMap#putVal 不会对 value == null 做出检查，只要 key 不同就会允许插入  

扰动函数

// 哈希冲突无法解决只能尽力避免
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

* Java 在计算对象在 HashMap 的位置时利用了最优化问题中的扰动函数，基本思路是：先将对象的 hasCode 右移 16 位，获得大概四十亿的映射空间中的一个值，
再将该值和原先的 hashCode 做异或运算进行缩放，使之能够放入 HashMap 中

* 当一个对象的 hasCode 足够特殊时（很小或是个奇数）经扰动函数扰动后结果仍可能相同，此时通过 equals 比较是否相等是避免碰撞的最好方法

以二为底的幂

* 同一时期 HashMap 的长度是固定的
* 与运算： 0 与 1 为 0，1 与 1 为 1
* e = tab[index = (n - 1) & hash]
* 以 2 为底的 k 次幂的值减一后的结果的二进制表示是 k 个一
* 以 2 为底的幂可以保证 HashMap 中的每一个位置发生冲突的概率是相同的

* HashMap 未对扩容和插入删除做同步设计，并发环境下请使用 HashTable 或 ConcurrentHashMap

static final int tableSizeFor(int cap) {
        // 无符号左移高位补零
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        // 溢出返回一
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

// 计算一个 int 类型的整数补码的前导零的数量
public static int numberOfLeadingZeros(int i) {
        // HD, Count leading 0's
        if (i <= 0)
            return i == 0 ? 32 : 0;  // 0 的补码全是零，负数没有前导零
        int n = 31;
        /*
        32 位整数，每 8 位一段，从 1 开始，最多有 31 个 0
        */
        // i >= 2 ** 16
        if (i >= 1 << 16) { n -= 16; i >>>= 16; }  // 65535
        // i >= 2 ** 8
        if (i >= 1 <<  8) { n -=  8; i >>>=  8; }  // 256
        // i >= 2 ** 4
        if (i >= 1 <<  4) { n -=  4; i >>>=  4; }  // 32
        // i >= 2 ** 2
        if (i >= 1 <<  2) { n -=  2; i >>>=  2; }  // 2
        return n - (i >>> 1);
    }

final Node<K,V>[] resize() {  // resize 用于调整 HashMap 的大小，不只用于扩容
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // oldCap 超出最大容量时不再扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } // 两倍扩容 
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 下一次扩容阈值为上一次的两倍
                newThr = oldThr << 1; // double threshold
        } // 使用单参构造方法，在第一次会缩小至 0.75 * capacity
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {              // zero initial threshold signifies using defaults
            // 使用空构造方法，在第一次直接扩容至 16，阈值扩大为 12
            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) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {  // 数组和链表
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    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);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }