c++ - 如何为变化的 `std::map` 计算签名

Question

我们有 5 台服务器，每台服务器都运行生成 std::map 的相同服务。 std::map 中的每一项都由作为键的唯一整数和作为其对应值的 double 值组成。为了检查不同机器之间的一致性，我们需要不断检查五台服务器之间的 std::map 是否相等。

每个 std::map 存储 200 万个不同的项目，并且它在一天中不断变化。比较值的简单方法如下:

compare S1 with S2, S3, S4, S5
compare S2 with S3, S4, S5
compare S3 with S4, S5
compare S4 with S5

这是 N*N 的复杂度，每当映射中的单个值发生变化时，就必须重做 O(N) 的比较。

一个更好的想法是为每个 map 建立一个签名，最后将 map 比较简化为 float 比较。这里有两个挑战:

1. 如何基于巨大的 map 建立单一值(value)
2. 如何根据不断变化的 map 逐步计算这个值

如有任何建议，我们将不胜感激。

Answer 1

由于映射显然总是一致的，因此很自然地可以得出相同的修改以相同的顺序发生。

这意味着您可以使用修改序列的(安全)散列来代替比较 map 本身。对于每次修改，您更新 H = hash(H | Key | Value )，然后比较 H1...H5。

H 的初始选择无关紧要，主要要求是所有服务器应以相同的 H 值和相同状态的 map 开始。