All,
I am looking for an efficient hashing algorithm that can be easily translated to an FPGA. The hash does not have to be cryptographically secure, as I am just using it for a hash table lookup. Instead, I need it to run very fast (~25 Million hashes per second). Does anyone know of any resources where I could find such an algorithm? I have found a couple CRC-based algorithms, but I am concerned they will result in too many collisions. Thanks for your help.
John
I think the speed will depend on the stream size.
Hash over what data? A 32 bit word? A variable length string of data?
-- Ben Jackson http://www.ben.com/
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
31^n. A multiplication by 31 requires just one adder this means that you can implement it using only one adder in n clock cycles for n input words.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
20 bits. I did a 64 bit CRC (in software) once when N was in the millions to get the collision rate reasonably close to zero.-- glen
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.