简介
HashMap在工作中使用频率最高的用于映射(键值对)处理的数据类型。本文主要通过JDK1.8版本，深入探讨HashMap的结构实现和功能原理。
功能实现
一、传统 HashMap 的缺点
JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
二、JDK1.8实现
JDK1.8版本中HashMap是数组+链表+红黑树（查找时间复杂度为 O(logn)）实现的。
由于HashMap就是使用哈希表来存储的，当两个hash值算出同一个index时，就出现了“hash冲突”——两个键值对要被插在同一个bucket里了。
常见解法有两种：
①开放式hash map：用一个bucket数组作为骨干，然后每个bucket上挂着一个链表来存放hash一样的键值对。有变种不用链表而用例如说二叉树的，反正只要是“开放”的、可以添加元素的数据结构就行；
②封闭式hash map：bucket数组就是主体了，冲突的话就线性向后在数组里找下一个空的bucket插入；查找操作亦然。java.util.HashMap用的是开放式设计。Hash冲突越多越影响访问效率，所以要尽量避免。
三、HashMap的原理-哈希表
哈希表的本质是一个数组，数组中每一个元素称为一个箱子(bin)，箱子中存放的是键值对。
1、哈希表的存储过程如下:
根据 key 计算出它的哈希值 h。
假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。
如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决冲突。
在使用拉链法解决哈希冲突时，每个箱子其实是一个链表，属于同一个箱子的所有键值对都会排列在链表中。
1.1、负载因子(load factor)
它用来衡量哈希表的 空/满 程度，一定程度上也可以体现查询的效率，计算公式为:
负载因子 = 总键值对数 / 箱子个数
源码：
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
threshold = capacity * loadFactor
1.1.1、为啥负载因子（DEFAULT_LOAD_FACTOR）默认为0.75
源码文档
HashMap实例有两个参数会影响其性能:初始容量和负载因子。
（1）容量是哈希表中的桶数，初始容量就是创建哈希表时的容量。
（2）负载系数是在哈希表的容量自动增加之前，允许哈希表填满的度量。
当哈希表中的条目数量超过负载因子和当前容量的乘积时，哈希表就会被重新哈希(也就是说，重新构建内部数据结构)，这样哈希表的桶数大约是原来的两倍。
（3）一般来说，默认的负载因子(.75)在时间和空间成本之间提供了很好的权衡。较高的值减少了空间开销，但增加了查找成本(反映在HashMap类的大多数操作中，包括get和put)。在设置映射的初始容量时，应该考虑映射中的期望条目数及其负载因子，以最小化重哈希操作的数量。如果初始容量大于条目的最大数量除以负载系数，则不会发生重哈希操作。
如果要将许多映射存储在HashMap实例中，那么使用足够大的容量创建映射将使映射存储得比根据需要执行自动重哈希更有效。
注意，使用具有相同hashCode()的多个键肯定会降低任何哈希表的性能。为了改善影响，当键具有可比性时，该类可以使用键之间的比较顺序来帮助打破关系。
文档说的主要是：
1、负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。负载因子越小，越容易导致扩容，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
2、哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使 key 的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。
3、哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有 key 的哈希值都一样，那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低，但实际存储在每个箱子中的链表长度并不发生改变，因此也就不能提高哈希表的查询性能。
1.2、初始值和最大容量
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
默认情况下，HashMap 初始容量是16，即2的4次方，最大容量1 << 30;
基于以上总结，发现哈希表的两个问题:
1、如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。
2、如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低。
2、具体实现
首先需要清楚HashMap数据底层具体存储的是什么?
根据源码，HashMap类中有一个字段， Node[] table字段，即哈希桶数组，明显它是一个Node的数组。
我们来看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;
}
从源码可以看出：Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。当我们通过hashMap.put(key，value);时，Node存储的就是我们put的k-v键值对。每put一次就把node存储到bucket数组中
示意图如下：
2.1、确定哈希桶数组索引位置
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// h = key.hashCode() : 取hashCode值
// h ^ (h >>> 16) :高位参与运算
//tab[i = (n - 1) & hash]: 取模运算【这段代码是在下面的put（）方法里面】
这段代码为啥要这样写，可以参考【位运算（java8 HashMap）】
2.2、put()方法
当我们通过下面的代码添加值的时候
Map<String, String> map = new HashMap<String, String>();
map.put("key1", "value2");
map.put("key2", "value2");
具体会由HashMap的put()方法进行处理，下面就是HashMap的put()方法源码
public V put(K key, V value) {
// 对key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// ①：tab为空或者tab长度为0
if ((tab = table) == null || (n = tab.length) == 0)
//执行resize()进行扩容
n = (tab = resize()).length;
// ②：根据键值key计算hash值得到插入的哈希数组索引i，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
//null的话说明tab中index位置没有node，那么就可以直接创建node添加到数组中
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// ③：节点key存在，直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//覆盖value
e = p;
// ④：判断该链表为红黑树，如果是红黑树，则直接在树中插入键值对
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// ⑤该链为链表则遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，
//在红黑树中执行插入操作，否则进行链表的插入操作；
//遍历过程中若发现key已经存在直接覆盖value即可
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍历过程中若发现key已经存在直接覆盖value即可
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;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// ⑥：超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
static final int TREEIFY_THRESHOLD = 8;
从上面的源码可以总结出HashMap的put()方法的执行流程：
①.判断哈希桶数组table[i]是否为空或length为0，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的哈希数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的元素，也就是Node节点中的hash值是否与要添加的key的hash值相等，并且Node节点中的key与要添加的key是否相等，也就是是hashCode以及equals，如果相同直接覆盖value，如果仅仅是hash值一样，key不一样，那么转向④；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
2.3、get()方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//①tab不为空并且tab.length不为0，tab[i]也不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果hash和key都一样，直接从哈希数组桶中获取value值
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//②如果hash一样，但是key不一样，则从红黑树或者链表中查找
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;
}
从上面的源码可以总结出HashMap的get()方法的执行流程：
①.判断哈希桶数组tab[i]是否为空或length为0，根据键值key计算hash值得到查找的哈希数组索引i，如果tab[i]==null，转向⑤；否则转向②
②.判断tab[i]的元素，也就是Node节点中的hash值是否与要查找的key的hash值相等，并且Node节点中的key与要查找的key是否相等，也就是hashCode以及equals，如果相同则return node<k,v>，如果仅仅是hash值一样，key不一样，那么转向③；
③.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中查找键值对，否则转向④；
④从链表中查找，首先遍历tab[i]，根据hashCode以及equals查找到Node<k,v>；如果查不到转向⑤；
⑤.如果查不到return null。
2.4、HashMap 在 JDK 1.8 中新增的数据结构 – 红黑树
2.4.1链表树化、红黑树链化与拆分
源码：
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，要不然频繁转换效率也不高
static final int TREEIFY_THRESHOLD = 8;
//一个树的链表还原阈值
//当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
//这个值应该比上面那个小，至少为 6，避免频繁转换
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的最小树形化容量
//当哈希表中的容量大于这个值时，表中的桶才能进行树形化
//否则桶内元素太多时会扩容，而不是树形化
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 将普通节点链表转换成树形节点链表
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 桶数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd 为头节点（head），tl 为尾节点（tail）
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);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
可以看到TreeNode有父亲、左右孩子、前一个元素的节点，还有个颜色值。
另外由于它继承自 LinkedHashMap.Entry
红黑树的三个关键参数TREEIFY_THRESHOLD、UNTREEIFY_THRESHOLD 、MIN_TREEIFY_CAPACITY
扩展
（1）为啥当桶中元素个数超过8时，需要使用红黑树节点替换链表节点？
（2）为啥桶中元素个数小于6，就会把树形的桶元素 还原（切分）为链表结构？
（3）哈希表的最小树形化容量为64？
1、因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。
2、链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
选择6和8，中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
3、当桶数组容量比较小时，键值对节点 hash 的碰撞率可能会比较高，进而导致链表长度较长。这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。容量小时，优先扩容可以避免一些列的不必要的树化过程。同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。
HashMap 在设计之初，并没有考虑到以后会引入红黑树进行优化。所以并没有像 TreeMap 那样，要求键类实现 comparable 接口或提供相应的比较器。但由于树化过程需要比较两个键对象的大小，在键类没有实现 comparable 接口的情况下，怎么比较键与键之间的大小了就成了一个棘手的问题。为了解决这个问题，HashMap 是做了三步处理，确保可以比较出两个键的大小，如下：
- 比较键与键之间 hash 的大小，如果 hash 相同，继续往下比较
- 检测键类是否实现了 Comparable 接口，如果实现调用 compareTo 方法进行比较
- 如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder
tie break 是网球术语，可以理解为加时赛的意思，起这个名字还是挺有意思的。
通过上面三次比较，最终就可以比较出孰大孰小。比较出大小后就可以构造红黑树了，最终构造出的红黑树如下：
橙色的箭头表示 TreeNode 的 next 引用。由于空间有限，prev 引用未画出。可以看出，链表转成红黑树后，原链表的顺序仍然会被引用仍被保留了（红黑树的根节点会被移动到链表的第一位），我们仍然可以按遍历链表的方式去遍历上面的红黑树。这样的结构为后面红黑树的切分以及红黑树转成链表做好了铺垫，我们继续往下分析。
红黑树拆分
扩容后，普通节点需要重新映射，红黑树节点也不例外。按照一般的思路，我们可以先把红黑树转成链表，之后再重新映射链表即可。这种处理方式是大家比较容易想到的，但这样做会损失一定的效率。不同于上面的处理方式，如上节所说，在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行。这样就避免了将红黑树转成链表后再进行映射，无形中提高了效率。
以上就是红黑树拆分的逻辑，下面看一下具体实现吧：
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 红黑树节点仍然保留了 next 引用，故仍可以按链表方式遍历红黑树。
* 下面的循环是对红黑树节点进行分组，与上面类似
*/
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
/*
* hiHead == null 时，表明扩容后，
* 所有节点仍在原位置，树结构不变，无需重新树化
*/
if (hiHead != null)
loHead.treeify(tab);
}
}
// 与上面类似
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
从源码上可以看得出，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于 UNTREEIFY_THRESHOLD（6），则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。举个例子说明一下，假设扩容后，重新映射上图的红黑树，映射结果如下：
红黑树链化
前面说过，红黑树中仍然保留了原链表节点顺序。有了这个前提，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。相关代码如下：
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// 遍历 TreeNode 链表，并用 Node 替换
for (Node<K,V> q = this; q != null; q = q.next) {
// 替换节点类型
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
2.5、死循环
在多线程使用场景中，应该尽量避免使用线程不安全的HashMap，而使用线程安全的ConcurrentHashMap。那么为什么说HashMap是线程不安全的，下面举例子说明在并发的多线程使用场景中使用HashMap可能造成死循环。代码例子如下(便于理解，仍然使用JDK1.7的环境)：
public class HashMapInfiniteLoop {
private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);
public static void main(String[] args) {
map.put(5， "C");
new Thread("Thread1") {
public void run() {
map.put(7, "B");
System.out.println(map);
};
}.start();
new Thread("Thread2") {
public void run() {
map.put(3, "A);
System.out.println(map);
};
}.start();
}
}
其中，map初始化为一个长度为2的数组，loadFactor=0.75，threshold=2*0.75=1，也就是说当put第二个key的时候，map就需要进行resize。
通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的“Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。
注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。
线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。
于是，当我们用线程一调用map.get(11)时，悲剧就出现了——Infinite Loop。
2.6、其他细节
前面的内容分析了 HashMap 的常用操作及相关的源码，本节内容再补充一点其他方面的东西。
被 transient 所修饰 table 变量
如果大家细心阅读 HashMap 的源码，会发现桶数组 table 被申明为 transient。transient 表示易变的意思，在 Java 中，被该关键字修饰的变量不会被默认的序列化机制序列化。我们再回到源码中，考虑一个问题：桶数组 table 是 HashMap 底层重要的数据结构，不序列化的话，别人还怎么还原呢？
这里简单说明一下吧，HashMap 并没有使用默认的序列化机制，而是通过实现readObject/writeObject两个方法自定义了序列化的内容。这样做是有原因的，试问一句，HashMap 中存储的内容是什么？不用说，大家也知道是键值对。所以只要我们把键值对序列化了，我们就可以根据键值对数据重建 HashMap。有的朋友可能会想，序列化 table 不是可以一步到位，后面直接还原不就行了吗？这样一想，倒也是合理。但序列化 talbe 存在着两个问题：
table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
同一个键值对在不同 JVM 下，所处的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能会发生错误。
以上两个问题中，第一个问题比较好理解，第二个问题解释一下。HashMap 的get/put/remove等方法第一步就是根据 hash 找到键所在的桶位置，但如果键没有覆写 hashCode 方法，计算 hash 时最终调用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能会有不同的实现，产生的 hash 可能也是不一样的。也就是说同一个键在不同平台下可能会产生不同的 hash，此时再对在同一个 table 继续操作，就会出现问题。
综上所述，大家应该能明白 HashMap 不序列化 table 的原因了。
参考
关于hashMap的一些按位与计算的问题
Java 8系列之重新认识HashMap
HashMap 源码详细分析(JDK1.8)
