字符串 conversion/shortening 到类似于 url-shortener 的固定长度
String conversion/shortening to a fixed length similar to url-shortener
我需要将唯一字符串 ID 缩短为最多 12 个字符。
转换前 ID 可以长于或短于 12 个字符，但转换后其长度必须短于或等于 12。转换后也可以表示为int甚至float
在同一个字符串上使用此函数应该始终return相同的缩短 ID。但是，它永远不会 return 两个不同 ID 的相同值。
(我知道，从理论上讲，这对于固定数量的输出字符是不可能的，但是如果不太可能两次产生相同的结果，那没关系，因为我只处理一个几千个ID。)
我在想一个散列函数，但你不能真正指定 return 值的长度。
一个好处是函数的可逆性，作为一个 URL 缩短器，但我也可以为此目的创建一个字典。
对于适用于这种情况的算法的任何提示，我们都将不胜感激！
让我们做一些数学运算。输出中有 12 个不区分大小写的字母数字字符，您将有 36 个不同的输出字符（26 个字母 + 10 个数字），以及 36^12 个可能的不同输出。如果哈希函数很好，其中的熵将为 log2(36^12) = 62 位。
虽然根据生日悖论，那么多可能性的平方根已经产生了 50% 的碰撞机会，即。在 2^31 哈希中很可能会有一个，50% 很多。 2^31不算多，20亿多一点。
使用 n 个哈希，使用完美的加密哈希函数，您将获得 p:
的碰撞机会
n=1000: p=10^-13
n=10000: p=10^-11
n=100000: p=10^-9
n=1000000: p=10^-7
...
如果您采用 SHA2 等已知良好散列的前几个字符，您将大都很好。但是，请注意，十六进制编码形式的 SHA2 输出的熵要少得多，每个字符只有 4 位，因此哈希输出的十六进制表示的 12 个字符将只有（略小于）48 位的熵。使用 1000 个这样的值将有略小于 1.77 * 10^-9 的机会发生碰撞，10000 将有 1.77 * 10^-7 的机会，100000 将是 1.77 * 10^-5，100 万已经在 0.1 中%数量级等等。
这是否足够好，只有您自己知道。
我需要将唯一字符串 ID 缩短为最多 12 个字符。 转换前 ID 可以长于或短于 12 个字符，但转换后其长度必须短于或等于 12。转换后也可以表示为int甚至float
在同一个字符串上使用此函数应该始终return相同的缩短 ID。但是，它永远不会 return 两个不同 ID 的相同值。
(我知道，从理论上讲，这对于固定数量的输出字符是不可能的，但是如果不太可能两次产生相同的结果，那没关系，因为我只处理一个几千个ID。)
我在想一个散列函数，但你不能真正指定 return 值的长度。 一个好处是函数的可逆性，作为一个 URL 缩短器，但我也可以为此目的创建一个字典。
对于适用于这种情况的算法的任何提示，我们都将不胜感激！
让我们做一些数学运算。输出中有 12 个不区分大小写的字母数字字符，您将有 36 个不同的输出字符（26 个字母 + 10 个数字），以及 36^12 个可能的不同输出。如果哈希函数很好，其中的熵将为 log2(36^12) = 62 位。
虽然根据生日悖论，那么多可能性的平方根已经产生了 50% 的碰撞机会，即。在 2^31 哈希中很可能会有一个，50% 很多。 2^31不算多，20亿多一点。
使用 n 个哈希，使用完美的加密哈希函数，您将获得 p:
的碰撞机会n=1000: p=10^-13
n=10000: p=10^-11
n=100000: p=10^-9
n=1000000: p=10^-7
...
如果您采用 SHA2 等已知良好散列的前几个字符，您将大都很好。但是，请注意，十六进制编码形式的 SHA2 输出的熵要少得多，每个字符只有 4 位，因此哈希输出的十六进制表示的 12 个字符将只有（略小于）48 位的熵。使用 1000 个这样的值将有略小于 1.77 * 10^-9 的机会发生碰撞，10000 将有 1.77 * 10^-7 的机会，100000 将是 1.77 * 10^-5，100 万已经在 0.1 中%数量级等等。
这是否足够好，只有您自己知道。