哈希:表格,列表和地图,哦,我的？

Question

我一直试图找到各种类型的哈希数据结构的具体(非专业;非超学术)定义,特别是哈希表,哈希列表和哈希映射.在线搜索为所有这些提供了许多有用的链接,但从未明确定义何时适合使用其他链接.

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

(2)他们的运营运行时间有何不同？是否应该使用或避免使用其他类型的哈希值？

(3)每个如何与地图ADT有关？它们只是不同的实现,还是完全不同的野兽？

感谢您的任何见解!

Answer 1

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

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

在可用于此数据结构的多种实现中，一些最流行的实现利用哈希函数来实现快速访问。这些实现有时被称为Hash Table或Hash Map，您可以在 Wikipedia 中阅读有关它们的更多信息。哈希表实现之间的性能也有所不同，有些达到了摊销 O(1) 插入和访问复杂性（以使用大量空间为代价）。

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