geordnete-hashmap

LinkedHashMap (Ordered Hash Map)

In short: A key-value mapping (map) that combines the fast hash-based lookup of HashSet-like access with a predictable order — elements are iterated in the order in which they were inserted.

In more detail: A normal, purely hash-based map guarantees no particular iteration order; LinkedHashMap additionally internally remembers a linked list of the insertion order, without losing the speed of hash-based access for individual reads/writes. Useful when both fast access via a key and a consistent order when iterating matter.

In Depth

An ordinary hash map (or HashMap in Java, a normal dict in older Python versions) internally organises its entries purely by the computed hash value of the keys — this is optimal for fast individual accesses (map.get(key)), but makes the iteration order practically random and implementation-dependent, since it has nothing to do with the actual insertion order.

Map<String, Integer> normal = new HashMap<>();
normal.put("first", 1);
normal.put("second", 2);
normal.put("third", 3);
// iteration order not guaranteed - could be "second, third, first"
 
Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("first", 1);
ordered.put("second", 2);
ordered.put("third", 3);
// iteration order ALWAYS: first, second, third

Technically, a LinkedHashMap achieves this by maintaining a doubly linked list over all entries in addition to the normal hash table structure, tracking the insertion order — every entry “knows” which one was inserted before and after it. This costs somewhat more memory compared to a pure HashMap, but doesn’t change the speed of individual reads/writes (still nearly O(1) thanks to hashing).

A typical use case is a simple LRU cache (Least Recently Used) — a bounded caching structure that removes the longest-unused entries first once capacity is reached. The ordered structure of a LinkedHashMap is especially well suited for this, because Java implementations of it can even be configured to track access order (instead of just insertion order).

To be distinguished from a TreeMap/sorted structure: LinkedHashMap preserves the INSERTION ORDER, not a SORTED order by the value of the keys. Anyone who instead wants to iterate the entries alphabetically, for example, needs a tree-based structure instead of a hash-based one.

See also: HashSet, Collections