什么是哈希表，在编程中它可以用在哪些地方？

Question

我经常听到人们谈论哈希、哈希映射和哈希表。 我想知道它们是什么，以及在哪里可以最好地使用它们。

- Saif Bechan

Answer 1

首先你可能需要阅读这篇文章。

当你使用列表并且正在寻找特定的项时，通常需要迭代整个列表。当你有大型列表时，这是非常昂贵的。
哈希表可以更快地完成此操作，在最佳情况下只需一次访问即可获取所需的项。
它是如何工作的？就像字典一样......当你在字典中查找单词“hashtable”时，你不会从“a”下的第一个单词开始。相反，你会直接前往字母“h”。然后是“ha”、“has”等，直到找到你的单词。你在字典中使用索引来加速搜索。
哈希表基本上也是这样做的。每个项都有一个唯一的索引（所谓的hash）。你使用这个哈希值进行查找。哈希值可以是普通链接列表中的索引。例如，你的哈希值可以是数字2130，这意味着你应该在列表的位置2130处查找。在已知索引的普通列表中进行查找非常容易和快捷。
整个方法的问题是所谓的哈希函数，它将此索引分配给每个项。当你在查找项时，你应该能够提前计算出索引。就像在真正的字典中，你看到单词“hashtable”以字母“h”开头，因此你知道大致位置。
一个好的哈希函数提供平均分布在所有可能哈希值的空间中的哈希码。当然它也尽量避免冲突。当两个不同的项得到相同的哈希码时会发生冲突。
例如，在C＃中，每个对象都有一个GetHashCode()方法，它为对象提供哈希值（不一定是唯一的）。这可用于在字典内进行查找和排序。

当你开始使用哈希表时，你应该始终记住正确处理碰撞的方法。在大型哈希表中很容易发生两个对象具有相同的哈希值的情况（也许是由于你GetHashcode()方法的重载有问题，或者可能是其他原因造成的）。

- tanascius

---

一个解释得很清楚的答案 - Kasun Siyambalapitiya

你说的“正确处理冲突”是什么意思？据我所知，我们只需要编写良好的哈希函数来尽量减少冲突（以获得更好的性能）。但是，并不需要“处理冲突”。如果哈希值发生冲突，它只会通过执行等值比较来转到下一级检查。 - Teddy

@Teddy：哈希函数只负责散列。没有“下一层”。这就是我所说的“处理冲突”的意思。当有多个匹配项时，您必须通过例如相等比较来进行选择。 - tanascius

@tanascius 我的意思是内置集合HashMap使用hashCode函数作为第一级检查。如果两个项具有相同的hashCode，则HashMap将继续进行下一级检查，即equals检查。因此，我们的工作就是为我们的自定义对象编写一个体面的hashCode实现。 - Teddy

@Teddy HashMap是Java特定的，我不知道确切的行为。但总体上问题并不是Java特定的。但你是对的，某些实现可能会有所不同，并已经内置了下一级检查。 - tanascius

Answer 2

在非加密的意义下，哈希是一个涵盖性的术语，用于对输入进行处理并生成输出以便进行标识。一个简单的哈希示例是将字符串中字母的总和相加，即:

f(abc) = 6

请注意，这个简单的哈希方案会在字符串abc、bca、ae等之间产生碰撞。一个有效的哈希方案应该为每个字符串生成不同的值。

哈希表和哈希表是数据结构（如数组和列表），它们使用哈希来存储数据。在哈希表中，通过产生哈希（从提供的键或对象本身中产生）来确定对象存储在表中的位置。这意味着只要哈希表的用户知道键，检索对象就非常快速。

相比之下，在列表中，您需要以某种方式搜索列表才能找到所需的对象。这也代表了哈希表的缺点，即没有知道键的情况下在其中查找对象非常复杂，因为对象在表中的存储位置与其值或输入时间无关。

哈希映射类似于哈希表，但每个对象示例仅存储一次（因此不需要提供密钥，对象本身就是密钥）。

这当然是一个非常简单的解释，我建议你从这里深入阅读。我希望我没有犯任何愚蠢的错误。=)

- mikek

Answer 3

HashMap基本上允许您使用标识符存储项目。它们以表格格式存储，其中标识符使用哈希算法进行散列。

通常，与搜索树等相比，检索项目的效率更高。

您可能会发现这个链接有用：http://www.relisoft.com/book/lang/pointer/8hash.html

希望能对您有所帮助，

Chris

- Chris

Answer 4

哈希表相对于其他搜索标准可以节省大量时间。我们有一个哈希键，它对应一个哈希码，进一步帮助找到其索引值。在实现上，哈希表将一个字符串转换为整数并重新映射它以将其转换为数组的索引，从而帮助查找所需的值。

要详细了解哈希表中的冲突处理，我们可以考虑使用链表而不是数组。

有一个短视频可用于理解。 此处提供： 实现示例--> https://www.youtube.com/watch?v=shs0KM3wKv8

示例： int hashCode(String s) { 逻辑 }

- Shivangi Shandilya

Answer 5

Hashmap 用于以键值对的形式存储数据。我们可以使用 Hashmap 在应用程序中存储对象，并在同一应用程序中进一步使用它来存储、更新和删除值。Hashmap 键和值存储在桶中，以特定条目的形式存储，该条目的位置是使用 Hashcode 函数确定的。这个 hashcode 函数决定了值存储的哈希位置。有关 Hashmap 工作原理的详细说明，请参见此视频：https://youtu.be/iqYC1odZSNo

- tek2tor