Python中不存储键的哈希表/字典实现是什么？
我正在一个哈希表里存储数百万，甚至可能是数十亿个4字节的值，但我不想存储任何键。我预计只需要存储键的哈希值和这些值。这个过程必须快速，并且所有数据都要保存在内存中。虽然我还是会用键来查找这些条目，但这和set()的用法不一样。
在Python中有什么实现方法吗？这个东西有什么特别的名字吗？
是的，允许发生冲突，并且可以忽略这些冲突。
（对于冲突，我可以做个例外，可以存储键。或者，冲突也可以直接覆盖之前存储的值。）
10 个回答
3
这是一个经典的问题，涉及到空间和运行时间之间的权衡：你可以在哈希表中使用线性的空间来存储键，这样可以实现常量时间的访问速度。或者，你可以隐式地存储键，使用二叉树来实现对数时间的访问。值的（哈希）二进制形式会告诉你在树中存储它的路径。
3
你可以试试用一个普通的字典，别再像这样做：
d[x]=y
而是用：
d[hash(x)]=y
来查找：
d[hash(foo)]
当然，如果发生了哈希冲突，你可能会得到错误的值。
5
Bloomier过滤器 - 节省空间的关联数组
来自维基百科的内容：
Chazelle等人（2004年）设计了一种Bloom过滤器的扩展版本，这种版本可以将一个值与每个插入的元素关联起来，从而实现了一个关联数组。和Bloom过滤器一样，这些结构通过接受一定概率的误报来节省空间。在“Bloomier过滤器”的情况下，误报是指当某个键不在映射中时却返回了结果。对于在映射中的键，映射永远不会返回错误的值。