dict为什么查这么快：从哈希冲突到开放寻址

一直知道dict是哈希表、查询O(1)，但O(1)是怎么来的、最坏会发生什么，我是读了CPython的dictobject实现笔记后才算真明白。顺便发现dict的内部结构和教科书版的「链地址法」并不一样。

查找的路径

dict底层维护一个Entry数组。查找key时先用hash(key)算出哈希值，再对数组长度取模定位槽位，比较槽里存的哈希值和key是否都相等，命中就返回。整条路径没有遍历，所以快。Python内置的str、int哈希稳定且分布均匀，这也是dict好用的前提。

冲突怎么处理

两个key落到同一个槽就是冲突。教科书常用链地址法（每个槽挂链表），CPython用的是开放寻址的变体：

# 简化的探测逻辑
perturb = hash_val
i = hash_val % table_size
while slot_taken(i):
    i = (i * 5 + perturb + 1) % table_size
    perturb >>= 5

真实代码里的探测序列把哈希值的高位也搅进来（perturb右移混合），避免极端情况下扎堆踩同一条线性路径。空槽是查找终止的条件，所以删除一个元素不能简单清空槽位，否则会截断后续元素的探测链——dict用DKIX_DUMMY墓碑标记「这里曾有元素，还得继续找」。

扩容与顺序

装载因子超过三分之二就触发扩容，按使用量翻倍申请新表并rehash。Python 3.6起dict改用紧凑布局：一坨连续的entry数组加一个小的索引数组，稀疏的索引和紧凑的数据分离，内存占用比老版本降了20%以上，还顺带让遍历顺序等于插入顺序，3.7起正式成为语言保证。

顺带弄懂的几件事

• key必须可哈希，list不能当key，tuple里嵌了list也不行
• 自定义类默认按id哈希，想按值判等就同时实现__hash__和__eq__，且二者必须一致
• hash(-1)是个特例，被替换成-2，防止和哨兵值冲突
• set用的是另一套更紧凑的实现，但思路同源

看完实现再看日常用法，内存和性能的很多直觉都对上了号。理解一个数据结构的最好方式，就是把它亲手拆开一次。