别再默认 dict 是 O(1):Python 哈希结构存在二次方性能陷阱

lemire · x · 2026-09-04

Daniel Lemire 发文分析 Python dict 与 set 的真实性能边界。人们普遍相信哈希表插入/查询是严格 O(1)，但这一说法经不起推敲。

文章从哈希函数讲起：哈希把对象（字符串、整数等）映射为整数，理想情况下应类随机且同对象同值；哈希表再由桶数组构建。作者指出，哈希函数在对抗性输入或退化情形下会导致桶冲突堆积，使操作退化为二次方时间。结论是：dict/set 的 O(1) 是「平均期望」而非严格保证，理解哈希函数的行为才能避开性能陷阱。