2 ms·
My understanding is you can't tell order using this trick. I guess the bitmap is just an optimization to skip the hash lookup? Order doesn't matter for you? So
by eloff 9y ago
My understanding is you can't tell order using this trick. I guess the bitmap is just an optimization to skip the hash lookup? Order doesn't matter for you?
Something I came up with is packing the pointers/values into a contiguous array and using the bitfield to tell not only if it's present, but what offset is at (mask + popcnt) * size of(value). This eliminates wasted space due to unused buckets in the hash table. I'm sure it's been done before, but I haven't seen it anywhere.
How's your Go? Want a remote contact doing Go microservices that pays very well? Email is in my profile.
- joshuak 9y agoThat's pretty much exactly how hash array mapped tries work. Take the first 5 bits of a 32 bit hash, use it to set a flag in the bitfield, a populated field indicates a populated child array element, find out which one using popcnt. When you find a conflict on insert take a step down the tree, use the next 5 bits in the 32 bit hash rinse and repeat. A HAMT is the basis of a fully concurrent data structure for maps which can also do fast atomic snapshots called a ctrie.
- eloff 9y agoI'll add HAMT and tries to my reading list, thanks.