本文介绍一种兼顾内存效率（接近理论下限128 mb）与查询性能的方案：用numpy数组模拟开放寻址哈希表，将每对64位整数以固定结构存储，空间开销仅比理论最小值高约25%，同时支持高速插入与成员判断。
本文介绍一种兼顾内存效率（接近理论下限128 mb）与查询性能的方案：用numpy数组模拟开放寻址哈希表，将每对64位整数以固定结构存储，空间开销仅比理论最小值高约25%，同时支持高速插入与成员判断。
在处理大规模整数对（如 (int64, int64)）去重与快速查存场景时，Python原生 set 存储元组会因对象头、引用计数及动态内存管理导致严重内存膨胀——单个 Python int 占用远超 8 字节，一对 int 实际可能占用 50+ 字节，百万级数据轻松突破 500 MB；而 numpy.array 虽能紧凑存储，但不支持直接哈希操作。
理想目标是：100 万个 (int64, int64) 对仅占 10⁶ × 2 × 64 bits = 128,000,000 bits ≈ 16 MB。为此，可采用「自定义开放寻址哈希表」策略，以 NumPy 数组为底层存储容器：
import numpy as np
class Int64PairSet:
def __init__(self, capacity=1_000_000):
# 预留25%空间，确保负载因子 ≤ 0.8，平衡性能与空间
self.size = int(capacity * 1.25)
self.table = np.zeros((self.size, 2), dtype=np.int64)
self.is_00_in_table = False # 特殊标记 (0, 0) 是否存在
def _hash(self, a: int, b: int) -> int:
# 使用简单但分布良好的混合哈希（可替换为更优哈希函数）
h = (a ^ (b << 32) ^ (b >> 32)) & 0xffffffffffffffff
return int(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)
for i in range(self.size): # 线性探测
probe_idx = (idx + i) % self.size
entry = self.table[probe_idx]
if entry[0] == 0 and entry[1] == 0: # 空槽位
entry[0], entry[1] = a, b
return
elif entry[0] == a and entry[1] == b: # 已存在
return
def __contains__(self, pair) -> bool:
a, b = pair
if a == 0 and b == 0:
return self.is_00_in_table
idx = self._hash(a, b)
for i in range(self.size):
probe_idx = (idx + i) % self.size
entry = self.table[probe_idx]
if entry[0] == 0 and entry[1] == 0:
return False # 探测到空位，未命中
elif entry[0] == a and entry[1] == b:
return True
return False✅ 优势总结：
- 内存极致紧凑：每个元素严格占用 2 × 8 = 16 字节，100 万对仅需 16 MB，加上 25% 扩容后约 20 MB，远低于 Python 原生结构（通常 > 300 MB）；
- O(1) 平均复杂度：开放寻址配合合理负载因子（≤0.8），插入/查询平均仅需 2–3 次内存访问；
- 零 Python 对象开销：全部数据位于连续 NumPy 数组中，无指针、无 GC 压力；
⚠️ 注意事项：
- (0, 0) 必须单独处理（因用作空槽位哨兵），若业务中该值合法且高频，可改用其他哨兵（如 (-1, -1)）并确保其不在数据中出现；
- 哈希函数应避免强碰撞，生产环境建议使用 xxhash 或 MurmurHash3 的 64 位变种替代简易异或；
- 若需删除操作，需引入“已删除”标记（如 (−2, −2)），否则线性探测链可能断裂；
- 初始容量应预估准确——扩容需重建整个表，成本高昂。
该方案在科学计算、图算法、索引构建等对内存与速度双敏感的场景中已被广泛验证，是 Python 生态下逼近 C 级内存效率的实用选择。
