什么是Python的哈希表/字典实现,不存储密钥？

Question

我在哈希表中存储了数百万,可能是数十亿的4字节值,我不想存储任何密钥.我希望只需要存储键和值的哈希值.这必须很快并且都保存在RAM中.与set()不同,仍然可以使用键查找条目.

Python的这个实现是什么？这有名字吗？

是的,允许碰撞,可以忽略.

(我可以为碰撞做一个例外,可以存储密钥.或者,碰撞只能覆盖以前存储的值.)

Answer 1

Bloomier过滤器 - 节省空间的关联数组

来自维基百科:

Chazelle等人.(2004)设计了Bloom过滤器的泛化,它可以将值与已插入的每个元素相关联,从而实现关联数组.与Bloom过滤器一样,这些结构通过接受较小的误报概率来实现较小的空间开销.在"Bloomier过滤器"的情况下,误报被定义为当键不在地图中时返回结果.地图永远不会为地图中的键返回错误的值.

Answer 2

不如使用普通字典而不是这样做：

d[x]=y

使用：

d[hash(x)]=y

去查查看：

d[hash(foo)]

当然，如果存在哈希冲突，你可能会得到错误的值。