3 ms·

This is a fun exercise, but if anyone is thinking about doing this for a project - don't - use a library.

• kevin_thibedeau 6y ago
  Existing libraries make decisions that aren't necessarily suitable for all applications. Most hash table code makes excessive use of malloc/realloc or has power of two growth which is problematic in memory constrained systems. If you want to minimize waste by using high load factors you're going to want Robin Hood hash which is still relatively uncommon in lib code.
  • attractivechaos 6y ago
    Although Robin Hood hashing has good performance under high load, it needs to record the probe length in each bucket. This partly cancels its advantage especially for small keys. In my evaluation, Robin Hood hashing doesn't use less memory in comparison to others. > Most hash table code makes excessive use of malloc/realloc or has power of two growth Libraries based on open addressing only call malloc when there is not enough room. That is not "excessive". Also, if you know the maximum size before hand, many libraries allow you to preallocate buckets such that you never trigger rehashing in this case.
• philwelch 6y ago
  “But Doctor, I am Pagliacci!”