哈希表和哈希映射是什么，它们的典型用例是什么？

Question

我最近几次遇到了这些术语，但我很困惑它们是如何工作的以及通常在什么情况下实现？

- Kamil Zadora

Answer 1

那么，这样想。

如果您使用数组，一种简单的基于索引的数据结构，并将其填满随机内容，则随着数据的填充，查找特定条目将变得越来越昂贵，因为您基本上必须从一端开始向另一端搜索，直到找到所需的元素。

如果您想更快地访问数据，则通常会对数组进行排序并使用二进制搜索。然而，这会增加查找现有值的速度，但使插入新值变慢，因为在需要在中间插入元素时需要移动现有元素。

另一方面，哈希表具有一个相关函数，该函数获取条目并将其减少为一个数字，即哈希键。然后将此数字用作数组中的索引，并在此处存储条目。

哈希表围绕一个数组展开，该数组最初为空。空并不意味着长度为零，数组始终具有大小，但数组中的所有元素都不包含任何内容。

每个元素都有两个属性：数据和标识数据的键。例如，美国邮政编码列表将是一种邮政编码->名称类型的关联。该函数减少键，但不考虑数据。

因此，当您将某些东西插入哈希表时，函数会将键减少为数字，该数字用作此（空）数组中的索引，并在此处存储数据，包括键和相关数据。

然后，稍后，您想要查找具有特定键的特定条目，因此将密钥通过相同的函数运行，获取其哈希键，并转到哈希表中的那个特定位置，并检索其中的数据。

理论认为，将您的键缩小为哈希键的函数（即该数字）的计算成本比线性搜索低得多。

一个典型的哈希表并没有无限数量的元素可供存储，因此通常将数字缩小到适合数组大小的索引中。其中一种方法是将索引对数组大小取模。例如，对于大小为10的数组，索引0-9将直接映射到一个索引，而索引10-19将重新映射到0-9，以此类推。

一些键将被缩减到与哈希表中现有条目相同的索引。此时，直接比较实际键，包括比较键的数据类型的所有规则（例如普通字符串比较）。如果完全匹配，则可以忽略新数据（它已经存在），或者覆盖旧数据（替换该键的旧数据），或者添加它（多值哈希表）。如果没有匹配项，则表示虽然哈希键相同，但实际键不同，您通常会找到一个新位置来存储该键+数据。

冲突解决方案有许多实现方法，最简单的方法是转到数组中的下一个空元素。这种简单的解决方案也存在其他问题，因此找到正确的解决方案算法也是哈希表的好练习。

哈希表也可以增长，如果它们完全填满（或接近），通常会创建一个新的大小为新大小的数组，再次计算所有索引，并将项目放置在它们的新位置中。

将键缩小为数字的函数并不生成线性值，例如“AAA”变为1，然后“AAB”变为2，因此哈希表不按任何典型值进行排序。

该主题也有一个很好的维基百科文章，链接在这里：here。

- lassevk

---

据我所知，这些哈希值不需要具备加密安全性，因此您可以选择最快的哈希算法，因为通常您并不试图通过这些隐藏任何内容。 - Kebman

Answer 2

lassevk的回答非常好，但可能包含了一些细节。以下是摘要，我有意省略了某些相关信息，您可以99%的时间安全地忽略它们。

在99%的情况下，哈希表和哈希映射之间没有重要区别。

哈希表是一个神奇的数据结构

说真的。这是一个神奇的数据结构，几乎保证了三件事情。（有例外情况。您可以基本忽略它们，但有一天学习它们可能对您有用。）

1）哈希表中的所有内容都是一对--有一个键(key)和一个值(value)。通过指定要操作的键，将数据放入哈希表并取出哈希表中的数据。

2）如果您正在使用哈希表上的单个键执行任何操作，则速度非常快速。 这意味着put(key, value)，get(key)，contains(key)和remove(key)都非常快速。

3）通用哈希表无法执行未列在#2中的任何操作！ （通过“失败”，我们的意思是它们非常慢。）

我们什么时候使用哈希表？

当哈希表的魔法与我们的问题相匹配时，我们使用哈希表。

例如，缓存通常会使用哈希表--例如，假设我们在大学里有45,000名学生，并且某个过程需要保留所有学生的记录。如果您经常使用学生的ID号来引用学生，则ID => student缓存非常合理。您正在优化此缓存的操作是快速查找。

哈希还可以非常有用地存储数据之间的关系，当您不想彻底更改对象本身时。例如，在课程注册期间，能够将学生与他们参加的课程联系起来可能是一个好主意。但出于某种原因，您可能不希望学生对象本身知道这一点。使用studentToClassRegistration哈希表并在进行任何必要操作时保留它。

除非您需要执行以下操作，否则它们也是数据结构的相当不错的首选：

不适合使用哈希表的情况

遍历元素。哈希表通常不能很好地进行迭代。（通常指通用哈希表，特定的实现有时包含用于减少其迭代负担的链接列表。例如，在Java中，LinkedHashMap 可以让您快速遍历键或值。）

排序。如果无法迭代，则排序也会非常麻烦。

从值到键。使用两个哈希表。相信我，我刚刚为您避免了很多痛苦。

- Patrick McKenzie

Answer 3

如果讲到Java，两者都是允许添加、删除和更新对象，并在内部使用哈希算法的集合。

然而，如果我们从Java的角度来看，显著的区别在于Hashtable本质上是同步的，因此是线程安全的，而HashMap不是线程安全的集合。

除了同步之外，存储和检索对象的内部机制在两种情况下都是哈希。

如果您想了解哈希如何工作，我建议在数据结构和哈希技术上进行一些搜索。

- Nrj

Answer 4

哈希表/哈希映射将一个值（为了消除歧义而称为“键”）与另一个值相关联。你可以将它们视为一种字典（单词：定义）或数据库记录（键：数据）。

- ΤΖΩΤΖΙΟΥ