为什么Java的语言设计者更喜欢将链式开放寻址用于大多数基于哈希的结构，除了一些像ThreadLocal之外的？ [英] Why did the language designers of Java preferred chaining over open addressing for most hash based structures except for some like ThreadLocal?

问题描述

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

I know the difference between Open Addressing and Chaining for resolving hash collisions . Most of the basic hash based data structures like HashSet,HashMap in Java primarily use chaining technique. I read that ThreadLocal actually uses a probing scheme . So I want to understand why is open addressing not so much used in Java ? I mean it would be difficult to delete records using that scheme , in the sense that you have to mark those cells with some special handling . However it seems like memory requirement will be low for open addressing scheme.

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

Edit : I just want to understand the possible major reason/reasons for this design decision . I do not want finer details . Also I would like to know why ThreadLocal uses the lesser common technique of open addressing . I guess the two answers can be related together . So I prefer to ask in the same question itself.

推荐答案

我目前正在讨论 HashMap 和 HashSet ，其中包括Doug Lea。这个问题还没有出现，但这里是我对这个问题的第一个想法......

I am currently discussing memory-compact reimplementations of HashMap and HashSet with, among others, Doug Lea. This particular question hasn't come up, but here's my first thoughts on the question...

• 链接的散列表合理地降级。无论是更高的加载因子还是大量的散列冲突，链接的降级速度都不会像开放寻址一样快。
正如您所说， remove code>是...在开放式表格上不是一个愉快的操作。一般来说， remove 是哈希表中最不常见的操作，但是是 应用程序更为常见，性能不佳我也怀疑 - 尽管我没有太多的数据 - 实现链接的开放地址散列表会明显更困难。 LinkedHashMap 被写为 HashMap 的子类，并借用了大部分的实现细节。当条目是离散对象时，实现条目的链接列表比较容易 - 在这一点上，您已经是实现链式实现的大部分途径。

• 规范将它们与这个实现绑定在一起 - 它们总是随时可以随意使用它。


• JDK集合库不会使内存消耗成为特别高的优先级。内存很便宜。 （您可能会也可能不会同意这一点，但这绝对是一个明显的趋势。）

• Chained hash tables degrade reasonably gracefully. Whether it's higher load factors or lots of hash collisions, chaining doesn't degrade nearly as quickly as open addressing can.
• As you've said, remove is...not a pleasant operation on open-addressed tables. As a general rule, remove is the least common operation on hash tables, but there are applications for which it's more common, and bad performance would be noticed.
• I also suspect -- though I don't have much data -- that implementing a "linked" open-addressed hash table would be noticeably more difficult. LinkedHashMap is written as a subclass of HashMap, and borrows most of the implementation details; it's somewhat easier to implement the linked list of entries when the entries are discrete objects -- and at that point, you're already most of the way to a chained implementation.
• Nothing in the spec ties them to this implementation -- they're always free to mess around with it later.
• The JDK collections libraries...don't make memory consumption an especially high priority. Memory is cheap. (You may or may not agree with this, but it's definitely a noticeable trend.)

这篇关于为什么Java的语言设计者更喜欢将链式开放寻址用于大多数基于哈希的结构，除了一些像ThreadLocal之外的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！