27

我知道解决哈希冲突的开放寻址和链接之间的区别。大多数基于哈希的基本数据结构HashSet，HashMap在 Java 中主要使用链接技术。我读到 ThreadLocal 实际上使用了探测方案。所以我想了解为什么在 Java 中没有那么多使用开放寻址？我的意思是很难使用该方案删除记录，因为您必须使用一些特殊处理来标记这些单元格。然而，开放寻址方案的内存要求似乎很低。

编辑：我只是想了解这个设计决策的可能主要原因/原因。我不想要更精细的细节。另外我想知道为什么 ThreadLocal 使用不太常见的开放寻址技术。我想这两个答案可以联系在一起。所以我更喜欢问同一个问题本身。

4

1 回答 1

20

我目前正在与 Doug Lea 等人讨论内存紧凑的重新HashMap实现HashSet。这个特殊的问题还没有出现，但这是我对这个问题的第一个想法......

  • 链式哈希表可以合理地优雅地降级。无论是更高的负载因子还是大量的哈希冲突，链接都不会像开放寻址那样迅速退化。
  • 正如您所说，remove在开放地址表上不是......不是一个愉快的操作。作为一般规则，remove它是哈希表上最不常见的操作，但有些应用程序更常见，并且会注意到性能不佳。
  • 我还怀疑——尽管我没有太多数据——实现一个“链接”的开放地址哈希表会明显更加困难。 LinkedHashMap写成 的子类HashMap，并借用了大部分实现细节；当条目是离散对象时，实现条目的链接列表会更容易一些——此时，您已经完成了链式实现的大部分工作。
  • 规范中没有任何东西将它们与这个实现联系起来——它们以后总是可以随意摆弄它。
  • JDK 集合库...不要将内存消耗作为特别高的优先级。内存很便宜。（你可能同意也可能不同意，但这绝对是一个明显的趋势。）
于 2012-08-18T16:00:03.577 回答