3 ms·
My research group at CMU uses a lot of hashing these days and we care mostly about performance. We've settled on three as our basics: - CityHash as a nice, gene
by dgacmu 13y ago
My research group at CMU uses a lot of hashing these days and we care mostly about performance. We've settled on three as our basics:
- CityHash as a nice, general purpose hash, particularly on newer machines with CRC32c support in hardware;
- SpookyHash for longer strings, particularly with no CRC32 support;
- CRC32c in hardware for a quick & dirty hash with possibly slightly more poor distribution.
It depends a lot on what you're hashing. For strings, both City and Spooky are great. You should benchmark both on your target architecture(s). If you're trying to take, e.g., integers to integers, we've found that CRC32c is a pretty darn good fallback if you need insanely high performance.
If you're running a hash table exposed to externally controlled input, then you also want to consider (whether you need) algorithms that provide decent resistance against "hash flooding". SipHash is the strongest contender there short of throwing your hands in the air and using MD5 with a local secret seed.
- mcguire 13y agoI think it's worth reiterating your last paragraph. If your hash table is exposed to external input, an effective DoS attack can be mounted by turning your hash table into an expensive linked list. http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.h...