language-agnostic - 什么是哈希表和哈希映射以及它们的典型用例？

Question

我最近几次遇到这些术语，但我很困惑它们是如何工作的以及它们通常何时实施？

Answer 1

嗯，这样想吧。

如果你使用一个数组，一个简单的基于索引的数据结构，并用随机的东西填充它，当你用数据填充它时，找到一个特定的条目会变得越来越昂贵，因为你基本上必须从一端朝向另一端，直到你找到你想要的。

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

另一方面，哈希表有一个相关的函数，它接受一个条目，并将其简化为一个数字，一个哈希键。然后将该数字用作数组的索引，这是您存储条目的位置。

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

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

因此，当您将某些内容插入哈希表时，该函数会将键减少为一个数字，该数字用作此（空）数组的索引，这是您存储数据的地方，包括键和相关数据。

然后，稍后，您想找到一个您知道密钥的特定条目，因此您通过相同的函数运行该密钥，获取它的哈希键，然后转到哈希表中的那个特定位置并在那里检索数据。

理论认为，将您的密钥减少为哈希密钥的函数，即该数字，在计算上比线性搜索便宜得多。

典型的哈希表没有无限数量的可用于存储的元素，因此该数量通常会进一步减少到适合数组大小的索引。一种方法是简单地将索引的模数与数组的大小进行比较。对于大小为 10 的数组，索引 0-9 将直接映射到索引，索引 10-19 将再次映射到 0-9，以此类推。

一些键将减少到与哈希表中现有条目相同的索引。此时，直接比较实际的键，所有规则都与比较键的数据类型相关联（例如，普通字符串比较）。如果完全匹配，则要么忽略新数据（它已经存在），要么覆盖（替换该键的旧数据），或者添加它（多值哈希表）。如果没有匹配，这意味着尽管哈希键是相同的，但实际的键不是，您通常会找到一个新的位置来存储该键+数据。

冲突解决有很多实现，最简单的一种就是直接去数组中的下一个空元素。不过，这个简单的解决方案还有其他问题，因此找到正确的解析算法也是哈希表的一个很好的练习。

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

将密钥减少为数字的函数不会产生线性值，即。“AAA”变为 1，然后“AAB”变为 2，因此哈希表不按任何典型值排序。

这里也有一篇很好的关于该主题的维基百科文章。

Answer 2

lassevk 的回答非常好，但可能包含太多细节。这是执行摘要。我故意省略了某些相关信息，您可以放心地忽略 99% 的时间。

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

哈希表很神奇

严重地。它是一个神奇的数据结构，几乎可以保证三件事。（也有例外。您可以在很大程度上忽略它们，尽管有一天学习它们可能对您有用。）

1) 哈希表中的所有内容都是一对的一部分——有一个键和一个值。您通过指定您正在操作的键来输入和取出数据。

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

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

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

当哈希表的魔力适合我们的问题时，我们会使用哈希表。

例如，缓存经常使用哈希表结束——例如，假设我们在一所大学有 45,000 名学生，并且某个进程需要保留所有学生的记录。如果您经常通过 ID 号引用学生，那么ID => student缓存非常有意义。您正在为此缓存优化的操作是快速查找。

当您不想全力以赴并更改对象本身时，哈希对于存储数据之间的关系也非常有用。例如，在课程注册期间，能够将学生与他们正在学习的课程联系起来可能是一个好主意。但是，无论出于何种原因，您可能不希望 Student 对象本身知道这一点。studentToClassRegistration在你做任何你需要做的事情时， 使用散列并保留它。

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

何时不使用哈希表

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

排序。 如果你不能迭代，排序也是一种痛苦。

从 value 到 key。使用两个哈希表。相信我，我只是为你减轻了很多痛苦。

Answer 3

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

然而，如果我们谈到 Java，显着的区别在于哈希表本质上是同步的，因此是线程安全的，而哈希映射不是线程安全的集合。

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

如果您需要了解散列是如何工作的，我建议您在谷歌上搜索一下数据结构和散列技术。

Answer 4

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