面试：HashMap 夺命二十一问！

<div id="js_content">
<p style="text-align: center">点击上方蓝色“Java编程指南”，选择“设为星标”<strong></strong></p>
<p style="text-align: center">回复“Java学习”获取独家整理的学习资料！</p>
<p style="text-align: center"><img src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-fe16b6c25689b2784ec98f84aa41a89e" width="100%"></p>
<p style="text-align: left">作者 | 菜鸟小于 </p>
<p style="text-align: left">来源 | cnblogs.com/Young111/p/11519952.html</p>
<h4><strong>1：HashMap 的数据结构？</strong></h4>
<p>A：哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。当链表长度超过 8 时，链表转换为红黑树。</p>
<pre class="blockcode"><code class="language-php">transient Node<K,V>\[\] table;
</code></pre>
<h4><strong>2：HashMap 的工作原理？</strong></h4>
<p>HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry接口）实现，HashMap 通过 put & get 方法存储和获取。</p>
<p>存储对象时，将 K/V 键值传给 put() 方法：</p>
<p>①、调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；</p>
<p>②、调整数组大小（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）；</p>
<p>③、i.如果 K 的 hash 值在 HashMap 中不存在，则执行插入，若存在，则发生碰撞；</p>
<p>ii.如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 true，则更新键值对；</p>
<p>iii. 如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 false，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式）。</p>
<p>（JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法）（注意：当碰撞导致链表大于 TREEIFY_THRESHOLD = 8 时，就把链表转换成红黑树）<br></p>
<p>获取对象时，将 K 传给 get() 方法：①、调用 hash(K) 方法（计算 K 的 hash 值）从而获取该键值所在链表的数组下标；②、顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。<br></p>
<p>hashCode 是定位的，存储位置；equals是定性的，比较两者是否相等。</p>
<h4><strong>3.当两个对象的 hashCode 相同会发生什么？</strong></h4>
<p><a href="http://mp.weixin.qq.com/s?__biz=MzI2MTIzMzY3Mw%3D%3D&chksm=ea5cdb7ddd2b526bcb46214f83f80859c8603497323a3cf933e511b6f018af666dd74b0e584d&idx=4&mid=2247489051&scene=21&sn=651c4a067c2f1d59151f484475144c20#wechat_redirect">因为 hashCode 相同，不一定就是相等的（equals方法比较），所以两个对象所在数组的下标相同，"碰撞"就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中。为什么要重写 hashcode 和 equals 方法？推荐看下。</a></p>
<h4><strong>4.你知道 hash 的实现吗？为什么要这样实现？</strong></h4>
<p>JDK 1.8 中，是通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。</p>
<h4><strong>5.为什么要用异或运算符？</strong></h4>
<p>保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。</p>
<h4><strong>6.HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？</strong></h4>
<p><a href="http://mp.weixin.qq.com/s?__biz=MzI2MTIzMzY3Mw%3D%3D&chksm=ea5cdaa0dd2b53b67ac2b9ba12935e13cb59250180fa302bd61629968e24f8853f208790fe80&idx=4&mid=2247489478&scene=21&sn=ad7321cd1948f0c8eaf955aaaa7a2046#wechat_redirect">①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；</a></p>
<p><a href="http://mp.weixin.qq.com/s?__biz=MzI2MTIzMzY3Mw%3D%3D&chksm=ea5cdaa0dd2b53b67ac2b9ba12935e13cb59250180fa302bd61629968e24f8853f208790fe80&idx=4&mid=2247489478&scene=21&sn=ad7321cd1948f0c8eaf955aaaa7a2046#wechat_redirect">②、loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；</a></p>
<p><a href="http://mp.weixin.qq.com/s?__biz=MzI2MTIzMzY3Mw%3D%3D&chksm=ea5cdaa0dd2b53b67ac2b9ba12935e13cb59250180fa302bd61629968e24f8853f208790fe80&idx=4&mid=2247489478&scene=21&sn&#

面试：HashMap 夺命二十一问！

浏览过的版块