1

我试图找到种子来散列最大可能长度的小写字母短字符串而不会发生冲突。我选择了 SSE 4.2 CRC32 来简化任务。对于长度为 4、5、6 的种子，如果达到某个合理的小值（我不能无限等待），则不会发生冲突。

#include <bitset>
#include <limits>
#include <iterator>
#include <iostream>

#include <x86intrin.h>

static std::bitset<size_t(std::numeric_limits<uint32_t>::max()) + 1> hashes;

static void findSeed()
{
    uint8_t c[7];
    const auto findCollision = [&] (uint32_t seed)
    {
        std::cout << "seed = " << seed << std::endl;
        hashes.reset();
        for (c[0] = 'a'; c[0] <= 'z'; ++c[0]) {
            uint32_t hash0 = _mm_crc32_u8(~seed, c[0]);
            for (c[1] = 'a'; c[1] <= 'z'; ++c[1]) {
                uint32_t hash1 = _mm_crc32_u8(hash0, c[1]);
                for (c[2] = 'a'; c[2] <= 'z'; ++c[2]) {
                    uint32_t hash2 = _mm_crc32_u8(hash1, c[2]);
                    for (c[3] = 'a'; c[3] <= 'z'; ++c[3]) {
                        uint32_t hash3 = _mm_crc32_u8(hash2, c[3]);
                        for (c[4] = 'a'; c[4] <= 'z'; ++c[4]) {
                            uint32_t hash4 = _mm_crc32_u8(hash3, c[4]);
                            for (c[5] = 'a'; c[5] <= 'z'; ++c[5]) {
                                uint32_t hash5 = _mm_crc32_u8(hash4, c[5]);
                                for (c[6] = 'a'; c[6] <= 'z'; ++c[6]) {
                                    uint32_t hash6 = _mm_crc32_u8(hash5, c[6]);
                                    if (hashes[hash6]) {
                                        std::cerr << "collision at ";
                                        std::copy(std::cbegin(c), std::cend(c), std::ostream_iterator<uint8_t>(std::cerr, ""));
                                        std::cerr << " " << hash6 << '\n';
                                        return;
                                    }
                                    hashes.set(hash6);
                                }
                            }
                        }
                    }
                }
            }
            std::cout << "c[0] = " << c[0] << std::endl;
        }
    };
    for (uint32_t seed = 0; seed != std::numeric_limits<uint32_t>::max(); ++seed) {
        findCollision(seed);
    }
    findCollision(std::numeric_limits<uint32_t>::max());
}

int main()
{
    findSeed();
}

很明显，对于长度为 7 的字符串，不可能找到这样的种子，因为('z' - 'a' + 1)^7 = 26^7 = 8 031 810 176 > 4 294 967 296 = size_t(std::numeric_limits<uint32_t>::max()) + 1. 但值得注意的是，对于字符串和abfcmbk任何种子来说，都有第一次碰撞。当碰撞发生时，不同的种子不同。我心中很好奇。baabaaahash6

怎么解释？

4

2 回答 2

6

如果CRC(seed,dat)是 的 CRC dat，使用指定的seed，那么对于任何种子（seed1，seed2）和匹配长度的数据对（dat1，dat2），并且给定 CRC（seed1，dat1），可以CRC(seed2,dat1)通过计算 xor 来计算CRC(seed1, dat1), CRC(seed1,dat2), 和CRC(seed2,dat2).

这反过来意味着，如果两条数据对任何特定种子产生相同的 CRC 值，它们将为每个可能的种子产生相同的值。如果对于任何seed1,CRC(seed1,dat1a)等于CRC(seed1,dat1b), 并且字符串长度相等, 那么对于任何其他种子seed2和相同长度的数据dat2,CRC(seed2,dat1a)将等于CRC(seed1, dat1a) xor CRC(seed1,dat2) xor CRC(seed2,dat2), 并且CRC(seed2,dat1b)将等于CRC(seed1, dat1b) xor CRC(seed1,dat2) xor CRC(seed2,dat2)。由于 xor 的所有三个项都相等，这意味着结果将同样相等。

于 2020-09-26T19:40:29.960 回答
3

正如另一个答案中所述，CRC对此无能为力。相反，您应该简单地将六个或更少的小写字母编码为 26 个 32 位整数，并根据字符串的长度进行一些偏移。n=0 到 6 的 26^n 之和小于 2^32。实际上要少得多，因为它可以用 29 位编码。或者正如 Peter Cordes 评论的那样，在 30 位中包含六个 5 位字段。

不会有碰撞。如果有用，您可以对该整数应用 32 位 CRC 来打乱这些位，这样就不会再发生冲突了。

正如您所观察到的，不可能在 32 位中对七个或更多小写字符进行唯一编码。

于 2020-09-27T14:13:25.297 回答