为何Python整数哈希表仍未修复哈希洪水攻击问题？

首先明确Python整数的哈希规则：小整数的哈希值就是自身，大整数则取 x % sys.hash_info.modulus（其中modulus是2**61 - 1，一个大质数）。这就导致当构造m*i（m为该模数）这类整数时，所有数的哈希值都是0，完全碰撞后哈希表退化成链表，操作时间复杂度直接飙升至O(n²)。

字符串采用SipHash是因为它常来自不可信输入（比如用户表单、网络数据），属于哈希洪水攻击的高风险场景。但整数哈希没改用SipHash，核心原因有两点：

• 性能代价过大：整数哈希是Python最常用的哈希操作之一，字典、集合、Counter等大量场景都依赖它。SipHash的计算开销远高于直接取模或返回自身，全面替换会拖慢所有涉及整数哈希的日常操作，这种性能损耗是Python团队无法接受的权衡。
• 攻击场景有限：哈希洪水攻击的前提是攻击者能控制输入到哈希表的数据。如果程序处理的是内部生成的整数，基本不会遇到这种恶意构造的碰撞序列；只有当整数来自不可信来源时才存在风险——这种场景相对少见，不值得为小众场景牺牲全局性能。

既然Python不允许直接修改内置整数的哈希实现，你可以通过以下方式规避问题：

1. 对整数进行哈希扰动 #

手动给整数的哈希值加入扰动，破坏恶意构造的碰撞序列。比如用位运算实现简单扰动：

import sys

def disturbed_hash(x):
    # 位运算打乱原有哈希值
    h = x ^ (x >> 16) ^ (x << 8)
    return h % sys.hash_info.modulus

如果是自己实现计数逻辑，可以用这个哈希值分组；如果用内置容器，需要配合包装类使用（见方法3）。

2. 用有序结构替代哈希表 #

如果只是做计数这类操作，可以先对列表排序，再通过一次遍历统计，时间复杂度降至O(n log n)，远快于O(n²)：

collide_sorted = sorted(collide)
count = {}
current = collide_sorted[0]
cnt = 1
for num in collide_sorted[1:]:
    if num == current:
        cnt += 1
    else:
        count[current] = cnt
        current = num
        cnt = 1
count[current] = cnt

3. 自定义包装类 #

把整数封装成自定义类，重写__hash__和__eq__方法，复用字符串的SipHash实现安全哈希：

class SafeInt:
    def __init__(self, val):
        self.val = val
    def __eq__(self, other):
        return isinstance(other, SafeInt) and self.val == other.val
    def __hash__(self):
        # 复用字符串的哈希，自动获得SipHash防护
        return hash(str(self.val))

# 使用时将整数替换为SafeInt实例
collide_safe = [SafeInt(m * i) for i in range(1, n+1)]
c = Counter(collide_safe)

处理后，原整数的碰撞序列会被打散，避免哈希表退化为链表带来的性能灾难。

内容的提问来源于stack exchange，提问作者user23546453