//这是根据key值获取value值的方法
public V get(Object key) {Node<K,V> e;//先调用hash(key)return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//Hash算法如下
static final int hash(Object key) {
int h;
//第一步：先获取key中的hashCode值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//第二步 再与hashcode向左移16位的值进行抑或
}
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 &&
//第三步 n是指数组长度，hash与(n-1)进行&与运算
(first = tab[(n - 1) & hash]) != null) {
//省略
…
…
}
return null;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

首先第一步获取hashcode没什么问题，到第二步为什么会跟hashcode左移16位的值进行抑或呢? 其实是将高位与低位进行与运算，减少碰撞机率。第三步取余运算，但在计算机运算中&肯定比%快，又因为h % n = h &（n - 1），所以最终将第二步得到的hash跟n-1进行与运算。n是table中的长度。

2、get方法，查询元素

查询get方法相对简单，只要明白hash算法后得到哈希桶的索引值，再对桶内的链表进行比较hash，key是否相等。下面是get方法中主要的代码

    final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//如果表为null或长度为0，或者经过hash算法后得到的哈希桶为null，则直接返回nullif ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//如果链表中的第一个节点元素相等则直接返回该Nodeif (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);//否则循环链表找到对应相等的元素，直到找到或下个节点为nulldo {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.put方法，增加

put方法是重点也是最复杂的操作。需要掌握在什么情况下要扩容（后面会讲一下是如何扩容的），满足什么条件下链表需要转成红黑树。下面是put方法中流程图

    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为null或length长度为0则扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//如果哈希桶为null，则创建节点放在该桶内if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//如果桶内第一个元素hash相等，key相等，则更新此节点if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//判断是否为红黑树，若是则调用红黑树的putTreeValelse if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//循环链表for (int binCount = 0; ; ++binCount) {//知道下个节点为null时if ((e = p.next) == null) {//增加节点p.next = newNode(hash, key, value, null);//如果桶内的节点是否大于8if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//这个方法里还会判断总节点数大于64则会转换为红黑树treeifyBin(tab, hash);break;}//如果找到相等的节点则退出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//只有找到相等节点是e不为nullif (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;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

4.扩容

扩容是Hashmap重点中的重点。也是最耗性能的操作。扩容的步骤是先对size扩大两倍，再对原先的节点重新经过hash算法得到新的索引值即复制到新的哈希桶里。最后得到新的table。其中jdk8对扩容进行了优化，提高了扩容的效率。但在平常运用中尽量要避免让hashmap进行扩容，若已知hashmap中的元素数量，则一开始初始化hashmap时指定容量，这样就减少了hashmap扩容次数。

    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) {//如果容量大于了最大容量时，直接返回旧的tableif (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//同时满足扩容两倍后小于最大容量和原先容量大于默认初始化的容量，对阈值增大两倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}
    else if (oldThr &gt; 0) // initial capacity was placed in thresholdnewCap = oldThr;else {               // zero initial threshold signifies using defaults//默认初始化容量和阈值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])new Node[newCap];table = newTab;if (oldTab != null) {//接下来对哈希桶的所有节点转移到新的哈希桶中for (int j = 0; j &lt; oldCap; ++j) {Node&lt;K,V&gt; e;//如果哈希桶为null，则不需任何操作if ((e = oldTab[j]) != null) {//将桶内的第一个节点赋值给e//将原哈希桶置为null，让gc回收oldTab[j] = null;if (e.next == null)//如果e的下个节点（即第二个节点）为null，则只需要将e进行转移到新的哈希桶中newTab[e.hash &amp; (newCap - 1)] = e;else if (e instanceof TreeNode)//如果哈希桶内的节点为红黑树，则交给TreeNode进行转移((TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap);else { // preserve order//将桶内的转移到新的哈希桶内//JDK1.8后将新的节点插在最后面//下面就是1.8后的优化//1.7是将哈希桶的所有元素进行hash算法后转移到新的哈希桶中//而1.8后，则是利用哈希桶长度在扩容前后的区别，将桶内元素分为原先索引值和新的索引值（即原先索引值+原先容量）。这里不懂为什么，可以看下一段图文讲解。//loHead记录低位链表的头部节点//loTail是低位链表临时变量，记录上个节点并且让next指向当前节点Node&lt;K,V&gt; loHead = null, loTail = null;//hiHead，hiTail与上面的一样，区别在于这个是高位链表Node&lt;K,V&gt; hiHead = null, hiTail = null;Node&lt;K,V&gt; next;do {//用于临时记录当前节点的next节点next = e.next;//e.hash &amp; oldCap==0表示扩容前后对当前节点的索引值没有发生改变if ((e.hash &amp; oldCap) == 0) {//loTail为null时，代表低位桶内无元素则记录头节点if (loTail == null)loHead = e;else//将上个节点next指向当前节点//即新的节点是插在链表的后面loTail.next = e;//将当前节点赋值给loTailloTail = e;}else {//跟上面的步骤是一样的。if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}//当next节点为null则退出循环} while ((e = next) != null);//如果低位链表记录不为null，则低位链表放到原index中if (loTail != null) {//将最后一个节点的next属性赋值为nullloTail.next = null;newTab[j] = loHead;}//如果高位链表记录不为null，则高位链表放到新index中if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104

1.8对扩容方法进行了优化，经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。 看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置
参考：resize方法详解
总结下通过分析代码后的一些心得

• 运算尽量用位运算代替，比较高效。例如hash算法中的取模运算，用&n-1去替代%n方法，元素起来更加高效
• 变量不用以后要赋值为null，让gc进行回收
• 当桶内节点大于8和节点总数大于64时才会转换为红黑树，前者在putValue中验证，后者treeifyBin方法中判断
• 扩容时，对容量进行扩大两倍后，原链表上的节点可能存放在原来的下表即low位。或者是存放在high位。high = low + oldCapacity

四、常见的面试题

1.HashMap底层是如何实现的？

首先底层数据结构是由数组+链表组成链表散列。HashMap先得到key的散列值，在通过扰动函数（减少碰撞次数）得到Hash值，接着通过hash & （n -1 ），n位table的长度，运算后得到数组的索引值。如果当前节点存在元素，则通过比较hash值和key值是否相等，相等则替换，不相等则通过拉链法查找元素，直到找到相等或者下个节点为null时。
1.8对扰动函数，扩容方法进行优化，并且增加了红黑树的数据结构。

2.HashMap 和 Hashtable 的区别

• 线程安全 HashMap是线程不安全的，而HashTable是线程安全的，每个人方法通过修饰synchronized来控制线程安全。
• 效率 HashMap比HashTable效率高，原因在于HashTable的方法通过synchronized修饰后，并发的效率会降低。
• 允不允许null HashMap运行只有一个key为null，可以有多个null的value。而HashTable不允许key，value为null。

3.HashMap的长度为什么是2的倍数

在HashMap的操作流程中，首先会对key进行hash算法得到一个索引值，这个索引值就是对应哈希桶数组的索引。为了得到这个索引值必须对扰动后的数跟数组长度进行取余运算。即 hash % n (n为hashmap的长度)，又因为&比%运算快。n如果为2的倍数，就可以将%转换为&，结果就是 hash & (n-1)。所以这就解释了为什么HashMap长度是2的倍数。

4.Jdk1.8中满足什么条件后将链表转化成红黑树？

很显然在putVal方法中是判断桶内的节点个数是否大于8，之后通过treeifyBin方法中判断长度是否大于最小红黑树容量64,小于则继续扩容，大于则转为红黑树。

//putVal方法判断桶内元素是是否大于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);
break;

//treeifyBin方法中判断长度是否大于最小红黑树容量64,小于则继续扩容，大于则转为红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

                                </div><link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-b6c3c6d139.css" rel="stylesheet"><div class="more-toolbox"><div class="left-toolbox"><ul class="toolbox-list"><li class="tool-item tool-active is-like "><a href="javascript:;"><svg class="icon" aria-hidden="true"><use xlink:href="#csdnc-thumbsup"></use></svg><span class="name">点赞</span><span class="count">3</span></a></li><li class="tool-item tool-active is-collection "><a href="javascript:;" data-report-click="{&quot;mod&quot;:&quot;popu_824&quot;}"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-csdnc-Collection-G"></use></svg><span class="name">收藏</span></a></li><li class="tool-item tool-active is-share"><a href="javascript:;"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-csdnc-fenxiang"></use></svg>分享</a></li><!--打赏开始--><!--打赏结束--><li class="tool-item tool-more"><a><svg t="1575545411852" class="icon" viewBox="0 0 1024 1024" version="1.1" xmlns="http://www.w3.org/2000/svg" p-id="5717" xmlns:xlink="http://www.w3.org/1999/xlink" width="200" height="200"><defs><style type="text/css"></style></defs><path d="M179.176 499.222m-113.245 0a113.245 113.245 0 1 0 226.49 0 113.245 113.245 0 1 0-226.49 0Z" p-id="5718"></path><path d="M509.684 499.222m-113.245 0a113.245 113.245 0 1 0 226.49 0 113.245 113.245 0 1 0-226.49 0Z" p-id="5719"></path><path d="M846.175 499.222m-113.245 0a113.245 113.245 0 1 0 226.49 0 113.245 113.245 0 1 0-226.49 0Z" p-id="5720"></path></svg></a><ul class="more-box"><li class="item"><a class="article-report">文章举报</a></li></ul></li></ul></div></div><div class="person-messagebox"><div class="left-message"><a href="https://blog.csdn.net/Yoga0301"><img src="https://profile.csdnimg.cn/4/8/C/3_yoga0301" class="avatar_pic" username="Yoga0301"><img src="https://g.csdnimg.cn/static/user-reg-year/2x/2.png" class="user-years"></a></div><div class="middle-message"><div class="title"><span class="tit"><a href="https://blog.csdn.net/Yoga0301" data-report-click="{&quot;mod&quot;:&quot;popu_379&quot;}" target="_blank">Yoga0301</a></span></div><div class="text"><span>发布了29 篇原创文章</span> · <span>获赞 14</span> · <span>访问量 3万+</span></div></div><div class="right-message"><a href="https://im.csdn.net/im/main.html?userName=Yoga0301" target="_blank" class="btn btn-sm btn-red-hollow bt-button personal-letter">私信</a><a class="btn btn-sm  bt-button personal-watch" data-report-click="{&quot;mod&quot;:&quot;popu_379&quot;}">关注</a></div></div></div>