哈希表和单独的链接：您如何知道从存储桶列表中返回哪个值？

Question

我们正在学习我的数据结构和算法类中的哈希表，并且我无法理解单独的链接。我知道基本前提：每个存储桶都有一个指向包含键值对的节点的指针，并且每个节点都包含一个指向当前存储桶小型链表中下一个（潜在）节点的指针。这主要用于处理碰撞。

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

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）操作结束链接列表中的正确项目。就是这样，按照您所说的循环，将使用匹配键搜索项目。但是，如果你有一个像平衡树一样的数据结构来进行搜索，它可能是O（logN）时间，就像Java8实现一样。

由于JEP 180: Handle Frequent HashMap Collisions with Balanced Trees说：

主要的想法是，一旦在一个散列桶 项目数量的增长超过一定的阈值，即斗将使用条目 链表均衡切换树。在发生冲突的情况下，这会改善从O（n）到 O（log n）的最差情况性能。

这种技术已经在 最新版本的java.util.concurrent.ConcurrentHashMap中的类，它是在JDK 8还预计 列入为JEP的部分尚未执行的代码155的部分将 重新 - 用于在HashMap和LinkedHashMap类中实现相同的想法。

我强烈建议总是看看现有的一些实现。要说一个，你可以看看Java 7的实现。这会提高你的代码阅读能力，这比编写代码更重要，或者你经常做更多的事情。我知道这是更多的努力，但它会得到回报。

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

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; 
} 

这里我们可以看到，如果（（e.hash ==哈希）& & e.key.equals（关键））正试图用匹配键找到正确的项目。

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