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