algorithm - 用于与多个任意值进行比较的存储算法

Question

我目前正在编写一个消息队列，这将要求我保留服务器已经看到的消息的历史记录。我为每条消息都有唯一的、固定大小的 ID 字段，这使它变得微不足道。但是，我担心存储每条消息的 ID 的长期前景，以及以后比较它们的延迟。我当前的 ID 长度为 160 位（是的，SHA1）。

理想情况下，我想知道是否有一种方法可以将多个 ID 压缩到一个字段中以节省内存，如果有，该算法的错误位置和错误否定率是多少消息压缩。理想情况下，我并不真正关心假阴性率，而是非常关心假阳性率，这使得比较看起来agrep很漂亮。

Answer 1

我建议使用 MD5，它是每条消息的 128 个摘要。冲突显然是无关紧要的，因为您总是可以逐个字节地仔细检查任何匹配字节。128 位的优点是它比 SHA1 短一些（16 字节）。

您可以将 MD5 存储在基数树中。这将使数据紧凑且易于搜索。

Answer 2

这个问题并没有真正包含足够的信息来给出明确的答案，但您可能想看看bloom filters。

Answer 3

我认为你想要一个持久哈希映射或持久集。大多数 Hash Map/Set 实现通过比较实际对象来处理冲突。

如果您的所有密钥散列都可以存储在内存中，这将实现摊销的常数时间查找。