六字符短哈希算法

Question

我的目标是为一个长度为42个大小写不敏感的字母数字字符的字符串生成一个包含[A-Z][a-z][0-9]字符的6个字符的短哈希字符串。唯一性是主要要求，安全性或性能并不那么重要。

是否有特定的算法可以达到这个结果，还是应该坚持截取MD5哈希或SHA-1哈希 (就像这个问题中的方法)？如果有，那么碰撞的概率是多少？

- Isuru

---

我试过了这个：string sourceString = "SomeTestStringWhichIs42CharactersInLength!"; Console.WriteLine(sourceString.GetHashCode().ToString("X6"));它返回一个8位哈希值。 - Isuru

如何为一个长度为42个字符的字符串生成一个唯一的6个字符哈希值？ - Paolo Tedesco

在您的限制下，您最多可以哈希62^6个数字而不发生冲突。尽管在哈希一半数量的数字后，您最多有50％的碰撞几率。当然，这取决于要哈希的数据和哈希算法。某些算法将在不同的数据集上表现更好。 - Bob2Chiv

Answer 1

你最好使用截断的著名哈希函数（MD5或SHA系列），因为这些算法具有统计上良好的哈希值均匀分布（并且使用完整哈希而不仅仅是6个字符）。

现在来计算一下碰撞的概率

- 英文字母数量：26 - 加入大写字母：26 - 加入数字：10 -------------- 总共得到了62个字符。

现在你有6个位置，这给你了62^6种可能的组合。 那是56,800,235,584〜57亿个组合。 这是可能的哈希值空间-N。 -------------- 为了计算碰撞，让我们使用公式

Pcollision = K^2 / 2N

这是一个非常粗略的碰撞概率近似公式。

现在让我们看看表格中的结果，其中包含了表中项目的数量-K

# items | Probability of collision --------------------------------------- 10 | 1.7 * 10^-9 100 | 1.7 * 10^-7 1K | 1.7 * 10^-5 10K | 1.7 * 10^-3 100K | 0.17

这个公式只适用于小的K值，但它表明，在哈希表中有100K个条目时，你大约有17%的碰撞几率。

链接

碰撞概率

- oleksii

---

感谢您的指导性评论。但是我认为您在表格中计算了Pcollision = K^2 / N，而不是Pcollision = K^2 / 2N？ - Alex Moore-Niemi

这些哈希算法的截断形式是否有数学证明与完整版本具有相同的特性？ - Robert Fischer

Answer 2

简单的哈希 :)

private string Hash(string str)
{
    var allowedSymbols = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".ToCharArray();
    var hash = new char[6];

    for (int i = 0; i < str.Length; i++)
    {
        hash[i % 6] = (char)(hash[i % 6] ^ str[i]);
    }

    for (int i = 0; i < 6; i++)
    {
        hash[i] = allowedSymbols[hash[i] % allowedSymbols.Length];
    }

    return new string(hash);
}

- Viacheslav Smityukh

---

由于 hash[i % 6] ^ str[i] 中的 XOR 运算，该算法具有较高的冲突率。原文指出输入字符串对大小写不敏感，对于所有字符，a-z 和 A-Z 的最高两位都相同。即使使用了所有常规可打印 ASCII 字符（0x20-0x7e），对于字符集的 66％，最高两位仍然相同。 - Syon

非常适合我。我必须根据名称和嵌套元素的程度生成颜色。https://jsfiddle.net/fgg8xx2k/ 的示例是用TypeScript编写的。 - Venson

我发现这个函数非常适合我的使用，但它存在高碰撞率的问题。我的解决方案是先使用MD5对我的字符串进行哈希处理，然后再使用这个函数来获得用户友好的输出。这似乎为我解决了问题。 - Feng Jiang

Answer 3

最好的解决方案几乎可以使用SHA1，转换为Base62（尽管Base64会更容易，因为它内置在框架Convert.ToBase64String中。您将需要寻找一个不错的Base62库），然后将输出截断为6个字节。

我不会使用GetHashCode()，因为它存在冲突问题历史记录。（我并不是要声称这个特定的错误适用于您，只是提到这一点作为GetHashCode过去实现得不好的证据。）

我也不会实现自定义哈希算法，因为很容易无意中编写具有高碰撞率的算法。对SHA1和其他主要哈希算法进行了大量研究和审查，您很难想出任何更好的东西。

- Syon