哈希表和单独的链接：你怎么知道从桶的列表中返回哪个值？

Question

我们正在我的数据结构和算法课程中学习哈希表，但我无法理解单独的链接。

我知道基本前提：每个桶都有一个指向包含键值对的节点的指针，每个节点都包含一个指向当前桶的迷你链表中的下一个（潜在）节点的指针。这主要用于处理碰撞。

现在，为了简单起见，假设哈希表有 5 个桶。假设我在创建了一个适当的哈希表实例后，在我的 main 中编写了以下代码行。

myHashTable["rick"] = "Rick Sanchez";
myHashTable["morty"] = "Morty Smith";

让我们想象一下我们使用的任何散列函数恰好为字符串键rick和morty. 为简单起见，假设桶索引为索引 0。

因此，在哈希表的索引 0 处，我们有两个节点，其值为Rick Sanchez和Morty Smith，无论我们决定将它们放入什么顺序（第一个指向第二个）。

当我想显示 的对应值时rick，Rick Sanchez根据我们这里的代码，散列函数将生成 0 的桶索引。

我如何决定需要返回哪个节点？我是否循环遍历节点，直到找到键匹配的节点rick？

Answer 1

要解决哈希表冲突，就是这样，将一个项目放入或获取其哈希值与另一个项目冲突的哈希表中，您最终将减少支持哈希表实现的数据结构的映射；这通常是一个链接列表。在发生冲突的情况下，这是哈希表结构的最坏情况，您最终将使用 O(n) 操作来获取链表中的正确项。就是这样，正如您所说的一个循环，它将搜索具有匹配 key 的项目。但是，如果您有一个像平衡树这样的数据结构需要搜索，则可能需要 O(logN) 时间，就像 Java8 实现一样。

正如JEP 180：使用平衡树处理频繁的 HashMap 冲突所说：

其主要思想是，一旦哈希桶中的项目数量超过某个阈值，该桶就会从使用条目链表切换到使用平衡树。在哈希冲突较高的情况下，这会将最坏情况下的性能从 O(n) 提高到 O(log n)。

这项技术已经在最新版本的 java.util.concurrent.ConcurrentHashMap 类中实现，该类也计划作为 JEP 155 的一部分包含在 JDK 8 中。该代码的部分内容将被重新用于实现相同的想法在 HashMap 和 LinkedHashMap 类中。

我强烈建议始终查看一些现有的实现。要说其中之一，你可以看看 Java 7 的实现。这将提高您的代码阅读技能，这几乎比编写代码更重要，或者说您这样做的频率更高。我知道这需要更多的努力，但会有回报。

例如，看一下 Java 7 中的 HashTable.get 方法：

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

在这里我们看到 if ((e.hash == hash) && e.key.equals(key)) 试图找到具有匹配键的正确项目。

这是完整的源代码：HashTable.java