散列表其实是一个稀疏数组（总是有空白元素的数组），通常会把散列表里的单元叫做表元，表元的大小是一致的，可以通过偏移量的方式来访问表元。dict中一组键值对占用一个表元。python会保证有大约三分之一的空间是空白的，超过阈值会把原有散列表复制到更大的空间。
mydict[key]的查找过程：首先会调用hash(key)计算散列值，取散列值的低几位作为偏移量进行表元查找，如果找到的表元为空，则KeyError；如果不为空，则会找到表元里有一对found_key:found_value，如果found_key=key，则返回found_value，如果不等，说明发生了冲突，这时会在散列值中再取几位，然后用特殊方法处理一下，把得到的数字当作索引来寻找表元，重复上面操作。添加和更新操作类似。
散列表查找.PNG
网友评论