我一直在寻找一些具体（非超学术）的定义，以了解各种哈希数据结构，特别是哈希表、哈希列表和哈希映射。在线搜索提供了许多有用的链接，但从来没有清晰地定义什么时候应该使用其中的哪一个。
(1) 从实际角度来看，这三者有何区别？
(2) 它们的操作运行时间有何不同？是否存在明确的情况，应该使用或避免使用其他类型的哈希？
(3) 这些如何与 Map ADT 相关联？它们都是它的不同实现，还是完全不同的东西？
感谢任何见解！
哈希表、列表和映射，它们是什么？
7
- IAmYourFaja
7
1根据维基百科上提供的信息，我不确定为什么这个被投票支持 - 它未能通过“显示研究努力”的测试。 - Ed Staub
因为这是一个好问题，有助于 SO 社区的全面发展，Ed Staub！ - IAmYourFaja
从Java的角度补充Oka的答案：https://dev59.com/E3VD5IYBdhLWcg3wQJOT - user953229
1考虑到在谷歌上搜索这些术语会立即找到同等或更好的易懂相关信息，我不认为试图使SO内容在这方面更加“全面”有意义。我更希望看到SO专注于“去他们没有去过的地方”——那些其他地方要么没有，要么不容易搜索，要么在其他地方使用起来很困难的信息。当你开始发布纯粹为了引导点击量而发布的内容——为了“全面”，它就开始走向内容农场的滑坡。（我假设你是SE员工Mara——是吗？） - Ed Staub
那伤害了我的感情，Ed Staub。现在我的偏头痛又开始了。还有那些声音.....那些声音。 - IAmYourFaja
显示剩余2条评论
1个回答
2
有一个抽象的数据结构，包含键和值之间的映射关系。它有几个不同的名称，包括Map、Dictionary、Table、Association Table等。
这个数据结构应该支持最基本的操作，如添加、删除和检索与其关联的键的值。围绕这个基本概念有一些变化和补充 - 例如，一些结构支持遍历所有键值对，一些结构支持每个键多个值等。不同实现之间的时间和空间复杂度也有所不同。
在这个数据结构的多种实现中，一些最受欢迎的实现利用哈希函数实现快速访问。这些实现有时被称为哈希表或哈希映射，您可以在维基百科上了解更多信息。哈希表实现的性能也有所不同，有些可以实现平摊O(1)的插入和访问复杂度（代价是使用大量的空间）。
另一方面，哈希列表是一种不同的东西，更多关于数据结构的使用而非它的实际结构。哈希列表通常只是一个普通的哈希值列表，没有什么特别之处。当验证大块数据的完整性时使用它——在这种情况下，它允许各种数据块独立验证，从而可以修复或检索仅有问题的块，而不是使用单个哈希值哈希整个数据块，这种情况下失败意味着所有数据必须再次修复或检索。
这个数据结构应该支持最基本的操作，如添加、删除和检索与其关联的键的值。围绕这个基本概念有一些变化和补充 - 例如，一些结构支持遍历所有键值对，一些结构支持每个键多个值等。不同实现之间的时间和空间复杂度也有所不同。
在这个数据结构的多种实现中，一些最受欢迎的实现利用哈希函数实现快速访问。这些实现有时被称为哈希表或哈希映射，您可以在维基百科上了解更多信息。哈希表实现的性能也有所不同，有些可以实现平摊O(1)的插入和访问复杂度（代价是使用大量的空间）。
另一方面，哈希列表是一种不同的东西，更多关于数据结构的使用而非它的实际结构。哈希列表通常只是一个普通的哈希值列表，没有什么特别之处。当验证大块数据的完整性时使用它——在这种情况下，它允许各种数据块独立验证，从而可以修复或检索仅有问题的块，而不是使用单个哈希值哈希整个数据块，这种情况下失败意味着所有数据必须再次修复或检索。
- Oak
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接