data-structures - 哈希表是如何工作的？

Question

我正在寻找关于哈希表如何工作的解释 - 对于像我这样的傻瓜来说，用简单的英语！

例如，我知道它需要密钥，计算哈希（我正在寻找解释如何），然后执行某种模来计算它在存储值的数组中的位置，但这就是我的知识停止的地方.

有人可以澄清这个过程吗？

编辑：我不是专门询问如何计算哈希码，而是对哈希表如何工作的一般概述。

Answer 1

Here's an explanation in layman's terms.

Let's assume you want to fill up a library with books and not just stuff them in there, but you want to be able to easily find them again when you need them.

So, you decide that if the person that wants to read a book knows the title of the book and the exact title to boot, then that's all it should take. With the title, the person, with the aid of the librarian, should be able to find the book easily and quickly.

So, how can you do that? Well, obviously you can keep some kind of list of where you put each book, but then you have the same problem as searching the library, you need to search the list. Granted, the list would be smaller and easier to search, but still you don't want to search sequentially from one end of the library (or list) to the other.

You want something that, with the title of the book, can give you the right spot at once, so all you have to do is just stroll over to the right shelf, and pick up the book.

But how can that be done? Well, with a bit of forethought when you fill up the library and a lot of work when you fill up the library.

Instead of just starting to fill up the library from one end to the other, you devise a clever little method. You take the title of the book, run it through a small computer program, which spits out a shelf number and a slot number on that shelf. This is where you place the book.

The beauty of this program is that later on, when a person comes back in to read the book, you feed the title through the program once more, and get back the same shelf number and slot number that you were originally given, and this is where the book is located.

The program, as others have already mentioned, is called a hash algorithm or hash computation and usually works by taking the data fed into it (the title of the book in this case) and calculates a number from it.

For simplicity, let's say that it just converts each letter and symbol into a number and sums them all up. In reality, it's a lot more complicated than that, but let's leave it at that for now.

The beauty of such an algorithm is that if you feed the same input into it again and again, it will keep spitting out the same number each time.

Ok, so that's basically how a hash table works.

Technical stuff follows.

First, there's the size of the number. Usually, the output of such a hash algorithm is inside a range of some large number, typically much larger than the space you have in your table. For instance, let's say that we have room for exactly one million books in the library. The output of the hash calculation could be in the range of 0 to one billion which is a lot higher.

So, what do we do? We use something called modulus calculation, which basically says that if you counted to the number you wanted (i.e. the one billion number) but wanted to stay inside a much smaller range, each time you hit the limit of that smaller range you started back at 0, but you have to keep track of how far in the big sequence you've come.

Say that the output of the hash algorithm is in the range of 0 to 20 and you get the value 17 from a particular title. If the size of the library is only 7 books, you count 1, 2, 3, 4, 5, 6, and when you get to 7, you start back at 0. Since we need to count 17 times, we have 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, and the final number is 3.

Of course modulus calculation isn't done like that, it's done with division and a remainder. The remainder of dividing 17 by 7 is 3 (7 goes 2 times into 17 at 14 and the difference between 17 and 14 is 3).

Thus, you put the book in slot number 3.

This leads to the next problem. Collisions. Since the algorithm has no way to space out the books so that they fill the library exactly (or the hash table if you will), it will invariably end up calculating a number that has been used before. In the library sense, when you get to the shelf and the slot number you wish to put a book in, there's already a book there.

Various collision handling methods exist, including running the data into yet another calculation to get another spot in the table (double hashing), or simply to find a space close to the one you were given (i.e. right next to the previous book assuming the slot was available also known as linear probing). This would mean that you have some digging to do when you try to find the book later, but it's still better than simply starting at one end of the library.

Finally, at some point, you might want to put more books into the library than the library allows. In other words, you need to build a bigger library. Since the exact spot in the library was calculated using the exact and current size of the library, it goes to follow that if you resize the library you might end up having to find new spots for all the books since the calculation done to find their spots has changed.

I hope this explanation was a bit more down to earth than buckets and functions :)

Answer 2

用法和行话：

1. 哈希表用于快速存储和检索数据（或记录）。
2. 记录使用哈希键存储在存储桶中
3. 哈希键是通过将哈希算法应用于记录中包含的选定值（键值）来计算的。这个选择的值必须是所有记录的公共值。
4. 每个存储桶可以有多个按特定顺序组织的记录。

现实世界的例子：

Hash & Co.成立于 1803 年，缺乏任何计算机技术，共有 300 个文件柜来保存大约 30,000 名客户的详细信息（记录）。每个文件夹都清楚地标有其客户编号，从 0 到 29,999 的唯一编号。

当时的备案文员不得不为工作人员快速获取和存储客户记录。工作人员决定使用散列方法来存储和检索他们的记录会更有效。

为了归档客户记录，归档文员将使用写在文件夹上的唯一客户编号。使用这个客户编号，他们将散列键调制300 以识别它所在的文件柜。当他们打开文件柜时，他们会发现它包含许多按客户编号排序的文件夹。在确定了正确的位置后，他们就会简单地把它塞进去。

为了检索客户记录，归档文员将在纸条上获得客户编号。使用这个唯一的客户编号（哈希键），他们会将其调整 300 以确定哪个文件柜有客户文件夹。当他们打开文件柜时，他们会发现里面有许多按客户编号排序的文件夹。通过搜索记录，他们会很快找到客户文件夹并检索它。

在我们的真实示例中，我们的存储桶是文件柜，我们的记录是文件夹。

---

要记住的重要一点是，计算机（及其算法）处理数字比处理字符串更好。因此，使用索引访问大型数组比顺序访问要快得多。

正如西蒙所提到的，我认为非常重要的是散列部分是转换一个大空间（任意长度，通常是字符串等）并将其映射到一个小空间（已知大小，通常是数字）以进行索引。记住这一点很重要！

所以在上面的例子中，大约 30,000 个可能的客户端被映射到一个更小的空间。

---

这样做的主要思想是将整个数据集划分为多个部分，以加快通常耗时的实际搜索。在我们上面的示例中，300 个文件柜中的每一个都将（从统计上）包含大约 100 条记录。搜索 100 条记录（无论顺序如何）比处理 30,000 条记录要快得多。

您可能已经注意到有些人实际上已经这样做了。但是，在大多数情况下，他们不会设计散列方法来生成散列密钥，而是简单地使用姓氏的第一个字母。因此，如果您有 26 个文件柜，每个文件柜都包含一个从 A 到 Z 的字母，那么理论上您只是对数据进行了分段并增强了归档和检索过程。

希望这可以帮助，

杰奇！

Answer 3

事实证明这是一个相当深的理论领域，但基本轮廓很简单。

从本质上讲，散列函数只是一个从一个空间（比如任意长度的字符串）获取事物并将它们映射到对索引有用的空间（比如无符号整数）的函数。

如果您只有一小部分要散列的东西，您可能只需将这些东西解释为整数就可以了，您就完成了（例如 4 字节字符串）

但是，通常情况下，您的空间要大得多。如果您允许作为键的事物空间大于您用于索引的事物空间（您的 uint32 或其他），那么您不可能为每个事物设置唯一值。当两个或更多事物哈希到相同的结果时，您必须以适当的方式处理冗余（这通常称为冲突，您如何处理它或不处理它取决于您是什么使用哈希）。

这意味着您希望它不太可能具有相同的结果，并且您可能还真的希望散列函数更快。

平衡这两个属性（以及其他一些属性）让许多人忙得不可开交！

在实践中，您通常应该能够找到一个已知适用于您的应用程序的函数并使用它。

现在让它作为一个哈希表工作：想象一下你不关心内存使用情况。然后，您可以创建一个数组，只要您的索引集（例如，所有 uint32）。当你向表中添加一些东西时，你对它的键进行散列并查看该索引处的数组。如果那里什么都没有，你就把你的价值放在那里。如果那里已经有东西了，你把这个新条目添加到那个地址的东西列表中，连同足够的信息（你的原始密钥，或者一些聪明的东西）来找到哪个条目实际上属于哪个密钥。

所以当你走很长的路时，你的哈希表（数组）中的每个条目要么是空的，要么包含一个条目，或者一个条目列表。检索很简单，例如对数组进行索引，然后返回值，或者遍历值列表并返回正确的值。

当然在实践中你通常不能这样做，它浪费了太多的内存。因此，您基于稀疏数组执行所有操作（其中唯一的条目是您实际使用的条目，其他所有内容都隐含为空）。

有很多计划和技巧可以使这项工作更好，但这是基础。

Answer 4

很多答案，但没有一个是非常直观的，并且哈希表在可视化时可以轻松“点击”。

哈希表通常实现为链表数组。如果我们想象一个存储人名的表，在几次插入之后，它可能会在内存中排列如下，其中()- 封闭的数字是文本/名称的哈希值。

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

几点：

• 每个数组条目（索引[0]，[1]...）都称为存储桶，并开始一个 - 可能为空 - 链表的值（又名元素，在本例中 -人名）
• 每个值（例如"fred"带有 hash 42）都从桶链接，[hash % number_of_buckets]例如42 % 10 == [2]；%是模运算符- 除以桶数时的余数
• 多个数据值可能会在同一个存储桶上发生冲突并相互链接，这通常是因为它们的哈希值在模运算之后发生冲突（例如42 % 10 == [2]，和9282 % 10 == [2]），但偶尔因为哈希值相同（例如"fred"，"jane"两者都显示为42上面的哈希）
  • 大多数哈希表通过将正在查找或插入的值的完整值（此处为文本）与哈希存储桶的链接列表中的每个值进行比较来处理冲突 - 性能略有降低但没有功能混淆

链表长度与负载因子有关，而不是值的数量

如果表大小增加，如上实现的哈希表倾向于调整自身大小（即创建更大的存储桶数组，从中创建新/更新的链表，删除旧数组）以保持值与存储桶的比率（也称为负载因子）在 0.5 到 1.0 范围内的某个位置。

Hans 在下面的评论中给出了其他负载因子的实际公式，但对于指示性值：使用负载因子 1 和加密强度哈希函数，1/e (~36.8%) 的桶往往是空的，另外 1/e (~36.8%) 有一种元素，1/(2e) 或~18.4% 两种元素，1/(3!e) 约 6.1% 三种元素，1/(4!e) 或~1.5% 四种元素，1/ (5!e) ~.3% 有五个等.. - 无论表中有多少元素（即是否有 100 个元素和 100 个桶，或 1 亿个），非空桶的平均链长度为 ~1.58元素和 1 亿个桶），这就是为什么我们说查找/插入/擦除是O (1) 个恒定时间操作。

哈希表如何将键与值关联起来

给定如上所述的哈希表实现，我们可以想象创建一个值类型，例如 `struct Value { string name; 年龄; };`，以及仅查看 `name` 字段（忽略年龄）的相等比较和哈希函数，然后发生了一些奇妙的事情：我们可以在表中存储 `Value` 记录，例如 `{"sue", 63}` ，然后在不知道她年龄的情况下搜索“sue”，找到存储的值并恢复甚至更新她的年龄 - 生日快乐 Sue - 有趣的是，它不会更改哈希值，因此不需要我们将 Sue 的记录移动到另一个桶。

当我们这样做时，我们使用哈希表作为关联容器又名map，它存储的值可以被认为由一个键（名称）和一个或多个其他字段组成 - 令人困惑的是 -值（在我的例子中，只是年龄）。用作映射的哈希表实现称为哈希映射。

这与此答案前面的示例形成对比，在该示例中，我们存储了诸如“sue”之类的离散值，您可以将其视为它自己的键：这种用法称为哈希集。

还有其他实现哈希表的方法

并非所有哈希表都使用链表（称为单独链接），但大多数通用哈希表都使用链表，因为主要替代封闭哈希（也称为开放寻址） - 特别是支持擦除操作 - 具有更不稳定的性能属性与易发生冲突的键/哈希函数。

---

关于散列函数的几句话

强哈希...

一个通用的、最坏情况冲突最小化散列函数的工作是随机有效地将键喷洒在散列表桶周围，同时始终为相同的键生成相同的散列值。理想情况下，即使密钥中任何位置的一位更改 - 随机 - 翻转结果哈希值中大约一半的位。

这通常与数学太复杂，我无法理解。我将提到一种易于理解的方式 - 不是最可扩展的或缓存友好的，但本质上是优雅的（例如使用一次性填充的加密！） - 因为我认为它有助于将上述理想品质带回家。假设您正在散列 64 位doubles - 您可以创建 8 个表，每个表有 256 个随机数（代码如下），然后使用 的内存表示的每个 8 位/1 字节切片double来索引到不同的表，异或您查找的随机数。使用这种方法，很容易看到（在二进制数字意义上）在double结果中的任何位置发生变化会导致在其中一个表中查找不同的随机数，以及完全不相关的最终值。

// note caveats above: cache unfriendly (SLOW) but strong hashing...
std::size_t random[8][256] = { ...random data... };
auto p = (const std::byte*)&my_double;
size_t hash = random[0][p[0]] ^
              random[1][p[1]] ^
              ... ^
              random[7][p[7]];

弱但经常快速的哈希...

许多库的散列函数通过不变传递整数（称为平凡或恒等散列函数）；这是上述强散列的另一个极端。身份哈希非常在最坏的情况下容易发生冲突，但希望是在相当常见的整数键趋于递增（可能有一些间隙）的情况下，它们将映射到连续的桶中，留下比随机散列叶更少的空（我们的 ~36.8 % 在前面提到的负载因子 1），因此与随机映射相比，具有更少的冲突和更少的更长的冲突元素链接列表。节省生成强哈希所需的时间也很棒，如果按顺序查找键，它们将在内存附近的存储桶中找到，从而提高缓存命中率。当密钥不能很好地增加时，希望它们足够随机，它们不需要强大的哈希函数来完全随机地将它们放置到桶中。

Answer 5

你们非常接近完全解释这一点，但缺少一些东西。哈希表只是一个数组。数组本身将在每个插槽中包含一些东西。至少，您将在此插槽中存储散列值或值本身。除此之外，您还可以存储在此插槽上发生冲突的值的链接/链式列表，或者您可以使用开放寻址方法。您还可以存储一个或多个指向要从此插槽中检索的其他数据的指针。

需要注意的是，哈希值本身通常不指示放置值的槽。例如，哈希值可能是负整数值。显然负数不能指向数组位置。此外，哈希值往往比可用槽数大很多倍。因此哈希表本身需要执行另一个计算来确定值应该进入哪个槽。这是通过模数数学运算完成的，例如：

uint slotIndex = hashValue % hashTableSize;

该值是该值将进入的槽。在开放寻址中，如果槽已经被另一个哈希值和/或其他数据填充，则将再次运行模运算以找到下一个槽：

slotIndex = (remainder + 1) % hashTableSize;

我想可能还有其他更高级的方法来确定槽索引，但这是我见过的常见方法……会对其他性能更好的方法感兴趣。

使用模数方法，如果您有一个大小为 1000 的表，则任何介于 1 和 1000 之间的哈希值都将进入相应的插槽。任何负值和任何大于 1000 的值都可能是冲突槽值。发生这种情况的机会取决于您的散列方法，以及您添加到散列表中的总项目数。通常，最佳做法是使散列表的大小使得添加到其中的值的总数仅等于其大小的大约 70%。如果您的哈希函数在均匀分布方面做得很好，您通常会遇到很少甚至没有桶/槽冲突，并且它会非常快速地执行查找和写入操作。如果事先不知道要添加的值的总数，请使用任何方法进行良好的猜测，

我希望这有帮助。

PS - 在 C# 中，该GetHashCode()方法非常慢，并且在我测试过的许多条件下会导致实际值冲突。为了获得真正的乐趣，构建自己的哈希函数并尝试让它永远不会与您正在哈希的特定数据发生冲突，运行速度比 GetHashCode 快，并且分布相当均匀。我已经使用 long 而不是 int 大小的哈希码值完成了这项工作，并且它在哈希表中多达 3200 万个整数哈希值上运行良好，并且冲突为 0。不幸的是，我无法共享代码，因为它属于我的雇主……但我可以透露某些数据域是可能的。当你能做到这一点时，哈希表会非常快。:)

Answer 6

在我的理解中，它是这样工作的：

这是一个示例：将整个表想象为一系列桶。假设您有一个带有字母数字哈希码的实现，并且每个字母都有一个存储桶。此实现将哈希码以特定字母开头的每个项目放入相应的存储桶中。

假设您有 200 个对象，但其中只有 15 个具有以字母“B”开头的哈希码。哈希表只需要查找和搜索“B”桶中的 15 个对象，而不是所有 200 个对象。

就计算哈希码而言，它没有什么神奇之处。目标只是让不同的对象返回不同的代码，并让相同的对象返回相同的代码。您可以编写一个始终返回与所有实例的哈希码相同的整数的类，但您实际上会破坏哈希表的有用性，因为它只会变成一个巨大的桶。

Answer 7

简短而甜蜜：

哈希表包装了一个数组，我们称之为internalArray。项目以这种方式插入到数组中：

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

有时两个键会散列到数组中的相同索引，并且您希望保留这两个值。我喜欢将这两个值存储在同一个索引中，通过创建internalArray一个链表数组来编写代码很简单：

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

所以，如果我想从我的哈希表中检索一个项目，我可以这样写：

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

删除操作与编写一样简单。如您所知，从我们的链表数组中插入、查找和删除几乎是O(1)。

当我们的 internalArray 太满时，可能在 85% 左右的容量，我们可以调整内部数组的大小并将所有项目从旧数组移动到新数组中。

Answer 8

它甚至比这更简单。

哈希表只不过是包含键/值对的向量数组（通常是稀疏数组）。此数组的最大大小通常小于存储在哈希表中的数据类型的可能值集中的项目数。

哈希算法用于根据将存储在数组中的项目的值生成该数组的索引。

这是在数组中存储键/值对向量的地方。由于可以作为数组中索引的值集通常小于该类型可以具有的所有可能值的数量，因此您的哈希值可能算法将为两个单独的键生成相同的值。一个好的散列算法会尽可能地防止这种情况（这就是为什么它通常被归为类型，因为它具有一般散列算法不可能知道的特定信息），但这是不可能防止的。

因此，您可以拥有多个生成相同哈希码的密钥。发生这种情况时，将遍历向量中的项目，并在向量中的键和正在查找的键之间进行直接比较。如果找到，则返回与该键关联的值，否则不返回任何内容。

Answer 9

You take a bunch of things, and an array.

For each thing, you make up an index for it, called a hash. The important thing about the hash is that it 'scatter' a lot; you don't want two similar things to have similar hashes.

You put your things into the array at position indicated by the hash. More than one thing can wind up at a given hash, so you store the things in arrays or something else appropriate, which we generally call a bucket.

When you're looking things up in the hash, you go through the same steps, figuring out the hash value, then seeing what's in the bucket at that location and checking whether it's what you're looking for.

When your hashing is working well and your array is big enough, there will only be a few things at most at any particular index in the array, so you won't have to look at very much.

For bonus points, make it so that when your hash table is accessed, it moves the thing found (if any) to the beginning of the bucket, so next time it's the first thing checked.

Answer 10

到目前为止，所有答案都很好，并且涉及哈希表如何工作的不同方面。这是一个可能有帮助的简单示例。假设我们想要存储一些带有小写字母字符串的项目作为键。

正如 simon 所解释的，散列函数用于从大空间映射到小空间。对于我们的示例，哈希函数的一个简单、朴素的实现可以获取字符串的第一个字母，并将其映射到一个整数，因此“alligator”的哈希码为 0，“bee”的哈希码为 1，“斑马”将是 25 等。

接下来我们有一个由 26 个桶组成的数组（在 Java 中可能是 ArrayLists），我们将项目放入与我们的键的哈希码匹配的桶中。如果我们有多个项目的键以相同的字母开头，它们将具有相同的哈希码，因此所有项目都将进入该哈希码的桶中，因此必须在桶中进行线性搜索以找到一个特定的项目。

在我们的示例中，如果我们只有几十个项目的键跨越字母表，它会很好地工作。但是，如果我们有一百万个项目或所有键都以“a”或“b”开头，那么我们的哈希表将不理想。为了获得更好的性能，我们需要一个不同的哈希函数和/或更多的桶。

Answer 11

这是另一种看待它的方式。

我假设您了解数组 A 的概念。它支持索引操作，无论 A 有多大，您都可以一步到达第 I 个元素 A[I]。

因此，例如，如果你想存储一组碰巧有不同年龄的人的信息，一个简单的方法是有一个足够大的数组，并使用每个人的年龄作为数组的索引。通过这种方式，您可以一步访问任何人的信息。

但是当然可能有不止一个人具有相同的年龄，因此您在每个条目中放入的数组是所有具有该年龄的人的列表。因此，您可以通过一个步骤以及在该列表（称为“存储桶”）中的一点点搜索来获取个人信息。只有当人太多以至于水桶变大时，它才会放慢速度。然后你需要一个更大的数组，以及其他一些方法来获取更多关于这个人的识别信息，比如他们姓氏的前几个字母，而不是使用年龄。

这是基本的想法。可以使用产生良好传播价值的人的任何功能，而不是使用年龄。这就是哈希函数。就像您可以将人名的 ASCII 表示的每三分之一位按某种顺序打乱一样。重要的是你不希望太多人散列到同一个桶，因为速度取决于桶保持小。

Answer 12

哈希表完全适用于实际计算遵循随机访问机器模型的事实，即内存中任何地址的值都可以在 O(1) 时间或恒定时间内访问。

所以，如果我有一个键域（我可以在应用程序中使用的所有可能键的集合，例如学生的卷号，如果它是 4 位数字，那么这个域是一组从 1 到 9999 的数字），以及将它们映射到一组有限大小的方法我可以在我的系统中分配内存，理论上我的哈希表已经准备好了。

通常，在应用程序中，键的大小比我想添加到哈希表中的元素数量要大（我不想浪费 1 GB 内存来散列，比如 10000 或 100000 个整数值，因为它们是 32二进制表示中的位长）。所以，我们使用这种散列。这是一种混合的“数学”运算，它将我的大宇宙映射到我可以在内存中容纳的一小组值。在实际情况下，哈希表的空间通常与（元素数*每个元素的大小）具有相同的“顺序”（big-O），因此，我们不会浪费太多内存。

现在，一个大集合映射到一个小集合，映射必须是多对一的。因此，不同的键将被分配相同的空间（？？不公平）。有几种方法可以解决这个问题，我只知道其中流行的两种：

• 使用要分配给该值的空间作为对链表的引用。这个链表将存储一个或多个值，这些值在多对一映射中驻留在同一个槽中。链接列表还包含帮助来搜索的人的键。就像很多人在同一个公寓里，当一个送货员来的时候，他会去房间里专门找那个人。
• 在数组中使用双哈希函数，每次都给出相同的值序列，而不是单个值。当我去存储一个值时，我会查看所需的内存位置是空闲的还是被占用的。如果它是免费的，我可以在那里存储我的值，如果它被占用，我从序列中获取下一个值，依此类推，直到我找到一个空闲位置并将我的值存储在那里。在搜索或检索该值时，我返回与序列给出的相同路径，并在每个位置询问是否存在该值，直到我找到它或搜索数组中的所有可能位置。

CLRS 的算法简介提供了关于该主题的非常好的见解。

Answer 13

基本理念

为什么人们使用梳妆台来存放他们的衣服？除了看起来时尚和时尚，他们的优势在于每件衣服都有它应该在的地方。如果您正在寻找一双袜子，您只需检查袜子抽屉。如果你正在寻找一件衬衫，你可以检查一下里面有你的衬衫的抽屉。当你在寻找袜子时，你有多少件衬衫或你拥有多少条裤子都没关系，因为你不需要看它们。您只需查看袜子抽屉并期望在那里找到袜子。

在高层次上，哈希表是一种存储东西的方式（有点像），就像衣服的梳妆台一样。基本思想如下：

• 你会得到一些可以存放物品的位置（抽屉）。
• 你想出了一些规则，告诉你每个项目属于哪个位置（抽屉）。
• 当您需要查找某些东西时，您可以使用该规则来确定要查看的抽屉。

像这样的系统的优点是，假设您的规则不太复杂并且您有适当数量的抽屉，您只需在正确的位置查找即可很快找到您要查找的内容。

当你把衣服收起来时，你使用的“规则”可能是“袜子放在左上方的抽屉里，衬衫放在中间的大抽屉里，等等”。但是，当您存储更多抽象数据时，我们会使用一种称为哈希函数的方法来为我们执行此操作。

考虑散列函数的一种合理方式是作为一个黑盒。你把数据放在一边，一个叫做哈希码的数字从另一边出来。从示意图上看，它看起来像这样：

              +---------+
            |\|   hash  |/| --> hash code
   data --> |/| function|\|
              +---------+

所有散列函数都是确定性的：如果你多次将相同的数据放入函数中，你总是会从另一端得到相同的值。一个好的散列函数应该看起来或多或少是随机的：输入数据的微小变化应该给出截然不同的散列码。例如，字符串“pudu”和字符串“kudu”的哈希码可能会彼此完全不同。（再说一遍，它们可能是相同的。毕竟，如果哈希函数的输出看起来或多或少是随机的，那么我们有可能两次获得相同的哈希码。）

您究竟是如何构建散列函数的？现在，让我们继续“体面的人不应该想太多”。数学家已经想出了更好和更差的方法来设计散列函数，但为了我们的目的，我们真的不需要太担心内部结构。把散列函数想象成一个函数就好了

• 确定性（相等的输入给出相等的输出），但是
• 看起来是随机的（很难预测给定另一个哈希码）。

一旦我们有了哈希函数，我们就可以构建一个非常简单的哈希表。我们将制作一系列“桶”，您可以将其视为类似于我们梳妆台中的抽屉。要将项目存储在哈希表中，我们将计算对象的哈希码并将其用作表中的索引，这类似于“选择该项目进入哪个抽屉”。然后，我们将该数据项放入该索引处的存储桶中。如果那个桶是空的，那就太好了！我们可以把物品放在那里。如果那个桶是满的，我们可以做一些选择。一种简单的方法（称为链式哈希）是将每个存储桶视为项目列表，就像您的袜子抽屉可能存储多个袜子一样，然后只需将项目添加到该索引处的列表中。

要在哈希表中查找某些内容，我们使用基本相同的过程。我们首先计算要查找的项目的哈希码，它告诉我们要查找哪个桶（抽屉）。如果项目在表中，它必须在那个桶中。然后，我们只需查看存储桶中的所有项目，看看我们的项目是否在其中。

这样做有什么好处？好吧，假设我们有大量的桶，我们希望大多数桶中不会有太多的东西。毕竟，我们的散列函数看起来有点像随机输出，所以项目在所有桶中均匀分布。事实上，如果我们将“我们的哈希函数看起来有点随机”的概念形式化，我们可以证明每个桶中的预期项目数是项目总数与桶总数的比率。因此，我们无需做太多工作就可以找到我们正在寻找的项目。

细节

解释“哈希表”的工作原理有点棘手，因为哈希表有很多种。下一节将讨论所有哈希表共有的一些通用实现细节，以及不同风格的哈希表如何工作的一些细节。

出现的第一个问题是如何将哈希码转换为表槽索引。在上面的讨论中，我只是说“使用哈希码作为索引”，但这实际上不是一个好主意。在大多数编程语言中，散列码都适用于 32 位或 64 位整数，您不能直接将它们用作存储桶索引。相反，一种常见的策略是创建一个大小为 m 的存储桶数组，为您的项目计算（完整的 32 位或 64 位）哈希码，然后根据表的大小对它们进行修改以获得介于 0 和m-1，包括在内。模数的使用在这里效果很好，因为它速度很快，并且可以很好地将全范围的哈希码传播到更小的范围内。

（您有时会看到这里使用的按位运算符。如果您的表的大小是 2 的幂，例如 2 ^k，那么计算哈希码的按位与，然后计算数字 2 ^k - 1 相当于计算模数，并且它明显更快。）

下一个问题是如何选择正确数量的桶。如果你选择了太多的桶，那么大多数桶将是空的或只有很少的元素（有利于速度 - 你只需要检查每个桶的几个项目），但你会使用一堆空间来简单地存储桶（不是这样太好了，虽然也许你买得起）。反之亦然——如果桶太少，那么平均每个桶会有更多的元素，使得查找需要更长的时间，但你会使用更少的内存。

一个好的折衷方案是在哈希表的生命周期内动态更改存储桶的数量。哈希表的负载因子，通常表示为 α，是元素数与桶数的比率。大多数哈希表选择一些最大负载因子。一旦负载因子超过此限制，哈希表就会增加其槽数（例如，通过加倍），然后将旧表中的元素重新分配到新表中。这称为重新散列。假设表中的最大负载因子是一个常数，这确保了，假设你有一个好的散列函数，进行查找的预期成本仍然是 O(1)。插入现在具有摊销O(1) 的预期成本，因为定期重建表的成本，就像删除的情况一样。（如果负载因子太小，删除同样可以压缩表。）

哈希策略

到目前为止，我们一直在讨论链式哈希，这是构建哈希表的许多不同策略之一。提醒一下，链式散列有点像衣服梳妆台 - 每个桶（抽屉）可以容纳多个物品，当您进行查找时，您会检查所有这些物品。

但是，这不是构建哈希表的唯一方法。还有另一个哈希表系列使用一种称为开放寻址的策略。开放寻址背后的基本思想是存储一个槽数组，其中每个槽可以是空的，也可以只容纳一个项目。

在开放寻址中，当您执行插入时，像以前一样，您会跳转到某个插槽，其索引取决于计算的哈希码。如果该插槽是免费的，那就太好了！你把物品放在那里，你就完成了。但是如果插槽已经满了怎么办？在这种情况下，您可以使用一些辅助策略来找到一个不同的空闲槽来存储该项目。执行此操作的最常见策略使用称为线性探测的方法。在线性探测中，如果您想要的插槽已满，您只需转移到表中的下一个插槽。如果那个插槽是空的，太好了！你可以把物品放在那里。但是，如果该槽已满，则您将移至表中的下一个槽，依此类推（如果您到达表的末尾，则返回到开头）。

线性探测是构建哈希表的一种非常快速的方法。CPU 缓存针对引用的局部性进行了优化，因此在相邻内存位置的内存查找往往比在分散位置的内存查找要快得多。由于线性探测插入或删除通过击中某个数组槽然后线性向前移动来工作，因此它会导致很少的缓存未命中并且最终比理论通常预测的要快得多。（而且理论预测它会非常快！）

最近流行的另一种策略是cuckoo hashing。我喜欢将杜鹃散列视为散列表的“冻结”。我们有两个哈希表和两个哈希函数，而不是一个哈希表和一个哈希函数。每个项目都可以恰好位于两个位置中的一个 - 它要么位于第一个哈希函数给出的第一个表中的位置，要么位于第二个哈希函数给出的第二个表中的位置。这意味着查找是最坏情况下的高效，因为您只需检查两个点即可查看表中是否有内容。

杜鹃散列中的插入使用与以前不同的策略。我们首先查看可以容纳该项目的两个插槽中的任何一个是否空闲。如果是这样，太好了！我们只是把物品放在那里。但如果这不起作用，那么我们选择一个插槽，将项目放在那里，然后踢出曾经在那里的项目。该物品必须放在某个地方，因此我们尝试将其放在另一张桌子的适当位置。如果这行得通，那就太好了！如果没有，我们将一个项目踢出该表并尝试将其插入另一个表。这个过程一直持续到一切都平静下来，或者我们发现自己陷入了一个循环。（后一种情况很少见，如果发生这种情况，我们有很多选择，例如“将其放入辅助哈希表”或“选择新的哈希函数并重建表。”）

杜鹃散列有许多改进可能，例如使用多个表，让每个插槽容纳多个项目，以及制作一个“存储”以容纳其他任何地方都无法容纳的项目，这是一个活跃的研究领域！

然后是混合方法。跳房子散列是开放寻址和链式散列之间的混合，可以被认为是采用链式散列表并将每个存储桶中的每个项目存储在项目想要去的位置附近的插槽中。这种策略与多线程配合得很好。瑞士表利用了一些处理器可以用一条指令并行执行多个操作的事实来加速线性探测表。可扩展散列是为数据库和文件系统设计的，它使用 trie 和链式散列表的混合来在加载单个存储桶时动态增加存储桶大小。罗宾汉哈希是线性探测的一种变体，其中项目可以在插入后移动，以减少每个元素可以居住的距离的差异。

延伸阅读

有关哈希表基础知识的更多信息，请查看这些关于链式哈希的讲座幻灯片以及这些关于线性探测和罗宾汉哈希的后续幻灯片。您可以在此处了解有关杜鹃散列的更多信息，并在此处了解散列函数的理论属性。

Answer 14

哈希的计算方式通常不取决于哈希表，而是取决于添加到其中的项目。在 .net 和 Java 等框架/基类库中，每个对象都有一个 GetHashCode()（或类似）方法，该方法返回该对象的哈希码。理想的哈希码算法和准确的实现取决于对象中所代表的数据。

Answer 15

直接地址表

要理解哈希表，直接地址表是我们应该理解的第一个概念。

直接地址表直接使用键作为数组中槽的索引。Universe 键的大小等于数组的大小。在 O(1) 时间内访问此密钥非常快，因为数组支持随机访问操作。

但是，在实现直接地址表之前有四个注意事项：

1. 要成为有效的数组索引，键应该是整数
2. 键的范围相当小，否则，我们将需要一个巨大的数组。
3. 不是两个不同的键映射到数组中的同一个槽
4. Universe 键的长度等于数组的长度

事实上，现实生活中并没有很多情况符合上述要求，所以哈希表来拯救

哈希表

哈希表不是直接使用密钥，而是首先应用数学哈希函数将任意密钥数据一致地转换为数字，然后使用该哈希结果作为密钥。

Universe 键的长度可以大于数组的长度，这意味着两个不同的键可以散列到同一个索引（称为散列冲突）？

实际上，有几种不同的策略来处理它。这是一个常见的解决方案：我们不是将实际值存储在数组中，而是存储一个指向链表的指针，该链表包含散列到该索引的所有键的值。

如果您仍然有兴趣了解如何从头开始实现 hashmap，请阅读以下帖子

Answer 16

对于所有寻找编程术语的人来说，这是它的工作原理。高级哈希表的内部实现对于存储分配/解除分配和搜索有许多复杂性和优化，但顶级想法将非常相似。

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

所有唯一性魔术必须发生calculate_bucket_from_val()的散列函数在哪里。

经验法则是： 对于要插入的给定值，存储桶必须是唯一的并且可以从它应该存储的值中派生。

Bucket 是存储值的任何空间 - 因为在这里我将它保存为 int 作为数组索引，但它也可能是一个内存位置。

Answer 17

里面的哈希表包含存储密钥集的罐子。哈希表使用哈希码来决定密钥对应该计划到哪个。从 Key 的 hashcode 中获取容器区域的能力称为 hash work。原则上，散列工作是一种容量，当给定一个键时，它会在表中创建一个地址。哈希工作始终返回项目的数字。两个等效的项目将始终具有相似的数字，而两个不一致的对象通常可能不会具有不同的数字。当我们将对象放入哈希表时，可以想象各种对象可能具有相同/相同的哈希码。这被称为碰撞。为了确定冲突，哈希表使用了各种列表。映射到单个数组索引的集合存储在列表中，然后列表引用存储在索引中。