哈希表是什么？

Question

• 它们是什么以及如何工作？
• 它们在哪里使用？
• 我何时应该（不）使用它们？

我一遍又一遍地听到这个词，但我不知道它的确切含义。

我听说它们通过将数组键发送到哈希函数中，将其转换为整数，然后使用常规数组来允许关联数组。我的理解正确吗？

（注意：这不是我的作业；我去上学，但他们只教我们计算机基础知识）

- keg

---

我怀疑他们不会告诉你太多关于哈希表。它们实际上很难分析（你需要一个基于概率的正常情况的论证，而不是最坏情况的论证），并且依赖于很多神奇的东西。大多数算法课程的教师更喜欢使用理论上更美丽的结构，如平衡树，因为它们展示了递归论证。但实际代码使用哈希表；它就是这么好用。 - Donal Fellows

Answer 1

维基百科 对于“散列表（Hash Table）”有一个很好的解释。

当您希望通过某个索引查找值时，应使用散列表。

至于何时不应使用它们... 当您不想通过某个索引查找值时（例如，如果您只想迭代访问它们），就不需要使用。

- brabster

---

@keg 哈希函数通常返回一个看起来更或少随机的值，而不是连续的整数。你为什么问这个？ - Matti Virkkunen

@key 这将是完美的哈希函数，就像维基百科文章中所描述的那样。阅读该文章以了解为什么这个函数很难找到，并且如何使事情至少半优化。 - PeterMmm

编写一个好的哈希函数非常非常困难。编写一个糟糕的哈希函数非常容易，而且文献资料不是很好（在密码哈希函数方面更加广泛）。输入语言也非常重要，有些哈希函数在理论上很好，但在实践中速度较慢。 - Donal Fellows

一个简单的方法来获取从0到9或其他数字的范围是将结果与整数10取模。这将限制结果在该范围内，但当然会大大增加冲突的可能性。我认为你永远不会使用只有10个位置的哈希表。如果你不知道，取模基本上返回除法操作的余数。例如，23 / 10 = 2余3。因此，23％10 = 3。 - Chris Cooper

@ItzWarty（猜测您的意思）是的。正如维基百科文章所说，“在许多情况下，哈希表比搜索树或任何其他表查找结构更有效”。 - brabster

Answer 2

你差不多明白了。哈希表是一种非常好的从任意事物（键）映射到任意事物（值）的方法。其思想是应用一个函数（哈希函数），将键转换为数组中存储值的索引；哈希函数的速度通常与键的大小成线性关系，当键的大小远小于条目数时（即典型情况）非常好。

棘手的是，哈希函数通常是不完美的。（完美哈希函数存在，但往往非常特定于特定应用程序和数据集；它们几乎从不值得使用。）处理这个问题有两种方法，并且每种方法都需要将键与值一起存储：一种（开放地址法）是使用预定模式从具有哈希的数组位置向前查找某个空闲位置，另一种（链接法）是在数组中的每个条目上存储悬挂的链表（因此您可以在短列表上进行线性查找）。我阅读源代码的生产代码案例都使用了动态重建哈希表的链接法，当负载因子过高时。

- Donal Fellows

Answer 3

好的哈希函数是一种单向函数，它允许您从任何给定的输入创建分布式值。因此，您将为每个输入值获得相对唯一的值。它们也是可重复的，这意味着任何输入都将始终生成相同的输出。

一个好的哈希函数的例子是SHA1或SHA256。

假设您有一个用户数据库表。列是id、last_name、first_name、telephone_number和address。

虽然这些列中的任何一个都可能有重复项，但我们假设没有行完全相同。

在这种情况下，id只是我们制作的唯一主键（代理键）。id字段实际上不包含任何用户数据，因为我们找不到一个对于用户来说是唯一的自然键，但我们使用id字段来构建与其他表的外键关系。

我们可以像这样从我们的数据库中查找用户记录：

SELECT * FROM users
WHERE last_name = 'Adams'
AND first_name = 'Marcus'
AND address = '1234 Main St'
AND telephone_number = '555-1212';

我们必须通过4个不同的列，使用4个不同的索引来查找我的记录。

然而，您可以创建一个新的“哈希”列，并存储所有四个列组合的哈希值。

String myHash = myHashFunction("Marcus" + "Adams" + "1234 Main St" + "555-1212");

你可能会得到一个类似于 AE32ABC31234CAD984EA8 的哈希值。

你可以将这个哈希值作为数据库中的一列并在其上建立索引。现在你只需要搜索一个索引。

SELECT * FROM users
WHERE hash_value = 'AE32ABC31234CAD984EA8';

一旦我们获得所请求用户的ID，我们可以使用该值在其他表中查找相关数据。

这个想法是哈希函数可以卸载数据库服务器的工作。

碰撞不太可能发生。如果两个用户具有相同的哈希值，则很可能它们具有重复的数据。

- Marcus Adams

---

7年过去了，但我来发表自己的问题时却发现了这个。我不知道为什么你没有任何赞（我的是第一个）。我认为你的解释最清晰、最易懂，适合那些对这个主题知之甚少或一无所知的人。但是：如果我知道主键，我可以查找所有信息，所以我仍然看不出散列有什么优势，相比之下，我还需要查找散列值 - 尤其是如果我冒着与主键不同的碰撞风险。我不明白这如何卸载数据库服务器的负担。如果散列和值都在数据库中，你岂不是仍然会访问数据库吗？ - Malik A. Rumi

我很久以前写了那个答案，早在我真正研究碰撞之前。坦白地说，你不会遇到碰撞的问题。你不必担心它们。虽然理论上可能发生碰撞，但从未有人发现过（对于SHA1或SHA256），而且我怀疑如果发现一个碰撞，它不会发生在两个可读文本字符串之间。它可以卸载数据库的工作，因为数据库服务器不必进行太多搜索。它只搜索一个索引而不是许多个。 - Marcus Adams