python - Python快速重复检测，我可以只存储哈希而不存储值吗

Question

我有一种创建图像“哈希”的方法，这对于重复帧检测很有用。（对于这个问题并不重要）

目前我将视频的每一帧都放在一个集合中，并且可以通过比较集合来做一些事情，比如找到包含交叉点的视频。（我有数十亿的哈希）

由于我有自己的“哈希”，我不需要集合的值，只需要检测重复项的能力。

这会将我的内存占用减少一半（因为我只有哈希值）。

我在内部知道一个集合实际上是哈希值对。必须有一种方法可以制作“SparseSet”或“hashonly”集。

就像是

2 in sparset(1,2,3) 

True

但是哪里

for s in sparset(1,2,3)

将不返回任何内容，或者哈希不返回值。

标签： pythonhashduplicatessetsparse-matrix

Answer 1

这不是集合的工作方式。哈希值和值都是必需的，因为在发生哈希冲突时必须检查值是否相等。

如果您不关心冲突，则可以使用Bloom 过滤器而不是集合。这些是非常节省内存的，但给出了概率答案（绝对不在集合中，或者可能在集合中）。标准库中没有布隆过滤器，但 PyPI 上有几个实现。

如果您更关心优化空间而不是时间，您可以将哈希保存在一个列表中，然后当您需要检查一个元素时，将其排序并进行二进制搜索。当列表大部分已经排序时， Python 的Timsort非常有效，因此后续排序会相对较快。Python 列表有一个方法，您可以使用标准库模块sort()相当轻松地实现二进制搜索。bisect

您可以结合这两种技术，即如果 Bloom 过滤器指示元素不在集合中，则不要打扰排序。当然，如果您自上次以来没有添加任何元素，请不要再次进行排序。