这是一个外行的解释。

让我们假设你想要用书填满一个图书馆，而不仅仅是把它们塞进去，而且你希望在你需要它们的时候能够很容易地再次找到它们。

因此，您决定，如果想要阅读一本书的人知道书名和确切的书名，那么这就是所有应该做的。有了书名，在图书管理员的帮助下，读者就能轻松快速地找到这本书。

那么，你该怎么做呢?当然，你可以列出你把每本书放在哪里的列表，但是你会遇到和搜索图书馆一样的问题，你需要搜索列表。当然，列表会更小，更容易搜索，但您仍然不希望从库(或列表)的一端到另一端依次搜索。

你想要的东西，有了书名，就能立刻给你正确的位置，所以你所要做的就是漫步到正确的书架上，拿起书。

但这怎么能做到呢?嗯，当你填满图书馆的时候要有一点先见之明，当你填满图书馆的时候要做很多工作。

你设计了一个聪明的小方法，而不是开始从一端到另一端填满这个库。你拿着书名，在一个小的计算机程序中运行，它会显示出书架的编号和书架上的槽号。这是你放书的地方。

这个程序的美妙之处在于，稍后，当一个人回来阅读这本书时，您再次通过程序输入标题，并获得与最初给您的相同的书架编号和插槽编号，这就是书的位置。

正如其他人已经提到的，这个程序被称为哈希算法或哈希计算，通常通过输入数据(在这种情况下是书名)并从中计算一个数字来工作。

为了简单起见，我们假设它只是将每个字母和符号转换为一个数字，并将它们全部相加。实际上，它要比这复杂得多，但现在让我们先把它放在这里。

这种算法的美妙之处在于，如果你一次又一次地向它输入相同的输入，它每次都会输出相同的数字。

这就是哈希表的基本工作原理。

接下来是技术方面的内容。

首先是数字的大小。通常，这种哈希算法的输出在一个较大的数字范围内，通常比表中的空间大得多。例如，假设我们的图书馆刚好有100万本书的空间。哈希计算的输出可以在0到10亿的范围内，这要高得多。

那么，我们该怎么办呢?我们使用所谓的模量计算，它基本上是说，如果你数到你想要的数字(即10亿数字)，但想要保持在一个小得多的范围内，每次你达到这个小范围的极限，你就从0开始，但你必须跟踪你在大序列中走了多远。

假设哈希算法的输出在0到20的范围内，并且从特定的标题中获得值17。如果图书馆的大小只有7本书，你数1、2、3、4、5、6，当你数到7时，你从0开始。因为我们需要数17次，所以我们有1、2、3、4、5、6、0、1、2、3、4、5、6、0、1、2、3，最后的数字是3。

当然模量的计算不是这样的，它是用除法和余数来完成的。17除以7的余数是3(17除7得14,17和14之差是3)。

因此，你把书放在3号槽里。

这就导致了下一个问题。碰撞。由于该算法无法将图书间隔开来以使它们完全填满库(或者填满哈希表)，因此它最终总是会计算一个以前使用过的数字。在图书馆的意义上，当你到达书架和你想放一本书的槽号时，那里已经有一本书了。

存在各种冲突处理方法，包括将数据运行到另一个计算中以获得表中的另一个位置(双重哈希)，或者只是在给定的位置附近找到一个空间(例如，就在前一本书的旁边，假设插槽可用，也称为线性探测)。这意味着当你稍后试图找到这本书时，你需要做一些挖掘工作，但这仍然比简单地从图书馆的一端开始要好。

最后，在某些情况下，您可能希望将更多的书放入图书馆，而不是图书馆所允许的。换句话说，你需要建立一个更大的库。由于图书馆中的确切位置是使用图书馆的确切和当前大小计算出来的，因此，如果您调整了图书馆的大小，那么您可能最终不得不为所有书籍找到新的位置，因为为找到它们的位置所做的计算已经改变了。

我希望这个解释比桶和函数更接地气一点:)

你取一堆东西，和一个数组。

对于每一个东西，你为它建立一个索引，称为哈希。关于哈希的重要事情是它“分散”了很多;你不希望两个相似的东西有相似的哈希值。

你把东西放到数组中哈希值表示的位置。在一个给定的哈希中可以有多个对象，所以你可以将这些对象存储在数组或其他合适的东西中，我们通常称之为bucket。

当你在哈希中查找东西时，你会经历相同的步骤，计算哈希值，然后查看那个位置的bucket中有什么，并检查它是否是你要寻找的东西。

当你的哈希工作得很好并且你的数组足够大时，在数组的任何特定下标处最多只会有很少的东西，所以你不需要看太多。

额外的好处是，当你的哈希表被访问时，它会把找到的东西(如果有的话)移动到桶的开头，这样下次它就会是第一个被检查的东西。

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

正如simon所解释的，哈希函数用于从大空间映射到小空间。对于我们的例子，一个简单的哈希函数实现可以取字符串的第一个字母，并将其映射为一个整数，因此“短吻鳄”的哈希代码为0，“蜜蜂”的哈希代码为1，“斑马”的哈希代码为25，等等。

接下来，我们有一个包含26个存储桶的数组(在Java中可以是数组列表)，我们将项放入与键的哈希码匹配的存储桶中。如果我们有不止一个元素键以相同字母开头，它们就会有相同的哈希码，所以它们都会进入存储桶中寻找那个哈希码所以必须在存储桶中进行线性搜索才能找到一个特定的元素。

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

有很多答案，但没有一个是非常可视化的，而哈希表在可视化时很容易“点击”。

哈希表通常实现为链表数组。如果我们想象一个存储人名的表，经过几次插入之后，它可能会被放置在内存中，其中()包含的数字是文本/姓名的哈希值。

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

以下几点:

each of the array entries (indices [0], [1]...) is known as a bucket, and starts a - possibly empty - linked list of values (aka elements, in this example - people's names) each value (e.g. "fred" with hash 42) is linked from bucket [hash % number_of_buckets] e.g. 42 % 10 == [2]; % is the modulo operator - the remainder when divided by the number of buckets multiple data values may collide at and be linked from the same bucket, most often because their hash values collide after the modulo operation (e.g. 42 % 10 == [2], and 9282 % 10 == [2]), but occasionally because the hash values are the same (e.g. "fred" and "jane" both shown with hash 42 above) most hash tables handle collisions - with slightly reduced performance but no functional confusion - by comparing the full value (here text) of a value being sought or inserted to each value already in the linked list at the hashed-to bucket

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

如果表的大小增加，上面实现的哈希表倾向于调整自己的大小(即创建一个更大的桶数组，在那里创建新的/更新的链表，删除旧的数组)，以保持值与桶的比率(又名负载因子)在0.5到1.0的范围内。

Hans gives the actual formula for other load factors in a comment below, but for indicative values: with load factor 1 and a cryptographic strength hash function, 1/e　(~36.8%) of buckets will tend to be empty, another 1/e (~36.8%) have one element, 1/(2e) or ~18.4% two elements, 1/(3!e) about 6.1% three elements, 1/(4!e) or ~1.5% four elements, 1/(5!e) ~.3% have five etc.. - the average chain length from non-empty buckets is ~1.58 no matter how many elements are in the table (i.e. whether there are 100 elements and 100 buckets, or 100 million elements and 100 million buckets), which is why we say lookup/insert/erase are O(1) constant time operations.

哈希表如何将键与值关联

Given a hash table implementation as described above, we can imagine creating a value type such as `struct Value { string name; int age; };`, and equality comparison and hash functions that only look at the `name` field (ignoring age), and then something wonderful happens: we can store `Value` records like `{"sue", 63}` in the table, then later search for "sue" without knowing her age, find the stored value and recover or even update her age - happy birthday Sue - which interestingly doesn't change the hash value so doesn't require that we move Sue's record to another bucket.

当我们这样做的时候，我们使用哈希表作为一个关联容器，也就是map，它存储的值可以被认为是由一个键(名称)和一个或多个其他字段组成，仍然被称为值(在我的例子中，只是年龄)。用作映射的哈希表实现称为哈希映射。

这与前面我们存储离散值的例子形成了对比，比如“sue”，你可以把它看作是它自己的键:这种用法被称为散列集。

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

并不是所有的哈希表都使用链表(称为独立链表)，但大多数通用哈希表都使用链表，因为主要的替代封闭哈希(又名开放寻址)-特别是支持擦除操作-与易于冲突的键/哈希函数相比性能不太稳定。

---

简单讲一下哈希函数

强大的散列…

一个通用的、最小化最坏情况碰撞的哈希函数的工作是有效地随机地在哈希表桶周围散布键，同时总是为相同的键生成相同的哈希值。理想情况下，即使在键的任何位置改变一个位，也会随机地翻转结果哈希值中的大约一半位。

This is normally orchestrated with maths too complicated for me to grok. I'll mention one easy-to-understand way - not the most scalable or cache friendly but inherently elegant (like encryption with a one-time pad!) - as I think it helps drive home the desirable qualities mentioned above. Say you were hashing 64-bit doubles - you could create 8 tables each of 256 random numbers (code below), then use each 8-bit/1-byte slice of the double's memory representation to index into a different table, XORing the random numbers you look up. With this approach, it's easy to see that a bit (in the binary digit sense) changing anywhere in the double results in a different random number being looked up in one of the tables, and a totally uncorrelated final value.

// 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]];

弱但通常快速的哈希…

Many libraries' hashing functions pass integers through unchanged (known as a trivial or identity hash function); it's the other extreme from the strong hashing described above. An identity hash is extremely collision prone in the worst cases, but the hope is that in the fairly common case of integer keys that tend to be incrementing (perhaps with some gaps), they'll map into successive buckets leaving fewer empty than random hashing leaves (our ~36.8% at load factor 1 mentioned earlier), thereby having fewer collisions and fewer longer linked lists of colliding elements than is achieved by random mappings. It's also great to save the time it takes to generate a strong hash, and if keys are looked up in order they'll be found in buckets nearby in memory, improving cache hits. When the keys don't increment nicely, the hope is they'll be random enough they won't need a strong hash function to totally randomise their placement into buckets.

直连地址表

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

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

然而，在实现直接地址表之前，有四个注意事项:

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

事实上，现实生活中并不是很多情况都符合上述要求，所以哈希表就可以救场了

哈希表

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

宇宙键的长度可以大于数组的长度，这意味着两个不同的键可以散列到相同的索引(称为散列碰撞)?

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

如果你仍然有兴趣知道如何从头开始实现hashmap，请阅读下面的帖子

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

本质上，哈希函数只是一个函数，它从一个空间(比如任意长度的字符串)获取内容，并将它们映射到一个用于索引的空间(比如无符号整数)。

如果你只有一个小空间的东西来散列，你可能只需要把这些东西解释为整数，你就完成了(例如4字节字符串)

不过，通常情况下，你的空间要大得多。如果你允许作为键的空间大于你用于索引的空间(你的uint32或其他)，那么你不可能为每个键都有唯一的值。当两个或多个东西散列到相同的结果时，您必须以适当的方式处理冗余(这通常被称为冲突，如何处理它或不处理它将略微取决于您使用散列的目的)。

这意味着你不希望得到相同的结果，你也可能希望哈希函数是快速的。

平衡这两个属性(以及其他一些属性)让许多人忙得不可开交!

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

Now to make this work as a hashtable: Imagine you didn't care about memory usage. Then you can create an array as long as your indexing set (all uint32's, for example). As you add something to the table, you hash it's key and look at the array at that index. If there is nothing there, you put your value there. If there is already something there, you add this new entry to a list of things at that address, along with enough information (your original key, or something clever) to find which entry actually belongs to which key.

因此，随着时间的推移，哈希表(数组)中的每个条目要么是空的，要么包含一个条目，要么包含一个条目列表。检索很简单，就像在数组中建立索引，然后返回值，或者遍历值列表并返回正确的值。

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

有很多方案和技巧可以让它更好地工作，但这是最基本的。