转载

JDK源码分析-HashMap(2)

前文「 JDK源码分析-HashMap(1) 」分析了 HashMap 的内部结构和主要方法的实现原理。但是,面试中通常还会问到很多其他的问题,本文简要分析下常见的一些问题。

这里再贴一下 HashMap 内部的结构图(JDK 1.8):

JDK源码分析-HashMap(2)

FAQ:

Q1: HashMap 是否线程安全?为什么?

首先 HashMap 是线程不安全的。这一点很多人应该都了解,HashMap 源码中也有说明。但是 为什么说不安全?体现在哪里呢?下面通过两个例子简要进行分析(可能不够全面,仅做参考)。

case 1

线程 T1 执行 put / remove 等结构性修改( structural modification )的操作;线程 T2 执行遍历操作,这种情况下会抛出 ConcurrentModificationException. 

示例代码(以 put 为例):

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">static</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">test</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">()</span> </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Map&lt;Integer, Integer&gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span> = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> HashMap&lt;&gt;();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> </span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Thread t1 = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> Thread(() -&gt; {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> i = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>; i &lt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">5000</span>; i++) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span>.put(i, i);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> });</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Thread t2 = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> Thread(() -&gt; {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (Map.Entry&lt;Integer, Integer&gt; entry : <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span>.entrySet()) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> System.out.println(entry);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> });</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> t1.start();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> t2.start();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 执行结果:</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 抛出 java.util.ConcurrentModificationException</span>

原因在这里:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (modCount != expectedModCount)</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">throw</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> ConcurrentModificationException();</span>

HashMap 的迭代器和 集合视图中 ,都会对该值进行比较。目的是判断是否有其他线程正在对该 HashMap 进行结构性修改,若有则抛会出异常。

PS: 细心阅读 HashMap 源码的话可以发现,结构性修改的方法中都会有如下一行代码:

++modCount;

该值就是用来记录结构性修改的次数

case 2:

线程 T1 和 T2 同时执行 put / remove 等结构性修改( structural modification )的操作。以 put 方法为例分析,会发生 元素覆盖。

示例代码:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">private</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">static</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">void</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">test</span><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">()</span> throws InterruptedException </span>{</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Map&lt;Integer, Integer&gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span> = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> HashMap&lt;&gt;();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Thread t1 = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> Thread(() -&gt; {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> i = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>; i &lt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">5000</span>; i++) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span>.put(i, i);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> });</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> Thread t2 = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">new</span> Thread(() -&gt; {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> i = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">5000</span>; i &lt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">10000</span>; i++) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span>.put(i, i);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> });</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> t1.start();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> t2.start();</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> </span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> TimeUnit.SECONDS.sleep(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">20</span>);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> System.out.println(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span>);</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> System.out.println(<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">&quot;size: &quot;</span> + <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">map</span>.size());</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// 输出结果:</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// {8192=8192, 8193=8193, 8194=8194, 8195=8195, ...</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// size: 9666</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">// PS: 这是某一次的结果,多次测试的具体结果可能不同,但基本都没有 size=10000 的情况。</span>

这里问题出在 put 方法上,通过前文 分析 HashMap 中  put 方法的内部实现原理可以找出原因,这里不再赘述。

这里再说一句,HashMap 的设计就是为了单线程下的高效率,了解线程不安全是为了加深对它的理解,知道在哪些情况不适合使用,若有线程安全的需求,可以考虑使用 ConcurrentHashMap。

Q2: 链表和红黑树的转换阈值为什么是 8 和 6 ?

首先分析下为什么会有链表和红黑树。理想情况下,HashMap 中每个 bin 所在位置只有一个节点,这样查询效率最高,为 O(1) 。而拉出一个链表、或者把链表再转为红黑树,是在散列冲突比较严重时的一种应对措施,目的是为了让 HashMap 在极端情况下仍然能够保持较高的效率。

至于为什么是 8,HashMap 的部分 Implementation notes 如下:

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">/* Because TreeNodes are about twice the size of regular nodes, we</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * use them&gt;<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * (see TREEIFY_THRESHOLD). And when they become too small (due to</span></span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * removal or resizing) they are converted back to plain bins. In</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * usages with well-distributed user hashCodes, tree bins are</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * rarely used. Ideally, under random hashCodes, the frequency of</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * nodes in bins follows a Poisson distribution</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * (http://en.wikipedia.org/wiki/Poisson_distribution) with a</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * parameter of about 0.5&gt;<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * threshold of 0.75, although with a large variance because of</span></span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * resizing granularity. Ignoring variance, the expected</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * factorial(k)). The first values are:</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> *</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 0: 0.60653066</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 1: 0.30326533</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 2: 0.07581633</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 3: 0.01263606</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 4: 0.00157952</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 5: 0.00015795</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 6: 0.00001316</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 7: 0.00000094</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * 8: 0.00000006</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * more: less than 1 in ten million</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> */</span>

由于 TreeNode 的大小是普通节点(Node)的两倍,因此只有当 bin 中包含足够多(即树化的阈值 TREEIFY_THRESHOLD)的节点时才会转为 TreeNode;而当 bin 中节点减少时(删除节点或扩容),又会把红黑树再转为链表。

hashCode 均匀分布时,TreeNode 用到的机会很小。理想情况下,在随机分布的 hashCode 下,bin 中节点的分布遵循泊松分布,并列出了几个数据,可以看到一个 bin 中链表长度达到 8 的概率(0.00000006)不足千万分之一,因此将转换的阈值设为 8.

两个转换阈值及其说明如下:

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">/**</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * The bin count threshold for using a tree rather than list for a</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * bin. Bins are converted to trees when adding an element to a</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * bin with at least this many nodes. The value must be greater</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * than 2 and should be at least 8 to mesh with assumptions in</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * tree removal about conversion back to plain bins upon</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * shrinkage.</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> */</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">static</span> final <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> TREEIFY_THRESHOLD = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">8</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><br style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;" /></span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">/**</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * The bin count threshold for untreeifying a (split) bin during a</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * resize operation. Should be less than TREEIFY_THRESHOLD, and at</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * most 6 to mesh with shrinkage detection under removal.</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> */</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">static</span> final <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> UNTREEIFY_THRESHOLD = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">6</span>;</span>

至于将红黑树转为链表的阈值为 6,网上有说法是为了避免频繁转换。比如,若红黑树转为链表的阈值也是 8,如果一个 HashMap 不停地进行插入和删除元素,链表的个数一直在 8 左右,这种情况会频繁地进行树和链表的相互转换,效率很低。

这样解释似乎也有些道理,各位可以去探索。

Q3: 为什么负载因子是 0.75?

JDK 1.7 中的相关描述:

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;">/* As a general rule, the default load factor (.75) offers a good tradeoff</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * between time and space costs. Higher values decrease the space overhead</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * but increase the lookup cost (reflected in most of the operations of the</span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> * &lt;tt&gt;HashMap&lt;/tt&gt; class, including &lt;tt&gt;get&lt;/tt&gt; and &lt;tt&gt;put&lt;/tt&gt;). </span>

<span style="padding:0px;margin:0px;max-width:1000%;font-style:italic;box-sizing:border-box !important;overflow-wrap:break-word !important;"> */</span>

下面文章也对此做了分析:

HashMap的loadFactor为什么是0.75?

https://www.jianshu.com/p/64f6de3ffcc1

也许这个问题没必要那么深究,简单来讲,其实就是时间和空间的 tradeoff.

Q4: 为什么容量是 2 的次幂?

位运算 n & (length - 1) 和取余运算 n % length 效果是一样的。但是在 计算机中,位运算的效率却远高于取余运算。因此,这样做是为了提高运算效率。

Q5: 一般用什么类型的元素作为 Key?为什么?

一般用 String、Integer 等,它们是不可变的(Immutable),作为不可变类天生是线程安全的。 而且重写了 hashCode 方法和 equals 方法。

Q6: 衡量 hash 算法的好坏?String 类的 hashCode 实现?

hash 方法的设计可以有很多。虽然散列值越均匀越好, 但 HashMap 首要目的是追求快,因此 hash 算法的设计要尽可能地快。 String 类的 hashCode 方法如下:

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"><span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">public</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">hashCode</span>()</span> {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> h = hash;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">if</span> (h == <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span> && <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">value</span>.length &gt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">char</span> val[] = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">value</span>;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">for</span> (<span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">int</span> i = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">0</span>; i &lt; <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">value</span>.length; i++) {</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> h = <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">31</span> * h + val[i];</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> hash = h;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> }</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;"> <span style="padding:0px;margin:0px;max-width:1000%;box-sizing:border-box !important;overflow-wrap:break-word !important;">return</span> h;</span>

<span style="margin: 0px; padding: 0px; max-width: 1000%; box-sizing: border-box !important; overflow-wrap: break-word !important;">}</span>

PS: 上述问题是本人从网上搜索后整理和思考的结果,仅做参考,并不一定完全准确(要持有怀疑态度)。有关 HashMap 的问题可能还有很多,这里不再一一列举。

参考链接:

https://www.jianshu.com/p/7af5bb1b57e2

相关阅读:

JDK源码分析-HashMap(1)

Stay hungry, stay foolish.

JDK源码分析-HashMap(2)

原文  https://juejin.im/post/5d54300151882551d172f22d
正文到此结束
Loading...