直连地址表

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

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

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

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

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

哈希表

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

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

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

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

用法和行话:

哈希表用于快速存储和检索数据(或记录)。 记录使用散列键存储在桶中 哈希键是通过对记录中包含的选定值(键值)应用哈希算法来计算的。所选值必须是所有记录的公共值。 每个桶可以有多条记录，这些记录按照特定的顺序组织。

现实世界的例子:

哈希公司成立于1803年，当时没有任何计算机技术，只有300个文件柜来保存大约3万名客户的详细信息(记录)。每个文件夹都清楚地标识其客户端编号，从0到29,999的唯一编号。

当时的档案管理员必须迅速为工作人员获取和存储客户记录。工作人员决定使用哈希方法来存储和检索他们的记录会更有效。

要归档客户记录，档案管理员将使用写在文件夹上的唯一客户编号。使用这个客户端编号，他们将哈希键调整300，以识别包含它的文件柜。当他们打开文件柜时，他们会发现里面有很多按客户号排序的文件夹。在确定正确的位置后，他们会简单地把它塞进去。

要检索客户记录，档案管理员将在一张纸上获得客户号码。使用这个唯一的客户端编号(哈希键)，他们会将其调整300，以确定哪个文件柜拥有客户端文件夹。当他们打开文件柜时，他们会发现里面有很多按客户号排序的文件夹。通过搜索记录，他们可以快速找到客户端文件夹并检索它。

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

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

正如Simon提到的，我认为非常重要的是哈希部分是转换一个大空间(任意长度，通常是字符串等)，并将其映射到一个小空间(已知大小，通常是数字)进行索引。记住这一点非常重要!

因此，在上面的示例中，大约30,000个可能的客户机被映射到一个较小的空间中。

这样做的主要思想是将整个数据集划分为几个部分，以加快实际搜索的速度，而实际搜索通常是耗时的。在我们上面的例子中，300个文件柜中的每个(统计上)将包含大约100条记录。搜索100条记录(不管顺序)要比处理3万条记录快得多。

你可能已经注意到有些人已经这样做了。但是，在大多数情况下，他们只是使用姓氏的第一个字母，而不是设计一个哈希方法来生成哈希键。因此，如果您有26个文件柜，每个文件柜都包含从a到Z的一个字母，理论上您只是将数据分割并增强了归档和检索过程。

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

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

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

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

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

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

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

我假设你理解数组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表示的每三分之一，按某种顺序打乱。重要的是，您不希望太多人散列到同一个存储桶，因为速度取决于存储桶保持较小。

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

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

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

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

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

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

其实比这更简单。

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

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

This is where storing vectors of key/value pairs in the array come in. Because the set of values that can be indexes in the array is typically smaller than the number of all possible values that the type can have, it is possible that your hash algorithm is going to generate the same value for two separate keys. A good hash algorithm will prevent this as much as possible (which is why it is relegated to the type usually because it has specific information which a general hash algorithm can't possibly know), but it's impossible to prevent.

因此，您可以使用多个键来生成相同的散列代码。当这种情况发生时，将遍历向量中的项，并在向量中的键和正在查找的键之间进行直接比较。如果找到，则返回与该键关联的值，否则不返回任何值。