哈希表和桶阵列

Question

我读到一个哈希表中，我们有一个桶阵列，但我不明白什么桶数组包含。

它是否包含哈希指数？条目（键/值对）？都？

该图像，对我来说，不是很清楚：

^{（reference）}

所以，这是一个斗阵？

Answer 1

在实际中，已经计算（通过散列密钥）计算的条目的链接列表以进入该存储桶。

Answer 2

在HashTable中有大部分时间冲突。那就是当不同的元素具有相同的散列值时。具有相同散列值的元素存储在一个存储桶中。因此，对于每个散列值，您都有一个存储桶，其中包含具有该散列值的所有元素。

Answer 3

桶数组中涉及的内容很大程度上取决于散列表中存储的内容以及冲突解决策略。

当您使用linear probing或其他open addressing technique，你的水桶表存储键或键值对，这取决于您使用哈希表^*的。

当您使用separate chaining technique时，您的存储区数组存储密钥对和链接结构的标题（例如链接列表）。

要记住关于桶数组的重要事项是它建立了一个哈希码和一组零个或多个键之间的映射。换句话说，给定一个散列码和一个桶数组，你可以在常量时间内找出与这个散列码相关联的可能键（枚举候选键可能是线性的，但找到第一个键需要是常数以便满足散列表的平均等待时间插入和恒定时间搜索的性能保证）。

^*如果您的哈希表我们用于检查成员资格（即它代表一组密钥），那么存储区数组存储密钥;否则，它存储键值对。

Answer 4

数组索引大多等同于散列值（好吧，散列值mod是数组大小），所以根本不需要将数组存储在数组中。

至于什么实际的数组包含有几个选项：

• 如果我们使用separate chaining：

  • 到所有具有元素的链接列表的引用那个散列值。因此：

    LinkedList<E>[] 
    

  • 链接列表节点（即，链接列表的头部） - 类似于第一个选项，但是我们只需从链接列表中直接开始，而不必通过单独引用它来浪费空间。所以：

    LinkedListNode<E>[] 
    

• 如果我们使用open addressing，我们只是存储实际元素。如果有另一个具有相同散列值的元素，我们使用一些可重现的技术为它找到一个位置（例如，我们只是尝试下一个位置）。所以：

  E[] 
  

• 可能有一些其他的选择，但以上是最知名的，具有独立，链接是最流行的（据我所知）

* I”假设熟悉泛型和Java/C＃/ C++语法 - E这里只是我们存储的元素的类型，LinkedList<E>表示存储E类型的元素的LinkedList。 X[]是一个包含X类型元素的数组。

Answer 5

存储桶是键值对的链接列表。散列索引是告诉“哪个桶”的一个 ，并且键值对中的“键”是告诉“该桶中的哪个条目”的那个。 也退房 hashing in Java -- structure & access time，我有蜜蜂在那里告诉更多的细节。