data-structures - 哈希表和随机访问表的区别

Question

哈希表和随机访问表有什么区别。我觉得它们很相似，但想找出确切的区别，谷歌搜索对我没有多大帮助。

Answer 1

一般来说，哈希表能够将各种实体之类的东西映射到其他实体。根据编程语言，它可能将元组映射到字符串、字符串到对象、字符串到字符串等等——无限的可能性。

常规数组允许您使用整数索引来寻址实体：

数组[索引] ==> 字符串例如

相反，哈希映射又名哈希表又名字典又名关联数组又名哈希等让您 - 除其他可能性外 - 将字符串映射到整数，例如：

hash_map['Bill'] => 23 等

有关基本了解，请访问：

• 维基哈希表
• Python 字典
• PHP 数组

为了更深入的理解，我推荐这两本书：

• 萨奇维克的“算法”
• Drozdek 的“数据结构和算法”

Answer 2

哈希表（又名哈希映射，或关联数组或字典或只是哈希）是一种特定类型的随机访问数据结构。

哈希表是“随机访问”，因为它允许在恒定时间内对单个成员进行直接、“索引”访问。数组也可以被认为是一种随机访问数据结构，因为您可以通过其索引获取单个元素。

相比之下，链表不是随机访问数据结构，因为您需要遍历其成员才能找到特定元素。