[JDK] HashMap 原理剖析
简介
哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而 HashMap 的实现原理也常常出现在各类的面试题中，重要性可见一斑。本文会对 Java 集合框架中的 HashMap，就 JDK7、JDK8 的源码实现进行分析。
正文
[JDK] HashMap 原理剖析
哈希表（hash table）也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，而 HashMap 的实现原理也常常出现在各类的面试题中，重要性可见一斑。本文会对 Java 集合框架中的 HashMap，就 JDK7、JDK8 的源码实现进行分析。
什么是哈希表
在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能差异。
-
数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
-
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
-
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
-
哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
比如我们要新增或查找某个元素，我们把当前元素的关键字，利用某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。
//其中，这个函数function一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：
index = function(key)
![.]()
这个函数就是我们后面会讨论的哈希函数，查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。
哈希冲突
然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和**散列地址分布均匀,**但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:
- 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）
- 再散列函数法
- 链地址法
而HashMap(JDK7)即是采用了链地址法，也就是数组+链表的方式。
一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。
这样子的 HashMap 性能上就抱有一定疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(n)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。
JDK7 中 HashMap 采用的是位桶+链表的方式，即我们常说的散列链表的方式，而 JDK8 中采用的是位桶+链表/红黑树（有关红黑树请查看红黑树）的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。
![.]()
HashMap实现原理
核心数组
HashMap 的主干是一个 Node 数组。Node 是 HashMap 的基本组成单元，每一个 Node 包含一个key-value键值对。
transient Node<K,V>[] table;
Node是HashMap中的一个静态内部类。代码如下
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
}
链表和红黑树转换机制
见后文源码分析
源码分析
我们大致知道Map内部通过数组来维护数据，元素在放入数组时，会通过hash函数计算存放在数组的哪个下标位置，放入后，如果该位置非空，则将该处数据通过链表存储，如果长度超出指定范围，则转换为有序的红黑树存储。那么，在源码分析前我们先做个描述上的约定（源码中使用的是英文单词bin，含义上可以理解为箱子或是桶）：
- 数组：桶容器（包含多个桶）
- 数组的某一位置对应的元素集合：桶中元素集合
- 数组的某一位置对应的元素集合的存储结构：链表结构桶、树结构桶
- 数组的某一位置对应的元素集合中的存储元素：桶中的元素节点
基础参数
/* ---------------- Fields -------------- */
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//元素桶数组
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
//Set集合，进行了节点数组的Map.Entry<K,V>
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
//实际存储的key-value键值对的个数
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
构造器
HashMap有4个构造器，其他构造器如果用户没有传入 initialCapacity 和 loadFactor 这两个参数，默认值：initialCapacity默认为16，loadFactory默认为0.75
/* ---------------- Public operations -------------- */
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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;
//此处进行了容量阈值的初始化操作，返回一个比初始化容量大的最接近的一个2的幂次方的值
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
hash 运算
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
//计算 HashCode ，并通过异或方式从高位到低位扩展了 hash 集合中的元素。因为散列桶使用的是2的幂次方长度，因此仅在当前二级制码更高位变化中的散列将发生碰撞。（众所周知，前文的例子中的是在小的列表中连续行的存储Float类型的集合。）因此，我们将其应用在扩展高位向下扩散分布的冲突形式转换。这是在二进制扩散的一种速度、效率和质量多方面权衡。通常大量的hash集合会被合理分配（所以并不是得益于扩散）。我们使用树结构来解决大数据集合场景下的桶中元素冲突的问题，我们仅仅是通过XOR（异或）的方式来来移动一些二进制位，实现减少系统性能损失的目的。以及，通过避免由于列表的限制而使用的索引计算的方式来合并高位的冲突。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从上面的代码可以看到key的hash值的计算方法。key 的 hash 值高16位不变，低16位与高16位异或作为 key 的最终 hash 值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此 key 的 hash 值高16位不变。）
![.]()
后文会继续讨论此处这样设计的用途，详见元素节点存放下标的计算。
扩容阈值初始化
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
//由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如0000 11xx xxxx。
n |= n >>> 1;
//注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为0000 11xx xxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00 0011 11xx xxxx 。
n |= n >>> 2;
//这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00 0011 1111 11xx xxxx 。
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
以此类推：
注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1（但是这已经是负数了。在执行 tableSizeFor 之前，对 initialCapacity 做了判断，如果大于 MAXIMUM_CAPACITY(2 ^ 30)，则取 MAXIMUM_CAPACITY。如果等于 MAXIMUM_CAPACITY(2 ^ 30)，会执行移位操作。所以这里面的移位操作之后，最大30个1，不会大于等于 MAXIMUM_CAPACITY。30个1，加1之后得2 ^ 30） 。
For Example:
![.]()
// 构造器中threshold（当HashMap的size到达threshold这个阈值时会扩容）。但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。
this.threshold = tableSizeFor(initialCapacity);
扩容机制
put
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;
//1. 如果当前map中无数据，执行resize方法进行初始化。并且返回n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.1 如果要插入的键值对要存放的这个位置刚好没有元素，那么把他封装成Node对象，放在这个位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//2.2 否则的话，说明这上面有元素
else {
Node<K,V> e; K k;
//2.2.1 如果这个元素的key与要插入的一样，那么就替换一下。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.2.2 【红黑树结构】如果当前节点是TreeNode类型的数据，执行putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//2.2.3 【链表结构】遍历这条链子上的数据，跟JDK7没什么区别
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//判断如果链表数目是否超过了8，是的话执行treeifyBin方法转换为红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果key存在,且值相等，直接覆盖
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;
}
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.
*
* @return the table
*/
//初始化或增加数组容量大小，如果为null,则分配符合初始化容量目标的值到变量`threshold`中,否则，因为我们用的是2的幂次方扩展方式，每个桶中的元素，必须保持相同的索引，或在新的数组中移动2的幂次方的偏移量
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//如果当前的数组大小大于0
if (oldCap > 0) {
//超过最大值，返回最大值 2^31 -1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//否则，如果当前数组大小的两倍小于最大容值范围，且当前数组大小>=默认初始化容量(16) ，则当前扩容阈值左移2位，相当于 * 2 ；注意，此处会将当前容量 * 2 赋值给局部变量 newCap
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//数组大小为0，但是当前的扩容阈值大于0，则更新当前的的扩容阈值到局部变量
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);
}
//如果扩容阈值为0，进行扩容计算，并赋值当前元素个数 * 负载因子（0.75）
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;
//1.1 判断当前数组是否为空
if (oldTab != null) {
//循环当前数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//逐个取出非空元素
if ((e = oldTab[j]) != null) {
//原地址引用置空
oldTab[j] = null;
//判断元素下一节点是否为null，是的话，进行hash运算获得平均分布的下标，存放元素到新的数组中对应下标位置处（单个元素直接存放）
if (e.next == null)
//此处就是为什么要将Map的容量大小定义为2的幂次方的原因，(2^n -1) & hashVal,比如2的4次方（16），对应-1计算后的2进制数位1111 1111，那么可以看做有8个位置存放数据，剩下的取决于hash函数对于键值key的运算结果分布是否均匀了。这个前文我们提到过HASH的运算方式，屏蔽了高位对低位的hash运算影响，我们结合下面这个下标的计算方式继续讨论。
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是红黑树结构，执行split函数，在树的元素桶中进行节点拆分，就是将当前元素，放到合适的位置（有序），或是取消树结构（如果现在桶的元素不够多的时候），该方法仅在调整大小时调用，源码中有关于桶中元素的拆分和索引计算的论述
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//链表桶数据存储，保持一定顺序，分链操作，后续会继续分析
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//循环获取链表桶中的下个元素节点的数据，如果数组中存放的是链表，会将原来的链表分成两条链表
do {
next = e.next;
//通过计算e.hash&oldCap==0构造一条链，oldCap，低位容量，如果是8，对应0000 1111
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//通过e.hash&oldCap!=0构造另外一条链，newCap,高位容量，如16，对应1111 0000
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//遍历结束以后，将tail指针指向null，e.hash&oldCap==0构造而来的链的位置不变
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//e.hash&oldCap!=0构造而来的链的位置在数组j+oldCap位置处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
元素节点存放下标的计算
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//...
//通过hash运算解析存放的位置，因为我们每次初始化的容量是根据扩容阈值判断和历史容量的2倍计算而来，此处通过和newCap-1进行与操作，如果容量是2的幂次方，对应减1后的二进制数值一般表示为 1111...,再和对应key的hash值相与后，可以实现数据更均匀的落在散列桶的槽。而分布的均匀程度，也由hash函数来保证了。
//另外一方面，新的容量由于是旧容量的2倍，也是2的幂次方，高位的数据特征不会由于扩容操作，影响低位数据的hash运算分布情况，也避免了重新计算hash的性能损耗
newTab[e.hash & (newCap - 1)] = e;
table 的长度都是 2 的幂，因此 index 仅与 hash 值的低 n 位有关（此 n 非table.length，而是 2 的幂指数），hash 值的高位都被与操作置为 0 了。
假设 table.length=2^4=16
![.]()
Q: 如果没有中间这一步异或操作，直接使用(n-1)&hashCode(),又会怎么样？
A: 只有 hashCode 的低四位参与了运算，这样的设计明显很容易发生碰撞。
Q: 这个异或操作，设计者是如何考虑的？
A: 源码的注释中有写到，设计者权衡了 speed，utility，quality，将高 16 位与低 16 位异或来减少这种影响。设计者考虑到现在的 hashCode 分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算 ( table 长度比较小时)，从而引起的碰撞。
Q: 为什么要用异或来实现这个目的？
A: 所谓的异或，就是相反为1，相同为0，说明高位的结构特征对低位的结构特征产生了影响，这样得出的hashCode会包含高位的数据特征，可以降低低位HashCode发生碰撞的可能性（此处碰撞几率的控制，原先参考的维度只有hashCode函数,现在加入了高位数据特征的维度，降低了发生的几率）
Q: 那前面扩容使用2的幂次方又是为了什么呢？
A: 2的幂次方扩容，当列表容量扩展为原理来的2倍时，计算对应下标时，低位的数据的 hash 值和 n-1 相与的计算结果是其本身。2^n-1 = 111…1,对应n位二进制数，其数值不会对hash计算的结果产生影响。如果不是2的幂次方，任意一位都可能为0，如容量为10的话，对应二进制数为1010，相与的结果，其中有两位数字必定为0，增大了碰撞的结果，分析到这里，真的不得不感慨这样设计的巧妙。
存储结构
来段代码看下执行结果：
static void mapResize(){
Map<Object, Object> map = new HashMap<>(0);
map.put("x.1", "1.1");
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ViEhaN4H-1583848674211)(…/…/…/…/resources/image/2020-03/1583741239996.png)]
hash 碰撞
static void mapResize(){
Map<Object, Object> map = new HashMap<>(0);
map.put("x.1", "1.1");
//继续执行
for (int i = 0; i < 9; i++) {
map.put("x.2"+i, "2."+i);
}
for (int i = 0; i < 3; i++) {
map.put("x.3"+i, "3."+i);
}
map.put("x.4", "3.1");
}
![.]()
扩容中的分链操作
如果存储的数据结构是链表桶，在发生哈希碰撞时，会将原来的链表同过计算e.hash&oldCap==0分成两条链表,再将两条链表散列到新数组的不同位置上。
![.]()
扩容前数组长度为8，扩容为原数组长度的2倍即16。原来有一条链表在tab[2]的位置，扩容以后仍然有一条链在tab[2]的位置，另外一条链在tab[2+8]即tab[10]的位置处。
链表
我们知道当通过hash运算，分布在一个桶中的元素发生哈希碰撞的话，会采用链表的形式进行存储。
红黑树
那么，当桶中的元素超过一定范围之后，由于链表遍历查找复杂度较高，O(n)，而红黑树的遍历查找复杂度为O(log(n))，若桶中链表元素超过8时，会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。
为什么此处要使用6和8呢？
红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
其实,源码中也给出了解释
Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) pow(0.5, k) /
factorial(k)). The first values are:
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
more: less than 1 in ten million
大致翻译过来意思是：因为树节点的大小约为常规节点的两倍，所以我们仅在桶中包含足够多的节点数时才会使用它。当他们在重新调整大小时，如果开始变得更小，此时会转换为链表结构的桶进行存储。在使用上会通过他们的hash值来使其分布的更加均匀，树结构桶是极少被使用的。理想情况下，通过hash运算生成的随机值，桶中节点的分布概率是符合泊松分布的。默认调整大小的平均参数为0.5，扩容阈值为0.75。尽管粒度调整会带来一些较大幅度的冲突。忽略这些冲突，预期不同列表容量大小而发生的冲突的出现的概率是 exp(-0.5) pow(0.5, k) / factorial(k)。在长度为8时，其发生冲突的概率为千万分之一。
性能提升
篇末，我们来梳理下 JDK8 较 JDK7 中，做的一些调整来实现的性能上的提升。
数据存储结构
JDK7中使用数组+链表来实现，JDK8 使用的数组+链表+红黑树
hash算法优化
JDK7默认初始化大小16，加载因子0.75。如果传入了size，会变为大于等于当前值的2的n次方的最小的数。
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
为什么是2次方数？因为 indexFo r方法的时候，h&(length-1) , length是2的次方，那么 length-1 总是00011111等后面都是1的数，h&它之后，其实就相当于取余，与的效率比取余高，所以用了这种方式达到高效率。
下面是 JDK7 的 indexfor 的实现：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
另外在hash函数里面方法里面，数会经过右移，为什么要右移？因为取余操作都是操作低位，hash碰撞的概率会提高，为了减少hash碰撞，右移就可以将高位也参与运算，减少了hash碰撞。
哈希函数如下：
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
而前文分析的 JDK8 的哈希函数比较简单，可以直接通过右移实现。
/* ---------------- Static utilities -------------- */
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么 JDK8 的哈希函数会变简单？ JDK8 中我们知道用的是链表过度到红黑树，效率会提高，所以 JDK8 提高查询效率的地方由红黑树去实现，没必要像 JDK7 通过复杂友谊来减少碰撞(避免链表过长)。
扩容机制优化
在计算hash值的时候，JDK7 用了9次扰动处理=4次位运算+5次异或，而 JDK8 只用了2次扰动处理=1次位运算+1次异或。
![.]()
元素节点操作复杂度
扩容时机
JDK7的时候是先进行扩容后进行插入，而在JDK8的时候则是先插入后进行扩容。
//其实就是当这个Map中实际插入的键值对的值的大小如果大于这个默认的阈值的时候（初始是16*0.75=12）的时候才会触发扩容，
//这个是在JDK1.8中的先插入后扩容
if (++size > threshold)
resize();
其实这个问题也是 JDK8 对 HashMap 中，主要是因为对链表转为红黑树进行的优化，因为你插入这个节点的时候有可能是普通链表节点，也有可能是红黑树节点，
void addEntry(int hash, K key, V value, int bucketIndex) {
//这里当前数组如果大于等于12（假如）阈值的话，并且当前的数组的Entry数组还不能为空的时候就扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容数组，比较耗时
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//把新加的放在原先在的前面，原先的是e，现在的是new，next指向e
table[bucketIndex] = new Entry<>(hash, key, value, e);//假设现在是new
size++;
}
在 JDK7 中的话，是先进行扩容后进行插入的，就是当你发现你插入的桶是不是为空，如果不为空说明存在值就发生了hash冲突，那么就必须得扩容，但是如果不发生Hash冲突的话，说明当前桶是空的（后面并没有挂有链表），那就等到下一次发生 Hash 冲突的时候在进行扩容，但是当如果以后都没有发生hash冲突产生，那么就不会进行扩容了，减少了一次无用扩容，也减少了内存的使用。
JDK8 动态转换链表和红黑树结构（以8为分界线）
前文已分析，不再赘述，源码中也有对应解释。
总结
哈希表如何解决Hash冲突
![.]()
为什么HashMap具备下述特点：键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化
![.]()
为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键
![.]()
HashMap 中的 key若 Object类型， 则需实现哪些方法
![.]()
REFERENCES
