介绍
传统的哈希方式采用一个大的连续空间来存储元素，当元素满了之后，它需要将空间的容量扩充为两倍，并将之前所有的元素重新哈希到新的空间里面，这个过程成为Rehash. 现在我们有一个问题是，
如果将数据按照范围等分成K份，将一个大的空间等分成K个桶。然后将每一份数据分别hash到对应的桶里面，这样做的话，hash的冲突数量和之前的相比如何？
传统hash的冲突数量
假设现在连续空间的大小是M，即它有M个位置。我们在这里面插入N个数据，那么hash冲突的期望值是多少？为了便于数学分析，我们假设hash函数是完美的，也就是hash到每一个位置的概率是相等的。
hash冲突数量的定义是每一个位置冲突数量的总和，其中每一个位置的冲突数量是有该位置存储元素的个数决定的。对于任意一个位置$p$,定义$n(p)$为该位置实际存储的元素数量。如果$n(p) \ge 2$，则该位置的冲突数量$C_p = n(p)-1$，否则该位置的冲突数即为0.
为了求得hash冲突的期望值，我们令随机变量$X$为hash冲突的总数量。为了求期望$E(X)$，我们同样利用期望的线性性质，将X拆成几个较小的随机变量之和。定义随机变量$Y_i$为第$i$个位置的冲突数量，则随机变量$X$和$Y_i$的关系为
$$
X = Y_1 + Y_2 + … + Y_M
$$
接下来，我们讨论如何求随机变量$Y_i$的期望。首先$Y_i$的取值范围为$[0,N-1]$. 对于每一个元素，它被放到第$i$个位置的概率为$p = \frac{1}{M}$，放到了其他位置的概率为$q= \frac{M-1}{M}$。定义$b_i$为该位置中放入了$i$个元素的概率，则$b_i= C_{M}^{i} \cdot p^i \cdot q^{N-i}$。则变量$Y_i$的期望$E(Y_i)$为
$$
E(Y_i) = 0 (b_0 +b_1) + 1b_2 + 2b_3 + … + (N-1)b_N
$$
这个二项分布的期望非常类似，也就是说我们已经知道
$$
Np = 0b_0 + 1 b_1 + 2b_2 + 3b_3 + … + Nb_N
$$
所以，把两个式子相减，我们就得到
$$
Np - E(Y_i) = b_1 + b_1 + b_2 + b_3 + … + b_N = 1-b_0 = 1 - q^N
$$
所以，$E(Y_i) = \frac{N}{M} + (\frac{M-1}{M})^N -1$，可以看出，这个期望和位置$i$是没有任何关系的，因此我们可以得到随机变量$X$的期望
$$
E(X) = M \cdot E(Y_i) = N - M + M \cdot (\frac{M-1}{M})^N
$$
至此，我们就从数学上分析了，对于传统哈希来说，他的理论冲突数量是多少。那么现在的问题是，如果我把分成多个较小的桶进行hash，会导致理论冲突数量增多么？
多桶hash的冲突数量
多桶hash，也就是说现在hash的空间不再是一个，而是多个大小相同的桶，比如说一共$K$个。那么，对于任意一个数来说，首先我们决定它要哈希到的桶$B_i$，然后在$B_i$中进行hash。我们假设每一个元素去每一个桶的概率和每一个元素到桶里面的每一个位置的概率都是相同的。那么在这种情况下，总hash冲突数量会有变化么。
我们考虑相同的情况，也就是说这K个桶的总大小也为M，所需插入的总量也为N。那么平均每一个桶的容量为$M_B = \frac{M}{K}$,每一个桶的插入数量为$N_B = \frac{N}{K}$。在这种情况下，我们套用上面推导出来的公式，得到其冲突数的期望为
$$
E(B) = \frac{N}{K} - \frac{M}{K} + \frac{M}{K} \cdot (\frac{M-K}{M})^{\frac{N}{K}}
$$
同样，每一个桶的冲突数量的期望都是一样的，而我们一共有K个桶，所以最终总的冲突数为
$$
E(X) =N- M+ M \cdot (\frac{M-K}{M})^{\frac{N}{K}}
$$
结论
通过上面的分析我们可以发现，多桶hash和单桶hash的冲突数量的唯一差别在于$f(K)= (\frac{M-K}{M})^{\frac{N}{K}}$这一项上，由于函数$f(K)$不是单调的，所以单桶hash和多桶hash的冲突数量关系是不确定的。可能多个桶的情况下，hash出来的冲突数量会更少也是完全有可能的。
事实上，由于$M,N$一般都是比较大的数，而$K$一般数值较小，因此$f(K)= (\frac{M-K}{M})^{\frac{N}{K}}$的值都差不多，也就是说多桶hash并不会导致冲突数量的明显增加。
