什么是“存储桶条目"?在哈希表的背景下意味着什么? [英] What does "bucket entries" mean in the context of a hashtable?

问题描述

在哈希表的上下文中，存储桶条目"是什么意思?

What does "bucket entries" mean in the context of a hashtable?

推荐答案

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

A bucket is simply a fast-access location (like an array index) that is the the result of the hash function.

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

The idea with hashing is to turn a complex input value into a different value which can be used to rapidly extract or store data.

考虑以下散列函数，用于将人的名字映射到街道地址.

Consider the following hash function for mapping people's names into street addresses.

首先使用名字和姓氏的缩写，然后将它们都转换为数值(0至25，从A至Z).将第一个乘以26，然后加上第二个，这将为您提供一个从0到675的值(26 * 26不同的值或存储区ID).然后，此存储区ID将用于存储或检索信息.

First take the initials from the first and last name and turn them both into numeric values (0 through 25, from A through Z). Multiply the first by 26 and add the second, and this gives you a value from 0 to 675 (26 * 26 distinct values, or bucket IDs). This bucket ID is then to be used to store or retrieve the information.

现在您可以拥有一个 perfect 哈希(每个允许的输入值都映射到一个 distinct 存储桶ID)，这样一个简单的数组就可以满足这些存储桶.在这种情况下，您只需维护一个676个街道地址的数组，然后使用存储区ID即可找到所需的地址:

Now you can have a perfect hash (where each allowable input value maps to a distinct bucket ID) so that a simple array will suffice for the buckets. In that case, you can just maintain an array of 676 street addresses and use the bucket ID to find the one you want:

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

但是，这意味着George Wendt和Allan Langer将来会引起问题.

However, this means that George Wendt and Allan Langer are going to cause problems in the future.

或者您可以有一个不完美哈希(例如，约翰·史密斯和简·西摩将以相同的存储桶ID结尾的哈希).

Or you can have an imperfect hash (such as one where John Smith and Jane Seymour would end up with the same bucket ID).

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

In that case, you need a more complex backing data structure than a simple array, to maintain a collection of addresses. This could be as simple as a linked list, or as complex as yet another hash:

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

然后，除了进行初始哈希查找外，还需要在存储桶本身中进行额外级别的搜索，以查找特定信息.

Then, as well as the initial hash lookup, an extra level of searching needs to be carried out within the bucket itself, to find the specific information.

这篇关于什么是“存储桶条目"?在哈希表的背景下意味着什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！