地图与列表搜索时间复杂度 [英] Map vs List w.r.t searching Time complexity
问题描述
您可能在某个地方遇到过提到在哈希图/字典/表中查找元素比在列表/数组中查找元素更快的地方.我的问题是为什么?
You might have come across someplace where it is mentioned that it is faster to find elements in hashmap/dictionary/table than list/array. My question is WHY?
(到目前为止，我所做的推断:就我所知，为什么在两个数据结构中它都必须遍历直到达到所需元素的速度更快)
(inference so far I made: Why should it be faster, as far I see, in both data structure, it has to travel throughout till it reaches the required element)
推荐答案
以类推.假设您想找一件特定的衬衫在早上穿.我认为这样做的话，您不必看字面上的每一件衣服.相反，您可能会做一些事情，例如检查梳妆台中的特定抽屉或壁橱的特定区域，然后仅查看那里.毕竟，您(我希望)不会在袜子抽屉里找到衬衫.
Let’s reason by analogy. Suppose you want to find a specific shirt to put on in the morning. I assume that, in doing so, you don’t have to look at literally every item of clothing you have. Rather, you probably do something like checking a specific drawer in your dresser or a specific section of your closet and only look there. After all, you’re not (I hope) going to find your shirt in your sock drawer.
哈希表比列表更快地搜索，因为它们采用类似的策略-它们根据每个项目都有其应有"位置的原理来组织数据，然后仅在该位置查找即可搜索该项目.与此形成对比的是列表，列表中的项目是根据添加的顺序来组织的，并且没有关于每个项目为何位于何处的特定模式.
Hash tables are faster to search than lists because they employ a similar strategy - they organize data according to the principle that every item has a place it "should" be, then search for the item by just looking in that place. Contrast this with a list, where items are organized based on the order in which they were added and where there isn’t a a particular pattern as to why each item is where it is.
更具体地说:一种实现哈希表的常见方法是采用称为链式哈希的策略.这个想法是这样的:我们维护一个 buckets 数组.然后，我们提出一个规则，为每个对象分配一个存储桶编号.当我们将某些东西添加到表中时，我们确定它应该去哪个存储桶号，然后跳转到该存储桶，然后将项目放在那里.要搜索一个项目，我们确定存储桶编号，然后跳到那里，仅查看该存储桶中的项目.假设我们用于分配项目的策略最终会在桶中或多或少地平均分配项目，这意味着我们在搜索时将不必查看哈希表中的大多数项目，这就是为什么散列表的搜索往往比列表快得多.
More specifically: one common way to implement a hash table is with a strategy called chained hashing. The idea goes something like this: we maintain an array of buckets. We then come up with a rule that assigns each object a bucket number. When we add something to the table, we determine which bucket number it should go to, then jump to that bucket and then put the item there. To search for an item, we determine the bucket number, then jump there and only look at the items in that bucket. Assuming that the strategy we use to distribute items ends up distributing the items more or less evenly across the buckets, this means that we won’t have to look at most of the items in the hash table when doing a search, which is why the hash table tends to be much faster to search than a list.
For more details on this, check out these lecture slides on hash tables, which fills in more of the details about how this is done.
希望这会有所帮助！
这篇关于地图与列表搜索时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
