散列表算法

为了获取my_dict[search_key]背后的值，Python首先会调用hash(search_key)来计算search_key的散列值，把这个值最低的几个数字当作偏移量，在散列表中查找表元（具体取几位，得看当前散列表的大小）。若找到的表元是空的，则抛出KeyError异常。若不是空的，则表元里会有一对found_key:found_value。这时候Python会检查search_key == found_key是否为真，如果他们相等的话，就会返回found_value。

如果search_key和found_key不匹配的话，这种情况称为散列冲突。发生这种情况是因为，散列表所做的其实是把随机的元素映射到只有几位的数字上，而散列表本身的索引又只依赖于这个数字的一部分。为了解决散列冲突，算法会在散列表中另外再取几位，然后用特殊方法处理一下，把新得到的数字再当作索引来寻找表元。若这次找到的表元是空的，则同样抛出KeyError；若非空，或者键匹配，则返回这个值；或者又发现了散列冲突，则重复以上的步骤。

添加新元素和更新现有键值的操作几乎跟上面一样。只不过对于前者，在发现空表元的时候会放入一个新元素；对于后者，在找到相对应的表元后，原表里的值对象会被替换成新值。

另外再插入新值时，Python可能会按照散列表的拥挤程度来决定是否重新分配内存为它扩容。如果增加了散列表的大小，那散列值所占的位数和用作索引的位数都会随之增加，这样做的目的是为了减少发生散列冲突的概率。

表面上看，这个算法似乎很费事，而实际上就算dict里有数百万个元素，多数的搜索过程中并不会有冲突的发生，平均下来每次搜索可能会有一到两次冲突。在正常情况下，就算是最不走运的键所遇到的冲突的次数用一只手也能数过来。