5 ms·

Attractivechaos's stuff blows my mind. Shameless plug - I've started dissecting his header-only hashmap library (khash.h) bit by bit, and I've been documenting

Attractivechaos's stuff blows my mind. Shameless plug - I've started dissecting his header-only hashmap library (khash.h) bit by bit, and I've been documenting my adventure here: https://medium.com/@makmanalp/dissecting-khash-h-part-1-origins-7577d6445670#.s7e4au49z https://medium.com/@makmanalp/dissecting-khash-h-part-1-orig... edit: and part 2: https://medium.com/@makmanalp/dissecting-khash-h-part-2-scouting-32eda6660919#.ys3d0org4 https://medium.com/@makmanalp/dissecting-khash-h-part-2-scou...

santaclaus 10y ago
Rad, I wasn't aware of khash, thanks! Any idea how it compares to Google's dense_hash_map?
- makmanalp 10y ago
  No clue! Your comment history seems to say you're more qualified to answer that than me. My first look says that dense_hash_map seems to use STL stuff and generics, khash is in pure C, and uses macro hacks to achieve the same functionality and only has a few key types it can use (str, int, int64). Other than that, dense_hash_map and khash both use quadratic probing (https://en.wikipedia.org/wiki/Quadratic_probing https://en.wikipedia.org/wiki/Quadratic_probing) to resolve collisions. I couldn't really dig and find the hashing functions used by dense_hash_map but khash uses a weird one called X31 (search in https://download.samba.org/pub/unpacked/ntdb/lib/ccan/hash/hash.h https://download.samba.org/pub/unpacked/ntdb/lib/ccan/hash/h...) for the string ones and .... nothing??? for ints, with an alternative of Wang's integer hash function (https://gist.github.com/badboy/6267743 https://gist.github.com/badboy/6267743). The world of hashing functions seem to be a crazy underworld of arcane incantations, old tomes, and copy pasting and emailing and trying random shit. It's really wonderful, reminds me of the olden days. Khash.h is a measly 624 lines of code, everything included, so there's that.
  - makmanalp 10y ago
    OK, a bit more here: https://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/ https://attractivechaos.wordpress.com/2008/08/28/comparison-...

santaclaus 10y ago

Rad, I wasn't aware of khash, thanks! Any idea how it compares to Google's dense_hash_map?

makmanalp 10y ago
No clue! Your comment history seems to say you're more qualified to answer that than me. My first look says that dense_hash_map seems to use STL stuff and generics, khash is in pure C, and uses macro hacks to achieve the same functionality and only has a few key types it can use (str, int, int64). Other than that, dense_hash_map and khash both use quadratic probing (https://en.wikipedia.org/wiki/Quadratic_probing https://en.wikipedia.org/wiki/Quadratic_probing) to resolve collisions. I couldn't really dig and find the hashing functions used by dense_hash_map but khash uses a weird one called X31 (search in https://download.samba.org/pub/unpacked/ntdb/lib/ccan/hash/hash.h https://download.samba.org/pub/unpacked/ntdb/lib/ccan/hash/h...) for the string ones and .... nothing??? for ints, with an alternative of Wang's integer hash function (https://gist.github.com/badboy/6267743 https://gist.github.com/badboy/6267743). The world of hashing functions seem to be a crazy underworld of arcane incantations, old tomes, and copy pasting and emailing and trying random shit. It's really wonderful, reminds me of the olden days. Khash.h is a measly 624 lines of code, everything included, so there's that.
- makmanalp 10y ago
  OK, a bit more here: https://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/ https://attractivechaos.wordpress.com/2008/08/28/comparison-...