使用 XOR Shift 作为更快的 CRC32 校验和？

Question

使用异或移位来产生可用的校验和是否有效？我找不到任何证据表明它比 CRC32 更能碰撞。

我对 1000 万个随机生成的 8 到 32 长度字节数组进行了运行模拟，下面的 hash32 方法实际上产生的冲突比 CRC32 少 2%。

此外，该代码似乎运行比 Java 的内置 util.zip.CRC32 class.

快大约 40 倍

public static long hash64( byte[] bytes )
    {
    long x = 1;
    for ( int i = 0; i < bytes.length; i++ )
        {
        x ^= bytes[ i ];
        x ^= ( x << 21 );
        x ^= ( x >>> 35 );
        x ^= ( x << 4 );
        }

    return x;
    }


public static int hash32( byte[] bytes )
    {
    int x = 1;
    for ( int i = 0; i < bytes.length; i++ )
        {
        x ^= bytes[ i ];
        x ^= ( x << 13 );
        x ^= ( x >>> 17 );
        x ^= ( x << 5 );
        }

    return x;
    }

Answer 1

是的，如果您只需要一个简单的文件校验和，这是一个完全有效的替代方案，但这不是最佳解决方案。

CRC 已针对可靠检测 burst errors, not collision resistance or uniform distribution. CRC-32 may superficially appear to work as a general hash function or a checksum, but it readily fails avalanche and collision tests 进行了优化，如您在测试中所见。 CRC 也很慢，因为它必须实现多项式除法，这需要昂贵的操作，即使在大量优化为移位操作时也是如此。 Table 使用查找表 (LUT) 的 CRC 版本在诸如 Java 之类的解释语言中也很慢，因为每次查找都不可避免地要进行边界检查和条件检查。

您的解决方案是采用伪随机函数 (PRF) Xorshift，并将其转换为哈希函数。从表面上看，这似乎可以通过基本的碰撞测试，但这并不是一个很好的选择。它的雪崩行为非常差，因此您的测试不够灵敏而无法发现的碰撞概率大于概率。不仅如此，它还是次优的，一次只读取一个字节。存在具有可比性能的更好解决方案。

更好的选择是 64-bit MurmurHash3, it performs quite well in Java when sufficiently optimized. It may even be faster than your solution for large inputs. I also recommend reading Bret Mulvey's article on Hash Functions。它解释了如何以易于理解的方式构造和测试哈希函数。

使用 XOR Shift 作为更快的 CRC32 校验和？

Using XOR Shift as a faster CRC32 checksum?

java

hash

crc32

checksum