直连地址表

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

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

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

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

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

哈希表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我的理解是这样的:

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

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

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