Hash概率问题

「爱情、让人受尽委屈。」 2022-07-28 11:43 106阅读 0赞

Hash是把锋利的刀子，处理海量数据时经常用到，大家可能经常用hash，但hash的有些特点你是否想过、理解过。我们可以利用我们掌握的概率和期望的知识，来分析Hash中一些有趣的问题，比如：

*  平均每个桶上的项的个数
 *  平均查找次数
 *  平均冲突次数
 *  平均空桶个数
 *  使每个桶都至少有一个项的项个数的期望

本文hash的采用链地址法发处理冲突，即对hash值相同的不同对象添加到hash桶的链表上。

**每个桶上的项的期望个数**

**　　**将n个不同的项hash到大小为k的hash表中，平均每个桶会有多少个项？首先，对于任意一个项items(i)被hash到第1个桶的概率为1/k，那么将n个项都hash完后，第1个桶上的项的个数的期望为C(项的个数)=n/k，这里我们选取了第一个桶方便叙述，事实上对于任一个特定的桶，这个期望值都是适用的。这就是每个桶平均项的个数。

用程序模拟的过程如下：

[![复制代码][000053C15-0.gif]][000053C15-0.gif 1]

1     /***  2      * 对N个字符串hash到大小为K的哈希表中，每个桶上的项的期望个数  3      *   4      * @return  5      */  6     private double expectedItemNum() {  7         // 桶大小为K  8         int[] bucket = new int[K];  9         // 生成测试字符串 10         List<String> strings = getStrings(N); 11         // hash映射 12         for (int i = 0; i < strings.size(); i++) { 13             int h = hash(strings.get(i), 37); 14             bucket[h]++; 15         } 16         // 计算每个桶的平均次数 17         long sum = 0; 18         for (int itemNum : bucket) 19             sum += itemNum; 20         return 1.0 * sum / K; 21     } 22  23     /*** 24      * 多次测试计算每个桶上的项的期望个数， 25      */ 26     private static void expectedItemNumTest() { 27         MyHash myHash = new MyHash(); 28         // 测试100次 29         int tryNum = 100; 30         double sum = 0; 31         for (int i = 0; i < tryNum; i++) { 32             double count = myHash.expectedItemNum(); 33             sum += count; 34         } 35         // 取100次测试的平均值 36         double fact = sum / tryNum; 37         System.out.println("K=" + K + " N=" + N); 38         System.out.println("程序模拟的期望个数：" + fact); 39         double expected = N * 1.0 / K; 40         System.out.println("估计的期望个数 n/k：" + expected); 41     }

[![复制代码][000053C15-0.gif]][000053C15-0.gif 1]

输出的结果如下，可以看到我们用公式计算的期望与实际是很接近的，这也说明我们的期望公式计算正确了，毕竟实践是检验真理的唯一标准。

K=1000 N=618 程序模拟的期望个数：0.6180000000000007 估计的期望个数 n/k：0.618

**空桶的期望个数**

将n个不同的项hash到大小为k的hash表中，平均会有多少个空桶？我们还是以第1个桶为例，任意一个项item(i)没有hash到第一个桶的概率为(1-1/k)，hash完n个项后，所有的项都没有hash到第一个桶的概率为(1-1/k)^n，这也是每个桶为空的概率。桶的个数为k，因此期望的空桶个数就是C(空桶的个数)=k(1-1/k)^n，这个公式不好计算，用程序跑还可能被归零了，转化一下就容易计算了：

C(空桶的个数)=k(1−1k)n=k(1−1k)−k(−nk)=ke(−nk)(1)

同样我们模拟测试一下：

![0000535354-2.gif][]

输出结果：

K=1000 N=618 程序模拟的期望空桶个数：539.0 估计的期望空桶个数ke^(-n/k)：539.021403076357

**冲突次数期望**

我们这里的n个项是各不相同的，只要某个项hash到的桶已经被其他项hash过，那就认为是一次冲突，直接计算冲突次数不好计算，但我们知道C(冲突次数)=n-C(被占用的桶的个数)，而被占用的桶的个数C(被占用的桶的个数)=k-C(空桶的个数)，因此我们的得到：

C(冲突次数)=n−(k−ke−n/k)(2)

程序模拟如下：

![0000535354-2.gif][]

输出结果：

K=1000 N=618 程序模拟的冲突数：157.89 估计的期望冲突次数n-(k-ke^(-n/k))：157.02140307635705

**不发生冲突的概率**

将n个项hash完后，一次冲突也没有发生的概率，首先对第一个被hash的项item(1)，item(1)可以hash到任意桶中，但一旦item(1)固定后，第二个项item(2)就只能hash到除item(1)所在位置的其他k-1个位置上了，依次类推，可以知道

P(不发生冲突的概率)=kk×k−1k×k−1k×k−2k×⋅⋅⋅×k−(n−1)k

这个概率也是不好计算，但当k比较大、n比较小时，有

P(不发生冲突的概率)=e−n(n−1)2k

模拟过程：

![0000535354-2.gif][]

输出结果如下，这个逼近公式只有在k比较大n比较小时误差较小。

K=1000 N=50 程序模拟的不冲突概率：0.29 估计的期望不冲突概率e^(-n(n-1)/(2k))：0.29375770032353277 程序模拟的冲突概率：0.71 估计的期望冲突冲突概率1-e^(-n(n-1)/(2k))：0.7062422996764672

**使每个桶都至少有一个项的项个数的期望**

**　　**实际使用Hash时，我们一开始并不知道要hash多少个项，如果把桶设置过大，会浪费空间，一般都是设置一个初始大小，当hash的项超过一定数量时，将桶的大小扩大一倍，并将桶内的元素重新hash一遍。查看Java的HashMap源码可以看到，每次调用put添加数据都会检查大小，当n>k\*装置因子时，对hashMap进行重建。

[![复制代码][000053C15-0.gif]][000053C15-0.gif 1]

1 public V put(K key, V value) {  2          if(...)  3               return ...;     4         ...  5         modCount++;  6         addEntry(hash, key, value, i);  7         return null;  8     }   9      /** 10      * Adds a new entry with the specified key, value and hash code to 11      * the specified bucket.  It is the responsibility of this 12      * method to resize the table if appropriate. 13      * 14      * Subclass overrides this to alter the behavior of put method. 15      */ 16 void addEntry(int hash, K key, V value, int bucketIndex) { 17         if ((size >= threshold) && (null != table[bucketIndex])) { 18             resize(2 * table.length); 19             hash = (null != key) ? hash(key) : 0; 20             bucketIndex = indexFor(hash, table.length); 21         } 22  23         createEntry(hash, key, value, bucketIndex); 24     }

[![复制代码][000053C15-0.gif]][000053C15-0.gif 1]

现在我们不是直接当n大于某一个数时对Hash表进行重建，而是预计Hash表的每一个桶都至少有了一个项时，才对hash表进行重建，现在问当n为多少时，每个桶至少有了一个项。要计算这个n的期望，我们先设 Xi 表示从第一次占用 i−1 个桶到第一次占用 i 个桶所插入的项的个数。首先，很容易理解 X1=1 ，对于 X2 表示从插入第一个元素后，占用两个桶所需要的插入次数，理论上它可以是任意大于1的值，我们一次接一次的插入项，每次插入有两种独立的结果，一个结果是映射到的桶是第一次映射的桶；另一个是映射到的桶是新的桶，当占用了新桶时插入了项的个数即为 X2 ，又因为此时映射到新桶的概率 p=k−1k ，因此 X2 的期望 E(X2)=1/p=kk−1 ；同样的道理，占用两个桶后，对任意一次hash映射到新桶的概率为 k−2k ，因此 E(X2)=kk−2 。

现在定义随机变量 X=X1+X2+⋅⋅⋅+Xk ，我们可以看出 X 实际上就是每个桶都填上项所需要插入的项的个数。

E(X)=∑j=1kE(Xj)

=∑j=1kkk−j+1

=k∑j=1k1k−j+1

=令i=k−j+1k∑i=1k1i

上面这个数是一个有趣的数，叫做调和数（[Harmonic\_number][Harmonic_number]），这个数（常记做 Hk ）没有极限，但已经有数学家给我们确定了它关于n的一个等价近似值：

14+lnk≤Hk≤1+lnk

因此 E(X)=O(klnk) ，当项的个数为 klnk 时，平均每个桶至少有一个项。

**结论总结**

*  **每个桶上的项的期望个数：**将n个项hash到大小为k的hash表中，平均每个桶的项的个数为 nk
 *  **空桶的期望个数：**将n个项hash到大小为k的hash表中，平均空桶个数为 ke(−nk)
 *  **冲突次数期望：**当我们hash某个项到一个桶上，而这个桶已经有项了，就认为是发生了冲突
 *  **不发生冲突的概率：**将n个项hash到大小为k的hash表中，平均冲突次数为 n−(k−ke−n/k)
 *  **调和数：** Hk=∑ki=11i 称为调和数， ∑ki=11i=Θlogk

本文主要参考自参考文献\[1\]，写这边博客复习了一下组合数学和概率论的知识，对hash理解得更深入了一点，自己设计hash结构时能对性能有所把握。另外还学会了在博客园插入公式，之前都是在MathType敲好再截图。

[000053C15-0.gif]: http://img.kuqin.com/upimg/allimg/140620/000053C15-0.gif
[000053C15-0.gif 1]: /images/20220724/5dc2ba5fbc6b40c58edddb81d770c57f.png
[0000535354-2.gif]: http://img.kuqin.com/upimg/allimg/140620/0000535354-2.gif
[Harmonic_number]: http://en.wikipedia.org/wiki/Harmonic_number