0

So I've been looking around to find a suitable hash function for a hashmap. Currently the best one I've found was from xxhash and maybe murmur after that, but they excluded CRC32C which can be optimized greatly by using 3 64 bit parallel crc32c instructions on SSE4.2 capable CPUs. CRC32 by itself seems to be quite outdated, but mostly used for things like zip or ethernet. From what I've heard, CRC32C outperforms other hashing algorithms.

Is there any reason not to use CRC32C for a hashmap? For example collisions, the key not being 64-bit (I don't think that matters because it goes into buckets anyways) or it being slower on smaller data?

Thanks for the help

10
  • 1
    Personally, I would approach this problem by surveying which hash functions are used by the standard libraries of popular programming languages. They probably did their research, and I would just bootleg it :D However, be wary of older standard libraries, which might have made a then-optimal choice which has become outdated since (and couldn't be changed because of backwards compatibility needs). Swift, Go and Rust might be good modern candidates to look into. They have open development processes, so you can probably find some discussion of how they made their pick.
    – Alexander
    Nov 19 at 15:51
  • @Alexander they might have chosen for it because SSE4.2 wasn't as widespread as it is now though (99.05% of steam hardware survey) and I don't think the 0.95% is worth targeting, but other languages might want to. A good example of outdated choices is C++ unordered map, which apparently uses suboptimal layout (boost flat map is better) since they chose it in 2005. Swift & rust use siphash. Unsure about go, but siphash seems slower than hardware crc32c
    – Niels
    Nov 19 at 16:00
  • One thing to not forget is that the performance of a hash function in a hashed collection doesn't just come down to the time it takes to compute the hash function, but also the quality of the output. Regardless if you're side chaining, double-hashing, or whatever other collision-handling scheme you're using, you'll probably see that handling collisions takes more time than computing hash functions. Hopping around in RAM is much slower than for loops going brrrrrrrr.
    – Alexander
    Nov 19 at 16:04
  • 1
    What are your goals for this hash? What kind of data will you be hashing? Typical suggestions include SipHash when concerned about HashDoS attacks, FNV-1a for hashing short trusted strings. CRC32 is slow compared to many fast hash functions and needs a large lookup table to be somewhat efficient. See also the epic answer to Which hashing algorithm is best for uniqueness and speed?. CRC3C might be better, but the strength of CRCs are error detection, not achieving a good bit distribution. See also rurban.github.io/smhasher
    – amon
    Nov 19 at 16:05
  • @Alexander CRC32C has way less collisions than a lot of other algorithms tho.
    – Niels
    Nov 19 at 19:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.