HashMap 1.8

HashMap 在实际开发中和面试当中都是用的比较多也是作为面试题出现比较多的一个集合类
在从jdk1.7 到 1.8中 HashMap 有一次大的更新。

举个例子说明下HashMap的结构 与 演变过程：
假设你有二十个行李箱，这个时候你想去找到你的衣服，这个时候你就凉了。怎么找？
这个时候你对二十个箱子进行分类，第一个箱子放鞋子，第二箱子放......
那么这个时候你可以迅速的找到你放衣服的那个箱子。
但是还是很慢，因为这个箱子里面的衣服很多。你必须要一件一件的去翻，才能找到。
这个时候如果你按一种规则堆放可以更快的找到你想要的衣服（二叉查找树，红黑树）

这里直接放红黑树的图

image.png

如果当中的数字是你衣服的价格那么你可以很快的找到你想要的衣服。
红黑树满足 左节点< 根节点 < 右节点
这个你想找到一件9块钱的衣服，不用一件一件的去翻
从跟节点找起五块比九块小 往右边找，如果小于那么往左边找，以此类推。

HashMap 1.8 依然再延用链接的结构，初始化默认是链接结构
在单个Hash桶大于8 时将链接转换为红黑树，查找效率会更快

下面看是如何计算hash值的

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

image.png

对应下标计算，假设这里的table.length 是初始化容量

index = (n - 1) & hash

image.png

这里我之前有个疑惑点，为什么不直接用table的length 和 key的hashcode 直接坐& 运算，
h ^ h >>> 16 没有让高位丢失 如果是直接用hashcode 进行& 运算
然后会发现 总是只有hashcode的 底n位会进行 & 运算，如果大量的hashcode 的底n 位相同，然而达不到散列的效果。

hashmap 扩容

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;    //数组扩容阈值
        int newCap, newThr = 0; 
        if (oldCap > 0) {      //初始化过的数组
            if (oldCap >= MAXIMUM_CAPACITY) {  // 当数组长度大于最大限制 
                threshold = Integer.MAX_VALUE;      //把扩容阈值放到最大 不再进行扩容
                return oldTab; 
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
                     oldCap >= DEFAULT_INITIAL_CAPACITY)       // 如果hash数组长度 乘以2 小于最大限制，并且hash数组大于默认初始化数组长度时进行 双倍扩容
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold   自定义初始化扩容阈值
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults  默认初始化长度
            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) {
            // 扩容进行重新计算hash位置
        }
        return newTab;
    }

三种情况
1，使用HashMap 默认构造。默认的大小 1 << 4 负载因子 0.75f 扩容极限 1<<4 * 0.75
2，自定义初始化容量 newCap = oldThr 观察代码 后面的newThr = newCap * loadFactor
3，如果初始化过后，或扩容后，则直接翻倍扩容 newThr = oldThr << 1