c# - 如何得到一个合理的CRC的CRC

Question

我有一个树结构，其中每个节点都知道它的 CRC。什么是计算每个子树的 CRC 的合理方法，它会为我提供整个子树的良好值(value)？换句话说，一个值来标识子树的任何部分是否已更改。

我目前的想法是简单地获取每个子节点的 CRC，将其转换为字符串/byte[]，将所有节点连接在一起，然后获取该 byte[] 的 CRC。但我不确定这是否会导致容易发生碰撞，因为我怀疑这会删除相当多的信息。

(我查看了 crc32_combine，但它似乎不合适，因为我没有任何长度。我可以使用零长度，但这会更好还是更坏？)

在 C# 中工作，但我想这确实与语言无关。

编辑:最终采用了这种技术。如果冲突似乎是一个问题，将切换到更长的哈希值。虽然我不需要叶顺序很重要，但我不会使用 xor 以防万一。

Answer 1

理想情况下，您可以结合节点的 CRC 来计算子树的 CRC，使用类似于 crc32_combine() 的方法.结果与按照您定义的任何规范顺序计算所有节点的 CRC 相同。这只会检查顺序，而不是树的结构。具有相同顺序的不同结构将给出相同的 CRC。无论您如何组合 CRC，这都是正确的，除非您包含有关树结构的附加信息。

crc32_combine() 的使用需要每个被组合的 CRC 的数据长度(第一个除外)。这显然没有保存，在这种情况下不可用。您可以改为按规范顺序制作 CRC 字节流，并获取该流的 CRC。 (您需要决定 CRC 是存储在字节流中的大端还是小端，然后遵守您的约定。)

使用 SHA1 或 MD5 等加密签名是不必要的，除非您出于某种原因担心狡猾的人会干扰您计算的检查值并试图欺骗您认为树的内容在以下情况下没有改变他们有。 (无论如何，狡猾的人已经可以在节点级别执行此操作，因为 CRC 很容易被欺骗。)否则此类签名只是浪费 CPU 时间。如果你只是想要一个更长的散列，超过 32 位，以减少冲突的可能性，那么你可以使用一个快速的散列函数，比如来自 CityHash family 的散列函数。 .