非常低的散列函数 [英] Very low cost hash function

问题描述

我需要一个查找表的哈希函数，这样如果我的值从0到N，我需要一个哈希函数给我一个从0到n的值，其中n < N.另一条信息是我已经预先知道了N。

我一直在研究不同的低成本散列函数，我发现只有这个：

  h = z mod n range（z） -  0 to N，range（h） -  0 to n 
  

我的哈希函数需要在硬件中实现，所以它需要非常低的成本。任何人都可以推荐任何其他的公式或算法，除了那件简单的事情吗？当我说硬件时，我的意思是硬件上的真正实现，而不是微处理器中的指令。

谢谢。

解决方案更新

感谢所有答案，我不是去选择一个最喜欢的，因为它们都是同等有效的，这取决于目标应用程序的特性。 形式是 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/

I need a hash function for a Look Up table, so that if my values are from 0 to N, I need a hash function that give me a value from 0 to n, being n << N. Another piece of information is that I already know N in advance.

I have been investigatinv about different low cost hash functions and I have found only this:

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

My hash function needs to be implemented in HW, so it needs to have a very low cost. Can anyone recommend any other formula or algorithm apart from that simple thing?. When I say HW I mean a truly implementation in HW, and not instructions in a microprocessor.

Thank you.

Update with the solution

Thanks for all the answer, I am not going to select a favourite one, because all of them are equally valid depending on the characteristics of the target application.

解决方案

The canonical form of that is h(x) = (a*x + b) mod n, where a and b are constants and n is the size of your hash table. You want to make n a prime number, to get optimal(ish) distribution.

Note that this is sensitive to certain kind of distributions -- for example, just doing x mod n is mostly relying on randomness of low-order bits; if they are not random in your set, you will get fairly significant skew.

Bob Jenkins has designed several very good hashing functions; here's one specifically designed to be simple to implement in hardware: http://burtleburtle.net/bob/hash/nandhash.html

For a lot of different hash functions, design discussions, etc, see the rest of the site: http://burtleburtle.net/bob/hash/

这篇关于非常低的散列函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！