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

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

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

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

我的理解是这样的:

这里有一个例子:把整个表想象成一系列的桶。假设您有一个带有字母-数字哈希码的实现，并且每个字母都有一个存储桶。该实现将哈希码以特定字母开头的每个项放入相应的bucket中。

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

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

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

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

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

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

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

这是一个外行的解释。

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

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

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

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

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

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

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

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

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

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

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

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

首先是数字的大小。通常，这种哈希算法的输出在一个较大的数字范围内，通常比表中的空间大得多。例如，假设我们的图书馆刚好有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号槽里。

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

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

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

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

你们已经很接近完整地解释了这个问题，但是遗漏了一些东西。哈希表只是一个数组。数组本身将在每个槽中包含一些内容。至少要将哈希值或值本身存储在这个插槽中。除此之外，您还可以存储在此插槽上碰撞的值的链接/链表，或者您可以使用开放寻址方法。您还可以存储一个或多个指针，这些指针指向您希望从该槽中检索的其他数据。

It's important to note that the hashvalue itself generally does not indicate the slot into which to place the value. For example, a hashvalue might be a negative integer value. Obviously a negative number cannot point to an array location. Additionally, hash values will tend to many times be larger numbers than the slots available. Thus another calculation needs to be performed by the hashtable itself to figure out which slot the value should go into. This is done with a modulus math operation like:

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

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

With the modulus method, if you have a table of say size 1000, any hashvalue that is between 1 and 1000 will go into the corresponding slot. Any Negative values, and any values greater than 1000 will be potentially colliding slot values. The chances of that happening depend both on your hashing method, as well as how many total items you add to the hash table. Generally, it's best practice to make the size of the hashtable such that the total number of values added to it is only equal to about 70% of its size. If your hash function does a good job of even distribution, you will generally encounter very few to no bucket/slot collisions and it will perform very quickly for both lookup and write operations. If the total number of values to add is not known in advance, make a good guesstimate using whatever means, and then resize your hashtable once the number of elements added to it reaches 70% of capacity.

我希望这对你有所帮助。

PS - In C# the GetHashCode() method is pretty slow and results in actual value collisions under a lot of conditions I've tested. For some real fun, build your own hashfunction and try to get it to NEVER collide on the specific data you are hashing, run faster than GetHashCode, and have a fairly even distribution. I've done this using long instead of int size hashcode values and it's worked quite well on up to 32 million entires hashvalues in the hashtable with 0 collisions. Unfortunately I can't share the code as it belongs to my employer... but I can reveal it is possible for certain data domains. When you can achieve this, the hashtable is VERY fast. :)