4

I have an application where each element is identified by a unique 32-bit number, aka the "key". My main concern is look-up speed into the Hash table for any particular key to get the attached element. The choices I have for the Hash Table are ELF, PJW, and BKDR. Security is not an issue so in that case, which of these hashing algorithms will create a table with the best look-up speed?

One other consideration. Would I get better performance if I converted the number to its string representation and used it for the key?

Note: I did find this relevant SO thread:

What integer hash function are good that accepts an integer hash key?

But the accepted answer had some some opposing viewpoints in the comments that seemed reasonable and the spread of caveats and opinions across all the other answers left me still uncertain as to the best algorithm for my use case scenario.

Community
  • 1
  • 1
Robert Oschler
  • 14,153
  • 18
  • 94
  • 227

3 Answers3

4

The problem of finding a good, fast hash-function has been solved: http://code.google.com/p/smhasher/wiki/MurmurHash3

The time, where hash functions where based on math tricks like Knut's multiplicative hash, are over. Modern hashes operate using binary operations.

Maybe you can just take integer that you already have and not hash it at all. If there are too many collisions, which only happens because of some special data distribution, use MurmurHash.

usr
  • 168,620
  • 35
  • 240
  • 369
1

Just use a dictionary. Since each element is identified by a "unique" 32-bit number, a hashset is not the data structure that you are looking for. You're looking for a dictionary of key-value pairs.

Zoran Pavlovic
  • 1,166
  • 2
  • 23
  • 38
0

Conversion to a string and hashing the string is likely to be slow. For a simple hash function I would be inclined to split the large (how large?) number into 32 bit chunks and XOR the chunks together.

rossum
  • 15,344
  • 1
  • 24
  • 38