HashMap 源码赏析 JDK8
超级小小黑 人气:3一、简介
HashMap源码看过无数遍了，但是总是忘，好记性不如烂笔头。
本文HashMap源码基于JDK8。
文章将全面介绍HashMap的源码及HashMap存在的诸多问题。
开局一张图，先来看看hashmap的结构。
二、历史版本
再次声明一下本文HashMap源码基于JDK8。不同版本HashMap的变化还是比较大的，在1.8之前，HashMap没有引入红黑树，也就是说HashMap的桶（桶即hashmap数组的一个索引位置）单纯的采取链表存储。这种结构虽然简单，但是当Hash冲突达到一定程度，链表长度过长，会导致时间复杂度无限向O(n)靠近。比如向HashMap中插入如下元素，你会神奇的发现，在HashMap的下表为1的桶中形成了一个链表。
1 map.put(1, 1); 2 map.put(17,17); 3 map.put(33,33); 4 map.put(49,49); 5 map.put(65,65); 6 map.put(81,81); 7 map.put(97,97);
...
16^n + 1
为了解决这种简单的底层存储结构带来的性能问题，引入了红黑树。在一定程度上缓解了链表存储带来的性能问题。引入红黑树之后当桶中链表长度超过8将会树化即转为红黑树（put触发）。当红黑树元素少于6会转为链表（remove触发）。
在这里还有一个很重要的知识点，树化和链表化的阈值不一样？想一个极端情况，假设阈值都是8，一个桶中链表长度为8时，此时继续向该桶中put会进行树化，然后remove又会链表化。如果反复put和remove。每次都会进行极其耗时的数据结构转换。如果是两个阈值，将会形成一个缓冲带，减少这种极端情况发生的概率。
上面这种极端情况也被称之为复杂度震荡。
类似的复杂度震荡问题ArrayList也存在。
三、基础知识
3.1，常量和构造方法
1 // 16 默认初始容量（这个容量不是说map能装多少个元素，而是桶的个数）
2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
3 // 最大容量值
4 static final int MAXIMUM_CAPACITY = 1 << 30;
5 // 默认负载因子
6 static final float DEFAULT_LOAD_FACTOR = 0.75f;
7 //树化阈值 一个桶链表长度超过 8 进行树化
8 static final int TREEIFY_THRESHOLD = 8;
9 //链表化阈值 一个桶中红黑树元素少于 6 从红黑树变成链表
10 static final int UNTREEIFY_THRESHOLD = 6;
11 //最小树化容量，当容量未达到64，即使链表长度>8，也不会树化，而是进行扩容。
12 static final int MIN_TREEIFY_CAPACITY = 64;
13 //桶数组，bucket. 这个也就是hashmap的底层结构。
14 transient Node<K,V>[] table;
15 //数量，即hashmap中的元素数量
16 transient int size;
17 //hashmap进行扩容的阈值。 （这个表示的元素多少，可不是桶被用了多少哦，比如阈值是16，当有16个元素就进行扩容，而不是说当桶被用了16个）
18 int threshold;
19 //当前负载因子，默认是 DEFAULT_LOAD_FACTOR=0.75
20 final float loadFactor;
21 /************************************三个构造方法***************************************/
22 public HashMap(int initialCapacity, float loadFactor) {//1，初始化容量2，负载因子
23 if (initialCapacity < 0)
24 throw new IllegalArgumentException("Illegal initial capacity: " +
25 initialCapacity);
26 if (initialCapacity > MAXIMUM_CAPACITY)// > 不能大于最大容量
27 initialCapacity = MAXIMUM_CAPACITY;
28 if (loadFactor <= 0 || Float.isNaN(loadFactor))
29 throw new IllegalArgumentException("Illegal load factor: " +
30 loadFactor);
31 this.loadFactor = loadFactor;
32 this.threshold = tableSizeFor(initialCapacity);//总要保持 初始容量为 2的整数次幂
33 }
34 public HashMap(int initialCapacity) {
35 this(initialCapacity, DEFAULT_LOAD_FACTOR);
36 }
37 public HashMap() {
38 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
39 }
3.2、桶的两种数据结构
前面说了，JDK8 HashMap采用的是链表+红黑树。
链表结构
1 static class Node<K,V> implements Map.Entry<K,V> {
2 final int hash;
3 final K key;
4 V value;
5 Node<K,V> next;
6
7 Node(int hash, K key, V value, Node<K,V> next) {
8 this.hash = hash;
9 this.key = key;
10 this.value = value;
11 this.next = next;
12 }
13 }
红黑树结构
1 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
2 TreeNode<K,V> parent; // red-black tree links
3 TreeNode<K,V> left;
4 TreeNode<K,V> right;
5 TreeNode<K,V> prev; // needed to unlink next upon deletion
6 boolean red;
7 TreeNode(int hash, K key, V val, Node<K,V> next) {
8 super(hash, key, val, next);
9 }
10 }
3.3、hash算法实现
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算桶下标方法
(n - 1) & hash//n表示HashMap的容量。 相当于取模运算。等同于 hash % n。
n其实说白了就是HashMap底层数组的长度。(n-1) & hash这个与运算，等同于hash % n。
hash()方法，只是key的hashCode的再散列，使key更加散列。而元素究竟存在哪个桶中。还是 (n - 1) & hash 结果决定的。
综合一下如下，在hashmap中计算桶索引的方法如下所示。
public static int index(Object key, Integer length) {
int h;
h = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
return (length - 1) & h;
}
假设当前hashmap桶个数即数组长度为16，现在插入一个元素key。
计算过程如上图所示。得到了桶的索引位置。
在上面计算过程中，只有一步是比较难以理解的。也就是为什么不直接拿 key.hashcode() & （n - 1） ，为什么要用 key.hashcode() ^ （key.hashcode() >>> 16） 为什么要多一步呢？后面问题总结会详细介绍。
四、HashMap put过程源码
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2 boolean evict) {
3 Node<K,V>[] tab; Node<K,V> p; int n, i;
4 if ((tab = table) == null || (n = tab.length) == 0)//put1，懒加载，第一次put的时候初始化table（node数组）
5 n = (tab = resize()).length;//resize中会进行table的初始化即hashmap数组初始化。
6 if ((p = tab[i = (n - 1) & hash]) == null)//put2，(n - 1) & hash：计算下标。// put3，判空，为空即没hash碰撞。直接放入桶中
7 tab[i] = newNode(hash, key, value, null);//将数据放入桶中
8 else {//put4，有hash碰撞
9 Node<K,V> e; K k;
10 if (p.hash == hash &&
11 ((k = p.key) == key || (key != null && key.equals(k))))//如果key已经存在，覆盖旧值
12 e = p;
13 else if (p instanceof TreeNode)//put4-3：如果是红黑树直接插入
14 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
15 else {//如果桶是链表，存在两种情况，超过阈值转换成红黑树，否则直接在链表后面追加
16 for (int binCount = 0; ; ++binCount) {
17 if ((e = p.next) == null) {//put4-1：在链表尾部追加
18 p.next = newNode(hash, key, value, null);
19 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
20 treeifyBin(tab, hash);//put4-2：链表长度超过8，树化（转化成红黑树）
21 break;
22 }
23 if (e.hash == hash &&
24 ((k = e.key) == key || (key != null && key.equals(k))))//如果key已经存在，覆盖旧值
25 break;
26 p = e;
27 }
28 }
29 if (e != null) { // existing mapping for key //put5：当key已经存在，执行覆盖旧值逻辑。
30 V oldValue = e.value;
31 if (!onlyIfAbsent || oldValue == null)
32 e.value = value;
33 afterNodeAccess(e);
34 return oldValue;
35 }
36 }
37 ++modCount;
38 if (++size > threshold)//put6，当size > threshold，进行扩容。
39 resize();
40 afterNodeInsertion(evict);
41 return null;
42 }
其实上面put的逻辑还算是比较清晰的。（吐槽一下JDK源码，可读性真的不好，可读性真的不如Spring。尤其是JDK中总是在if或者for中对变量进行赋值。可读性真的差。但是逻辑是真的经典）
总结一下put的过程大致分为以下8步。
1，懒汉式，第一次put才初始化table桶数组。（节省内存，时间换空间）
2，计算hash及桶下标。
3，未发生hash碰撞，直接放入桶中。
4，发生碰撞
4.1、如果是链表，迭代插入到链表尾部。
4.2、如果链表长度超过8，树化即转换为红黑树。（当数组长度小于64时，进行扩容而不是树化）
4.3、如果是红黑树，插入到红黑树中。
5，如果在以上过程中发现key已经存在，覆盖旧值。
6，如果size > threshold。进行扩容。
以上过程中，当链表长度超过8进行树化，只是执行树化方法 treeifyBin(tab, hash); 。但是在该方法中还有一步判断，也就是当桶数组长度<64。并不会进行树化，而是进行扩容。你想想，假如容量为16，你就插入了9个元素，巧了，都在同一个桶里面，如果这时进行树化，树化本身就是一个耗时的过程。时间复杂度会增加，性能下降，不如直接进行扩容，空间换时间。
看看这个方法
1 final void treeifyBin(Node<K,V>[] tab, int hash) {
2 int n, index; Node<K,V> e;
3 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//如果容量 < 64则直接进行扩容；不转红黑树。（你想想，假如容量为16，你就插入了9个元素，巧了，都在同一个桶里面，如果这时进行树化，时间复杂度会增加，性能下降，不如直接进行扩容，空间换时间）
4 resize();
5 else if ((e = tab[index = (n - 1) & hash]) != null) {
6 TreeNode<K,V> hd = null, tl = null;
7 do {
8 TreeNode<K,V> p = replacementTreeNode(e, null);
9 if (tl == null)
10 hd = p;
11 else {
12 p.prev = tl;
13 tl.next = p;
14 }
15 tl = p;
16 } while ((e = e.next) != null);
17 if ((tab[index] = hd) != null)
18 hd.treeify(tab);
19 }
20 }
在put逻辑中还有最重要的一个过程也就是扩容。
五、扩容
5.1、扩容
1 final Node<K,V>[] resize() {
2 Node<K,V>[] oldTab = table;
3 int oldCap = (oldTab == null) ? 0 : oldTab.length;
4 int oldThr = threshold;
5 int newCap, newThr = 0;
6 if (oldCap > 0) {
7 if (oldCap >= MAXIMUM_CAPACITY) {// 大于最大容量，不进行扩容（桶数量固定）
8 threshold = Integer.MAX_VALUE;
9 return oldTab;
10 }
11 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
12 oldCap >= DEFAULT_INITIAL_CAPACITY)//扩容为原来的两倍，<< 位运算
13 newThr = oldThr << 1; // double threshold threshold不在重新计算，同样直接扩容为原来的两倍
14 }
15 else if (oldThr > 0) // initial capacity was placed in threshold
16 newCap = oldThr;
17 else { // zero initial threshold signifies using defaults
18 newCap = DEFAULT_INITIAL_CAPACITY;
19 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
20 }
21 if (newThr == 0) {
22 float ft = (float)newCap * loadFactor;
23 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
24 (int)ft : Integer.MAX_VALUE);
25 }
26 threshold = newThr;
27 @SuppressWarnings({"rawtypes","unchecked"})
28 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建新的桶（原来的两倍）
29 table = newTab;
30 if (oldTab != null) {
31 for (int j = 0; j < oldCap; ++j) {//一共oldCap个桶
32 Node<K,V> e;
33 if ((e = oldTab[j]) != null) {//如果第j个桶没元素就不管了
34 oldTab[j] = null;
35 if (e.next == null)//只有一个元素，直接移到新的桶中（为什么不先判断是不是TreeNode？很简单，因为TreeNode没有next指针，在此一定为null，也能证明是一个元素。对于大多数没有hash冲突的桶，减少了判断，处处充满着智慧）
36 newTab[e.hash & (newCap - 1)] = e;//计算桶下标，e.hash & (newCap - 1)是newCap哦
37 else if (e instanceof TreeNode)
38 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
39 else { // rehash 源码很经典 40 Node<K,V> loHead = null, loTail = null;//下标保持不变的桶 41 Node<K,V> hiHead = null, hiTail = null;//下标扩容两倍后的桶 42 Node<K,V> next; 43 do { 44 next = e.next;
45 if ((e.hash & oldCap) == 0) {//判断成立，说明该元素不用移动
46 if (loTail == null)//尾空，头插 47 loHead = e; 48 else//尾不空，尾插 49 loTail.next = e; 50 loTail = e; 51 } 52 else {//判断不成立，说明该元素要移位到 (j + oldCap) 位置 53 if (hiTail == null) 54 hiHead = e; 55 else 56 hiTail.next = e; 57 hiTail = e;
58 }
59 } while ((e = next) != null);
60 if (loTail != null) {
61 loTail.next = null;
62 newTab[j] = loHead;
63 }
64 if (hiTail != null) {
65 hiTail.next = null;
66 newTab[j + oldCap] = hiHead;
67 }
68 }
69 }
70 }
71 }
72 return newTab;
73 }
从以上源码总计一下扩容的过程：
1，创建一个两倍于原来（oldTab）容量的数组（newTab）。
2，遍历oldTab
2.1，如果当前桶没有元素直接跳过。
2.2，如果当前桶只有一个元素，直接移动到newTab中的索引位。（e.hash & (newCap - 1)）
2.3，如果当前桶为红黑树，在split()方法中进行元素的移动。
2.4，如果当前桶为链表，执行链表的元素移动逻辑。
在以上过程中，我们着重介绍链表的元素移动。也就是上述代码中的39-68行。
首先，我们看其中
1 Node<K,V> loHead = null, loTail = null;//下标保持不变的桶 2 Node<K,V> hiHead = null, hiTail = null;//下标扩容两倍后的桶
loHead和loTail分别对应经过rehash后下标保持不变的元素形成的链表头和尾。
hiHead和hiTail分别对应经过rehash后下标变为原来(n + oldIndex）后的链表头和尾。
经过上面变量，我们不难发现，桶中的数据只有两个去向。（oldIndex和 n + oldIndex）
接下来我们思考一个问题。为什么经过rehash，一个桶中的元素只有两个去向？
以下过程很烧脑，但是看懂了保证会收获很多。 更会体会到源码之美。
大致画一下图，如下所示。
HashMap的容量总是2的n次方（n <= 32）。
假设扩容前桶个数为16。
看扩容前后的结果。观察扩容前后可以发现，唯一影响索引位的是hash的低第5位。
所以分为两种情况hash低第5位为0或者1。
1 当低第5位为0:newIndex = oldIndex 2 当低第5位为1:newIndex = oldIndex + oldCap
以上过程也就说明了为啥rehash后一个桶中的元素只有两个去向。这个过程我看没有博客介绍过。为什么在这里详细介绍这个呢？因为这个很重要，不懂这个就看不懂以上rehash代码，也很难体会到JDK源码的经典之处。给ConcurrentHashMap rehash时的锁打一个基础。
回到源码第45行。
if ((e.hash & oldCap) == 0)
这个判断成立，则说明该元素在rehash后下标不变，还在原来的索引位置的桶中。为什么？
我们先看一下 (e.hash & oldCap)
看结果，如果判断 if ((e.hash & oldCap) == 0) 成立，也就是说hash的低第5位为0。
在上个问题我们推导桶中元素的两个去向的时候，发现低第5位的两种情况决定了该元素的去向。再观察上面问题推导中的hash的第一种情况当*为0；
惊不惊喜，意不意外，神奇的发现，当hash低5位为0时，其新索引为依然为oldIndex。OK，你不得不佩服作者的脑子为何如此聪明。当然了这一切巧妙的设计都是建立在hashmap桶的数量总是2的n次方。
回到源码第60-67行。很简单了，将新的两个链表分别放到newTab的oldIndex位置和newIndex位置。正如我们上面推导的那样
1 if (loTail != null) {
2 loTail.next = null;
3 newTab[j] = loHead;//j 即oldIndex
4 }
5 if (hiTail != null) {
6 hiTail.next = null;
7 newTab[j + oldCap] = hiHead; //j + oldCap即newIndex
8 }
以上resize过程就说完了。
留一个问题，以上resize过程性能还能不能进一步优化呢？有兴趣的可以对比ConcurrentHashMap的这个rehash源码。你会神奇的发现JDK8的作者为了性能究竟有多拼。
当然resize过程在并发环境下还是存在一定问题的。接下来继续往下看。
5.2、JDK7并发环境扩容问题——循环链表
先看源码
1 //将当前所有的哈希表数据复制到新的哈希表
2 void transfer(Entry[] newTable, boolean rehash) {
3 int newCapacity = newTable.length;
4 //遍历旧的哈希表
5 for (Entry<K,V> e : table) {
6 while(null != e) {
7 //保存旧的哈希表对应的链表头的下一个结点
8 Entry<K,V> next = e.next;
9 if (rehash) {
10 e.hash = null == e.key ? 0 : hash(e.key);
11 }
12 //因为哈希表的长度变了，需要重新计算索引
13 int i = indexFor(e.hash, newCapacity);
14 //第一次循环的newTable[i]为空，赋值给当前结点的下一个元素，
15 e.next = newTable[i];
16 //将结点赋值到新的哈希表
17 newTable[i] = e;
18 e = next;
19 }
20 }
21 }
JDK7 hashmap采用的是头插法，也就是每put一个元素，总是插入到链表的头部。相对于JDK8尾插法，插入操作时间复杂度更低。
看上面transfer方法。假设扩容前数组长度为2，扩容后即长度为4。过程如下。（以下几张图片来自慕课网课程）
第一步：处理节点5，resize后还在原来位置。
第二步：处理节点9，resize后还在原来位置。头插，node(9).next = node(5);
第三步：处理节点11，resize后在索引位置3处。移动到新桶中。
并发环境下的问题
假设此时有两个线程同时put并同时触发resize操作。
线程1执行到，只改变了旧的链表的链表头，使其指向下一个元素9。此时线程1因为分配的时间片已经用完了。
紧接着线程2完成了整个resize过程。
线程1再次获得时间片，继续执行。解释下图，因为节点本身是在堆区。两个线程栈只是调整链表指针的指向问题。
当线程2执行结束后，table这个变量将不是我们关注的重点，因为table是两个线程的共享变量，线程2已经将table中的变量搬运完了。但是由于线程1停止的时间如上，线程1的工作内存中依然有一个变量next是指向9节点的。明确了这一点继续往下看。
当线程2执行结束。线程1继续执行，newTable[1]位置是指向节点5的。如下图。
如上图线程1的第一次while循环结束后，注意 e = next 这行代码。经过第一次循环后，e指向9。如下图所示。
按理来说此时如果线程1也结束了也没啥事了，但是经过线程2的resize，9节点时指向5节点的，如上图。所以线程1按照代码逻辑来说，依然没有处理完。然后再将5节点插入到newTable中，5节点继续指向9节点，这层循环因为5.next==null，所以循环结束（自己看代码逻辑哦，e是在while之外的，所以这里不会死循环）。如下图所示，循环链表形成。
然后在你下一次进行get的时候，会进入死循环。
最后想一下JDK7会出现死循环的根源在哪里？很重要哦这个问题，根源就在于JDK7用的是头插法，而resize又是从头开始rehash，也就是在老的table中本来是头的，到新table中便成为了尾，改变了节点的指向。
5.3、JDK8的数据丢失问题
上面介绍了JDK7中循环链表的形成，然后想想JDK8中的resize代码，JDK8中的策略是将oldTab中的链表拆分成两个链表然后再将两个链表分别放到newTab中即新的数组中。在JDK8会出现丢失数据的现象（很好理解，在这里就不画图了，感兴
趣的自己画一下），但是不会出现循环链表。丢数据总比形成死循环好吧。。。另外一点JDK8的这种策略也间接的保证了节点间的相对顺序。
好吧，还是说说JDK8的丢数据问题吧。
1 do {
2 next = e.next;
3 if ((e.hash & oldCap) == 0) {//判断成立，说明该元素不用移动
4 if (loTail == null)//尾空，头插
5 loHead = e;
6 else//尾不空，尾插
7 loTail.next = e;
8 loTail = e;
9 }
10 else {//判断不成立，说明该元素要移位到 (j + oldCap) 位置
11 if (hiTail == null)
12 hiHead = e;
13 else
14 hiTail.next = e;
15 hiTail = e;
16 }
17 } while ((e = next) != null);
18 if (loTail != null) {
19 loTail.next = null;
20 newTab[j] = loHead;//j 即oldIndex
21 }
22 if (hiTail != null) {
23 hiTail.next = null;
24 newTab[j + oldCap] = hiHead; //j + oldCap即newIndex
25 }
假设两个线程，根据代码逻辑，线程1执行了4次循环让出时间片，如下图所示。
此时链表table索引1位置的桶如下所示
如果此时线程2也进行resize。此时线程2看到的oldTab是如上图所示的。很明显，接下来线程1执行完成，并顺利将两个链表放到了newTab中。
此时线程2又获取时间片并继续执行以下操作相当于之前线程1的resize结果被线程2覆盖了。此时就发生了数据的丢失。
终于介绍完了扩容过程，不容易啊。
六、HashMap get过程源码
1 public V get(Object key) {
2 Node<K,V> e;
3 return (e = getNode(hash(key), key)) == null ? null : e.value;//get1，计算hash
4 }
5 final Node<K,V> getNode(int hash, Object key) {
6 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
7 if ((tab = table) != null && (n = tab.length) > 0 &&
8 (first = tab[(n - 1) & hash]) != null) {// get2，(n - 1) & hash 计算下标
9 if (first.hash == hash && // always check first node //get3-1，首先检查第一个元素（头元素），如果是目标元素，直接返回
10 ((k = first.key) == key || (key != null && key.equals(k))))
11 return first;
12 if ((e = first.next) != null) {
13 if (first instanceof TreeNode)//get3-2，红黑树
14 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
15 do {//get3-3，链表
16 if (e.hash == hash &&
17 ((k = e.key) == key || (key != null && key.equals(k))))
18 return e;
19 } while ((e = e.next) != null);
20 }
21 }
22 return null;
23 }
看完了put的源码，会发现get过程是何其简单，大致过程如下
1，计算hash
2，计算下标
3，获取桶的头节点，如果头结点key等于目标key直接返回。
3.1，如果是链表，执行链表迭代逻辑，找到目标节点返回。
3.2，如果是红黑树，执行红黑树迭代逻辑，找到目标节点返回。
关于remove方法，不介绍了，无非就是就是get过程+红黑树到链表的转化过程。不介绍了。
七、问题总结
7.1、为什么hashmap的容量必须是2的n次方。
回顾一下计算下标的方法。即计算key在数组中的索引位。
hash&(n - 1)
其中n就是hashmap的容量也就是数组的长度。
假设n是奇数。则n-1就是偶数。偶数二进制中最后一位一定是0。所以如上图所示， hash&(n - 1) 最终结果二进制中最后一位一定是0，也就意味着结果一定是偶数。这会导致数组中只有偶数位被用了，而奇数位就白白浪费了。无形中浪费了内存，同样也增加了hash碰撞的概率。
其中n是2的n次方保证了（两个n不一样哦，别较真）hash更加散列，节省了内存。
难道不能是偶数吗？为啥偏偏是2的n次方？
2的n次方能保证(n - 1)低位都是1，能使hash低位的特征得以更好的保留，也就是说当hash低位相同时两个元素才能产生hash碰撞。换句话说就是使hash更散列。
呃。。。个人觉得2在程序中是个特殊的数字，通过上文resize中的关于二进制的一堆分析也是建立在容量是2的n次方的基础上的。虽然这个解释有点牵强。如果大家有更好的解释可以在下方留言。
两层含义：
1，从奇偶数来解释。
2，从hash低位的1能使得hash本身的特性更容易得到保护方面来说。（很类似源码中hash方法中 <<< 16的做法）
7.2、解决hash冲突的方法
hashmap中解决hash冲突采用的是链地址法，其实就是有冲突了，在数组中将冲突的元素放到链表中。
一般有以下四种解决方案。详情度娘。
1 链地址法 2 开放地址法 3 再哈希法 4 建立公共溢出区
7.3、HashMap、HashTable、ConcurrentHashMap区别
HashMap是不具备线程安全性的。
HashTable是通过Synchronized关键字修饰每一个方法达到线程安全的。性能很低，不建议使用。
ConcurrentHashMap很经典，Java程序员必精通。下篇文章就介绍ConcurrentHashMap。该类位于J.U.C并发包中，为并发而生。
7.4、如何保证HashMap的同步
Map map = Collections.synchronizedMap(new HashMap());其实其就是给HashMap的每一个方法加Synchronized关键字。
性能远不如ConcurrentHashMap。不建议使用。
7.5、为什么引入红黑树
这个问题很简单，因为红黑树的时间复杂度表现更好为O(logN)，而链表为O(N)。
为什么红黑树这么好还要用链表？
因为大多数情况下hash碰撞导致的单个桶中的元素不会太多，太多也扩容了。只是极端情况下，当链表太长会大大降低HashMap的性能。所以为了应付这种极端情况才引入的红黑树。当桶中元素很少比如小于8，维护一个红黑树是比较耗时的，因为红黑树需要左旋右旋等，也很耗时。在元素很少的情况下的表现不如链表。
一般的HashMap的时间复杂度用平均时间复杂度来分析。除了极端情况链表对HashMap整体时间复杂度的表现影响比较小。
7.6、为什么树转链表和链表转树阈值不同
其实上文中已经介绍了，因为复杂度震荡。详情请参考上文。
7.7、Capacity的计算
变相问一下这个问题就是当初始化hashMap时initialCapacity参数传的是18，HashMap的容量是什么？是32。
1 static final int tableSizeFor(int cap) {
2 int n = cap - 1;
3 n |= n >>> 1;
4 n |= n >>> 2;
5 n |= n >>> 4;
6 n |= n >>> 8;
7 n |= n >>> 16;
8 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9 }
该方法大意：如果cap不是2的n次方则取大于cap的最小的2的n次方的值。当然这个值不能超过MAXIMUM_CAPACITY 。
（这里对这个方法没怎么看懂，明白的大神们回应在留言区指教。）
7.8、为什么默认的负载因子loadFactor = 0.75
1 * Because TreeNodes are about twice the size of regular nodes, we 2 * use them only when bins contain enough nodes to warrant use 3 * (see TREEIFY_THRESHOLD). And when they become too small (due to 4 * removal or resizing) they are converted back to plain bins. In 5 * usages with well-distributed user hashCodes, tree bins are 6 * rarely used. Ideally, under random hashCodes, the frequency of 7 * nodes in bins follows a Poisson distribution 8 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a 9 * parameter of about 0.5 on average for the default resizing 10 * threshold of 0.75, although with a large variance because of 11 * resizing granularity. Ignoring variance, the expected 12 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / 13 * factorial(k)). The first values are: 14 * 15 * 0: 0.60653066 16 * 1: 0.30326533 17 * 2: 0.07581633 18 * 3: 0.01263606 19 * 4: 0.00157952 20 * 5: 0.00015795 21 * 6: 0.00001316 22 * 7: 0.00000094 23 * 8: 0.00000006 24 * more: less than 1 in ten million
源码中有这么一段注释，重点就是 Poisson distribution 泊松分布。
以上是桶中元素个数和出现的概率对照表。
意思就是说当负载因子为0.75的时候，桶中元素个数为8的概率几乎为零。
通过泊松分布来看，0.75是"空间利用率"和"时间复杂度"之间的折衷。关于这个请参考《为什么默认的负载因子是0.75》。
7.9、HashMap中为什么用位运算而不是取模运算
主要是位运算在底层计算速度更快。
简单证明一下
1 long s1 = System.nanoTime();
2 System.out.println(2147483640 % 16);//8
3 long e1 = System.nanoTime();
4 long s2 = System.nanoTime();
5 System.out.println(2147483640 & 15);//8
6 long e2 = System.nanoTime();
7 System.out.println("取模时间：" + (e1 - s1));//取模时间：134200
8 System.out.println("与运算时间：" + (e2 - s2));//与运算时间：15800
题外话：还有一个刷leetcode题，二分法计算中心点。总结的经验，用除法会导致部分算法题超时。
1 long s1 = System.nanoTime();
2 System.out.println(1 + (2147483640 - 1) / 2);//1073741820
3 long e1 = System.nanoTime();
4 long s2 = System.nanoTime();
5 System.out.println(1 + (2147483640 - 1) >> 1);//1073741820
6 long e2 = System.nanoTime();
7 System.out.println("除法时间：" + (e1 - s1));//除法时间：20100
8 System.out.println("位运算时间：" + (e2 - s2));//位运算时间：15700
注意：一般二分法用left + (right - left)/2;因为如果用(right+left)/2;right + left容易>Integer.MAX_VALUE;
如有错误的地方还请留言指正。
原创不易，转载请注明原文地址： https://www.cnblogs.com/hello-shf/p/12168181.html
参考文献：
https://www.jianshu.com/p/003256ce41ce
https://www.cnblogs.com/morethink/p/7762168.html
加载全部内容