时间戳

首页 > 解决方案 > CRC-32 是否保证生成 40 亿个唯一值？

php - CRC-32 是否保证生成 40 亿个唯一值？

问题描述

我只想知道对于 CRC32 哈希函数，特别是 PHPcrc函数，我是否会为输入值（整数）获得 2^32（40 亿）个不同的值，保证从 1 到 40 亿按顺序递增？

标签： phphashcryptographycrc32

解决方案

我不认为 CRC32 是专门为所有可能的四字节输入而设计的。然而，它似乎确实是这样工作的。您可以通过简单地检查每个可能的输出来自己验证这一点。为了加快速度，我使用了以下 C 程序：

/* Compile: cc crc_check.c -O3 -lz -o crc_check */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <zlib.h>

int main() {
    uint32_t x, y, d;
    uint64_t i, *seen, mask;

    seen = calloc(0x4000000, 8);
    if (!seen) return -1;

    /* Make sure we're calculating the same values as PHP's crc32 function */
    printf("crc32(\"ABCD\") = %lu\n", crc32(0, (unsigned char*)"ABCD", 4));

    for (i=x=0; i<0x100000000ULL; i++) {
        y = crc32(0, (unsigned char*)(&x), 4);
        mask = 1ULL << (y & 0x003fULL);
        d = y >> 6;
        if (seen[d] & mask) {
            printf("Collision detected (x=%u, y=%u)\n", x, y);
            return 0;
        }
        seen[d] |= mask;
        x++;
    }
    puts("No collisions detected");
    return 0;
}

/*
   Output:
   crc32("ABCD") = 3675725989
   No collisions detected
*/

为了确保 zlib 使用相同的函数，我添加了一行来输出字符串“ABCD”的 CRC32 校验和。PHP 产生相同的值：

$ php -r 'echo crc32("ABCD");'
3675725989

不过，我不得不问：你需要这些信息做什么？如果您想将连续的 32 位整数转换为唯一的伪随机值，有很多更有效的方法可以做到这一点。例如，考虑使用线性同余生成器。

推荐阅读