图解HashMap和HashSet的内部工作机制

   <p>HashMap 和 HashSet 内部是如何工作的？散列函数（hashing function）是什么？</p>    <p>HashMap不仅是一个常用的数据结构，在面试中也是热门话题。</p>    <p>Q1. HashMap 如何存储数据？</p>    <p>A1. 以键／值对（key/value）形式存储。你可以使用键（key）来存、取值。</p>    <p>Q2. HashMap 查询时间的复杂度是怎样的？</p>    <p>A2. 是O( <strong>n</strong> ) = O(k * n)。如果 hashCode() 方法能向下面讨论的那样把数据分散到桶（bucket）中，那么平均是O(1)。</p>    <p>Q3. HashMap 内部是如何存储数据的？</p>    <p>A3. HashMap 使用后台数组（backing array）作为桶，并使用链表（linked list）存储键／值对。</p>    <p>桶的后台数组：如下所示</p>    <p><img src="https://simg.open-open.com/show/91f6aea5696bffde531e672478d0e723.png"></p>    <p>1）使用键（key）和值（value）将一个对象放入 map 中时，会隐式调用 <strong>hashCode()</strong> 方法，返回哈希值（hash code value），比如 123。两个不同的键能够返回一样的哈希值。良好的哈希算法（hashing algorithm）能够将数值分散开。在上面的例子中，我们假设 (“John”,01/01/1956) 的键和 (“Peter”, 01/01/1995) 的键返回相同的哈希值，都是  <strong>123</strong> 。</p>    <p><img src="https://simg.open-open.com/show/a821b1dcc0b12a92eb4f79cc280b6bde.png"></p>    <p>2）当返回一个 hashCode，例如是 123，初始的 HashMap 容量为 10，它如何知道存储到后台数组（backing array）的哪个索引（index）呢？HashMap 内部会调用 <strong>hash(int ) 和 indexFor(int h, int length)</strong> 方法。这被称为 <strong>哈希</strong> 函数（hashing function）。</p>    <p>简要解释下这个函数：</p>    <pre>  <code class="language-cpp">hashCode() % capacity    123 % 10 = 3  456 % 10 = 6</code></pre>    <p>这表示，“hashCode = 123”存储在备份数组的索引3上。</p>    <p>容量为 10 的情况下，你可能得到的数字在 <strong>0</strong> 到 <strong>9</strong> 之间。</p>    <p>一旦 HashMap 达到容量的 75%，也就是哈希因子(hash factor)默认值 0.75，后台数组（backing array）的容量就会加倍，发生 <strong>重散列</strong> （rehashing）为新的 20 的容量重新分配桶。</p>    <pre>  <code class="language-cpp">hashCode() % capacity    123 % 20 = 3  456 % 20 = 16</code></pre>    <p>上面重散列的取模方法有一个缺陷。如果 hashCode 是负数会怎样？负索引可不是你想要的。因此，一个改进的哈希公式会移出符号位，然后再用取模（即 %）运算符计算剩余部分。</p>    <pre>  <code class="language-cpp">(123  & 0x7FFFFFFF) % 20 = 3  (456 & 0x7FFFFFFF) % 20 = 16</code></pre>    <p>这确保你得到的索引值为正数。如果你查看 Java 8 的 HashMap 源码，它的实现使用以下方法：</p>    <p>a).通过只抽取重要的低位，来防止不良离散值（poorer hashes）。</p>    <pre>  <code class="language-cpp">static int hash(int h) {       // This function ensures that hashCodes that differ only by       // constant multiples at each bit position have a bounded       // number of collisions (approximately 8 at default load factor).       h ^= (h >>> 20) ^ (h >>> 12);       return h ^ (h >>> 7) ^ (h >>> 4);  }</code></pre>    <p>b).根据 <strong>哈希码</strong> （ <strong>hashCode</strong> ）和 <strong>容量</strong> （ <strong>capacity</strong> ），来决定索引（index）。</p>    <pre>  <code class="language-cpp">static int indexFor(int h, int length) {       return h & (length-1);  }</code></pre>    <p>实际的名称值对（name value pairs）作为一个键／值对存储在 LinkedList 中。</p>    <p>如上图所示，键／值对以链表形式存储。两个不同的键可以产生一样的 hashCode，例如123，并存储在同一个 bucket 中，理解这点至关重要。例如，上面例子中的 “John, 01/01/1956” 和 “Peter, 01/01/1995“ 。你如何只检索 “John, 01/01/1956” 呢？此时你的 key 所属类的 <strong>equals()</strong> 方法会被调用。它遍历 bucket 为 “123” 的 LinkedList 中的每个条目，使用 equals() 方法找到并检索出键为 “John, 01/01/1956” 的条目。这就是在你的类中实现 <strong>hashCode()</strong> 和 <strong>equals()</strong> 方法重要性的原因。如果你使用一个现有的包装类，如 Integer 或 String 作为键，它们已经实现了这两个方法。如果你使用自己写的类作为键，如 “John, 01/01/1956” 这样含有名字和出生日期属性的“MyKey”，你有责任正确地实现这些方法。</p>    <p>Q5. 为什么恰当地设置 HashMap 的初始容量（initial capacity）是最佳实践？</p>    <p>A5. 这样可以减少 <strong>重散列</strong> 的发生。</p>    <p>Q6. HashSet 内部如何存储数据？</p>    <p>A6. HashSet 内部使用 HashMap 。它将元素存储为键和值。（译者注：HashSet 把存储的值作为 key）</p>    <p>Q7. 为 Object 实现了一个糟糕的 hashcode() 会有什么影响？</p>    <p>A7. 不同的对象调用 hashCode() 方法应该返回不同的值。如果不同的对象返回相同的值，会导致更多的键／值对存储在同一个 bucket 中。这会 <strong>降低</strong> HashMap 和 HashSet 的 <strong>性能</strong> 。</p>    <p> </p>    <p>来自：http://www.importnew.com/21841.html</p>    <p> </p>