python - Python 是否优化了引擎盖下的字典查找？

Question

例如:

d = {"John": "Doe", "Paul": "Allen", "Bill": "Gates"}

想象一下这有几千/百万这样的名字，每个名字都是唯一的。

如果我想查看 key “Paul”是否存在，它在幕后做了什么？

Answer 1

Python 的字典实现通过要求键对象提供“散列”函数将字典查找的平均复杂度降低到 O(1)。这样的散列函数获取关键对象中的信息并使用它来生成一个称为散列值的整数。然后使用此哈希值来确定应将此(键，值)对放入哪个“桶”。此查找函数的伪代码可能类似于:

def lookup(d, key):
    '''dictionary lookup is done in three steps:
       1. A hash value of the key is computed using a hash function.

       2. The hash value addresses a location in d.data which is
          supposed to be an array of "buckets" or "collision lists"
          which contain the (key,value) pairs.

       3. The collision list addressed by the hash value is searched
         sequentially until a pair is found with pair[0] == key. The
         return value of the lookup is then pair[1].
   '''
   h = hash(key)                  # step 1
   cl = d.data[h]                 # step 2
   for pair in cl:                # step 3
       if key == pair[0]:
           return pair[1]
   else:
       raise KeyError, "Key %s not found." % key

来自Python Wiki