为什么Java的语言设计者更倾向于对大多数基于散列的结构的开放寻址进行链接,除了像ThreadLocal这样的结构？

Question

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

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

Answer 1

我目前正在讨论的内存紧凑重新实现HashMap和HashSet使用,除其他外,Doug Lea的.这个特殊的问题还没有出现,但这是我对这个问题的第一个想法......

• 链式哈希表可以合理地降级.无论是更高的负载因素还是大量的哈希冲突,链接都不会像开放寻址那样快速降级.
• 正如你所说remove的那样......在开放式表格上并不是一个愉快的操作.作为一般规则,remove是对哈希表的最常见的操作,但有是为它的应用比较普遍,而表现不好就会被注意到.
• 我也怀疑 - 虽然我没有太多数据 - 实现一个"链接"的开放式地址哈希表会明显更加困难. LinkedHashMap是作为的子类编写的HashMap,并借用了大部分实现细节; 当条目是离散对象时,实现条目的链接列表会更容易一些 - 此时,您已经大部分进入链式实现.
• 规范中没有任何东西将它们与这种实现联系起来 - 它们总是可以随意使用它.
• JDK集合库...不会使内存消耗成为特别高的优先级.记忆很便宜.(你可能会也可能不同意这一点,但这绝对是一个明显的趋势.)