本文介绍一种基于numpy数组模拟开放寻址哈希表的方法，以接近理论最小内存（128 mb/百万对）的代价，实现高速插入与查询，兼顾空间效率与操作性能。
本文介绍一种基于numpy数组模拟开放寻址哈希表的方法，以接近理论最小内存（128 mb/百万对）的代价，实现高速插入与查询，兼顾空间效率与操作性能。
在处理大规模结构化整数对（如 (int64, int64)）集合时，Python原生 set 存储元组会因对象开销导致内存激增（每个 int 对象约28字节+引用，元组额外开销），远超理论下限 16 字节/对（2 × 64 bit）。而 NumPy 的 uint64 虽紧凑，但其数组不可哈希，无法直接用于 set。此时，手动实现轻量级开放寻址哈希表成为最优解——它绕过 Python 对象层，完全运行在连续、类型固定的 NumPy 内存块中。
核心思路是：分配一个略大于实际容量的二维 NumPy 数组，每行存储一对 int64 值，并采用线性探测（linear probing）处理冲突。为支持空槽标识，约定 (0, 0) 为“未占用”占位符（需单独用布尔变量 is_00_in_set 记录真实 (0, 0) 是否存在）：
import numpy as np
class Int64PairSet:
def __init__(self, expected_n: int, load_factor: float = 0.8):
self.size = int(expected_n / load_factor)
self.table = np.zeros((self.size, 2), dtype=np.int64) # [x, y] pairs
self.is_00_in_set = False
self._count = 0
def _hash(self, x: int, y: int) -> int:
# 使用简单但分布良好的混合哈希（避免低位全零）
h = (x ^ (y > 32)) & 0xffffffffffffffff
return h % self.size
def add(self, x: int, y: int) -> None:
if x == 0 and y == 0:
self.is_00_in_set = True
return
idx = self._hash(x, y)
while not np.array_equal(self.table[idx], [0, 0]):
if np.array_equal(self.table[idx], [x, y]):
return # already exists
idx = (idx + 1) % self.size
self.table[idx] = [x, y]
self._count += 1
def contains(self, x: int, y: int) -> bool:
if x == 0 and y == 0:
return self.is_00_in_set
idx = self._hash(x, y)
while not np.array_equal(self.table[idx], [0, 0]):
if np.array_equal(self.table[idx], [x, y]):
return True
idx = (idx + 1) % self.size
return False
✅ 空间优势：100 万对数据仅需 1000000 × 1.25 × 16 = 20 MB（≈160 Mb），比原生 set 节省 5–10 倍内存，逼近理论极限（128 Mb）。
⚠️ 注意事项：
- 避免使用 (0, 0) 作为业务数据（或改用其他哨兵值，如 (-1, -1) 并调整 dtype 为 int64）；
- 哈希函数应尽量减少聚集，示例中采用位异或与移位混合，实践中可替换为 xxhash 等更快非加密哈希；
- 负载因子不宜超过 0.85，否则探测链显著增长，查询退化为 O(n)；
- 若需删除操作，需引入“已删除”标记（如 [0, 1]），使探测逻辑更复杂。
该方案将内存控制权交还给开发者，在 C 层级的 NumPy 数组上构建确定性行为的集合原语，是高性能数值计算场景下的务实之选。
