迹忆客 专注技术分享

Java 中的 HashMap 遵循散列原则。 它是一种数据结构，允许我们存储对象并在常数时间 O(1) 中检索它，前提是我们知道键。 在散列中，散列函数用于链接 HashMap 中的键和值。 对象通过调用 HashMap 的 put(key, value) 方法存储，通过调用 get(key) 方法检索。 当我们调用 put 方法时，会调用 key 对象的 hashcode() 方法，让 map 的 hash 函数找到一个 bucket 位置存放 value 对象，其实就是内部数组的索引，称为 表。

HashMap 在内部以包含键和值对象的 Map.Entry 对象的形式存储映射。

当我们想要检索对象时，调用 get() 方法并再次传递关键对象。 这一次，键对象再次生成相同的哈希码（它必须这样做才能检索对象，这就是 HashMap 键不可变的原因，例如 String），我们最终位于相同的存储桶位置。 如果只有一个对象，则返回它，这就是之前存储的值对象。

由于 HashMap 内部数组是固定大小的，如果一直存储对象，在某个时间点hash函数会为两个不同的key返回相同的bucket位置，这在 HashMap 中称为碰撞。 在这种情况下，将在该存储桶位置形成一个链表，并将一个新条目存储为下一个节点。

如果我们尝试从此链表中检索对象，则需要额外检查以搜索正确的值，这是由 equals() 方法完成的。 由于每个节点都包含一个条目，HashMap 使用 equals() 不断将条目的键对象与传递的键进行比较，当它返回 true 时，Map 返回相应的值。

由于搜索内联列表是一个复杂度为 O(n) 的操作，因此在最坏的情况下，哈希冲突会将映射减少为链表。 这个问题在 Java 8 中通过将链表替换为树来在 O(logN) 时间内搜索来解决。 顺便说一句，如果大家知道如何在 Eclipse 中附加 JDK 的源代码，则可以通过在 Eclipse IDE 中查看 HashMap.java 的代码来轻松验证 HashMap 的工作原理。

HashMap 在 Java 中是如何工作的？

HashMap 在 Java 中是如何工作的，或者有时 get 方法在 HashMap 中是如何工作的，这是当今 Java 面试中非常常见的问题。 几乎用过Java的人都知道 HashMap，HashMap 在什么地方用，Hashtable 和 HashMap 的区别，那为什么这个面试题会变得这么特别呢？

它已经成为几乎所有高级或中高级 Java 面试中非常流行的 Java 面试问题。

ConcurrentHashMap 和其他并发集合的引入也让这些问题成为深入研究更高级特性的起点。 让我们开始旅程吧。

问题以一个简单的陈述开始：

1.你以前用过HashMap或者什么是HashMap？ 你为什么使用它？

几乎每个人的回答都是肯定的，然后受访者一直在谈论关于 HashMap 的常见事实，比如 HashMap 接受 null 而 Hashtable 不接受，HashMap 不同步，HashMap 很快，等等基础知识，比如它存储键和值对， 等等

这表明此人已经使用过 HashMap 并且非常熟悉它提供的功能，但是面试从这里开始急转弯，下一组后续问题将更详细地介绍 Java 中 HashMap 所涉及的基础知识。 面试官反击这样的问题：

2.你知道HashMap在Java中是怎么工作的或者HashMap的get()方法在Java中是如何工作的吗

然后你会得到这样的答案，我不介意它的标准 Java API，你最好看看 Java 源代码或 Open JDK 上的代码； 我随时可以在谷歌上找到它，等等。但有些面试者肯定会回答这个问题，并会说 HashMap 的工作原理是散列，我们有 put(key, value) 和 get(key) 方法来存储和检索对象 哈希表。

当我们将 Key 和 Value 对象传递给 Java HashMap 上的 put() 方法时，HashMap 实现调用 Key 对象上的 hashCode 方法并将返回的 hashcode 应用到它自己的哈希函数中以找到存储 Entry 对象的存储桶位置，需要提及的重点是 Java 中的 HashMap 将键和值对象都存储为 Map。存储桶中的条目对于理解检索逻辑至关重要。

如果人们没有意识到这一点并说它只将值存储在桶中，他们将无法解释存储在 Java HashMap 中的任何对象的检索逻辑。 这个答案是非常可以接受的，并且确实有道理，因为受访者对散列的工作原理以及 HashMap 在 Java 中的工作原理有一定的了解。

但这只是故事的开始，当将候选人置于 Java 开发人员每天面临的场景中时，困惑就会增加。 下一个问题可能是关于 Java HashMap 中的碰撞检测和碰撞解决的，例如：

3. 如果两个不同的对象具有相同的哈希码会怎样？

现在从这里开始真正的混乱开始了，有时候选人会说因为 hashcode 是相等的，所以两个对象是相等的并且 HashMap 会抛出异常或者不再存储它们等等，那么你可能想提醒他们关于 equals() 和 hashCode() 约定 Java 中的两个不相等的对象可以具有相同的哈希码。

有些人会在这一点上放弃，很少有人会继续说“因为 hashcode 是相同的，桶的位置将是相同的，并且在 HashMap 中会发生冲突因为 HashMap 使用 LinkedList 存储对象，这个条目（Map.Entry 的对象包括键和 value ) 将存储在 LinkedList 中。很好，这个答案很有意义，虽然有许多可用的冲突解决方法，如线性探测和链接，这是最简单的，Java 中的 HashMap 确实遵循了这一点。但故事并没有到此结束，面试官 问

4. 如果两个 Key 具有相同的哈希码，您将如何检索 Value 对象？

HashMap 在Java内部是如何工作的面试者会说我们会调用 get() 方法，然后 HashMap 使用Key Object的hashcode来找出bucket位置并检索Value对象但是你需要提醒他有两个Value对象存储在同一个 bucket，所以他们会说遍历LinkedList直到我们找到值对象，然后你问你如何识别值对象，因为你没有值对象可以比较直到他们知道 HashMap 将Key和Value都存储在 LinkedList 节点或 作为 Map.Entry 他们将无法解决此问题，并且会尝试失败。

但是那些记住这个关键信息的人会说，找到桶位置后，我们将调用 keys.equals() 方法在 LinkedList 中识别一个正确的节点，并在 Java HashMap 中返回该键的关联值对象。 完美这是正确答案。

在许多情况下，受访者在这个阶段失败是因为他们混淆了 hashCode() 和 equals() 或 Java HashMap 中的键和值对象，这很明显，因为他们在处理之前所有问题中的 hashcode() 和 equals() 只有在从 Java 中的 HashMap 检索值对象的情况下才会出现。

一些优秀的开发人员在这里指出，使用具有适当 equals() 和 hashcode() 实现的不可变最终对象将充当完美的 Java HashMap 键，并通过减少冲突来提高 Java HashMap 的性能。

不变性还允许缓存不同键的哈希码，这使得整个检索过程非常快，并建议 String 和各种包装类，例如 Java HashMap 中的整数非常好的键。

现在，如果我们通过了整个 Java HashMap 面试，则会对这个非常有趣的问题感到惊讶“如果 HashMap 的大小超过由负载因子定义的给定阈值，Java 中的 HashMap 会发生什么？”。 在我们了解 HashMap 的确切工作原理之前，将无法回答这个问题。 如果 Map 的大小超过由负载因子定义的给定阈值，例如 如果加载因子为 0.75，它将在填充 75% 后重新调整 Map 大小。

与 ArrayList 等其他集合类类似，Java HashMap 通过创建一个大小是 HashMap 先前大小两倍的新桶数组来重新调整自身大小，然后开始将每个旧元素放入新的桶数组中。 此过程称为重新散列，因为它还应用散列函数来查找新的存储桶位置。

如果我们设法在 Java 中的 HashMap 上回答这个问题，则将收到“你是否发现 Java 中 HashMap 的大小调整有任何问题”，我们可能无法选择上下文，然后他会尝试给出提示 关于多个线程访问 Java HashMap 并可能在 Java 中寻找 HashMap 上的竞争条件。

所以答案是肯定的，如果两个线程同时发现现在 HashMap 需要调整大小并且它们都尝试调整大小，那么在 Java 中调整 HashMap 大小时存在潜在的竞争条件。 在 Java 中调整 HashMap 大小的过程中，存储在链表中的桶中的元素在迁移到新桶的过程中顺序颠倒，因为 Java HashMap 不会在尾部追加新元素，而是在头部追加新元素以避免尾部穿越。

如果发生竞争情况，那么将陷入无限循环。 尽管这一点，你可能会向面试官争辩说，到底是什么让你想到在多线程环境中使用 HashMap :)

一些更多的 Hashtable 和 HashMap 问题

下面是一些读者提供的关于 Java 中 HashMap 的问题。

5. 为什么 String、Integer 和其他包装类被认为是好的键？

String、Integer 和其他包装类是 HashMap 键的自然候选，而 String 也是最常用的键，因为 String 是不可变的和 Final，并且覆盖了 equals 和 hashcode() 方法。 其他包装类也有类似的属性。

不变性是必需的，以防止用于计算 hashCode() 的字段发生更改，因为如果键对象在插入和检索期间返回不同的 hashCode，则将无法从 HashMap 中获取对象。

不变性是最好的，因为它提供了其他优点以及线程安全性，如果我们可以通过仅将某些字段设置为 final 来保持 hashCode 相同，那么我们也可以这样做。

由于在从 HashMap 中检索值对象期间使用了 equals() 和 hashCode() 方法，因此关键对象正确地覆盖这些方法并遵循联系非常重要。 如果一个不相等的对象返回不同的哈希码，那么发生冲突的机会就会减少，从而提高 HashMap 的性能。

6. 我们可以使用任何自定义对象作为 HashMap 中的键吗？

这是前面问题的延伸。 当然，我们可以使用任何对象作为 Java HashMap 中的键，前提是它遵循 equals 和 hashCode 协定，并且一旦将对象插入 Map，其 hashCode 不应发生变化。 如果自定义对象是不可变的，那么这将已经被处理好，因为一旦创建就无法更改它。

7. 我们可以使用 ConcurrentHashMap 代替 Hashtable 吗？

这是另一个由于 ConcurrentHashMap 越来越受欢迎而变得流行的问题。 因为我们知道 Hashtable 是同步的，ConcurrentHashMap 通过只锁定由并发级别决定的映射的一部分来提供更好的并发性。 ConcurrentHashMap 肯定是作为 Hashtable 引入的，可以代替它使用，但是 Hashtable 提供了比 ConcurrentHashMap 更强的线程安全性。 有关更多详细信息，请参阅我们的的文章 Hashtable 和 ConcurrentHashMap 之间的区别。

就个人而言，我喜欢这个问题，因为它的深度和它间接触及的概念数量，如果你看一下面试中提出的问题，这个 HashMap 问题已经验证

• 哈希的概念
• HashMap 中的冲突解决
• equals()和hashCode()的使用以及它们在HashMap中的重要性？
• 不可变对象的好处？
• Java 中 HashMap 的竞争条件
• 调整 Java HashMap 的大小

这里只是总结一下对上述问题有意义的答案

8. HashMap 在 Java 中的工作原理

HashMap 的工作原理是哈希，我们有 put() 和 get() 方法来从 HashMap 中存储和检索对象。当我们将键和值都传递给 put() 方法存储在 HashMap 上时，它使用键对象 hashcode() 方法来计算哈希码和它们通过在该哈希码上应用哈希来识别存储值对象的存储桶位置。

在检索它时使用键对象 equals 方法找出正确的键值对并返回与该键关联的值对象。 HashMap 使用链表以防发生冲突，对象将存储在链表的下一个节点中。 此外，HashMap 以 Map.Entry 对象的形式在链表的每个节点中存储键和值元组。

9.如果两个不同的HashMap key对象有相同的hashcode会怎样？

它们将存储在同一个桶中，但没有链表的下一个节点。 而 keys equals() 方法将用于在 HashMap 中识别正确的键值对。

10. HashMap中如何处理null key？ 由于 equals() 和 hashCode() 用于存储和检索值，它在 null 键的情况下如何工作？

空键在 HashMap 中被特殊处理，有两个单独的方法用于 putForNullKey(V value) 和 getForNullKey()。 后来是 get() 的卸载版本，用于查找空键。 空键总是映射到索引 0。

为了在两个最常用的操作（get 和 put）中的性能，这个 null case 被分成单独的方法，但在其他情况下与条件合并。 简而言之，HashMap 中的空键不使用 equals() 和 hashcode() 方法。

这是从 HashMap 中检索空值的方式

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

在使用方面，Java HashMap 的用途非常广泛。

JDK 1.7 和 JDK 1.8 中的 HashMap 更改

从 JDK 1.7 开始，对 HashMap 和 ArrayList 进行了一些性能改进，减少了内存消耗。 由于这个空 Map 被延迟初始化，并且会消耗更少的内存。 早些时候，当你像 new HashMap() 这样创建 HashMap 时，它会自动创建一个默认长度的数组，例如 16.

经过研究，Java 团队发现这些 Map 中的大多数都是临时的，不会使用那么多元素，最终只会浪费内存。 此外，从 JDK 1.8 开始，HashMap 引入了一种改进的策略来处理高冲突率。

由于哈希函数很差，例如 它总是返回同一个桶的位置，可以将 HashMap 转换为链表，例如将 get() 方法转换为在 O(n) 而不是 O(1) 中执行并且有人可以利用这个事实，Java 现在 一旦超过某个阈值，就在内部将链表替换为二进制 true。 即使在散列函数未正确分配密钥的最坏情况下，这也能确保性能或顺序 O(log(n))。