HashMap，哈希表，一种存储键值对的数据结构。

JDK 7 的 HashMap的结构

JDK 7 的HashMap底层结构十分简单：数组 + 链表。
示意图：

table[]
   |
   v
[0] -> Node -> Node -> Node
[1] -> null
[2] -> Node -> Node
[3] -> null

源码结构

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    //指向下一个节点的指针
    Entry<K,V> next;
    //哈希值
    int hash;
}

为什么会有链表在数据后面？

答：

不同的Key经过哈希函数的计算，得出的哈希值是不同的。而这个哈希值，在经过一系列算法后，会给数据在数组中找到一个位置插入。我们可以通过一个简单的模型来理解这个问题：
index = hash % table.length，可以看出，如果数据量够大，就会出现数组长度不够用，多个数据会挤在一个位置。我们称这种情况为哈希冲突(或哈希碰撞)。
但我们又不想丢弃数据，怎么办呢？于是我们便将数组的每个位置想象成一个头节点，当出现哈希冲突时，便插入在已存在的数据之后，便形成了一个链表的结构。
值得注意的是，JDK 7对链表插入采用的是头插法，即新元素成为头节点，旧元素接在新元素后面，这为后面的安全隐患埋下了伏笔。

JDK 7的HashMap存在什么问题吗?

答：

存在，最大的问题是多线程扩容时出现的死循环问题。
我们来分析一下它的扩容源码：

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历旧数组
        for (Entry<K,V> e : table) {
	    //遍历链表
            while(null != e) {
	        //记录下一个节点
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //算出在新数组的下标
                int i = indexFor(e.hash, newCapacity);
                //当前节点的next指向新桶的头节点
                e.next = newTable[i];
                //让当前节点成为新的头节点
                newTable[i] = e;
                //移动到下一个节点
                e = next;
            }
        }
    }

两个线程A，B同时进行扩容，旧链表结构为A -> B -> null.
假设线程A执行完Entry<K,V> next = e.next;时，线程B就已经完成了扩容，此时是先插A，再插B，由于是头插法，形成了
B -> A -> null。
但是线程A里面的e.next是旧值，相当于线程A此时依旧是A(e) -> B(e.next)，但现在新链表是B -> A -> null。当A完成扩容时便形成了
B -> A -> B -> A这样的环形链表。

链表成环会带来什么后果?

答：后续调用 get() 方法查询一个不存在的Key时，程序会进入这个环形链表不断循环，最终导致 CPU 利用率飙升到 100%。

JDK 8对HashMap的升级

JDK 8对HashMap做了三个重大升级

1.链表尾插法
2.扩容算法优化
3.引入红黑树

JDK 8的HashMap结构：数组 + 链表 + 红黑树。

结构：

/**
The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two. 
**/

/**
翻译:表格在首次使用时初始化，并根据需要调整大小。分配时，长度总是2的幂
**/
transient Node<K,V>[] table;

HashMap的一些参数

//默认的大小2^4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  
//最大大小2^30
static final int MAXIMUM_CAPACITY = 1 << 30;  
//负载因子 -> 扩容阈值 = 负载因子 * 数组大小 = 0.75 * 16 = 12所以第一次扩容阈值是12
static final float DEFAULT_LOAD_FACTOR = 0.75f;  
//树化阈值，即转换成红黑树需要 节点数>= 8
static final int TREEIFY_THRESHOLD = 8;  
//退化阈值，从红黑树转换成链表需要 节点数<= 8
static final int UNTREEIFY_THRESHOLD = 6;  
//最小树化容量，需要满足数组大小>=64
static final int MIN_TREEIFY_CAPACITY = 64;

Node：

static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;  
    final K key;  
    V value;  
    Node<K,V> next;  
  
    Node(int hash, K key, V value, Node<K,V> next) {  
        this.hash = hash;  
        this.key = key;  
        this.value = value;  
        this.next = next;  
    }

红黑树结构：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  
    TreeNode<K,V> parent;  // red-black tree links  
    TreeNode<K,V> left;  
    TreeNode<K,V> right;  
    TreeNode<K,V> prev;    // needed to unlink next upon deletion  
    boolean red;  
    TreeNode(int hash, K key, V val, Node<K,V> next) {  
        super(hash, key, val, next);  
    }

红黑树的条件?

答：在链表长度 >8 && 数组长度>64时，会转换成红黑树。

使用红黑树有什么好处？

答：链表增删改查的复杂度为O(n)，红黑树的增删改查时间复杂度是 O(logn)。

为什么树化阈值是8，退化阈值是6，以及中间的空出7是为什么？

答：

这背后的设计逻辑主要基于 泊松分布（Poisson Distribution） 的概率统计：在理想状态下，哈希桶中元素长度达到 8
的概率极低（约为 $0.00000006$）。
只有当碰撞概率达到一定程度，链表查询性能显著下降时，才会采用牺牲空间换取时间进行树化。
空出的7是为了缓冲，避免在链表和红黑树之间频繁转换导致性能浪费。
节点数6 -> 7时会继续是链表，节点数8 -> 7时会继续是红黑树。

完整的HashMap计算流程是什么样的？

答：

key
 ↓
key.hashCode()
 ↓
扰动函数
h ^ (h >>> 16)
 ↓
得到hash
 ↓
index = hash & (length - 1)
 ↓
找到桶
 ↓
链表 / 红黑树

扩容机制

源码精简版：

final Node<K,V>[] resize() {
    //扩容发生在size > threshold = capacity * loadFactor
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        newCap = oldCap << 1;  // 新容量 = 旧容量* 2
        newThr = oldThr << 1;  // 新阈值 = 旧阈值 * 2
    }
    threshold = newThr;
    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;
                // 迁移节点
            }
        }
    }
    return newTab;
}

为什么数组长度总是2的n次幂？

答：这是出于三个方面的考量: 位运算替代取模，减少hash冲突，扩容优化

1.位运算替代取模：

要找到数据在数组中的位置，最原始的算法其实是index = hash % length
但是取模运算比位运算慢的多，所以出于性能的考量，我们将这个算法改良成index = hash & (length - 1)。
HashMap计算index的源码在方法putVal中，下面是截选：

1 2	//n = table.length if ((p = tab[i = (n - 1) & hash]) == null)

2.减少Hash冲突：

在index = hash & (length - 1)这个运算中，只用到了hash的低位，在哈希值相似时会出现严重的哈希冲突。

举例：

length = 16
length - 1 = 15
二进制 = 1111

计算 index:
hash & 1111
只会取最后4位。

假设存在key:
00010000
00100000
01000000
10000000
此时最后4位全是0000
计算 index:
hash & 1111
全都等于0，都进入一个桶，出现哈希冲突，查询复杂度上升

于是便有了扰动函数：

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

这里做了三件事：
1 取hashCode
2 高16位右移
3 和原hash做异或

举例：
h = 1010101010101010 0000111100001111
右移16位
h >>> 16
0000000000000000 1010101010101010
异或
1010101010101010 0000111100001111
^
0000000000000000 1010101010101010
--------------------------------
1010101010101010 1010010110100101
低位被高位信息影响了，随机性更大

3.扩容优化：

在JDK 7 中，扩容后使用

1
2
3

static int indexFor(int h, int length) {
        return h & (length-1);
    }

每遍历一个元素，都要重新计算所有元素在新数组的位置。性能较差。

在JDK 8 中，使用了新的扩容算法，下面是扩容流程：

HashMap size > threshold
        │
        ▼
      resize()
        │
        ▼
   newCap = oldCap * 2
        │
        ▼
遍历旧数组每个桶
        │
        ▼
遍历链表节点
        │
        ▼
判断 (hash & oldCap)
        │
     ┌──┴───┐
     ▼      ▼
   0(不变) 1(移动)
     │      │
     ▼      ▼
 index   index+oldCap

举例：

原数组:
length = 16, length - 1 = 15
二进制下:
16 = 10000, 15 = 01111
下标计算
index = hash & 01111
---------------------
扩容规则:
newCap = oldCap * 2
---------------------
新数组:
oldCap = 16
newCap = 32
二进制下:
32 = 100000
31 = 011111
下标计算
index = hash & 11111
---------------------
注意变化:
旧:01111
新:11111
多了一位:10000
刚好是oldCap: 16 = 10000
---------------------
扩容后，元素只有两种选择:index Or index + oldCap
我们通过对首位进行&运算便能判断是否该将元素移动，而不用重新hash

2的幂次方在二进制下首位都是1，其余位置是0。所以使用2的幂次方来做容量铺垫在此刻利用了起来。

节点迁移

Node<K,V> loHead = null, loTail = null;//低位 lo = low
Node<K,V> hiHead = null, hiTail = null;//高位 hi = high
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;
}

利用尾插法保持链表顺序不变，解决了死循环问题。
将链表拆分成两个链表：

原链表
   │
   ▼
  / \
低位 高位
链表 链表

性能优化体现在哪？

答：

JDK 7： 扩容 = O(n) + 重新hash
JDK 8： 扩容 = O(n)，因为hash不重新算，index不重新算，只判断首位。

Put和Get

Put流程

put(key,value)
   │
   ▼
计算 hash(key)
   │
   ▼
index = hash & (n-1)
   │
   ▼
桶是否为空？
   │
   ├─ 是 → 直接插入
   │
   └─ 否
        │
        ▼
   key是否相同？
        │
        ├─ 是 → 覆盖value
        │
        └─ 否
             │
             ▼
        是红黑树？
             │
      ├─ 是 → 树插入
      │
      └─ 否 → 链表插入
                │
                ▼
              链表≥8？
                │
            ├─ 是 → 树化
            │
            └─ 否
                │
                ▼
          size > threshold ?
                │
          ├─ 是 → resize
          └─ 否

伪代码说明：

if table[index] == null
    newNode
else if (key相同)
    覆盖
else if (TreeNode)
    红黑树插入
else
    链表遍历

源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //这里判断是否初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //这里判断要put的位置是否为null
        if ((p = tab[i = (n - 1) & hash]) == null)
            //位置为null直接修改该节点
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //找到桶的位置直接修改值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //是树就走树的put方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //是链表就走链表的put方法
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //尾部插入一个节点
                        p.next = newNode(hash, key, value, null);
                        //如果桶大小≥ 7
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //树化这个桶
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //这里是putIfAbsent，存在就会返回一个旧值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //如果size+1大于扩容阈值，会进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

Get流程：

get(key)
   │
   ▼
计算 hash
   │
   ▼
index = hash & (n-1)
   │
   ▼
找到 bucket
   │
   ▼
第一个节点key匹配？
   │
   ├─ 是 → 返回value
   │
   └─ 否
        │
        ▼
     是红黑树？
        │
   ├─ 是 → 红黑树查找
   │
   └─ 否 → 链表遍历

源码：

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

GetNode方法:

final Node<K,V> getNode(Object key) {  
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;  
    if ((tab = table) != null && (n = tab.length) > 0 &&  
        (first = tab[(n - 1) & (hash = hash(key))]) != 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;  
}

线程安全：快速失败机制

在JDK8中HashMap依旧在并发环境下存在安全问题，但它提供了一个防御策略：快速失败。
如果对HahMap进行并发修改，会快速抛出异常ConcurrentModificationException。
因此，面对并发修改时，迭代器能够迅速且干净利落地失败，而不是在未来某个未知时间点冒着任意、非确定性行为的风险(原文：Thus, in
the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary,
non-deterministic behavior at an undetermined time in the future.)
在多线程下建议使用Collections.synchronizedMap(new HashMap(...))或者ConcurrentHashMap。

总结

JDK8 对 HashMap 做了三大优化：

当链表长度超过 8 时转为红黑树，将查询复杂度从 O(n) 降到 O(log n)。
插入方式由头插法改为尾插法，解决了 JDK7 扩容时可能出现的环形链表死循环问题。
扩容时利用 (e.hash & oldCap) 判断节点是否需要移动到 index + oldCap，避免重新计算 hash，提高扩容效率。