c - 操作一个非常大的 SHA256 哈希文本数据库的最有效方法？

Question

我必须经常在格式为 CSV 的大型(最多 1G)数据库中搜索哈希

sha256_hash, md5_hash, sha1_hash, field1, field2, field3 etc

在 C 中。这需要非常快并且内存使用不是问题(最少 32G)。我找到了 this这与我的想法非常接近:将数据加载到 RAM 中，按散列一次性对数据库进行排序，按散列的前“n”个字节进行索引，然后搜索较小的子列表。但是上面的线程似乎没有解决我中间的问题。因为我不是密码学专家，所以我想知道散列的分布以及它是否可以用来更快地搜索子列表。关于这个或我的一般方法有什么建议吗？

Answer 1

是的，通过散列位的分布，布隆过滤器可用于尽早排除“明确否定”。

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

要为给定的桶创建一个布隆过滤器，逻辑或将所有哈希一起创建您的过滤器。然后用你的目标散列逻辑与过滤器。如果结果<你的目标哈希(或结果异或目标哈希!= 0)，那个桶肯定不包含那个目标哈希，你可以跳过搜索它，但如果结果==目标哈希，那个桶可能包含你的目标哈希，您需要继续搜索它才能确定。布隆过滤器可以在添加新哈希时简单地缓存和更新，但在删除哈希时必须重新计算，因此搜索剩下的就是 AND 和 < 操作，它们非常便宜并且会减少你的 O(N ) 在最好的情况下操作到 O(1) 时间。

必须注意桶的大小，以便生成有意义值的过滤器，因为所有高位的过滤器对任何人都没有值(value)。