Linked Hash/Tree Maps, simple, but elegant. A Map with its nodes connected in a linked list so you can traverse them in insertion order (and O(n) time). Very useful for window queries over sequential data and other cases where you want FIFO access, but also quick access by a field of the data.
You forgot the most important feature over normal hash maps: they offer a deterministic iteration order without incurring the cost of a tree-based ordered map.
(If you don't know why this is important then maybe you haven't worked on large systems that undergo rigorous evaluation)
Is (non-)determinism really the right concern here? I’m aware that most hash tables do not have generally predictable iteration orders, but I nevertheless understood them to be deterministic.
They are deterministic in the sense that provided everything else is the same, iteration order would be the same after each insertion.
However, it can change after insertion (if the hash bucket count changes). If the hash function is random-keyed, iteration order would be different for different instances of the hash table even if you insert the same items in the same order.
Sometimes you want the order to be consistent every time. Be it insertion order, or some natural order of the items.
>Is (non-)determinism really the right concern here?
A massive one - there is a lot of code that implicitly depends on the order of iteration (think configurations/initialization). The issue might be invisible, and reproduce rarely in production only. The iteration order depends on the hash of the keys, plus the capacity of the underlying array.
In Java I advise to never use the standard HashMap in favor of LinkedHashMap. In cases where data density is important both are a terrible fit having nodes instead of a plain object array (and linear probe/search).
Well, hard/impossible to predict perhaps. Iteration order can depend on the order things were inserted and deleted and may differ from computer to computer (for example in Julia the hash-based dictionary ordering differs between 32 and 64 bit systems, and might change between versions of Julia, etc - you’d see the same thing with C++ unordered maps, etc, etc).
You can do this without a linked list and it can be quite performant, like python’s newest dictionary implementation (appeared around Python 3.6 or 3.7 from memory).
Hence the "simple but good". It's not really obscure, but also not on the common path. I've lost track of the number of times I've pointed this one out to a colleague or student.
