集合的增量散列

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

一種解決方案是增加紅黑樹，以便每個節點都包含以該節點爲根的子樹的組合散列（始終將子代散列與具有正確子散列的當前節點散列組合在一起）。這允許在常量時間內查找所有元素的散列（根節點的散列），否則不會影響紅黑樹的屬性。可以創建一個通用的紅黑樹實現，該實現允許自動更新節點中的分層信息，其中更新規則由數據結構的用戶指定。由於紅黑樹在重新平衡時可能會旋轉，這意味着哈希組合函數必須是關聯的。在Tillich和Zémor的文章「用SL2進行散列」中，可以找到具有關聯散列組合函數（矩陣相乘）的散列函數。我不確定這是否具有可接受的性能。