Thanks for this insightful article. I find this structure fascinating. I was wondering if there is a way to iterate this hash (i.e. get every keypair one by one, no matter the order) without using recursion. Best regards, Ángel Ortega
Great question, Angel! That part isn't so simple and pretty, which is why I had suggested an intrusive linked list. It turns it a hash trie into a "linked hash map" where the list order is independent of the hash trie, and iteration is as simple as traversing that list. It could track, say, insertion order, or you could sort it — mergesort goes well with linked lists — all without disrupting the underlying hash trie. If you'd like to see hash trie iteration, I wrote an example iterator over an integer hash set (iter, newiter, iternext): https://gist.github.com/skeeto/e416b3b07bf63792db91a5139526612e I initially considered a fixed-size stack, but as the hash trie does not enforce balance, depth is unbounded, so instead the stack is a linked list (iternode) with a freelist for reuse. Though unlike hash tries and linked lists, that's not something I'd want to write from scratch often. Iteration order is random, though not uniformly so. The first element is always the first inserted, the second element was probably inserted early, etc. A nice property is that insertion does not invalidate iterators. They just might not see the newly-inserted element.
25/10/23 17:13, Christopher Wellons: > If you'd like to see hash trie iteration, I wrote an example iterator over an integer hash set (iter, newiter, iternext): > > https://gist.github.com/skeeto/e416b3b07bf63792db91a5139526612e This is a pretty elegant solution. I like it. I've made my own toying and found that it may prove convenient to build a plain LIFO linked list at the same time a new node is added. Every node has the added weight of another pointer, but if iterating the hash is common, the added build cost is minimal and the traversal code is very simple (nodes will be found in inverse insertion order). Thanks for your articles, Christopher. They are always food for thought. Best regards, Ángel