Python 是否在底层优化了字典查找？

Question

例如：

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

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

如果我想看看关键“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 维基