10

除了性能和安全考虑之外，假设一个具有完美雪崩效应的散列函数，我应该使用它来校验数据块：CRC32 还是截断为 N 字节的散列？即哪个将有更小的概率错过错误？具体来说：

  1. CRC32 与 4 字节哈希
  2. CRC32 与 8 字节哈希
  3. CRC64 与 8 字节哈希

数据块将通过网络传输并重复存储在磁盘上。块的大小可以是 1KB 到 1GB。

据我了解，CRC32 可以以 100% 的可靠性检测多达 32 位翻转，但之后它的可靠性接近1-2^(-32)并且对于某些模式来说要差得多。完美的 4 字节散列可靠性始终为1-2^(-32)，所以请看图。

8 字节散列应该具有更好的整体可靠性（2^(-64)错过错误的机会），那么它应该优于 CRC32 吗？那么CRC64呢？

我想答案取决于此类操作中可能出现的错误类型。我们是否可能会看到稀疏的 1 位翻转或大量块损坏？此外，鉴于大多数存储和网络硬件都实现了某种 CRC，不应该已经处理意外的位翻转吗？

4

2 回答 2

13

只有您可以说 1-2 -32是否适合您的应用程序。一个好的散列函数的 CRC -n位和n位之间的错误检测性能将非常接近，因此选择更快的那个。那很可能是 CRC -n。

更新：

上面的“那很可能是 CRC -n ”只是有点可能。如果使用非常高性能的散列函数，则不太可能。特别是，CityHash似乎几乎与使用英特尔crc32硬件指令计算的 CRC-32 一样快！crc32我在一个 434 MB 的文件上测试了三个 CityHash 例程和 Intel指令。crc32指令版本（计算 CRC-32C）占用了 24 毫秒的 CPU 时间。CityHash64 用了 55 毫秒，CityHash128 用了 60 毫秒，CityHashCrc128 用了 50 毫秒。CityHashCrc128 使用相同的硬件指令，但它不计算 CRC。

为了快速进行 CRC-32C 计算，我不得不crc32在三个独立的缓冲区上使用三个指令，以便在一个内核中并行使用三个算术逻辑单元，然后在汇编程序中编写内部循环. CityHash 非常快。如果您没有该crc32指令，那么您将很难计算出与 CityHash64 或 CityHash128 一样快的 32 位 CRC。

但是请注意，需要为此目的修改 CityHash 函数，或者需要做出任意选择，以便为大型数据流上的 CityHash 值定义一致的含义。原因是这些函数没有设置为接受缓冲数据，即一次为函数提​​供一个块，并期望获得与将整个数据集一次性提供给函数相同的结果。CityHash 函数需要修改以更新中间状态。

另一种方法，以及我为快速和肮脏的测试所做的，是使用函数的种子版本，我将使用前一个缓冲区中的 CityHash 作为下一个缓冲区的种子。问题在于结果取决于缓冲区大小。如果您使用这种方法为 CityHash 提供不同大小的缓冲区，您将获得不同的哈希值。

四年后的另一个更新：

更快的是xxhash 系列。我现在建议将 CRC 用于非加密哈希。

于 2013-01-26T17:06:01.983 回答
0

抛开“性能”问题；您可能要考虑使用 SHA-2 函数之一（例如 SHA-256）。

于 2013-01-28T05:35:32.950 回答