哈希表碰撞（溢出）概率计算

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 4k 阅读时长 ≈ 5 分钟

这篇文章简单谈谈目前业界使用的密码学库中，是如何计算哈希表（Hash table）的桶（bin）碰撞（溢出）概率的。

昨天遇到这样一个问题：在GitHub中，osu-crypto/BaRK-OPRF这个密码学相关repo中，有如下代码：

BaRK-OPRF/bOPRFlib/Common/Defines.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
double getBinOverflowProb(u64 numBins, u64 numBalls, u64 binSize, double epsilon = 0.0001)
{
    if (numBalls <= binSize)
        return std::numeric_limits<double>::max();

    if (numBalls > unsigned(-1))
    {
        auto msg = ("boost::math::binomial_coefficient(...) only supports " + std::to_string(sizeof(unsigned) * 8) + " bit inputs which was exceeded." LOCATION);
        std::cout << msg << std::endl;
        throw std::runtime_error(msg);
    }

    typedef boost::multiprecision::number<boost::multiprecision::backends::cpp_bin_float<16>> T;
    T sum = 0.0;
    T sec = 0.0;// minSec + 1;
    T diff = 1;
    u64 i = binSize + 1;

    while (diff > T(epsilon) && numBalls >= i /*&& sec > minSec*/)
    {
        sum += numBins * boost::math::binomial_coefficient<T>(numBalls, i)
            * boost::multiprecision::pow(T(1.0) / numBins, i) * boost::multiprecision::pow(1 - T(1.0) / numBins, numBalls - i);

        T sec2 = boost::multiprecision::log2(sum);
        diff = boost::multiprecision::abs(sec - sec2);
        sec = sec2;

        i++;
    }

    return std::max<double>(0, (double)-sec);
}

从函数名能看出是在计算哈希表的桶溢出概率（溢出和碰撞其实是一个意思），但就是这个简简单单的while循环，看的人云里雾里。但稍加分析，我们就可以还原出来这段代码其实是在计算这样一个式子： \[P\{Hash\; overflows\}=numBins \cdot \sum_{k=binSize+1}^{numBalls}C_{numBalls}^{i}(1/numBins)^i(1-1/numBins)^{numBalls - i}.\] 最后的输出结果其实是\(-\log_2 P\{Hash\; overflows\}\)，至于为何如此，后文详谈。先来说说这个式子是怎么来的。

为了方便叙述，我们规范化一下这个问题。

问题设置

一个哈希表可以看成是\(M\)个桶（bin），元素可以看成放进桶里的球（ball），假设每个桶容量（size）相同且固定为\(k\)（很多情况下\(k=1\)）。假设我们已知共有\(N\)个元素（球）要放进桶里，那么哈希表的碰撞概率就等价于

\(N\)个球放进\(M\)个桶里，每个桶最多放\(k\)个球，有任意一个桶溢出（放了超过\(k\)个球）的概率。

下面分步求解。

选定一个桶\(bin_j\)，里面放了\(i\leq N\)个球的概率？

这就是一个简单的二项分布：重复\(N\)次把球放进桶的实验，成功（球放进桶\(bin_j\)）的次数为\(i\)的概率为 \[P\{X=i\}=C_{N}^{i}(1/M)^i(1-1/M)^{N - i},\] 不用多说，请查阅“二项分布”相关资料。

一定注意，这里的前提是我们选定了一个桶，就这个桶而言讨论“成功”。

选定一个桶\(bin_j\)，这个桶溢出的概率？

溢出，即这个桶里放了\(i>k\)个球，那么对上面的\(P\\{X=i\\}\)求和 \[P\{bin_j\; overflows\}=\sum_{i=k+1}^{N} P\{X=i\}=\sum_{i=k+1}^{N}C_{N}^{i}(1/M)^i(1-1/M)^{N - i}.\] 是不是已经看起来很像最开始的式子了？但是还差个系数\(M\)，这是哪里来的？

任意一个桶溢出的概率（的上界）？

前面的讨论都是基于已经选定了某一个桶，但事实上我们有\(M\)个桶，其中任意一个溢出都算哈希表溢出，那么我们要用的工具就是取并集。因此哈希表溢出概率为 \[P\{Hash\; overflows\}=P\{\cup_{j\in[M]}bin_j\; overflows\}.\]

那么问题来了，这个并集怎么算呢？

事实上，很多情况下我们讨论哈希表溢出问题，并不需要确切地知道这个数值，而是要利用这个概率估计哈希表容量应该有多大。我们只需要估计溢出概率的上界，只要容量能满足这个上界，就可以满足我们对哈希表的要求。

为了解决事件的并集概率问题，我们需要借助布尔不等式（Boole's inequality），也叫联合边界（Union Bound）（其实我之前只知道Union Bound这个名字，其他都是现查的）。其实很简单，事件并集的概率不超过单独事件发生的概率之和（不要求事件相互独立）。那么上式进一步化为 \[\begin{aligned} P\{Hash overflows\}&=P\{\cup_{j\in[M]}bin_j\; overflows\}\leq \sum_{j=1}^{M}P\{bin_j\; overflows\}\\ &=\sum_{j=1}^{M}\sum_{i=k+1}^{N}C_{N}^{i}(1/M)^i(1-1/M)^{N - i}\\ &=M\sum_{i=k+1}^{N}C_{N}^{i}(1/M)^i(1-1/M)^{N - i}. \end{aligned} \] 这不就是我们要求的式子吗？

不过代码里为了加速，用了一个小量epsilon控制精度，如果精度够了就可以及时截断。

为什么要取负对数？

这个问题要继续往代码下面看。在这里：

BaRK-OPRF/bOPRFlib/Common/Defines.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
u64 get_bin_size(u64 numBins, u64 numBalls, u64 statSecParam)
{
    auto B = std::max<u64>(1, numBalls / numBins);

    double currentProb = 0;
    u64 step = 1;

    bool doubling = true;

    while (currentProb < statSecParam || step > 1)
    {
        if (!step)
            throw std::runtime_error(LOCATION);

        if (statSecParam > currentProb)
        {
            if (doubling) step = std::max<u64>(1, step * 2);
            else          step = std::max<u64>(1, step / 2);

            B += step;
        }
        else
        {
            doubling = false;
            step = std::max<u64>(1, step / 2);
            B -= step;
        }
        currentProb = getBinOverflowProb(numBins, numBalls, B);
    }

    return B;
}

这里的statSecParam是密码学里的统计安全参数，类似经常听说的SHA256、SHA512里的数字，数字代表bit位数，越大越安全。在这个实现里，这一参数取值范围是uint64的非负整数。

安全参数越大越安全，密码学里碰撞概率（两个本来不同的明文Hash之后结果相同，其实也就是溢出概率）越小越安全；安全参数是非负整数，概率是\([0,1]\)间的实数。如何建立映射关系呢？很简单，就是对概率取负对数，就变成了\([0,\infty)\)的实数，而且越大越安全。这就和安全参数产生了对应关系。

因此，在前面算概率时，就直接返回这个映射过的“概率”，稍后求哈希表容量时，就可以直接和安全参数比较了。

题外话

这个问题其实最早是我在CMU的15-451/651 Algorithms课上，Sleator给我们布置的作业题。当时我真是毫无头绪，多亏了John和Wael两位大哥认真讲解，我才搞明白为啥要用那个之前听都没听说过的Union Bound。没想到这次又在实际中遇到了这个问题，第一次发现Sleator讲的东西是有用的，而不是为了难为我们。

离开美国时走得太仓促，很多东西都没能带走，似乎Algo的lecture notes我是扔下了。想到这里，多少有点惋惜。只能安慰自己，东隅已逝桑榆非晚。