Python中一个不存储键的哈希表/字典实现是什么？

Question

Python中一个不存储键的哈希表/字典实现是什么？

pythondictionaryhashtabledata-structures

6

我正在使用哈希表存储数百万，甚至数十亿个4字节值，并且不想存储任何键。我期望只需要存储键的哈希值和值。这需要快速完成并全部保存在RAM中。与set()不同，条目仍将使用键查找。

有没有Python的实现方法？这种方法有名称吗？

是的，允许冲突并且可以忽略它们。

（对于冲突，我可以为其存储键。或者，冲突可以覆盖先前存储的值。）

- user213060

你的键是均匀分布的，还是有一些规律？ - user227667

10个回答

3

如何使用普通字典代替以下操作：

d[x]=y

用途：

d[hash(x)]=y

查找：

d[hash(foo)]

当然，如果发生哈希冲突，您可能会得到错误的返回值。

- Mark Byers

例如，hashlib.sha512。您可以计算碰撞的可能性 - 对于数十亿来说非常非常小，并权衡碰撞的成本。根据应用程序，甚至可能不值得检测碰撞。 - John La Rooy

是的，对于这个应用程序，只要忽略一定阈值内的冲突就可以了，比如1%到10%左右。 - user213060

数组没问题。这正是我已经使用numpy实现的方式。但它缺少了许多Python字典的功能，比如自动调整大小和快上千倍的速度。 - user213060

1

你期望哈希的大小有多大？我认为它们通常是32位无符号整数。指针的大小也是这么大，所以要想更小的话就祝你好运吧。通过完美哈希，32位无符号整数可以保证在40亿个值中不发生碰撞。如果比32位还少的话，你肯定会遇到许多碰撞。以下是一个快速的自定义哈希算法，至少看起来很有潜力，你可以用C语言实现： http://burtleburtle.net/bob/hash/doobs.html - Merlyn Morgan-Graham

此外，完美的哈希算法并不存在，因此，除非您使用超过4个字节的键/哈希值，否则在处理“数十亿”个值时会有大量冲突。 - Merlyn Morgan-Graham

如果表格会带来巨大的开销，是否可以将4字节值附加到你的键数据结构上，或者编写一个包含两者的结构？ - Merlyn Morgan-Graham

3

这是经典的时间与空间权衡之一：你可以在哈希表中使用线性空间，以恒定时间访问键；或者你可以隐式地存储键，并通过使用二叉树来使用对数时间。值的（二进制）哈希将给出它在树中存储的路径。

- Jochen Ritzel

2

在RAM中构建自己的B树。

内存使用：

（4字节）比较哈希值

（4字节）下一叶子的索引，如果哈希小于或等于比较值，则为负数索引；或者是值的负数索引

（4字节）下一个叶子的索引，如果哈希大于比较值，则为负数索引；或者是值的负数索引

每个B树节点需要12个字节。对于值还需要更多的开销（请参见下文）。

在Python中如何组织这些——难道没有32位整数的“本地数组”吗？几乎不需要额外的内存开销……？它们被称为什么来着……？

有一个单独的子数组排序数组，每个子数组包含一个或多个值。“值的索引”上面是大数组的索引，允许检索与哈希匹配的所有值。

这假定了32位哈希。如果您有超过2^31-1个条目或更大的哈希，则每个B树节点需要更多的字节。

但是可能会出现问题：请注意，如果您不存储键值，则无法验证查找的哈希值是否仅对应于您的键，除非通过某种算法或组织机制保证没有两个键具有相同的哈希值。这是一个相当严重的问题。您考虑过吗？ :)

- martinr

假设您没有在表中存储实际键。现在假设您有一个键值对K1-V1要插入哈希表，其中hash(K1) = H1。您在哈希表中查找H1并发现它存在。问题是您不知道H1是来自hash(K1)还是来自hash(K5000)，其中hash(K5000)也恰好等于H1。因此，您甚至不知道K1-V1是否是冲突。+1给最后一段话，这是我对这个问题的第一反应。 - shoover

你可能找到了什么好东西。我正在研究这个：pypi.python.org/pypi/blist - user213060

为了压缩值存储，您可以放弃在上面的“负索引”中使用两个额外的位来指示散列匹配值的数量是否为1、2、3或4+。然后，所有三个值匹配项都可以在一个32位数组中一起存储（以三个连续的形式存储，因此没有额外开销），所有两个值可以在一起以两个的形式存储，没有额外的开销，同理适用于一个值和4+个值，您可以将它们组合在一个数组中，其中包含32位数量计数，然后是这些值。这取决于您想要节省多少内存/所涉及的确切对象数量。 - martinr

2

虽然Python字典非常高效，但如果你要存储数十亿个项目，你可能希望使用数据结构创建自己的C扩展，针对你实际使用它的方式进行优化（顺序访问？完全随机？等等）。

为了创建一个C扩展，你可以使用SWIG，或者类似Pyrex的东西（我从未使用过）。

- rob

1

哈希表必须存储键，除非您提供一个几乎不可能产生冲突的哈希函数。

然而，如果您的键类似于字符串，那么有一种非常节省空间的数据结构 - 有向无环字图（DAWG）。不过我不知道任何Python实现。

- el.pescado - нет войне

我已经说过，在这个应用程序中，碰撞是完全可以接受的。DAWG 的想法很好，但不幸的是我的键非常随机。 - user213060

1

虽然不是你要求的，但为什么不考虑使用Tokyo Cabinet或BerkleyDB来完成这项工作呢？虽然它们不会在内存中运行，但你可以通过牺牲一些性能来获得更大的存储容量。你仍然可以将列表保存在内存中，并仅使用数据库来检查存在性。

- Victor Olex

1

如果你实际上要存储数百万个唯一值，为什么不使用字典呢？
存储：d[hash(key)/32] |= 2**(hash(key)%32)
检查：(d[hash(key)/32] | 2**(hash(key)%32))

如果你有数十亿条记录，可以使用大小为(2**32)/32的numpy数组。毕竟，你只有40亿个可能的值需要存储。

- user227667

事实上，您可以根据您愿意容忍的冲突与权衡程度自动增加numpy数组实现。例如，对于较少的值，通过hash(key)/(2**K)进行索引，其中K从20开始，并随着表格中条目变得更加密集而逐渐减少。 - user227667

1

请问您能否更多地介绍一下这些键吗？我在想我们是否可以利用这些键中的任何规律。

如果这些键是小字母表中的字符串（例如数字字符串，如电话号码），您可以使用 trie 数据结构：

http://en.wikipedia.org/wiki/Trie

- steveha

0

为什么不用字典+哈希值？

>>> import hashlib
>>> hashtable = {}
>>> def myHash(obj):
    return hashlib.sha224(obj).hexdigest()

>>> hashtable[myHash("foo")] = 'bar'
>>> hashtable
{'0808f64e60d58979fcb676c96ec938270dea42445aeefcd3a4e6f8db': 'bar'}

- jbochi

每个4字节条目的开销超过28位...行不通。 - user213060

你可以根据自己的需求设置摘要大小，对吧？ - jbochi

是的，但任何大于零的东西都比我想要的多，而任何小于哈希表内部哈希大小的东西都会导致比必要更多的冲突。无论哪种方式，存储键在这里都是一个巨大的空间浪费。 - user213060

你可以使用md5()函数而不是hexdigest()函数，但它仍然太长了。那么Murmur呢？"他们"提供了8字节的哈希值。 - Nick

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jfs · Accepted Answer

布隆过滤器 —— 空间高效的关联数组

维基百科介绍：

Chazelle 等人（2004）设计了一种布隆过滤器的扩展，可以将一个值与每个已插入的元素关联起来，实现关联数组。与布隆过滤器类似，这些结构通过接受一定概率的误判来实现小空间开销。对于“布隆过滤器”，当键不在映射中时返回结果被定义为误判。映射永远不会为映射中不存在的键返回错误的值。