crc32哈希的默认/无效值是什么？

Question

我正在使用crc32生成32位整数句柄从我的字符串中构建一个简单的字符串ID系统。我想将StringID包装类中的哈希默认值默认为无效索引，是否存在crc32无法生成的值？我需要使用单独的标志吗？ 澄清：我不关心特定于语言的答案。 我只想知道在crc32范围之外是否有一个整数可以用于表示未经哈希处理的值。

谢谢！

- moka

---

你使用哪种编程语言？为什么需要默认哈希呢？ - melpomene

语言的选择很重要，例如在 Perl 中，您可以将其设置为 undef 或者甚至创建一个没有特定属性的对象（并且可能标记该属性为 lazy，以便按需创建）。但是为什么您的 StringID 需要一个默认构造函数呢？而且为什么它首先就是一个类呢？ - melpomene

@melpomene 这个珍珠的例子很有道理。它是一个类，因为它提供了检索原始字符串、隐藏实现特定逻辑等方式。问题实际上是：是否有一个整数值可以用来表示它（即超出crc32范围的值）。我将更新问题以澄清这一点。 - moka

crc32 可以生成每一个可能的 32 位值，抱歉。 - Mark Ransom

@MarkRansom 谢谢，这就是我在寻找的。 - moka

Answer 1

crc32是否会生成任何特定的值？

不会，它会生成32位整数范围内的所有值。

我需要使用单独的标志吗？

不一定需要。

如果你决定将（例如）0x00000000视为“未设置CRC”，非零值为CRC值；则在计算CRC之后（但在存储或检查存储的值之前），你可以执行if(CRCvalue == 0) CRCvalue = 0xFFFFFFFF;。

这会微弱地削弱CRC。具体来说，对于2个随机数据片段，对于纯CRC32，CRC匹配的概率为4294967296中的1次，而对于"零表示未设置"，CRC匹配的概率为4294967295.000000000232830643654中的1次。

- Brendan

Answer 2

不是的。CRC-32可以是任何32位值。你需要在其他地方指示一个无效的索引。

我的欺骗代码允许您选择要修改的消息中的位位置和所需的CRC，并将解决要翻转哪些位置以获得完全相同的CRC。

- Mark Adler

---

一些推理会让你更值得信赖 :) - Luis Colorado

@LuisColorado https://cs.stackexchange.com/questions/18431/range-of-crc-32 - Michael Foukarakis

Answer 3

有一个简单的演示可以证明您可以生成任何crc32值，因为它是在伽罗瓦域（实数或复数一样）中除以P（生成多项式）的余数，您可以从多项式中减去其模数（这是一个XOR操作，所以加法和减法实际上是相同的），得到余数为0，然后您可以将模数的倍数与所有可能的crc32值之一相加（因为它们已经是除法的余数，它们的crc32值就是它们本身），以获得2 ^ 32个可能值中的任何一个。

通常的做法是添加尽可能多的零位以完成完整的32位字（这看起来像乘以一个常数值x ^ 32），然后从中减去（异或）余数，使结果成为模数的倍数（请记住，加法和减法是相同的- XOR操作），从而使

编辑（更易于查看）

实际上，crc32的2^32个可能值中，每一个在除以生成多项式时都会得到自己（它们与生成多项式互质，就像在整数模N算术中，数字1..N一样），因此它们都是运算符的可能结果。

许多地方实现的 crc 操作并不是那么简单... 因为一些实现会将余数寄存器初始化为 0xffffffff，并在终止时查找 0xffffffff(实际上，crc32 就是这样做的).... 如果你算一下，你就会猜到原因：将寄存器初始化为0x11111111等同于在更长的字符串中有一个前一个余数为0xffffffff... 并在结尾处寻找0xffffffff就像在原始字符串后面添加0xffffffff。 这样做的效果是在您的字符串之前和之后连接比特串0xffffffff，使余数对于在计算出 crc32 后追加一串零位于字符串之前和之后的情况敏感（通过在任意一侧附加零位来改变位串）。无论如何，此修改不会更改计算多项式余数的原始算法，因此在这种情况下任何2**32个值都是可能的。

- Luis Colorado