如何获得CRC的合理CRC
本文关键字：CRC 何获得 | 更新日期: 2023-09-27 18:29:41
我有一个树结构，其中每个节点都知道其CRC。有什么合理的方法来计算每个子树的CRC，从而为整个子树提供一个良好的值？换句话说，一个值，用于标识子树的任何部分是否发生了更改。
我目前的想法是简单地取每个子节点的CRC，将其转换为字符串/字节[]，将所有节点连接在一起，并取该字节[]的CRC。但我不确定这是否会导致容易的碰撞，因为我怀疑这会删除相当多的信息。
（我看了crc32_comine，但它似乎不合适，因为我没有任何长度。我可以使用零的长度，但这会更好还是更糟？）
在C#中工作，但我想这真的是语言不可知论
编辑：最终采用了这种技术。如果冲突似乎是个问题，将切换到更长的哈希。虽然我不需要叶序很重要，但我不会使用xor，以防以后出现。
理想情况下，您可以组合节点的CRC来计算子树的CRC，使用类似crc32_combine()的东西。结果将与在您定义的任何规范排序中计算所有节点的CRC相同。不过，这只会检查排序，而不会检查树的结构。具有相同排序的不同结构将给出相同的CRC。无论如何组合CRC，除非在树结构中包含其他信息，否则都是如此。
crc32_combine()的使用需要被组合的每个CRC的数据长度（第一个除外）。这显然没有保存，在这种情况下也不可用。相反，您可以按照规范顺序生成CRC的字节流，并获取该流的CRC。（您需要决定CRC是存储在字节流中的大端还是小端，然后遵守您的约定。）
使用SHA1或MD5等加密签名是不必要的，除非你出于某种原因担心一个狡猾的人干扰了你计算的检查值，并试图欺骗你，让你认为树的内容在发生变化时没有改变。（狡猾的人无论如何都可以在节点级别做到这一点，因为CRC很容易被欺骗。）否则，这样的签名只是浪费CPU时间。如果你只是想要一个更长的散列，超过32位，以降低冲突的概率，那么你可以使用快速散列函数，比如CityHash家族的函数。
我可能会为您的校验和使用最少的SHA1，因为MD5的冲突并不罕见，而且您关于组合CRC的想法似乎很可靠，尽管我个人会将哈希异或在一起以节省RAM和CPU周期。
您应该使用为此设计的东西，如SHA-2。根据您的特殊要求，您可以使用CRC32。这里发布了一个类似的问题，并进行了更多讨论：
CRC32可以用作哈希函数吗？