HashMap考点相关源码解析
参考资料：
面试的一面通常以基础知识为考点，其中HashMap是数据结构考察的常客。本文在HashMap源码分析基础上，对考点由进行了汇总和总结，方便读者和自己查阅。
1.什么是哈希表
哈希表（也称为散列表，英文叫Hash table）是一种很重要的数据结构，就是用来存储键值对的。
1.基础结构
哈希表中，有个很重要的部分叫做哈希函数。哈希函数是一个将输入（键）转换为固定大小输出（哈希值）的函数。通过哈希值，就可以确定元素在哈希表中的位置。
举一个例子来看看哈希函数的作用
如下图，使用数组来存储键值对，键key通过哈希函数，得到一个数组下标，这个下标就是用来存储当前键值对的位置。假设哈希表的数组大小为n，那么可以使用哈希函数 index = hasCode(key) % n（key的hashCode对n取余/取模） 来获取下标，并且可以保证下标在数组有效范围内。
其实Java中的HashMap的实现方式也正是如此。
这里重点说一下，文中经常出现哈希函数、哈希算法、哈希值，这几个名词，容易让人搞混。这篇文章中所说的哈希函数就是哈希算法，即将 key 转变为 数组下标的方法。而哈希值需要根据情景判断，通常指的是key的hashCode（在HashMap中由名为hash的方法计算所得） 。
2.哈希冲突
细心的朋友就会想到，如果不同的key通过哈希函数算出来一样的结果咋办。
这种情况叫做哈希冲突（或者哈希碰撞），常用的一种方法是用链表来解决，官方术语叫做拉链法。也就是将冲突的几组键值对以链表的形式链在一起，第一个放入数组的数据作为链表头。如下图。
HashMap也是这样处理哈希冲突的，只不过它内部还做了一些优化操作，比如当链表太长的时候，为了加快查找的速度，就会把链表转化成红黑树（平衡二叉树）来存储。
2.HashMap源码分析
有了以上基础，HashMap的源码分析会变得非常容易。
HashMap就是用数组来存储键值对，就是用链表和红黑树来解决哈希冲突，除此之外，HashMap内部在设计数组、、计算哈希值，处理哈希冲突等方面有着精巧实用的设计。这些设计也成为面试官爱问的考点。
下面展示了HashMap中数据的存储方式。
1.HashMap的成员变量
代码中对HashMap的关键成员变量做了注释，不理解也没有关系，看完后面内容可以回头来看。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 默认初始容量。16
// AKA，是一个网络流行词，是“Also Known As”的缩写，意思是又名、亦称、也被称为。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量，如果构造函数指定容量的值比这个值大，那就把容量指定成这个值。必须是 2的次幂，且小于等于 (1<<30, 1左移30位) 。
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 转化成树的最小容量。当数组大小小于64时，如果节点链表超过阈值，不转换成树，而是尝试扩容。
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储数据节点的数组
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
// 包含的键值对的数量
transient int size;
// HashMap 被结构化修改的次数,进行HashMap迭代操作时，可以用这个字段执行fail-fast。
// fail-fast即快速失败，当一个线程迭代器进行迭代操作，而另一个线程进行插入或者删除操作，那此时根据fail-fast机制就会抛出错误。
transient int modCount;
// 数组调整大小（扩容）的门槛（capacity * load factor）。
int threshold;
// 加载因子，当size(键值对数量)超过 loadFactor * 当前数组大小时，进行扩容操作
final float loadFactor;
// 省略以下内容
}
2.HashMap的数组
HashMap存储数据的数组是Node类型数组，Node为HashMap中的内部静态类。
HashMap有一个成员变量 transient Node<K,V>[] table 正是用来存储数据节点的数组。
Node中有四个成员变量：
key、value、hash（key的hash值）和next：下一个hash值相同的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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
HashMap注释中将数组的节点叫做bin，中文资料中常翻译做桶。
红黑树中使用的节点为TreeNode，也是HashMap中的内部类，TreeNode是Node的子类。
3.HashMap的put方法
1.方法总览
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 将节点数组table赋给tab
if ((tab = table) == null || (n = tab.length) == 0)
// 如果当前数组为空，则初始化数组。resize方法作用是初始化数组（16）或者扩容（翻倍）
n = (tab = resize()).length;
// if条件语句里做了三件事：
// 1.获取下标 i = (n - 1) & hash
// 2.将下标的节点赋值给p p = p = tab[i = (n - 1) & hash]
// 3.判断节点是否为null
if ((p = tab[i = (n - 1) & hash]) == null)
// 当前节点为null,创建新节点
tab[i] = newNode(hash, key, value, null);
else {
// 处理hash碰撞的情况，已有节点为p
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 如果key相同（==比较或者equals比较）,则将变量e指向p。if语句结束有对e节点的处理逻辑
e = p;
else if (p instanceof TreeNode)
// 如果当前节点是红黑树,将新节点放入红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 当前节点为链表
for (int binCount = 0; ; ++binCount) {
// 循环遍历链表元素，将当前元素赋值给e
if ((e = p.next) == null) {
// 达到链表尾部，将新节点放置链表尾部
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// TREEIFY_THRESHOLD值为8，当节点数大于等于8时，调整数组大小或者将链表转为红黑树。
// 当数组数量小于64时，进行扩容操作；大于64时转化为树。
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 链表中存在元素的key与插入的key相等
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// 变量e不等于null，说明存在一组键值对的key与当前插入的key相等
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// onlyIfAbsent为false或者旧值为null时，替换key对应的value
// 调用put方法默认onlyIfAbsent为false，同时hashmap也提供了putIfAbsent方法供用户使用
e.value = value;
// HashMap中为空方法，LinkedHashMap中用来实现accessOrder能力
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
// 插入新键值对，如果超过门槛，扩容
resize();
// HashMap中为空方法
afterNodeInsertion(evict);
return null;
}
static final int hash(Object key) {
int h;
// key的hashCode的前16位和后16位异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
根据源代码，对HashMap的put方法做一个介绍
当调用put方法存储键值对时，首先，它会判断数组是不是null，如果是null，便会初始化一个大小为16的数组。
接着通过哈希算法计算键值对的数组下标，如果没有发生冲突，直接存储到数组。如果发生冲突，会有两种情况：
第1种，当前节点是红黑树节点，那么将节点放入到红黑树，如果树上存在相同的key，默认将value值覆盖为新值（变量onlyIfAbsent控制是否覆盖）。
第2种，当前节点为链表，且链表上没有相同的key，这里就要非常注意了，因为这时候会把键值对保存在链表尾部，导致链表长度变长。当链表长度超过8时，HashMap开始做优化操作，来防止链表过长导致搜索效率变低：就是代码中的treeifyBin方法。
treeifyBin从字面意思理解是树化，也就是把链表转化成树的意思。那这里操作完成后真的会转化成树吗？答案是不一定。如下代码，当数组的大小小于64时，只是进行扩容工作，扩容之后之前冲突的节点可能就会成为非冲突节点。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 当数组长度小于64时,扩容
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 将链表转化为二叉树
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);
}
}
putVal代码最后，还判断是否插入了新节点，如果有插入，并且还超过了扩容的阈值，那就进行扩容。put方法总体流程的分析至此结束。
下图绘制了put操作的流程图（为了防止阅读混乱，隐藏了关于相同key替换的逻辑）
2.扩容机制
HashMap中有个设定，数组大小初始值为16（2的4次方，也可以在构造方法中设置），每次扩容，都是之前容量的2倍。所以，HashMap的容量始终是2的次幂。
2.1什么时候会触发扩容操作呢？
当HashMap中节点数量大于阈值threshold时，进行扩容操作。threshold = loadFactor * 当前数组大小。
节点数为变量size，数组数量为table.size，这两个值需要注意区分哦。
loadFactor默认值为0.75。如果loadFactor过大，将容易造成哈希碰撞；如果loadFactor过小，则会出现更多空位，造成资源浪费。选择选择0.75作为默认的加载因子，是时间和空间成本上的一种折中选择。
2.2为什么HashMap大小始终是2的次幂呢？
有两个原因，这两个原因都与哈希函数有关。
p = tab[i = (n - 1) & hash]
哈希函数中，n为数组的长度，即tab.length。hash为key的hashCode（哈希值），这个后面再解释哈希值如何计算到的。
1.哈希函数计算下标更快
我们前面讲过，计算数组下标使用取余的方式，这里使用的是位运算&，其实，当n为2的次幂时，下面的等式成立
(n-1) & hash = hash % n
对于这个等式，稍加思考可以理解，下面举个例子验证一下:
假设 n=16 ，hash值为50
hash % n = 50 % 16 = 2
16的二进制为10000，50的二进制为110010
(n-1) & hash = 1111 & 110010 = 000010（十进制为2）
可以看到两种算法相等。
既然等式成立，便可以使用 (n-1) & hash 计算下标，位运算的速度显然是优于取余运算。
2.扩容后Node移动方便
当数组扩容后，n值变为原来的2倍，n - 1在原来的基础上又增加1位，那么哈希函数计算得到的下标也会发生变化。(n-1) & hash计算得到的结果要么与原值相等，要么等于“原值+旧数组容量”。
还是以n=16 ，hash=50为例
(n-1) & hash = 1111 & 110010 = 000010
扩容之后n = 32
(n-1) & hash = 11111 & 110010 = 010010 (原值 000010 + 旧数组容量10000[16的2进制] )
HashMap详细扩容的计算逻辑可以看源码中resize方法。
3.哈希算法
面试经常会问到Hashmap的哈希算法是什么？
上面提到了哈希算法：
index = (n - 1) & hash
这里的哈希算法其实可以分成两步，第一步获取hash值，第二步获取下标。
第二步计算下标上面已经介绍过，这里只介绍第一步计算hash值的源码。
hash值是通过HashMap中的静态方法hash(Object key)得到，如下。
static final int hash(Object key) {
int h;
// key的hashCode的前16位和后16位异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
“>>>”表示无符号右移，高位插入0。
这里的操作是将key的哈希值右移16位，与原哈希值进行异或（^）操作。
之所以这么做，是因为当n值较小时，只有hash的后面几位参与哈希算法操作，高位不参与运算。如果有几组数据，哈希值只是高位发生变化，那么他们将会发生哈希冲突，将高位加入到运算过程中，可以使得到的结果更加分散。
4.树化和非树化阈值
树化阈值为8，非树化阈值为6。
当链表长度大于8时，调用树化函数。
当树节点小于6时，讲树转为链表。
至于为什么树化阈值为8，这里简单说一下。
由于 TreeNode 的大小大约是常规节点的两倍，因此仅在有足够多的冲突节点时才使用红黑树存储（参见 TREEIFY_THRESHOLD）。当树变得太小时（由于移除或调整大小），则会被转换回普通节点。在具有良好分布的hashCode 的用法中，很少使用树。
泊松分布是一种概率分布，它描述了在给定时间间隔内发生指定数量事件的概率。在 HashMap 的上下文中，泊松分布可以用来描述在给定哈希桶中找到特定数量节点的概率。HashMap注释中，出现哈希桶大小为8的概率为0.00000006，如果设置阈值为 9，概率已经非常小，几乎不会再次发生碰撞。设置为8既考虑性能，也避免频繁树化操作。
3.HashMap的get方法
get方法要简单很多，通过哈希函数获取到数组下标，根据key是否相等（== 或者 equals二者满足其一即可），来判断是否命中。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != 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;
}
3.其他的Map
在Java中，Map也表示着一个接口。实现接口的类有HashMap、HashTable、TreeMap、LinkedHashMap、ConcurrHashMap。这些类有着不同的实现和不同的使用场景。
HashTable
实现几乎与HashMap一样，这个是线程安全的类，常用的方法都用synchronized修饰。
另外如果需要使用线程安全的HashMap，也可以使用Map m = Collections.synchronizedMap(new HashMap(...))生成一个线程安全的Map。
TreeMap
内部使用红黑树存储键值对。特点是有序。
LinkedHashMap
HashMap的子类，Node节点中多了两个字段before, after，插入的节点之间是一个双向链表结构，用来记录节点的顺序。
ConcurrHashMap
JUC包中的类。ConcurrentHashMap 使用分段锁设计，将映射划分为多个段，每个段都有自己的锁。这允许多个线程同时访问不同的段，从而提高并发性能。
4.ArrayMap、SparseArray
Android SDK的包中有两个类ArrayMap和SparseArray，尝尝用来与HashMap做对比。
在这两个类的注释中，明确表示它们的存在就是为了更省内存。
ArrayMap
实现了Map接口。内部使用2个数组进行存储，一个记录key的hash值，另外一个记录key和value。
相比hashMap的节点node而言，少了next这个成员变量；并且它还尝试更积极地控制这些数组大小的增长（因为增长它们只需要复制数组中的条目，而不是重建哈希映射）。当从中删除项目时，它会收缩其数组。
而对于数据的插入和获取，采用的二分查找，没有hash算法快，插入时还涉及到数组的搬移。
整体的时间效率不如hashMap，对于小于一百个item的场景，性能差别小于50%。
SparseArray
key是int类型，根据key来确定位置。
key为int类型，而HashMap中需要对int自动装箱，同样是基于2分查找计算下标。对于小于一百个item的场景，性能差别小于50%。
为了提高性能，容器在删除键时进行了优化：它不会立即压缩其数组，而是将删除的条目标记为已删除。然后，可以将该条目重新用于同一键，或者稍后在垃圾回收中被占用。每当需要增长数组或检索map大小或条目值时，都必须执行此垃圾回收。