由一篇误导性性的文章说起-再谈hash

前段时间跟某大牛叽歪的时候，才被提到我写的一篇文章里(http://code.google.com/p/ttsunny)提到的CRC32算法有误。今天写代码，恰好需要用到这个函数，想起来了，就又回去看了下。确认了下，原先的文章并没有错误，但是有一处描述是很有问题的,极易误导人。
      原文是这样的，『综合以上的思路，决定采用CRC32来实现。CRC32也是一个哈希算法，和MD5类似，不过它是32位的，故更短一些,速度也更快。它所能表示的范围为40亿，也会产生冲突，但是对以一般应用足够了，这也是个成本很低廉的做法。』
这只是我提到的一种简单做法而已。但是我确实是在这里可能误导数学不好的读者。我们知道，CRC32是32位的，MD5是128位（谁说16位、32位，我敲死他），也就是CRC128的演化版。通常我们习惯用MD5来做hash。但是我在此文为了简单和压缩长度，使用了CRC32。容易知道，CRC32发生冲突的概率是1//2^32，即大约40亿分之一。
     这是不是说在实际应用中，我们就可以大胆使用CRC32了呢？因为一般来说，我们所用的数据很少过亿，更别说40亿了。在原文，我是作为短网址算法的引子展开的。就算腾讯那样的规模，也没那么容易超过40亿（腾讯的短网址算法是用在微博里的）。如果你回答，应该是的。那么我断定，你一定没上过大学，要么就是你的高数是周公教的。在这里，我们说的40亿分之一的概率指的是40亿个对象CRC32后一定有一个会冲突。在概率论中，尤其要注意至少这样的字眼。CRC碰撞的概率是2^-32次方，这并不表明在40亿（2的32次方）的数据中就才可能产生一个碰撞，而是比这大得多。
  假设有1000万组数据，
则第一个数据不碰撞的概率为,1/4000000000
第二个数据不和第一个碰撞的概率是(4000000000-1)/4000000000
以此类推，1000万个数据完全不碰撞的概率是个小的不能再小的数字，反过来，就是有可能碰撞了。1减去一个小的不能再小的数据，即“完全不碰撞”的逆事件，那么就是一个大的不能再大的数据了（和小于1的数比较）。想到了什么？生日悖论！不是吗？
  任意两个数经过CRC32后不碰撞，是一个随机事件。根据期望的线性限制，对模型简化，可以得到，碰撞对的数目，即E(X)=k(k-1)/2n，代入1000万，结果可知。实际上，只需要92682组数据，CRC32就已经有碰撞的可能性了。
   那么为了让1000万组数据碰撞的可能性不大于1/2，也该有多少位呢？如果利用从一个全散列中随机选出的散列函数h,将n个关键字存储到一个大小为m=n^2的那么出现碰撞的概率小于1/2.E(X)=(n,2)*1/n^2<1/2（此式子来自算法导论，证明略）。即N的桶最好承载square(N)的数据，这样保证冲突概率小于50%。
     到这里已经很清楚了，CRC32不是足够用，而是用不成的。原文也提供了另一种思路。
    更多知识请参考概率论。希望你没有被我之前的文章所误导，也希望此文没有误导人。有兴趣的话，可以去看下生日悖论。这也告诉我们，学好概率很重要。不然你用我的那个结论做出来的程序，其BUG一定不少。

nice

虽然在博客里已经看过一遍了，但还是要支持。
特别是知识普及贴。