ayu*_*hen 9 hash crc32 checksum error-detection
抛开性能和安全性考虑,并假设具有完美雪崩效应的散列函数,我应该将其用于校验和数据块:CRC32或散列截断为N个字节？即错过错误的可能性较小？特别:
数据块将通过网络传输并重复存储在磁盘上.块大小可以是1KB到1GB.
据我了解,CRC32可以检测高达32位的翻转,具有100%的可靠性,但在此之后,其可靠性接近1-2^(-32)并且对于某些模式来说更糟糕.总是有一个完美的4字节散列可靠性1-2^(-32),所以请看一下.
8字节散列应该具有更好的整体可靠性(2^(-64)错过错误的机会),所以它应该优先于CRC32吗？CRC64怎么样？
我想答案取决于在这种操作中可能出现的错误类型.我们是否可能会看到稀疏的1位翻转或大量的块损坏？另外,鉴于大多数存储和网络硬件都实现了某种CRC,不应该意外地进行位翻转吗？
Mar*_*ler 12
只有你可以说1-2 -32对你的应用是否足够好.来自良好散列函数的CRC- n和n位之间的错误检测性能将非常接近相同,因此选择哪一个更快.这可能是CRC- n.
更新:
上述"可能是CRC- n "只是有可能.如果使用非常高性能的散列函数则不太可能.特别是,CityHash似乎与使用英特尔crc32硬件指令计算的CRC-32一样快!我crc32在434 MB文件上测试了三个CityHash例程和Intel 指令.该crc32指令版本(计算一个CRC-32C)花的CPU时间24毫秒.CityHash64需要55毫秒,CityHash128需要60毫秒,CityHashCrc128需要50毫秒.CityHashCrc128使用相同的硬件指令,但它不计算CRC.
为了获得CRC-32C计算那么快,我有三个获得幻想crc32在三个不同的缓存指令,以使并行使用三个算术逻辑单元的单核,然后写在汇编内环.CityHash非常快.如果您没有该crc32指令,那么您将很难像CityHash64或CityHash128那样快速地计算32位CRC.
但请注意,为此需要修改CityHash函数,或者需要进行任意选择,以便为大型数据流上的CityHash值定义一致的含义.原因是这些函数没有被设置为接受缓冲数据,即一次向一个块提供函数并期望获得相同的结果,就像整个数据集一次被馈送到函数一样.需要修改CityHash函数以更新中间状态.
替代方案,以及我为快速和脏测试所做的是使用函数的Seed版本,我将使用前一个缓冲区中的CityHash作为下一个缓冲区的种子.问题在于结果取决于缓冲区大小.如果使用此方法为CityHash提供不同大小的缓冲区,则会获得不同的哈希值.
四年后的另一个更新:
xxhash系列的速度更快.我现在建议通过CRC获取非加密哈希值.