在几乎所有的教科书和计算机课程中,实现哈希函数有两种基本方法:
- 除留余数法,我们简单地执行
k mod m
,选择 m 为质数且不太接近2的幂。 - 乘法取整法,我们将 k 与某个精心选择的无理数相乘(Knuth 建议使用基于黄金比例的数字),介于0到1之间,取乘积的小数部分,并使用所需数量的最高有效位。
大多数教科书和课程都列出了方法1的几个缺点,包括它很昂贵,而且结果取决于m。然而,我从未见过任何教科书或课程提到方法2的任何缺点。
这使得方法2更受欢迎。此外,方法2可以在现代计算机上变得非常高效,完全消除浮点运算。因此,看起来方法2是毋庸置疑的胜者,没有人应该谈论方法1。但显然并非如此。事实上,我从未见过方法2在任何实际实现中被使用。所以它确实有一些缺点。
问题是它们是什么,为什么方法1尽管有缺点却更常被使用?