hash - 集合的增量散列

Question

什么是增量散列元素集的好方法？这必须发生，以便可以按任何顺序添加和删除元素，并且仍然相等的集合具有相同的散列。目的是能够从一组集合中快速找到一个集合或其轻微修改。

关于组合算子的向量空间方法

这是不起作用的东西。b 位整数整数可以被认为是 GF(2) 上的向量空间 V，其中加法是 XOR 运算符（例如 10 + 11 = 01），乘以 0 或 1 是分量明智的逻辑与（例如 1 * 10 = 10, 0 * 10 = 00）。可以将元素随机（但固定）映射到 b 位整数 E = {e_1, ..., e_b}，然后通过将元素的哈希相加来计算集合的哈希。这样做时，必须确保 E 构成向量空间 V 的基础；否则哈希不能使用 b 位整数的所有值。

这种技术的问题是，如果 E 基的使用子集没有，例如，任何基向量 e_i 的非零第一个分量，那么得到的散列不能是奇数。取决于正在使用的基向量的哪个子集，会出现类似的问题。总之，不应该使用 XOR 来查找集合的哈希值。使用正常的求和 + 可能不会更好。

Answer 1

一种解决方案是增加一棵红黑树，以便每个节点包含以该节点为根的子树的组合哈希（总是左子哈希与当前节点哈希与右子哈希相结合）。这允许在恒定时间内找到所有元素的散列（根节点的散列），同时不影响红黑树的属性。可以创建一个通用的红黑树实现，它允许自动更新节点中的分层信息，其中更新规则由数据结构的用户指定。由于红黑树在重新平衡时可能会旋转，这意味着哈希组合函数必须是关联的。在论文“用 SL2 散列”中 通过 Tillich 和 Zémor 可以找到具有关联散列组合函数（矩阵乘法）的散列函数。我不确定这是否具有可接受的性能。