"存储区条目"在哈希表的上下文中意味着什么？

Question

"存储区条目"在哈希表的上下文中意味着什么？

Answer 1

存储桶只是一个快速访问位置(如数组索引),它是散列函数的结果.

散列的想法是将复杂的输入值转换为可用于快速提取或存储数据的不同值.

考虑以下哈希函数,用于将人名转换为街道地址.

首先从名字和姓氏中取出较低的首字母,并将它们都转换为数字值(0到25,从'a'到'z').将第一个乘以26并添加第二个,这将为您提供0到675之间的值(26*26个不同的值或存储区ID).

然后,该桶ID用于存储或检索信息.现在您可以拥有一个完美的哈希值(每个允许的输入值映射到一个不同的桶ID),这样一个简单的数组就足以满足桶的需要.换句话说,您维护一个包含676个街道地址的数组,并使用存储桶ID找到您想要的地址:

+-------------------+
| George Washington | -> hash(GW)
+-------------------+      |
                           +-> GwBucket[George's address]
+-------------------+
|  Abraham Lincoln  | -> hash(AL)
+-------------------+      |
                           +-> AlBucket[Abe's address]

或者你可以有一个不完美的哈希(例如John Smith和Jane Seymour最终会使用相同的桶ID).

在这种情况下,您需要一个比简单数组更复杂的后备数据结构来维护一组地址.这可以像链表一样简单,也可以像另一个哈希一样复杂:

+------------+       +--------------+
| John Smith |       | Jane Seymour |
+------------+       +--------------+
      |                     |
      V                     V
   hash(JS)              hash(JS)
      |                     |
      +-----> JsBucket <----+
                 \/
+-----------------------------------+
| "John Smith   -> [John's address] |
| "Jane Seymour -> [Jane's address] |
+-----------------------------------+

然后,除了初始哈希查找之外,还需要在桶本身内执行额外的搜索级别,以查找特定信息.

Answer 2

来自维基百科:

散列表或散列映射是使用散列函数将标识值(称为密钥(例如,人名)映射到其关联值(例如,其电话号码)的数据结构.因此,哈希表实现了一个关联数组.散列函数用于将密钥转换为要在其中寻找相应值的数组元素(槽或桶)的索引(散列).

数组/向量中的每个条目都称为Bucket.

Answer 3

我认为Bucket是一个至少包含哈希值的结构，它充当索引（哈希值由哈希函数生成），但结构本身可能包含条目（数据），也可能不包含。

插图：

[哈希值][指向实际数据] ---> [实际数据]
|<------------桶结构------>|

[哈希值][实际数据]
|-----桶结构--->|

它是[哈希值]部分作为索引。

我发现来自hash_table 维基百科的这些照片非常简单。

下图表明条目（数据）可以存储在桶中，也可以用自己的数据结构存储，而桶只是指向数据。