为什么在哈希映射中查找项目比在数组中查找项目更快？

Question

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

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

Answer 1

让\xe2\x80\x99s 以此类推。假设您想找到一件特定的衬衫早上穿。我认为，这样做时，您不必逐字查看您拥有的每件衣服。相反，您可能会做一些事情，例如检查梳妆台中的特定抽屉或衣柜的特定部分，然后只看那里。毕竟，你\xe2\x80\x99（我希望）不会在你的袜子抽屉里找到你的衬衫。

\n\n

哈希表的搜索速度比列表更快，因为它们采用了类似的策略 - 它们根据每个项目都有一个位置 \xe2\x80\x9cshould\xe2\x80\x9d 的原则来组织数据，然后通过以下方式搜索该项目看着那个地方。将此与列表进行对比，列表中的项目是根据添加顺序进行组织的，并且没有\xe2\x80\x99t 特定的模式来解释每个项目为何位于其所在位置。

\n\n

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

\n\n

有关这方面的更多详细信息，请查看有关哈希表的讲座幻灯片，其中填充了有关如何完成此操作的更多详细信息。

\n\n

希望这可以帮助！

\n