为什么Java的语言设计师在大多数基于哈希的结构中更喜欢链接而不是开放寻址，除了像ThreadLocal这样的结构？[已关闭]

java hash thread-local

2022-09-01 16:11:44

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

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

答案 1

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

链接的哈希表会合理优雅地降级。无论是更高的负载因子还是大量的哈希冲突，链接都不会像开放寻址那样快速降级。
正如你所说，是...在开放式寻址表上不是一个愉快的操作。作为一般规则，它是对哈希表最不常见的操作，但是对于某些应用程序来说，它更常见，并且会注意到性能不佳。removeremove
我还怀疑 - 尽管我没有太多数据 - 实现“链接”的开放寻址哈希表将明显更加困难。编写为的子类，并借用了大部分实现细节;当条目是离散对象时，实现条目的链接列表会更容易一些 - 在这一点上，您已经掌握了大部分链接实现的方法。LinkedHashMapHashMap
规范中没有任何内容将它们与此实现联系起来 - 它们以后总是可以自由地搞砸它。
JDK馆藏库...不要将内存消耗作为特别高的优先级。内存很便宜。（你可能同意也可能不同意这一点，但这绝对是一个明显的趋势。

答案 2