非常低成本的哈希函数

我需要一个查找表的哈希函数,所以如果我的值从0到N,我需要一个哈希函数给我一个从0到n的值,即n << N.另一条信息就是我已事先知道N.

我一直在研究不同的低成本哈希函数,我发现只有这个:

h = z mod n  range(z) - 0 to N, range(h) - 0 to n

我的哈希函数需要在HW中实现,因此它需要具有非常低的成本.任何人都可以推荐除了那个简单的东西之外的任何其他公式或算法？当我说HW时,我的意思是硬件中的真正实现,而不是微处理器中的指令.

谢谢.

更新解决方案

感谢所有答案,我不打算选择一个最喜欢的答案,因为根据目标应用程序的特性,它们都同样有效.

规范形式是h(x) = (a*x + b) mod n,其中a和b是常量,n是哈希表的大小.您想要制作n素数,以获得最佳(ish)分布.

请注意,这对某些类型的分布很敏感 - 例如,刚刚做x mod n的主要是依赖于低阶位的随机性; 如果它们在你的集合中不是随机的,你会得到相当大的偏差.

Bob Jenkins设计了几个非常好的散列函数; 这是一个专门设计为在硬件中实现的简单方法:http: //burtleburtle.net/bob/hash/nandhash.html

对于许多不同的哈希函数,设计讨论等,请参阅网站的其余部分:http://burtleburtle.net/bob/hash/