我试图找到种子来散列最大可能长度的小写字母的短字符串而不会发生冲突。 我选择了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和baabaaa对于任何种子，都会发生第一次碰撞。 发生碰撞时，不同种子的hash6不同。我心里很好奇。
怎么解释？
如果CRC(seed,dat)是dat的CRC，使用指定的seed，那么对于任何种子(seed1，seed2)和匹配长度的数据对(dat1，dat2)，并给定CRC(seed1，dat1)，可以通过计算CRC(seed1, dat1)，CRC(seed1,dat2)和CRC(seed2,dat2)的异或来计算CRC(seed2,dat1)。
这反过来意味着，如果两条数据对任何特定种子产生相同的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)。 由于异或的所有三个项都相等，这意味着结果也将同样相等。
正如另一个答案中所指出的，CRC对此无济于事。相反，您应该简单地将六个或更少的小写字母编码为基数 26 个 32 位整数，并根据字符串的长度进行一些偏移。n=0 到 6 时 26^n 的总和小于 2^32。实际上要少得多，因为它可以用 29 位编码。或者正如彼得·科德斯(Peter Cordes)所评论的那样，在30位中，带有六个五位字段。
不会有碰撞。如果它有用，您可以将 32 位 CRC 应用于该整数以对位进行加扰，并且不会再次发生冲突。
正如您所观察到的，不可能以 32 位对七个或更多小写字符进行唯一编码。