星期日, 一月 11, 2009

无影灯与散列(HASH)函数的选择

  医学手术对于灯的要求是很高的,关键是不能有影子妨碍医生观察手术的情况。在物理学上,灯光如果被阻挡肯定会产生影子,这样一个难题是怎样解决的呢?显然用一盏灯是肯定解决不了问题的,那样肯定会在某个方向上留下影子。将一盏变为多盏,互相弥补缺点,这样就成为了无影灯。无影不是某盏灯的功劳,而是多盏灯相互弥补,综合作用的结果。
  散列函数所要解决的问题是碰撞,最好使每个值对应的键都是唯一且二者之间相互转换是低复杂度的。问题总是要辩证分析的,对于每一个具体的散列函数来说,总有一些特殊的值会发生碰撞,而且碰撞的几率会非常大。
  解决这一问题是增加散列函数的个数,这些函数需要精心挑选,互相弥补,达到全局统计上的无影灯效果。对于特定数据,采用哪个散列函数的问题可能有建议,使用智能的判断方法,总是决定使用最优的散列函数。其实这样到犯了矫枉过正的错误,因为选择最优函数的过程是十分耗费时间的,甚至比使用最差的散列函数处理此数据的时间还长。这里使用了另一个技巧,就是随机选择,虽然有可能把数据交给最差的函数处理,但是这种概率已经大大降低。
  这个问题的解决告诉我,解决问题的方法不单单是找到一种最好的,有的时候三个臭皮匠也是可以一起上阵的。同时,我们不能为了极小的不足而放弃一种方法,思想上要追求完美,但有时残缺也是一种美和优雅~~

没有评论: