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

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

如果你只有一个小空间的东西来散列，你可能只需要把这些东西解释为整数，你就完成了(例如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.

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

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

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

直连地址表

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

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

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

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

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

哈希表

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

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

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

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

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

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

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

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

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

我的理解是这样的:

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

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

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

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

我假设你理解数组A的概念，它支持索引操作，你可以一步找到第I个元素，A[I]，不管A有多大。

因此，例如，如果您想存储一组恰好年龄不同的人的信息，一个简单的方法是有一个足够大的数组，并使用每个人的年龄作为数组的索引。这样，你就可以一步获取任何人的信息。

But of course there could be more than one person with the same age, so what you put in the array at each entry is a list of all the people who have that age. So you can get to an individual person's information in one step plus a little bit of search in that list (called a "bucket"). It only slows down if there are so many people that the buckets get big. Then you need a larger array, and some other way to get more identifying information about the person, like the first few letters of their surname, instead of using age.

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