单独链接的哈希表

是否有一个java Map接口的实现，它利用单独的链接作为冲突解决方案。通过阅读HashMap和HashTable的javadocs，我得出结论：实现所做的工作基本上取代了这个值，并且基本上不采用任何冲突解决方案？单独链接的哈希表

2011-11-23 LordDoskias

可能的重复http://stackoverflow.com/questions/2756479/java-hashtable-with-seperate-chaining-collision-resolution – Manish

你弄错了：它使用每个存储桶的条目的链接列表。

当在地图中放置一个值时，地图首先通过调用hashCode对该键进行转换，然后转换该散列码，使其位于0和桶数之间。如果存储桶是空的，则存储在该存储桶中。如果不是，则将该存储桶中的每个密钥与新密钥equals进行比较。如果一个是相等的，那么它的值将被新值所取代。否则，带有新密钥的新条目将被添加到存储桶的条目列表中。

如果要为给定密钥存储多个值，请使用Map<Key, List<Value>>或使用Guava的MultiMap。

来源

2011-11-23 11:46:42

看看源代码 - 是的，它使用链接列表。但值得注意的是，有一个TREEIFY_THRESHOLD，如果超过了桶，那么链表将被转换为红黑树。 – manyways

它确实有冲突解决方案，但这是因为两个不同的密钥可能会在哈希后在同一个桶中合理结束。

如果要为单个密钥存储多个值，则始终可以使用HashMap<KeyType, ArrayList<ValueType>>并在必要时执行一些内务操作以初始化阵列。

来源

2011-11-23 11:45:08 Vlad

检查出番石榴的ListMultimap。它实现了一个'Map >'：http://docs.guava-libraries.googlecode.com/git-history/v10.0.1/javadoc/com/google/common/collect/ListMultimap.html –

这是一个很好的观点，谢谢。我会记住我的下一个项目。 – Vlad

单独链接的哈希表

回答

相关问题