HashMap

JDK8和JDK7不一样，JDK7中没有红黑树,数组中只挂载链表.
而JDK8中在桶容量大于等于64且链表节点数大于等于8的时候转换为红黑树. 当红黑树节点数量小于6时又会转换为链表.

桶容量就是Map元素的总个数

// 初始化容量，必须要2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 需要从链表转换为红黑树时,链表节点的最小长度
static final int TREEIFY_THRESHOLD = 8;

// 转换为红黑树时数组的最小容量: 最小树化容量
static final int MIN_TREEIFY_CAPACITY = 64;

// resize操作时,红黑树节点个数小于6则转换为链表. 
static final int UNTREEIFY_THRESHOLD = 6;

// HashMap阈值，用于判断是否需要扩容(threshold = 容量*loadFactor)
int threshold;

// 负载因子
final float loadFactor;

HashMap解决hash冲突的方法

Hash冲突

由于用于计算的数据是无限的H(key),key属于(-∞,+∞),而映射到区间是有限的，所以肯定会存在两个key:key1,key2，H(key1)=H(key2)，这就是hash冲突.

一般的解决Hash冲突方法有: 开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区.

开放定址法: 再次hash，直到不冲突
换hash算法
将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行. 链表法适用于经常进行插入和删除的情况. HashMap采用的就是链地址法来解决hash冲突. (链表长度大于等于8时转为红黑树)
冲突的元素放入溢出表

Java7的死循环问题

在 JDK 1.8 之前，rehash 的过程中采用头插法转移结点，高并发下，多个线程同时操作一条链表将直接导致闭链，死循环并占满 CPU。

JDK 1.8 以来，对 HashMap 的内部进行了很大的改进，采用数组+链表+红黑树来进行数据的存储。
rehash 的过程也进行了改动，基于复制的算法思想，不直接操作原链，而是定义了两条链表分别完成对原链的结点分离操作，
即使是多线程的情况下也是安全的。

Java8 中的HashMap扩容

而newTab[j + oldCap] = hiHead;这一步，是一个非常巧妙的地方，也是本文分析的重点.

优化点1: 扩容，避免重复计算hash值，还随机

解释

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置.

对应的就是下方的resize的注释.

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 * /

看下图可以明白这句话的意思，n为table的长度，
图（a）表示扩容前的key1和key2两种key确定索引位置的示例，
图（b）表示扩容后key1和key2两种key确定索引位置的示例，
其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果.

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，
只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”.

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，
因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了.

这一块就是JDK1.8新增的优化点.

优化点2: Rehash链表元素不倒置

有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置.

再解释：为什么刚好原位置+原数组长度就会等于新的数组中的位置呢？
要搞明白这个问题首先要清楚

HashMap的数组长度恒定为2的n次方，也就是说只会为2 4 8 16 . . . . . 这种数. 源码中有限制，也就是说即使你创建HashMap的时候是写的

1	Map<String,String> hashMap = new HashMap<>(13);

最后数组长度也会变成16，而不是你的13. 会取与你传入的数最近的一个2的n次方的数.

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }


static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

那么明确这一点有什么用呢？我们知道2,4,8,16,32所对应的二进制分别为

2：  0000 0000 0000 0000 0000 0000 0000 0010
4：  0000 0000 0000 0000 0000 0000 0000 0100
8：  0000 0000 0000 0000 0000 0000 0000 1000
16： 0000 0000 0000 0000 0000 0000 0001 0000
32:  0000 0000 0000 0000 0000 0000 0010 0000

而我们知道，0在做位与运算时与任何一个数运算结果都恒为0

1 2	0 & 1 = 0 0 & 0 = 0

故看源码中

1	if ((e.hash & oldCap) == 0)

这一步是否为0只需要看元素的二进制数对应数组长度的二进制数1那个位置是否为0.
假设某个元素的hashcode为52：

而假设某个元素的hashcode为100：

而通过源码可以看出0就还是在原来的位置. 不为0就需要变动位置了，新的位置为元素在原数组的位置+原数组的长度，那么为什么是这样呢？我们接着看
看之前我们先使用JDK1.7中的方式重新进行hash运算
HashMap在运算元素位置的时候使用为数组长度-1. 也就是15.31这种数15 31 对应的二进制为

1 2	15：0000 0000 0000 0000 0000 0000 0000 1111 31: 0000 0000 0000 0000 0000 0000 0001 1111

这里需要注意的是hashmap中，计算元素位置采用的是length-1，而leng是用来判断元素是否需要更换位置

1	if ((e.hash & oldCap) == 0) //仅仅是判断元素是否需要换位置

这一步才是计算位置，使用的是length-1.

16扩容后变成32.那么1.7中计算元素的位置方式为 31&52, 31&100.我们把他与扩容前的15&52. 15&100做对比看看

可以看到，由于每次扩容会把原数组的长度*2，那么再二进制上的表现就是多出来一个1，比如元数组16-1二进制为1111，那么扩容后的32-1的二进制就变成了1 1111
而扩容前和扩容后的位置是否一样完全取决于多出来的那一位与key值的hash做按位与运算之后的值值是为0还是1. 为0则新位置与原位置相同，不需要换位置，不为零则需要换位置.

而为什么新的位置 = 原位置 + 原数组长度，是因为每次换的位置只是前面多了一个1而已. 那么新位置的变化的高位进1位. 而每一次高位进1都是在加上原数组长度的过程.

正好1+2=3 3+4=7 7+8=15 . 也就验证了新的位置为原位置+原数组长度.

[参考文献]
————————————————

Guadazi

Java HashMap