Hash algorithm for hardware?

I think the speed will depend on the stream size.

Hash over what data? A 32 bit word? A variable length string of data?

Followup to: By author: snipped-for-privacy@yahoo.com (John M) In newsgroup: comp.arch.fpga

Use a wider CRC? What is your collision metric? For statistically collisionless hashing, you need to keep in mind the birthday paradox, which states that if you have N items, you have ~50% chance of collision with N^2 hash values; this is functionally equivalent to saying that if you have 2^n items you want >> 2n bits of hash.

-hpa

The hardware implementation would be greatly simplified if you can be sure there are no collisions. However, this is only practical if you know a 'worst case table', for example something like a word list. If you do, there are things called "perfect hash function generators". These create a hash function that is guaranteed to hit first time on each hash. You need to give an input table, a hash table size, and lots-o-cpu to calculate the function parameters. Take a look at the Gnu Perfect Hash generator (gperf) as an example:

-bh

The hash function used in Java of strings multiplies each byte by

Kolja Sulimma

I need to hash over variable sized keys (from 72-288 bits) and produce a hash that is 20 bits. The bits would be presented in 32-bit words. I do have access to a sample data base that can be used to determine how well a hash will perform in terms of collisions. I can't really say what type of data it is, other than it is not text. Thanks for everyone's help so far.

John

(snip)

With a 20 bit hash, you will have a reasonably collision probability at 1000 keys. The number of key pairs is N*(N-1)/2.

CRC's are fairly easy to compute in FPGAs, even much larger than

-- glen