计算科学 - 在集合概率中散列？ - 吾爱随笔录

计算科学可能性

2021-12-07 22:10:55

首先，我想提一下，我在统计方面绝对很糟糕……所以请多多包涵。

问题：

sha1 哈希是 40 个字符的十六进制字符串，最大的数字是：

ffffffffffffffffffffffffffffffffffffffff

如果将其转换为小数，则变为1.2830013993246E+48.

我不知道确切的值是什么或如何获得它，但可以说它是X.

使用 sha1 算法散列的 X 个唯一字符串将具有 sha1 字符串的每个可能的字符组合的概率是多少？

这也适用于其他哈希算法吗？

基本上是 2^160 个唯一字符串的序列保证生成 sha1 哈希的每个可能组合吗？

PS如果有人对这个问题有更好的标题，那将不胜感激，我也不确定这是否是问这个问题的最佳地点：/

3个回答

要回答您的编辑...

基本上是 2^160 个唯一字符串的序列保证生成 sha1 哈希的每个可能组合吗？

不，几乎没有机会。概率是一些双指数，如 exp(-exp(100))。

假设您奇迹般地没有看到前 2^160 - 1 个唯一字符串之间发生冲突。那么你最后一个唯一的字符串仍然有大约 (2^160-1)/(2^160) 散列到你已经看到的 sha1 值的概率。

概率为零，因为 X 比 sha1 字符串的可能字符组合的数量少（减一）。

如果您反复从 bin 中选择元素 $n$ 对象，每次替换对象，期望每个元素至少选择一次的时间是

E = n (\log n + γ + o (1)) .

$E = n \left(\log n + \gamma + o(1)\right).$ 为了

n = 2^{160}

$n = 2^{160}$ ，这是

1.6 \times 10^{50}

$1.6 \times 10^{50}$ .

要看到这一点，请注意选择一个新对象的概率，如果 $k$ 已经选择的元素是 $(n-k)/n$ . 求和给出

E = \sum_{k = 0}^{n - 1} \frac{n}{n - k} = n \sum_{k = 1}^{n} \frac{1}{k} = n H_{n}

$E = \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{k=1}^n \frac{1}{k} = n H_n$ 在哪里

H_{n}

$H_n$ 是个

n

$n$ 次谐波数。

其它你可能感兴趣的问题