data-structures - 哈希 : Tables, 列表和 map ，哦，天哪？

Question

我一直在寻找一些 混凝土 (外行；非学术)各种类型的哈希数据结构的定义，特别是哈希表、哈希列表和哈希映射。在线搜索为所有这些提供了许多有用的链接，但从未给出明确定义何时适合使用它们。

(1) 从实际的角度来看，这三个有什么区别？

(2) 他们的操作的运行时间有何不同？是否有明确的实例应该使用或避免使用其他类型的哈希？

(3) 这些与 map ADT 有何关系？它们只是它的不同实现，还是完全不同的野兽？

感谢您在这里的任何见解!

Answer 1

有一个包含键和值之间映射的抽象数据结构。它有几个不同的名称，包括 Map , Dictionary , Table , Association Table ， 和更多。

这个数据结构应该支持的最基本的操作是添加、删除和检索一个值，给定它的关联键。围绕这个基本概念有一些变化和补充——例如，一些结构支持迭代所有键值对，一些结构支持每个键多个值等。各种实现之间在时间和空间复杂度上也存在差异。

在此数据结构可用的多种实现中，一些最流行的实现使用 hash functions快速访问时间。这些实现有时被称为 Hash Table或 Hash Map ，您可以 read more about them in Wikipedia .哈希表实现之间的性能也有所不同，有些达到分摊 O(1) 插入和访问复杂性(以使用大量空间的代价)。

A 哈希列表 ，另一方面，是另一回事，更多的是关于数据结构的使用，而不是它的实际结构。散列列表通常只是散列值的常规列表，没有什么特别之处。它在验证大量数据的完整性时使用 - 在这种情况下，它允许独立验证各种数据块，从而只修复或检索坏块。这与使用单个散列值对整个数据进行散列相反，在这种情况下，失败意味着必须修复或再次检索所有数据。