Very low cost hash function

Question

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.

Answer 1

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/

Answer 2

CRC?

There is already a lot of hardware support for this too.