c为字符串生成唯一整数(4字节或8字节)

Question

如果我有一个由字符a-z和"组成的字符串列表"（即总共27个字符），每个字符串的最大大小可以是256字节，我可以有一个0冲突的哈希函数吗（实际上，而不是理论上）？完美的散列函数在这里不起作用，因为字符串不仅仅是只读的。

我知道生成一个0冲突的哈希函数是不可能的，我对一个实用的解决方案感兴趣。

我可以使用md5sum，但它会生成一个16字节的整数。我只想要4个字节或最多8个字节。

Answer 1

一个解决方案：只需使用已知的散列函数，如MD5，并使用最低的4或8个字节。

Answer 2

其他人已经提出了正确的解决方案（使用哈希和），但如果你真的对尽可能少的冲突感兴趣，这里有两个想法可以在更大范围内考虑这个问题：

1. 如果您在内存中保留了要为其生成ID的部分（或全部）字符串，则可以使用存储字符串的内存地址作为ID。假设可以在适当的位置更改字符串，则在字符串更改时，此ID甚至会保持稳定。

2. 使用一些简单的压缩系统（例如miniLZO）将列表中的字符串压缩为某种内部表示形式可能是可行的。您可能最终要散列的数据要少得多，因此可能会有一个更简单的散列函数。当然，通过这种方式计算哈希会更昂贵，但您可能能够避免冲突。

Answer 3

某种校验和或散列是的正确答案。

你不能避免碰撞，这是对的。但是，如果您将校验和或哈希缩短到只有4个字节，那么冲突的频率将大幅增加。

如果可以的话，你可以看看http://en.wikipedia.org/wiki/Hash_function找到一个你觉得舒服的。

Answer 4

由于您的数据是有限的，您可以使用它来指导哈希。

假设字符串是以nul结尾的ASCII，您可以从映射到一个小整数开始。

char *charset = "abcdefghijklm"
                "nopqrstuvwxyz.";
int c = strchr(charset, *s++) - charset;

然后，将每个值视为以27为基数的数字。通过将和乘以27进行解码，然后将当前字符的0-26"单位"相加。你提到了最大长度。我猜这意味着字符串存储在固定长度的数组中。如果是这样的话，并且数组不仅是nul终止的，而且是nul填充的。然后，您可以反向解码数组，将显著差异放在27基数的最低有效"位置"。但是，如果尺寸只是一个很大的高估值，并且大多数字符串预计会短得多，那么最好向前扫描并在nul上终止。

int sum;
sum *= 27;
sum += c;