本文介绍一种空间接近理论下限（128 mb/百万对）、支持高速插入与查询的方案：用numpy数组模拟开放寻址哈希表，牺牲25%冗余空间换取o(1)均摊性能。
本文介绍一种空间接近理论下限（128 mb/百万对）、支持高速插入与查询的方案：用numpy数组模拟开放寻址哈希表，牺牲25%冗余空间换取o(1)均摊性能。
在处理大规模整数对（如 (int64, int64)）去重与快速存在性查询时，Python原生 set 存储元组会因对象开销导致内存暴涨（每个 int 对象约28字节，元组额外开销显著），远超理论最小值 16 字节/对（即 128 位）。而 NumPy 的 uint64 虽紧凑，但其数组不可哈希，无法直接用于 set。此时，自定义紧凑哈希表成为兼顾速度与空间的最优解。
核心思路是：用固定大小的二维 NumPy 数组 table 模拟开放寻址哈希表，每行存储一对 int64 值，并通过哈希函数定位槽位，冲突时线性探测（linear probing）寻找下一个空闲位置。
✅ 实现要点与代码示例
import numpy as np
class Int64PairSet:
def __init__(self, expected_n: int):
# 预留25%空间，目标负载因子 ≈ 0.8
self.size = int(expected_n * 1.25)
self.table = np.zeros((self.size, 2), dtype=np.int64)
self.is_00_in_table = False # 特殊标记 (0, 0) 是否存在（因 (0,0) 作为空槽哨兵）
self._count = 0
def _hash(self, a: int, b: int) -> int:
# 使用简单但分布良好的组合哈希（避免全零冲突）
h = (a ^ (b << 32) ^ (b >> 32)) & 0x7fffffffffffffff
return h % self.size
def add(self, a: int, b: int) -> None:
if a == 0 and b == 0:
self.is_00_in_table = True
return
idx = self._hash(a, b)
start = idx
while True:
row = self.table[idx]
if row[0] == 0 and row[1] == 0: # 空槽
row[0], row[1] = a, b
self._count += 1
return
elif row[0] == a and row[1] == b: # 已存在
return
idx = (idx + 1) % self.size
if idx == start: # 表满（实际不会发生，因预留空间+负载控制）
raise MemoryError("Hash table full")
def __contains__(self, pair: tuple[int, int]) -> bool:
a, b = pair
if a == 0 and b == 0:
return self.is_00_in_table
idx = self._hash(a, b)
start = idx
while True:
row = self.table[idx]
if row[0] == 0 and row[1] == 0: # 查到空槽 → 不存在
return False
elif row[0] == a and row[1] == b: # 找到匹配
return True
idx = (idx + 1) % self.size
if idx == start:
return False⚠️ 注意事项与优化建议
- (0, 0) 的特殊处理是必须的：因我们用 (0, 0) 作为空槽标记，所有业务逻辑中若需存储该值，必须单独维护（如本例中的 is_00_in_table 标志）。若业务中 (0, 0) 永不出现，可省略此逻辑并简化判断。
- 哈希函数质量影响性能：示例中采用异或+移位组合，适用于大多数分布；若键具有强规律性（如连续ID对），建议改用更鲁棒的哈希（如 xxhash 的 Python 绑定预哈希后取模）。
- 内存即为极致紧凑：100 万对数据仅占用 1.25e6 × 2 × 8 = 20 MB 内存（≈ 160 Mb），逼近理论下限 128 Mb（16 MB），冗余仅 25%。
- 时间复杂度：平均 O(1) 插入/查询（负载因子 ≤ 0.8 时探测长度极短）；最坏 O(n)，但实践中几乎不发生。
- 扩展性提示：如需持久化或跨进程共享，可将 self.table 映射到内存文件（np.memmap）；若需动态扩容，需实现 rehash 逻辑（但会破坏“零拷贝”优势）。
综上，该方案以可控的内存冗余为代价，将 Python 生态中难以兼顾的“高吞吐”与“低内存”统一于 NumPy 的底层效率之上，是处理千万级整数对集合场景的专业级实践选择。
