algorithm - 检查给定的哈希在一个非常非常长的列表中

Question

我有一个哈希列表。长长的名单。很长的清单。我需要检查给定的哈希是否在该列表中。

最简单的方法是将哈希存储在内存中（在映射或简单数组中）并检查它。但它需要大量的 RAM/SSD/HDD 内存。不止一个服务器可以处理。

我想知道在合理的内存使用中是否有一个技巧。也许有我不熟悉的算法或特殊的集合？

标签： algorithmhash

Answer 1

三个想法——

• 根据这些哈希的结构，您也许可以从彩虹表的概念中借用一些想法来隐式存储其中的一些。
• 如果你有足够的哈希值，你可以使用 trie 来压缩共享前缀的存储，但是考虑到它们的长度和（可能的）一致性，你不会看到很大的节省。
• 您可以将散列拆分为多个较小的散列，然后使用这些散列来实现Bloom Filter，但这是一个概率测试，因此如果存在感知“ hit”，但是这可能使您能够过滤掉足够多的“未命中”，从而使性能较低（速度方面）的数据结构变得可行。