我没有在动态语言中使用哈希表以外的经验，所以最近才发现它们是通过对键进行哈希然后使用哈希值存储值来实现的。 我不理解的是，为什么不将键（字符串、数字或其他）作为关键字直接与值一起存储，而要对其进行哈希并存储它。
11个回答
20
这是一个近似重复的问题：为什么在哈希表中使用哈希码而不是索引？
简而言之，你可以非常快速地检查一个键是否已经被存储，并且同样快速地存储一个新的映射关系。否则，您将不得不保持一个已排序的键列表，这将使从中存储和检索映射关系变得更加缓慢。
- BobMcGee
1
旧线程，但哈希表仅在冲突解决正确时才有效。问题在于通常使用开链通过链接列表来进行冲突解决，而这使用原始键值。如果原始键不唯一，则无法使用此方法。但是，如果我们必须使用唯一的原始键，则为什么要使用哈希表呢？我们可以使用简单的键/值映射并获得所有相同的优点。 - Jackson
10
什么是哈希表？
它也被称为哈希映射，是一种用于实现关联数组的数据结构。它是一个可以将键映射到值的结构。
它如何工作？
哈希表使用哈希函数计算出一个索引，该索引指向一个包含正确值的桶或插槽数组。
下面的图表清楚地解释了这个过程。
优点：
在维度合适的哈希表中，每次查找的平均成本与表中存储的元素数无关。
许多哈希表设计也允许任意插入和删除键值对。
在许多情况下，哈希表被发现比搜索树或任何其他表查找结构更有效。
缺点：
当条目数非常少时，哈希表不太有效。（然而，在某些情况下，通过将哈希值与键一起保存，可以减轻计算哈希函数的高成本。）
用途：
它们广泛用于各种计算机软件中，特别是关联数组、数据库索引、缓存和集合。
- Durai Amuthan.H
9
我不理解的是为什么值没有与键（字符串，数字或其他）一起存储为键。
如何实现？
计算机只识别数字。哈希表是一个“表”，即一个“数组”，而归根结底，数组只能通过整数非负索引访问。其他所有内容都是欺骗手段。动态语言可以使用字符串键 - 它们使用的是欺骗手段。
其中一种这样的技巧，通常也是最优雅的技巧，就是计算密钥的可重复的数字“哈希”号码，并使用它作为索引。
（还有其他考虑因素，例如压缩键范围，但这是首要问题。）
如何实现？
计算机只识别数字。哈希表是一个“表”，即一个“数组”，而归根结底，数组只能通过整数非负索引访问。其他所有内容都是欺骗手段。动态语言可以使用字符串键 - 它们使用的是欺骗手段。
其中一种这样的技巧，通常也是最优雅的技巧，就是计算密钥的可重复的数字“哈希”号码，并使用它作为索引。
（还有其他考虑因素，例如压缩键范围，但这是首要问题。）
- Konrad Rudolph
4
简而言之：哈希表可以实现O(1)的查询/插入/删除操作，而排序结构（通常实现为平衡二叉树）需要O(logn)时间来完成相同的操作。
你可能会问为什么要用哈希表？如果你打算只存储(key, value)对，那么你的查找/插入/删除速度会有多快呢？你是否会在整个数组/列表上运行一个O(n)循环？
哈希值的全部意义在于它允许将所有键转换为一组有限的哈希值。这使我们能够将键存储在有限数组的插槽中（实现快速操作-而不是搜索整个列表，只搜索具有相同哈希值的密钥），即使可能键的数量非常大或无限（例如，键可以是字符串、非常大的数字等）。使用好的哈希函数，极少数的键才会具有相同的哈希值，并且所有操作有效地都是O(1)。
如果你对哈希和哈希表不熟悉，这可能不太容易理解。在这种情况下，最好是参考一本好的算法/数据结构书籍的相关章节（我推荐《算法导论》）。
你可能会问为什么要用哈希表？如果你打算只存储(key, value)对，那么你的查找/插入/删除速度会有多快呢？你是否会在整个数组/列表上运行一个O(n)循环？
哈希值的全部意义在于它允许将所有键转换为一组有限的哈希值。这使我们能够将键存储在有限数组的插槽中（实现快速操作-而不是搜索整个列表，只搜索具有相同哈希值的密钥），即使可能键的数量非常大或无限（例如，键可以是字符串、非常大的数字等）。使用好的哈希函数，极少数的键才会具有相同的哈希值，并且所有操作有效地都是O(1)。
如果你对哈希和哈希表不熟悉，这可能不太容易理解。在这种情况下，最好是参考一本好的算法/数据结构书籍的相关章节（我推荐《算法导论》）。
- MAK
3
哈希表的概念是为了提供对其项目的直接访问。因此，它计算键的“哈希码”并使用它来存储项目，而不是使用键本身。
这个想法是每个键只有一个哈希码。很多时候，生成哈希码的哈希函数是将质数除以它的余数作为哈希码。
例如，假设您有一个包含13个位置和一个整数作为键的表格，那么可以使用以下哈希函数：
f(x) = x % 13
这个想法是每个键只有一个哈希码。很多时候，生成哈希码的哈希函数是将质数除以它的余数作为哈希码。
例如，假设您有一个包含13个位置和一个整数作为键的表格，那么可以使用以下哈希函数：
f(x) = x % 13
- CARLOS LOTH
2
我不明白的是为什么不将值与键（字符串、数字或其他）一起存储作为键，而是要将其哈希并存储。
嗯，你有什么提议可以实现O（1）的查找呢？
哈希表的目的基本上是通过将键转换为数组索引，然后返回该索引处的数组内容来提供O（1）的查找。为了实现任意键的查找，您需要：
1. 将键转换为数组索引的方法（这就是哈希的目的） 2. 解决冲突的方法（具有相同哈希代码的键） 3. 数组大小调整的方法，当它太小（导致太多冲突）或太大（浪费空间）时。
嗯，你有什么提议可以实现O（1）的查找呢？
哈希表的目的基本上是通过将键转换为数组索引，然后返回该索引处的数组内容来提供O（1）的查找。为了实现任意键的查找，您需要：
1. 将键转换为数组索引的方法（这就是哈希的目的） 2. 解决冲突的方法（具有相同哈希代码的键） 3. 数组大小调整的方法，当它太小（导致太多冲突）或太大（浪费空间）时。
- Michael Borgwardt
1
通常哈希表的目的是存储一些稀疏值 -- 也就是存在大量键和少量要存储的内容。以字符串为例，可能存在无数个可能的字符串。如果你正在存储程序中使用的变量名，则实际上只使用了相对较小数量的这些字符串，尽管你事先不知道它们是什么。
- Joel
2
3从技术上讲，有可数无限个有限长度的可能字符串。;) - Mike Daniels
从技术上讲，有有限的可能字符串 :P - amara
0
在某些情况下，密钥可能非常长或大，因此保留这些密钥的副本是不切实际的。首先对它们进行哈希处理可以减少内存使用量，并提高查找速度。
- Aaron
1
1关键字始终存储在哈希映射中。否则，您无法处理哈希冲突（因为您无法检查传入的关键字是否真正等于存储的关键字）。因此，您不会节省内存。 - sepp2k
0
哈希表用于在（一定时间内）恒定数量的位置中存储一组值及其键。在简单情况下，假设您想使用哈希函数 i％10 保存从0到10000的每个整数。
这将创建一个哈希表，其中包含1000个块（通常是数组），每个块深度为10个元素。因此，如果您要搜索1234，则会立即知道要在123的表条目中搜索，然后开始比较以找到精确匹配项。当然，这并不比仅使用10000个元素的数组好多少，但这只是为了演示。
当您不知道将有多少元素时，哈希表非常有用，但哈希函数的碰撞次数要比总元素数少得多。（这使得哈希函数“哈希（x）= 0”非常糟糕。）您的表中可能有空位，但理想情况下，大部分都将有一些数据。
- Jon
0
还要考虑速度。如果您的键是字符串，而您的值存储在一个数组中，那么您的哈希可以在“近”恒定的时间内访问任何元素。与搜索字符串及其值进行比较。
- neuroguy123
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接