Skip to main content
PreparationZone Logo
PrepZone

Ordered and Sorted Maps

LinkedHashMap for insertion order and LRU caches, TreeMap for sorted keys and range queries.

Pass checkpoint below

Read these first

Why this matters

  • LinkedHashMap gives you a working LRU cache by overriding one method, which is a genuinely useful piece of knowledge.
  • TreeMap's navigation methods solve "find the nearest value at or below this" problems that a hash map cannot express at all.
  • Interviews frequently ask you to implement an LRU cache, and the one-method version is a strong answer when paired with the manual one.
table — array of buckets
bucket 0empty
bucket 1"asha" → 30
bucket 5 — collision chain
"ravi" → 24next →
"neha" → 29next → null
bucket 9 — treeified
Red-black treeMore than 8 entries: lookup becomes O(log n)

Bucket index comes from the key's hash, not its insertion order — which is why HashMap iteration has no predictable sequence.

The hash picks a bucket. Keys that land in the same bucket form a short list, and once a bucket grows past eight entries it becomes a balanced tree so lookups stay fast.

LinkedHashMap

It keeps everything HashMap does and adds a doubly linked list across entries.

Java
Loading compiler…

Iteration follows insertion order, and re-putting an existing key leaves its position alone. The cost is two extra references per entry and slightly slower insertion.

Access order

The three-argument constructor switches from insertion order to access order, where reading an entry moves it to the end.

Java
Loading compiler…

The head of the list is now the least recently used entry, which is exactly what a cache needs to evict.

The rest of this guide is part of Pro

Free covers every fresher guide in full. Pro unlocks Senior, Staff and Architect guides across every track.

Still to come · 6 sections

  • An LRU cache in one override
  • TreeMap
  • Navigation and range queries
  • Choosing between the three
  • EnumMap, briefly
  • Common misreadings

Test yourself

Answer these before moving on — recall is what makes it stick.