c++ - 允许增量计算的校验和实现有哪些？

Question

在我的程序中，我有一组存储在专有哈希表中的集合。与所有哈希表一样，我需要为每个元素提供两个函数。首先，我需要用于插入的散列值。其次，当有冲突时我需要一个比较函数。我突然想到校验和函数非常适合这个。我可以在两个函数中使用该值。不缺少校验和函数，但我想知道是否有任何我不需要将其引入库的常用函数(我的公司在这方面是 PIA)。系统库就可以了。

但是我还有一个更复杂的要求。我需要可以递增计算的校验和。也就是说，如果一个集合包含 A B C D E F 并且我从集合中减去 D，它应该能够返回一个新的校验和值而无需再次迭代集合中的所有元素。这样做的原因是为了防止我的代码中出现非线性。理想情况下，我希望校验和与顺序无关，但如果需要我可以先对它们进行排序。是否存在这样的算法？

Answer 1

只需在您的集合中存储一个项目字典，以及它们对应的哈希值。该集合的散列值是项目的串联、排序 散列的散列值。在 Python 中:

 hashes = '''dictionary of hashes in string representation'''
 # e.g.
 hashes = { item: hashlib.sha384(item) for item in items }

 sorted_hashes = sorted(hashes.values())
 concatenated_hashes = ''.join(sorted_hashes)
 hash_of_the_set = hashlib.sha384(concatenated_hashes)

作为散列函数，我会使用 sha384，但您可能想尝试 Keccak-384。

---

因为(当然)没有长度只有 32 位的加密哈希函数，所以您必须改用校验和，例如 Adler-32 或 CRC32。这个想法保持不变。最好对项目使用 Adler32，对连接的哈希使用 crc32:

 hashes = { item: zlib.adler32(item) for item in items }

 sorted_hashes = sorted(hashes.values())
 concatenated_hashes = ''.join(sorted_hashes)
 hash_of_the_set = zlib.crc32(concatenated_hashes)

在 C++ 中，您可以使用 Adler-32和 CRC-32的 Botan .