我正在使用哈希表存储数百万,甚至数十亿个4字节值,并且不想存储任何键。我期望只需要存储键的哈希值和值。这需要快速完成并全部保存在RAM中。与set()不同,条目仍将使用键查找。
有没有Python的实现方法?这种方法有名称吗?
是的,允许冲突并且可以忽略它们。
(对于冲突,我可以为其存储键。或者,冲突可以覆盖先前存储的值。)
有没有Python的实现方法?这种方法有名称吗?
是的,允许冲突并且可以忽略它们。
(对于冲突,我可以为其存储键。或者,冲突可以覆盖先前存储的值。)
维基百科介绍:
Chazelle 等人(2004)设计了一种布隆过滤器的扩展,可以将一个值与每个已插入的元素关联起来,实现关联数组。与布隆过滤器类似,这些结构通过接受一定概率的误判来实现小空间开销。对于“布隆过滤器”,当键不在映射中时返回结果被定义为误判。映射永远不会为映射中不存在的键返回错误的值。
d[x]=y
用途:
d[hash(x)]=y
查找:
d[hash(foo)]
这是经典的时间与空间权衡之一:你可以在哈希表中使用线性空间,以恒定时间访问键;或者你可以隐式地存储键,并通过使用二叉树来使用对数时间。值的(二进制)哈希将给出它在树中存储的路径。
哈希表必须存储键,除非您提供一个几乎不可能产生冲突的哈希函数。
然而,如果您的键类似于字符串,那么有一种非常节省空间的数据结构 - 有向无环字图(DAWG)。不过我不知道任何Python实现。
虽然不是你要求的,但为什么不考虑使用Tokyo Cabinet或BerkleyDB来完成这项工作呢?虽然它们不会在内存中运行,但你可以通过牺牲一些性能来获得更大的存储容量。你仍然可以将列表保存在内存中,并仅使用数据库来检查存在性。
如果你实际上要存储数百万个唯一值,为什么不使用字典呢?
存储:d[hash(key)/32] |= 2**(hash(key)%32)
检查:(d[hash(key)/32] | 2**(hash(key)%32))
如果你有数十亿条记录,可以使用大小为(2**32)/32的numpy数组。毕竟,你只有40亿个可能的值需要存储。
请问您能否更多地介绍一下这些键吗?我在想我们是否可以利用这些键中的任何规律。
如果这些键是小字母表中的字符串(例如数字字符串,如电话号码),您可以使用 trie 数据结构:
>>> import hashlib
>>> hashtable = {}
>>> def myHash(obj):
return hashlib.sha224(obj).hexdigest()
>>> hashtable[myHash("foo")] = 'bar'
>>> hashtable
{'0808f64e60d58979fcb676c96ec938270dea42445aeefcd3a4e6f8db': 'bar'}