3 ms·
This is one of those data structures with a misleading name. Throw out the hashing part. It's not part of the data structure, it's just one use case. When you d
by chowells 3y ago
This is one of those data structures with a misleading name. Throw out the hashing part. It's not part of the data structure, it's just one use case. When you do that, you discover that this structure is something between a trie and a B+ tree. It's a persistent data structure for indexing fixed-size bit patterns to arbitrary values, with node sizes that aim for a compromise between update (copy) speed and lookup speed (number of pointers chased before reaching the value).
It's cool, but don't tell yourself it's only good for hashing.
- Genbox 3y ago> don't tell yourself it's only good for hashing. The hash function[1] takes an arbitrary input and generate (in this case) a 32bit integer. This is nessecary to index values that are not integers (such as byte arrays or strings). It also doubles as a way to deterministically randomize values across the keyspace for better distribution of keys. [1] https://github.com/mkirchner/hamt/blob/main/src/hamt.c#L377 https://github.com/mkirchner/hamt/blob/main/src/hamt.c#L377
- joshlemer 3y agoNitpick: there's nothing in the data structure that limits it to only fixed-size bit patterns, you could easily have implementations which accept arbitrarily long bit patterns
- reitzensteinm 3y agoWhile it's true that the hashing isn't intrinsic to the mapping of key (bits) to value, hashing is what ensures that the tree stays balanced. You can absolutely use whatever bits you want, but patterns in the keys will open yourself up to potential loss of performance as the tree will get unnecessarily deep.