Insertion order vs access order
LinkedHashMap is a HashMap that also remembers order (insertion or, optionally, access order), which makes a five-line LRU cache. TreeMap keeps keys sorted in a red-black tree and answers range and nearest-key questions in O(log n).
Change the code and press Run (Ctrl+Enter). Try to predict the output first, then break it on purpose and read the error. Your edits are saved and match the lesson page.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Use a LinkedHashMap<String, Integer> to count words in "the cat and the hat and the bat" and print the counts in the order each word first appeared.
Build a booking checker with a TreeMap<Integer, Integer> mapping start time to end time. Add bookings 900-1000 and 1100-1200, then check whether 930-1030, 1000-1100 and 1150-1300 can be booked (no overlap), using floorEntry and ceilingEntry. Print each result.
Write a FIFO cache of capacity 2 (evicts the oldest inserted key, not the least recently used) using LinkedHashMap and removeEldestEntry. Put a, b, read a, put c, then print the keys.
Explain it without notes
How does LinkedHashMap maintain order, and what's the difference between insertion and access order?
Implement an LRU cache in Java and explain the time complexity of each operation.
When would you choose TreeMap over HashMap? Give two concrete use cases.
What are floorKey, ceilingKey, headMap and subMap, and are the range methods copies?
Expected output
insertion order: {tea=99, cake=4, chai=4}
access order: {chai=4, tea=99, cake=4}
after re-adding tea: {cake=4, chai=4, tea=3}