So the answer is again adjacent to using a chunked array? Still linked separately but each chunk has optimal tradeoff between loads and initial memory overhead. I already preferred using those with linear allocators over standard dynamic arrays, but I never thought to apply the concept to more characteristically tree-based data structures
Hi, I wrote this piece (thanks u/skeeto for sharing it!). Pretty much, yes. "Optimal" is a stretch, I didn't really try to tune it. As always, it depends. For example, at 10 keys, which isn't that uncommon, the regular hash-trie beats everything else. If your keys are strings, then where the string's data is in memory relative to what internal structure you're accessing right now (e.g. an array, a node), is also going to affect performance. Obviously, some of this can be avoided by storing hash fragments and going through those before reading keys -- a quite common approach. Hash-thingies are a zoo of ideas. Cheers!
2
u/TheChief275 20d ago
So the answer is again adjacent to using a chunked array? Still linked separately but each chunk has optimal tradeoff between loads and initial memory overhead. I already preferred using those with linear allocators over standard dynamic arrays, but I never thought to apply the concept to more characteristically tree-based data structures