哈希表之数学原理 哈希表之数学原理

   .NET程序员，大多数时候是不需要数学的。因为，有了.NET, 数据结构和算法的重要性被弱化了，操作系统接口相关的东西被强化了。程序员只要求管理好代码，而不是设计好算法。

    计算机，我只学会了技术，所以很多问题我都感觉似是而非，感觉是在学习一个API，而不是在学一门科学。

    最近要实现一个哈希表，我查找了很多哈希函数，高下难分。而且，网上有很多人做了实验，但是，很多数据居然是矛盾的，有的说这个好，有的说那个好。于是我在想，有没有一种理想的最优函数，这样的函数的效率是多少。我的函数，只要接近于这个值就可以了。这样的理想函数的分析，就必须理解计算机的科学部分，这个是计算机科学永恒的部分。

   首先，是一个很简单的也是很实用的问题：

“给一个url 做一个hash 值，通过这个hash 值，查找这个url 是否已经在数据库中存在了，我相信很多人都做过这个问题，很多人采用把一个url 转换成一个无符号的int 类型，然后通过这个int 类型进行查找。现在的问题是，如果我的网站有1000万个url，会有多少个url 是发生哈希冲突呢，也就是说，url链接不一样，但是映射成了相同的哈希值。”有多少冲突，读完这篇文章你也就会算了。

 

    我今天讲的只是哈希表中的一种类型：链地址哈希表。这种哈希表是最常用的哈希表，PHP数组的内部实现，就是采用这样的哈希表。估计.net 的字典类，也是通过这样的方法。

    链地址法相当的简单：就是先分配一个大数组，数组的元素是一个链表，然后，把key 映射到每个数组的链表上，如果有重复，那么就加到链表的后面去。不懂的可以去翻翻数据结构的书。

这个数组的长度为m，所以会有m个链表，现在的问题是，我有n个key，并且假设 n < m 。问：

没有元素的链表有多少个

只有一个元素的链表有多少个

有两个元素的链表有多少个

.....

这个问题虽然不是很复杂，但是，还是要稍微的转换一下，动一点点的脑筋。

看问题本身，好像是一个组合学的问题，就是有m个位置,n个元素往里面放。从这个角度可以做，但是，比较麻烦。考虑这样一个问题, 任意一个元素，在某个位置不出现，出现一次，出现两次... 出现n 次的概率。你会发现，这个其实就是上面的链表元素个数的问题。这里，假设元素都是一样的，位置也都是一样的。

这就是一个binary 分布的问题。不懂的可以看概率论的书本。

这样，链表有k 个元素的概率分布函数如下：

p = 1 / m

f[k] = (C[n,k]  * p^k * (1-p)^n-k );

现在我假设 m = 2^14, n = 10000

可以求出概率分布如下：

可以看出，大概54%的链表是空的，大概33%的链表有一个元素,10%左右的链表有两个元素。如果，你的哈希函数写的好，基本上，要接近上面的数字。如果超过了这个数字，哈希函数也会有问题。这个我已经通过实验证明了这一点。可能在接下来的章节中介绍我实现的哈希表。

当然，设计哈希表，最重要的是要求其平均查找长度最小。

所有一个元素的链表包含的元素数目为 m * f[1] * 1, 查找这些元素的次数为： m * f[1] * 1 * 1

两个元素的链表包含的元素数目为  m * f[2] * 2，查找这些元素的次数为： m * f[2] * 2 * 2

这样平均查找长度就是：（这里的平均，实际上不是平均，而是考虑最坏的查找情况，比如链表长度为2，平均是1.5次，最坏是2次）

求:

如果，看到这个式子，还不会求和的话，那么你赶快回去看看概率论了。

求出的结果是：

L = 1 + （n-1）/ m

是不是非常简单。

如果n 足够大，比如上万了，那么1就可以忽略了

L = 1 + n / m

这个公式表明，平均查找长度只和 n / m 的比例有关。如果 m > n 那么，理想情况下，不会出现平均查找长度大于2的情况。而，对于100万的数据的平衡二叉树，那么需要20次的查询，性能是10倍。当然，哈希表非常的的浪费内存。

再来看看我们刚开始提出的问题，转换一下就是：m = 2^32 n = 10,000,000.要求重复的数目，只要求出不重复的数目就可以了。就是求f[1] 就可以了，当然，如果你有数学计算软件，这个计算比较耗时，但是肯定能够算出来。

还有一个比较简单的方法，可以简单的估计大概的数目，那就是平均查找长度。这里估计的时候，有一个假设，就是，在一次查找时，只有两种情况，一种是查找一次，一种是查找两次找到。二项分布在m,n相差比较大的时候，随着k的上升，概率下降会非常的快，一般重复3次的就很少了，上面的假设是合理的。这样的话，出现重复的概率就是 n/m 了（可以很简单的推导出来），0.0023，也就是10000个链接里面，就会有23个重复。如果要求比较高的话，基本上，不能采用这样的哈希方法。当然，如果是100万的话，那10000个链接，只有2个重复，基本上是合理的。不过，最好只有10万。这样冲突概率就相当的低了。

接下来的文章，我可能会写哈希表的实现的一些技巧，如何管理内存，如何分配哈希表的长度（根据不同的需求）。