我知道的哈希结构 - HashTable、HashSet 和 HashMap。
它们是否都使用桶结构 - 即当两个哈希码完全相同时 ，一个元素不会覆盖另一个元素，而是将它们放置在与该哈希码关联的同一个桶中？
问问题
2722 次
7 回答
8
在 Sun 当前的 Java 库实现中，以及在使用探测结构IdentityHashMap的内部实现中。ThreadLocal
在 Java 中探测哈希表的一般问题是，hashCode并且equals可能相对昂贵。因此，您要缓存哈希值。你不能有一个混合引用和原语的数组，所以你需要做一些相对复杂的事情。另一方面，如果您==用于检查匹配项，那么您可以检查许多引用而不会出现性能问题。
IIRC，Azul 有一个快速并发的二次探测哈希图。
于 2009-11-24T17:53:35.203 回答
6
每个桶都使用一个链表来处理哈希冲突。请注意，javaHashSet实际上是由HashMap底层实现的（所有键都映射到所有HashSets 中的相同单例值），因此使用相同的桶结构。
如果添加了一个元素，则在将其添加到末尾之前，将针对链表中的所有项目（通过）检查其相等性。.equals因此，哈希冲突特别糟糕，因为随着链表变大，这可能是一项昂贵的检查。
于 2009-11-24T17:48:40.910 回答
5
我相信 Java 哈希结构在执行哈希时都使用一种链接形式来处理 colisions - 这会将具有相同哈希的项目放入列表中。
我不相信 Java 将开放寻址用于其基于哈希的数据结构（开放寻址根据重试序列重新计算哈希，直到它在表中找到一个开放的狭缝）
于 2009-11-24T17:44:32.337 回答
4
不——开放寻址是表示哈希表的另一种方法，其中对象直接存储在表中，而不是驻留在链表中。给定索引只能存储一个对象，因此解决冲突更加复杂。
当添加另一个对象已经存在于同一索引中的对象时，将使用探测序列来确定存储新对象的新索引。移除对象也比较复杂，因为如果你移除一个对象，你需要留下一个标记，上面写着“这里曾经有一个对象”；有关更多详细信息，请参阅维基百科。
当存储的对象很小并且很少被删除时，最好使用开放寻址。开放寻址提高了缓存性能，因为您不需要通过额外的间接级别来遍历链表。
您提到的类 -- HashTable、HashSet和HashMap不使用开放寻址，但您可以轻松创建实现开放寻址并提供与这些类相同的 API 的新类。
于 2009-11-24T17:54:25.937 回答
2
api 定义了行为，如何管理哈希冲突的内部不会影响 API 的保证……糟糕的哈希值计算对性能的影响是另一回事。让我们将所有内容哈希为 42，看看它的行为如何。
于 2009-11-24T17:52:11.493 回答
0
Maps 和 Sets 是确定 HashSet 或 HashMap 行为的接口。HashSet 是一个集合，因此它的行为类似于集合（即不允许重复）。HashMap 的作用类似于 Map - 它不会用类似的哈希码覆盖键，但如果再次使用相同的确切键，它会覆盖键。无论内部支持 Map 的数据结构是什么，这都是相同的。有关更多信息，请参阅 Sets 和 HashMaps 的javadoc。
你的意思是问一些关于这些结构之一的具体实现的事情吗？
于 2009-11-24T18:20:25.290 回答
-3
除了 HashSet。Set 根据定义是唯一的元素。
这是一个错误。请参阅下面的评论。
于 2009-11-24T17:41:03.637 回答