c# - 6 字符短散列算法

Question

我的目标是为长度为 42 个不区分大小写的字母数字字符的字符串生成一个 6 个字符的短哈希字符串（可能包含字符 [AZ][az][0-9]）。唯一性是关键要求。安全性或性能并不那么重要。

是否有特定的算法会给出这个结果，或者我应该坚持截断 MD5 哈希或 SHA-1 哈希（就像在这个问题中一样）？如果是这样，碰撞的概率是多少？

Answer 1

您最好的选择是截断众所周知的散列函数（MD5 或 SHA 系列），因为这些算法在统计上具有良好的散列值均匀分布（并且还使用完整的散列，而不仅仅是 6 个字符）。

现在计算碰撞概率

- 英文字母数量：26
- 添加大写字母：26
- 添加数字：10
--------------

总共你得到 26 + 26 + 10 = 62 个字符。

现在您有 6 个位置，这为您提供了 62^6 种可能的组合。
即 56.800.235.584 ~ 570 亿个组合。
这是一个可能的哈希值空间 - N。
--------------
要计算碰撞让我们使用公式

Pcollision = K^2 / 2N

这是碰撞概率的一个非常粗略的近似值

现在让我们看看一个表中的多个项目的结果表 - K

# 项目 | 碰撞概率
--------------------------------------
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% 的碰撞机会。

链接

碰撞概率

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);
}

Answer 3

最好的解决方案几乎肯定是使用 SHA1，转换为 Base62（尽管 Base64 会更容易，因为它内置在框架Convert.ToBase64String中。你必须做一些寻找一个像样的 Base62 库），然后截断输出到 6 个字节。

我不会使用GetHashCode()，因为它有碰撞问题的历史。（我并不是要声称这个特定的错误会适用于您，只是将此作为GetHashCode过去没有很好实施的证据。）

我也不会实现自定义散列算法，很容易意外编写具有高冲突率的算法。SHA1 和其他主要的散列算法已经进行了大量的研究和审查，你很难想出更好的东西。