摘要
HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别，深入探讨HashMap的结构实现和功能原理。
数学知识
- << : 左移运算符，num << 1,相当于num乘以2 低位补0
举例：3 << 2
将数字3左移2位，将3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，然后把该数字高位(左侧)的两个零移出，其他的数字都朝左平移2位，最后在低位(右侧)的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是12。
数学意义：
在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方。
: 右移运算符
举例：11 >> 2
则是将数字11右移2位，11 的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是2。
数学意义：
右移一位相当于除2，右移n位相当于除以2的n次方。这里是取商哈，余数就不要了。
: 无符号右移，忽略符号位，空位都以0补齐
按二进制形式把所有的数字向右移动对应位数，低位移出(舍弃)，高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。 其他结构和>>相似。
- % : 模运算 取余
简单的求余运算
- ^ : 位异或 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0
0^0=0， 1^0=1， 0^1=1， 1^1=0
- & : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0
0&0=0， 0&1=0， 1&0=0， 1&1=1 eg:用if ((a & 1) == 0) 代替 if (a % 2 == 0)来判断a是不是偶数。
- | : 或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0
0|0=0， 0|1=1， 1|0=1， 1|1=1
- ~ : 非运算 操作数的第n位为1，那么结果的第n位为0，反之，也就是取反运算（一元操作符：只操作一个数）
简介
Java为数据结构中的映射定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、HashTable、LinkedHashMap和TreeMap，类继承关系如下图所示：
下面针对各个实现类的特点做一些说明：
HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。
内部实现
搞清楚HashMap，首先需要知道HashMap是什么，即它的存储结构-字段；其次弄明白它能干什么，即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。
存储结构-字段
从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。
这里需要讲明白两个问题：数据底层具体存储的是什么？这样的存储方式有什么优点呢？
(1) 从源码可知，HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。
static class Node<K,V> implements Map.Entry<K,V> {final int hash; //用来定位数组索引位置final K key;V value;Node<K,V> next; //链表的下一个nodeNode(int hash, K key, V value, Node<K,V> next) { ... }public final K getKey(){ ... }public final V getValue() { ... }public final String toString() { ... }public final int hashCode() { ... }public final V setValue(V newValue) { ... }public final boolean equals(Object o) { ... }}
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。
(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如程序执行下面代码：
map.put("美团","小美");
系统将调用”美团”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该键值对的存储位置，有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进行初始化，源码如下：
int threshold; // 所能容纳的key-value对极限
final float loadFactor; // 负载因子
int modCount;
int size;
首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考这篇文章，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
static final int hash(Object key) {
int h;
// h右移并且进行异或操作，目的就是让高位也参与运算，尽量避免hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。
功能实现-方法
HashMap的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、put方法的详细执行、扩容过程三个具有代表性的点深入展开讲解。
确定哈希桶数组索引位置
不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):
方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。
:::success 为什么HashMap的大小必须的2的n次方时，目的是参与计算元素的索引下标 :::
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
下面举例说明下，n为table的长度。
分析HashMap的put方法
HashMap的put方法执行过程可以通过下图来理解，自己有兴趣可以去对比源码更清楚地研究学习。
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
JDK1.8HashMap的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为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
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))))
e = p;
// 步骤④：判断该链为红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤⑤：该链为链表
else {
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;
}
hash算法
//重新计算哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key如果是null 新hashcode是0 否则 计算新的hashcode
}
无符号右移16位后做异或运算?
根据上面的说明我们做一个简单演练
将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算，可以将高低位二进制特征混合起来
从上文可知高区的16位与原hashcode相比没有发生变化，低区的16位发生了变化
我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？
我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算，计算公式：(n - 1) & hash，假如这时数组槽位有16个，则槽位计算如下：
仔细观察上文不难发现，高区的16位很有可能会被数组槽位数的二进制码锁屏蔽，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征
也许你可能会说，即使丢失了高区特征不同hashcode也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现
使用异或运算的原因
异或运算能更好的保留各部分的特征，如果采用&运算计算出来的值会向0靠拢，采用|运算计算出来的值会向1靠拢
为什么槽位数必须使用2^n (重点)
1、为了让哈希后的结果更加均匀
这个原因我们继续用上面的例子来说明
假如槽位数不是16，而是17，则槽位计算公式变成：(17 - 1) & hash
从上文可以看出，计算结果将会大大趋同，hashcode参加&运算后被更多位的0屏蔽，计算结果只剩下两种0和16，这对于hashmap来说是一种灾难
上面提到的所有问题，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升hashmap的运行效率
自己的理解:
- HashMap采用的是懒加载,在创建好map的时候,并没有初始化 Node
- tab在默认情况下是16,为什么是16,请看源码
// 这个是计算HashMap中key的hashCode值 ,至于为什么还要讲h逻辑右移16位,上面我抄的作业已经将的很清楚了,为了 // 让key的后16位更散列,使其具备前16位和后16的特征,为后面讲key放在哪个桶上面做准备 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
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;
if ((p = tab[i = (n - 1) & hash]) == null) //重点是这一行 讲key放在哪一个桶上面
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
在算出hash值之后,计算这个key落在哪一个桶上面,方法有2中,一种是&,一种是%,这两种方法都可行,但是效率不一样,请看下面的的测试(抄作业的测试),这个差的还是挺多的,尤其是在map发生扩容的时候,需要重新计算所有key的hash值放到新的hash桶上面,这个时候差别的更大了
public class HashMapDemo {
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("test", 1);
System.out.println(hashMap.get("test"));
testHash();
}
/**
* 有人怀疑两种运算效率差别到底有多少，我做个测试：
* <p>
* 直接【求余】和【按位】运算的差别验证
*/
public static void testHash() {
long currentTimeMillis = System.currentTimeMillis();
int a = 0;
int times = 10000 * 100000;
for (long i = 0; i < times; i++) {
a = 9999 % 1024;
}
long currentTimeMillis2 = System.currentTimeMillis();
int b = 0;
for (long i = 0; i < times; i++) {
b = 9999 & (1024 - 1);
}
long currentTimeMillis3 = System.currentTimeMillis();
System.out.println(a + "," + b);
System.out.println("%: " + (currentTimeMillis2 - currentTimeMillis));
System.out.println("&: " + (currentTimeMillis3 - currentTimeMillis2));
}
}
结果如下
783,783 %: 608 &: 355
下面讲一下为什么HashMap的初始值是16,而不是15,14,17呢?
首先 这个长度应该是2^n,因为(2^n -1) 的二进制有效数字都是1,那么为什么不能用0呢,因为后面的&运算的时候0-0的0,0-1的0,这样结果只会是0,会发生很多的碰撞的概率,要想结果更加的散列,只有保证 & 运算的时候,有一个对象的有效数字全是1.
举个栗子:
- (2-1)>>>>>0001
- (4-1)>>>>>0011
- (8-1)>>>>>0111
- (16-1)>>>>1111
另外,额外记录一点,如果你想取234对8的余数是多少,就可以使用 234&(8-1),余数为2,这个前提a想对b取余时,b必须是2^n才能这样玩,还是上面讲过的2^n -1的二级制 会全是1,这样,取余的时候,结果就是高位全是0,低位就可以保留下来,保留下来的低位就是余数了
栗子: 234想对8取余数,就是 234&(8-1)=? 234 11101010 8-1=7 00000111 得 2 00000010
if ((e.hash & oldCap) == 0) 这个地方是源码的骚操作,在扩容的时候,需要把原来map中的元素移到新生成的hash桶中,那么就需要按照 hash & (32-1) 这样再算一次,你会发现,只会有2种情况,要么还是原来的位置 5 ,要么就是 5 + 16 (假设原来是16大小) , 在源码中 这帮大牛并没有这样做,而是用 hash & 16== 0来判断,那么为什么呢?这样算出来的能行么?
// preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
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 { //扩容后的hash桶索引要 + 16
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;
}
}
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit,因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”
扩容机制&链表扩容
扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
我们分析下resize的源码，鉴于JDK1.8融入了红黑树，较复杂，为了便于理解我们仍然使用JDK1.7的代码，好理解一些，本质上区别不大，具体区别后文再说。
void resize(int newCapacity) { //传入新的容量
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //！！将数据转移到新的Entry数组里
table = newTable; //HashMap的table属性引用新的Entry数组
threshold = (int)(newCapacity * loadFactor);//修改阈值
}
这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。
以下代码您要自己尝试手动画图理解
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
e.next = newTable[i]; //标记[1]
newTable[i] = e; //将元素放在数组上
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别，下文详解。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，是否会被重新计算hash是有rehash条件的，有可能被放到了新数组的不同位置上。
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);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子loadFactor=1，即当键值对的实际大小size 大于table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组resize成4，然后所有的Node重新rehash的过程。
下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash (通过观察源码发现，默认没有重新hash，还是使用原来那个hash值，还会存放在同一个数组元素上)，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码，写的很赞，如下:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超过最大值就不再扩充了，就只好随你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
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);
}
// 计算新的resize上限
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;
if (oldTab != null) {
// 把每个bucket都移动到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表优化重hash的代码块, 链表扩容
// 高位头节点,尾节点
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
// 低位头节点,尾节点
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
链表转红黑树
红黑树扩容
链表是什么时候转红黑树的？
1、在putVal()方法中如果链表长度大于阈值8；会进入到treeifyBin()方法中执行链表转红黑树操作；
2、HashMap中有个MIN_TREEIFY_CAPACITY变量 等于64，表示允许执行treeifyBin()链表转红黑树操作时HashMap数组的最小容量；如果数组容量容量小于64，则先执行扩容操作；
源码分析
treeifyBin()
HashMap的putval()方法中调用treeifyBin()方法执行链表转红黑树操作；而treeifyBin()主要做两件事：
1、先根据hash计算出当前链表所在table数组中的位置，然后将其数据结构从单向链表Node转为双向链表TreeNode；
2、如果双向链表TreeNode的头节点hd不为null，则调用treeify()方法对TreeNode双向链表进行树型化操作；
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 数组长度小于64时，就先进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 如果新增的node 要插入的数组位置已经有node存在了，取消插入操作
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 步骤一：遍历链表中每个节点，将Node转化为TreeNode
// hd指向头节点，tl指向尾节点
TreeNode<K,V> hd = null, tl = null;
do {
// 将链表Node转换为红黑树TreeNode结构
TreeNode<K,V> p = replacementTreeNode(e, null);
// 以hd为头结点，将每个TreeNode用prev和next连接成新的TreeNode链表
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 步骤二：如果头结点hd不为null，则对TreeNode双向链表进行树型化操作
if ((tab[index] = hd) != null)
// 执行链表转红黑树的操作
hd.treeify(tab);
}
}
接着我们看一下真正将链表转成红黑树的地方：treeify()方法；
treeify()
treeify()方法中大体上分为三步：
1、遍历TreeNode双向链表，确定待插入节点x在其父节点的左边还是右边，然后将其插入节点到红黑树中；
2、插入节点之后树结构发生变化，需要通过变色和旋转操作维护红黑树的平衡；
3、因为调整了红黑树，root节点可能发生了变化，所以需要把最新的root节点放到双向链表的头部，并插⼊到table数组中。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 最开始的x表示TreeNode双向链表的头结点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 构建树的根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
// 第一部分
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// p 表示parent节点
for (TreeNode<K,V> p = root;;) {
// dir表示x节点在parent节点的左侧还是右侧
int dir, ph; // ph表示parent节点的hash值
K pk = p.key; // pk表示parent节点的key值
// x节点在parent节点的左侧
if ((ph = p.hash) > h)
dir = -1;
// x节点在parent节点的右侧
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 第二部分
TreeNode<K,V> xp = p; // xp表示x的父节点
// 如果p节点的左节点/右节点不为空，则令p = p.left/p.right，继续循环
// 直到p.left/p.right为空
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 令待插入节点x的父节点为xp, 即p
x.parent = xp;
// 根据dir判断插入到xp的左子树(<0)还是右子树(>0)
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 往红黑树中插入节点后，进行树的平衡操作
root = balanceInsertion(root, x);
break;
}
}
}
}
// 将root节点插入到table数组中
moveRootToFront(tab, root);
}
在往红黑树中插入一个节点之后，会调用balanceInsertion()方法进行树的平衡操作，我们来看一下红黑树是怎么进行平衡的？
balanceInsertion()
这里和TreeMap中插入节点之后进行的红黑树平衡操作fixAfterInsertion()类似
对红黑树进行平衡操作时，主要分两部分：直接返回、变色旋转后返回；
第一部分：直接返回根节点：
1、如果待插入节点x没有parent节点，直接把x的节点变为黑色，并作为根节点返回；
2、如果x的父节点为黑色、或者没有祖父节点，则直接返回根节点root；
第二部分：根据x节点在父节点xp的左侧还是右侧、xp节点再其父节点xpp的左侧还是右侧进行旋转、变色；
如果x的父节点xp是祖父节点xpp的左子节点：
- 若x的祖父节点xpp的右子节点xppr存在并且是红色，直接交换祖父节点和其子节点的颜色、并返回。
- 若x是其父节点xp的右子节点，交换x和xp的位置，然后对x进行左旋；
- 接着设置父节点xp为黑色、祖父节点xpp为红色，以xpp节点为轴右旋。
x的父节点xp是祖父节点的右子节点：
这里和上面的类似，只是左旋变右旋、右旋变左旋；
- 若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色、并返回。
- 若x是其父节点xp的左子节点，交换x和xp的位置，然后对x进行右旋；
- 接着设置父节点xp为黑色、祖父节点xpp为红色，以xpp节点为轴左旋。
代码如下：
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 将待插入节点x的节点颜色置为红色
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 1、如果x没有父节点，自己变为黑色节点、作为根节点返回
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 2、如果x的父节点为黑色或者没有祖父节点，则直接返回root
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 3、如果x的父节点xp是祖父节点的左子节点
if (xp == (xppl = xpp.left)) {
// 1）仅变色：
// 如果xp和xppr都是红色节点，则把xppr、xp置为黑色、zpp置为红色。
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
// 2）旋转 + 变色：
else {
// （1）如果x 是其父节点xp的右子节点。令当前节点为其父节点，然后对当前节点x进行左旋
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// （2）如果x的父节点xp不为空
if (xp != null) {
// 令xp的颜色为黑色
xp.red = false;
// 如果x的祖父节点xpp不为空
if (xpp != null) {
// 令xpp的颜色为红色
xpp.red = true;
// 对祖父节点xpp进行右旋
root = rotateRight(root, xpp);
}
}
}
}
// 4、x的父节点xp是祖父节点的右子节点
else {
// 逻辑和3、类似，只是单纯的左变右、右变左
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
可能上面一顿文字描述，不够直观，下面我们结合源代码图解分析；
上面第二部分的场景一：
x的父节点xp是祖父节点xpp的左子节点；
变色操作
若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；
左旋+变色+右旋操作
（1）步骤一：将树节点左旋到同一侧；
（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴右旋；
上面第二部分的场景二：
x的父节点xp是祖父节点xpp的右子节点；
变色操作
若x的祖父节点xpp的左子节点xppl并在并且是红色，直接交换祖父节点和其子节点的颜色；
右旋+变色+左旋操作
（1）步骤一：将树节点右旋到同一侧；
（2）步骤二：父节点和祖父节点变色，以祖父节点xpp为轴左旋；
rotateLeft()
左旋操作是将待旋转节点p的和其右子节点r交换位置和所有的节点关联关系，具体如下：
1、令当前旋转节点p的右子节点为其原右子节点r的左子节点rl（右儿子节点中的 左孙子节点）；rl节点的parent节点为p；
2、先令r的parent指向p的parent，然后再判断p节点的父节点pp的情况：
1）pp为空时，设置r为root节点，并将r的parent节点置为空；
2）p节点是父节点pp的左子节点时，pp的的左子节点变更为r；
3）p节点是父节点pp的右子节点时，pp的的右子节点变更为r；
3、最后将r的left指向p，p的parent指向r；
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl; // r为p的右子节点，pp为p的父节点，rl为r的左子节点
// 如果p的右节点不为空
if (p != null && (r = p.right) != null) {
// rl赋值，并将p.right指向r.left
if ((rl = p.right = r.left) != null)
// rl的父节点为p
rl.parent = p;
// 1）当p节点没有父节点时，先令r的父节点为p的父节点
if ((pp = r.parent = p.parent) == null)
// 把p节点的右子节点r变为黑色，并作为root节点
(root = r).red = false;
// 2）p节点在其父节点pp的左子节点
else if (pp.left == p)
// 令pp节点的左子节点为r
pp.left = r;
// 3）p节点在其父节点的右子节点
else
// 令pp节点的右子节点为r
pp.right = r;
// 令r的左子节点为p
r.left = p;
// p的父节点为r
p.parent = r;
}
return root;
}
结合源代码图解分析：
左旋操作的最终态：
rotateRight()
右旋操作和左旋类似，只是左变右、右变左；本质上逻辑都是一样的；
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr; // l为p的左子节点，pp为p的父节点，lr为l的右子节点
// 如果p的左节点不为空
if (p != null && (l = p.left) != null) {
// rl赋值，并将p.left指向r.right
if ((lr = p.left = l.right) != null)
// 设置lr的父节点为p
lr.parent = p;
// 1）将l的parent指向p的parent，如果p的父节点pp为空
if ((pp = l.parent = p.parent) == null)
// 将的l的颜色设置为黑色，并作为根节点root
(root = l).red = false;
// 2）p节点在其父节点pp的右子节点
else if (pp.right == p)
// 令pp节点的右子节点为l
pp.right = l;
// 3）p节点在其父节点pp的左子节点
else
// pp节点的左子节点为l
pp.left = l;
// 令l的右子节点为p
l.right = p;
// p的父节点为l
p.parent = l;
}
return root;
}
结合源代码图解分析：
既然左旋的大家已经看懂了，右旋大家可以尝试一下自己画个图呀；锻炼一下自己的动手能力；
moveRootToFront()
在treeify()方法中调用balanceInsertion()对红黑树平衡完之后，最后会进入moveRootToFront()方法，将root节点放到整条双向链表的头部，并插⼊到table数组中。
注意这里说的双向链表是红黑树中的TreeNode。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 判断table数组中存储的元素是不是最新的root节点
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 如果不是
if (root != first) {
// 重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中
// A <--> root <--> C 变为 root <--> A <--> C
Node<K,V> rn; // rn表示root的下一个节点
tab[index] = root;
TreeNode<K,V> rp = root.prev; // rp表示root的前一个节点
if ((rn = root.next) != null)
// rn的prev节点修改为rp
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
// rp的next节点修改为rn
rp.next = rn;
if (first != null)
// 把root节点移动到first节点之前
first.prev = root;
root.next = first;
// root的前一个节点置为空
root.prev = null;
}
// 对整个红黑树结构执行check校验
assert checkInvariants(root);
}
}
重塑双向链表的连接，把root放到整个链表的头位置，并将root插入到table数组中；
将A <–> root(B) <–> C 变为 root(B) <–> A <–> C。
线程安全性
在多线程使用场景中，应该尽量避免使用线程不安全的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。
JDK1.8与JDK1.7的性能对比
HashMap中，如果key经过hash算法得出的数组索引位置全部不相同，即Hash算法非常好，那样的话，getKey方法的时间复杂度就是O(1)，如果Hash算法技术的结果碰撞非常多，假如Hash算极其差，所有的Hash算法结果得出的索引位置一样，那样所有的键值对都集中到一个桶中，或者在一个链表中，或者在一个红黑树中，时间复杂度分别为O(n)和O(lgn)。 鉴于JDK1.8做了多方面的优化，总体性能优于JDK1.7，下面我们从两个方面用例子证明这一点。
Hash较均匀的情况
为了便于测试，我们先写一个类Key，如下：
class Key implements Comparable<Key> {
private final int value;
Key(int value) {
this.value = value;
}
@Override
public int compareTo(Key o) {
return Integer.compare(this.value, o.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value == key.value;
}
@Override
public int hashCode() {
return value;
}
}
这个类复写了equals方法，并且提供了相当好的hashCode函数，任何一个值的hashCode都不会相同，因为直接使用value当做hashcode。为了避免频繁的GC，我将不变的Key实例缓存了起来，而不是一遍一遍的创建它们。代码如下：
public class Keys {
public static final int MAX_KEY = 10_000_000;
private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
static {
for (int i = 0; i < MAX_KEY; ++i) {
KEYS_CACHE[i] = new Key(i);
}
}
public static Key of(int value) {
return KEYS_CACHE[value];
}
}
现在开始我们的试验，测试需要做的仅仅是，创建不同size的HashMap（1、10、100、……10000000），屏蔽了扩容的情况，代码如下：
static void test(int mapSize) {
HashMap<Key, Integer> map = new HashMap<Key,Integer>(mapSize);
for (int i = 0; i < mapSize; ++i) {
map.put(Keys.of(i), i);
}
long beginTime = System.nanoTime(); //获取纳秒
for (int i = 0; i < mapSize; i++) {
map.get(Keys.of(i));
}
long endTime = System.nanoTime();
System.out.println(endTime - beginTime);
}
public static void main(String[] args) {
for(int i=10;i<= 1000 0000;i*= 10){
test(i);
}
}
在测试中会查找不同的值，然后度量花费的时间，为了计算getKey的平均时间，我们遍历所有的get方法，计算总的时间，除以key的数量，计算一个平均值，主要用来比较，绝对值可能会受很多环境因素的影响。结果如下：
通过观测测试结果可知，JDK1.8的性能要高于JDK1.7 15%以上，在某些size的区域上，甚至高于100%。由于Hash算法较均匀，JDK1.8引入的红黑树效果不明显，下面我们看看Hash不均匀的的情况。
Hash极不均匀的情况
假设我们又一个非常差的Key，它们所有的实例都返回相同的hashCode值。这是使用HashMap最坏的情况。代码修改如下：
class Key implements Comparable<Key> {
//...
@Override
public int hashCode() {
return 1;
}
}
仍然执行main方法，得出的结果如下表所示：
从表中结果中可知，随着size的变大，JDK1.7的花费时间是增长的趋势，而JDK1.8是明显的降低趋势，并且呈现对数增长稳定。当一个链表太长的时候，HashMap会动态的将它替换成一个红黑树，这话的话会将时间复杂度从O(n)降为O(logn)。hash算法均匀和不均匀所花费的时间明显也不相同，这两种情况的相对比较，可以说明一个好的hash算法的重要性。
测试环境：处理器为2.2 GHz Intel Core i7，内存为16 GB 1600 MHz DDR3，SSD硬盘，使用默认的JVM参数，运行在64位的OS X 10.10.1上。
小结
- 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
- 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
- HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
- JDK1.8引入红黑树大程度优化了HashMap的性能。
还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。
常见面试题
- new HashMap会创建数组吗?
当创建 HashMap 集合对象的时候，HashMap 的构造方法并没有创建数组，而是在第一次调用 put 方法时创建一个长度是16 的数组 Node[] table （jdk1.8 之前是 Entry[] table）用来存储键值对数据。
若有收获，就点个赞吧
0 人点赞
