arrays - 为什么在 HashMap 中查找项目比在数组中查找项目更快？

Question

您可能在某个地方提到过在 hashmap/dictionary/table 中查找元素比在 list/array 中查找元素更快。我的问题是为什么？

(到目前为止我做出的推论:为什么它应该更快，据我所知，在这两种数据结构中，它必须遍历直到到达所需的元素)

Answer 1

我们来类比一下。假设您想找到一件特定的衬衫早上穿。我认为，这样做时，你不必仔细查看你拥有的每一件衣服。相反，您可能会做一些事情，例如检查梳妆台中的特定抽屉或衣柜的特定部分，然后只看那里。毕竟，(我希望)你不会在 socks 抽屉里找到你的衬衫。

哈希表的搜索速度比列表更快，因为它们采用了类似的策略 - 它们根据每个项目都有它“应该”在的位置的原则来组织数据，然后通过在该位置查找来搜索该项目。将此与列表进行对比，列表中的项目是根据添加顺序进行组织的，并且没有特定的模式来说明每个项目为何位于其所在位置。

更具体地说:实现哈希表的一种常见方法是使用称为“链式哈希”的策略。这个想法是这样的:我们维护一个存储桶数组。然后我们提出一个规则，为每个对象分配一个桶号。当我们向表中添加某些内容时，我们确定它应该转到哪个存储桶编号，然后跳转到该存储桶，然后将项目放在那里。要搜索项目，我们确定存储桶编号，然后跳到那里并仅查看该存储桶中的项目。假设我们用于分配项目的策略最终将项目或多或少均匀地分布在存储桶中，这意味着我们在进行搜索时不必查看哈希表中的大多数项目，这就是为什么哈希表的搜索速度往往比列表快得多。

有关此内容的更多详细信息，请查看 these lecture slides on hash tables ，其中填写了有关如何完成此操作的更多详细信息。

希望这有帮助!