[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":93,"_73":94,"_35":95},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",110,"title","TreeMap and NavigableMap","slug","java-collections-part-14-treemap-navigable","excerpt","Master sorted key-value storage using Red-Black trees, NavigableMap range queries, time-series analytics patterns, and when O(log n) beats O(1) hashing.","# Java Collections Compendium Part 14: TreeMap & NavigableMap Operations\n\nMaster sorted key-value storage with TreeMap. Learn Red-Black tree fundamentals, NavigableMap operations for range queries, and real-world patterns for time-series data, autocomplete, and interval lookups.\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| **Topic** | TreeMap, NavigableMap, SortedMap, Red-Black Trees |\n| **Complexity** | Intermediate to Advanced |\n| **Prerequisites** | Part 10 (TreeSet), Part 12 (HashMap) |\n| **Time to Master** | 3-4 hours |\n| **Interview Frequency** | High (NavigableMap operations, tree complexity) |\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. Understand TreeMap's Red-Black tree implementation\n2. Use NavigableMap operations for range and proximity queries\n3. Implement time-series data handling with subMap\n4. Build autocomplete functionality with prefix matching\n5. Choose between TreeMap and HashMap for different use cases\n\n---\n\n## Production Story: Time-Series Analytics Without a Time-Series Database\n\n### The Incident\n\nOur analytics service needed to answer queries like \"Show me all events between 10am and 2pm\" with sub-millisecond response times. The initial implementation used HashMap and filtered all events:\n\n```java\n// EventStore.java - The slow approach\npublic class EventStore {\n private Map events = new HashMap<>(); // timestamp -> event\n\n public List getEventsBetween(long startTime, long endTime) {\n return events.entrySet().stream()\n .filter(e -> e.getKey() >= startTime && e.getKey() <= endTime)\n .map(Map.Entry::getValue)\n .collect(Collectors.toList());\n }\n}\n```\n\nWith 10 million events, this query took 500ms - unacceptable for real-time dashboards.\n\n### The TreeMap Solution\n\n```java\n// EventStore.java - The fast approach\npublic class EventStore {\n private NavigableMap events = new TreeMap<>();\n\n public List getEventsBetween(long startTime, long endTime) {\n // O(log n) to find range, O(k) to iterate k results\n return new ArrayList<>(\n events.subMap(startTime, true, endTime, true).values()\n );\n }\n\n public Event getClosestEvent(long timestamp) {\n Long floor = events.floorKey(timestamp);\n Long ceiling = events.ceilingKey(timestamp);\n\n if (floor == null) return events.get(ceiling);\n if (ceiling == null) return events.get(floor);\n\n return (timestamp - floor <= ceiling - timestamp)\n ? events.get(floor)\n : events.get(ceiling);\n }\n}\n```\n\n**Performance improvement:**\n- Before: O(n) = 500ms for 10M events\n- After: O(log n + k) = 0.5ms for same data\n- **1000x faster!**\n\n### How TreeMap Makes This Possible\n\n```text\nHashMap for timestamp lookup:\n┌─────────────────────────────────────────────────────────────────────┐\n│ Events scattered by hash, not by timestamp │\n│ Bucket 0: [15:00, 09:30, 22:15] │\n│ Bucket 1: [11:45, 08:00, 19:30] │\n│ Bucket 2: [10:15, 14:00, 12:30] │\n│ ... │\n│ To find 10am-2pm: Must scan ALL buckets! │\n└─────────────────────────────────────────────────────────────────────┘\n\nTreeMap for timestamp lookup:\n┌─────────────────────────────────────────────────────────────────────┐\n│ [12:00] │\n│ / \\ │\n│ [10:00] [14:00] │\n│ / \\ / \\ │\n│ [09:00][11:00][13:00][15:00] │\n│ │\n│ To find 10am-2pm: │\n│ 1. Navigate to 10:00 → O(log n) │\n│ 2. Iterate to 14:00 → O(k) for k results │\n│ Much faster for range queries! │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n### Lessons Learned\n\n1. **TreeMap excels at range queries** - O(log n) to find boundaries\n2. **HashMap excels at point queries** - O(1) for exact key lookup\n3. **Choose data structure based on query patterns**, not just storage needs\n4. **NavigableMap API** provides powerful range operations\n\n---\n\n## Mental Model: The Sorted Filing Cabinet\n\nThink of TreeMap as a filing cabinet where folders are always in order:\n\n```text\n┌─────────────────────────────────────────────────────────────────────┐\n│ SORTED FILING CABINET │\n├─────────────────────────────────────────────────────────────────────┤\n│ │\n│ HashMap = Pile of folders (find by label, but unsorted) │\n│ ┌─────┐┌─────┐┌─────┐┌─────┐┌─────┐ │\n│ │ M ││ A ││ Z ││ K ││ D │ Folders by hash, not order │\n│ └─────┘└─────┘└─────┘└─────┘└─────┘ │\n│ │\n│ TreeMap = Alphabetically sorted drawer │\n│ ┌─────┬─────┬─────┬─────┬─────┬─────┐ │\n│ │ A │ D │ K │ M │ P │ Z │ Always in order! │\n│ └─────┴─────┴─────┴─────┴─────┴─────┘ │\n│ │\n│ NavigableMap operations: │\n│ │\n│ floorKey(\"L\") = \"K\" │ Find folder at or before \"L\" │\n│ ceilingKey(\"L\") = \"M\" │ Find folder at or after \"L\" │\n│ subMap(\"D\", \"M\") │ Get folders D through M │\n│ headMap(\"K\") │ Get all folders before K │\n│ tailMap(\"M\") │ Get all folders from M onward │\n│ │\n└─────────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## Deep Dive: TreeMap Internals\n\n### Red-Black Tree Structure\n\n```java\n// TreeMap.Entry structure (simplified)\nstatic final class Entry implements Map.Entry {\n K key;\n V value;\n Entry left;\n Entry right;\n Entry parent;\n boolean color = BLACK;\n}\n\n// Red-Black Tree properties:\n// 1. Each node is either RED or BLACK\n// 2. Root is always BLACK\n// 3. Leaves (null) are BLACK\n// 4. RED node's children must be BLACK (no red-red)\n// 5. All paths from root to leaves have same BLACK count\n```\n\n### Visual Tree Example\n\n```text\nTreeMap with keys: [5, 3, 7, 2, 4, 6, 8]\n\n [5 BLACK]\n / \\\n [3 RED] [7 RED]\n / \\ / \\\n [2 BLACK] [4 BLACK] [6 BLACK] [8 BLACK]\n\nMemory per entry: ~40 bytes\n- Object header: 12 bytes\n- Key reference: 8 bytes\n- Value reference: 8 bytes\n- Left/right/parent: 24 bytes\n- Color: 1 byte + padding\n\nCompare to HashMap.Entry: ~32 bytes\nTreeMap has ~25% more overhead per entry\n```\n\n### TreeMap Construction\n\n```java\n// Natural ordering (keys must implement Comparable)\nTreeMap natural = new TreeMap<>();\nnatural.put(\"banana\", 2);\nnatural.put(\"apple\", 1);\nnatural.put(\"cherry\", 3);\n// Iteration: apple=1, banana=2, cherry=3\n\n// Custom Comparator\nTreeMap caseInsensitive = new TreeMap<>(\n String.CASE_INSENSITIVE_ORDER\n);\n\n// Reverse order\nTreeMap reverse = new TreeMap<>(Comparator.reverseOrder());\n\n// Complex key ordering\nTreeMap byAge = new TreeMap<>(\n Comparator.comparingInt(Person::getAge)\n .thenComparing(Person::getName)\n);\n\n// From another map\nMap source = Map.of(\"a\", 1, \"b\", 2);\nTreeMap sorted = new TreeMap<>(source);\n```\n\n---\n\n## Deep Dive: NavigableMap Operations\n\n### Entry Navigation Methods\n\n```java\nNavigableMap map = new TreeMap<>();\nmap.put(10, \"ten\");\nmap.put(20, \"twenty\");\nmap.put(30, \"thirty\");\nmap.put(40, \"forty\");\nmap.put(50, \"fifty\");\n\n// floorEntry/floorKey: greatest entry ≤ key\nMap.Entry floor = map.floorEntry(25); // 20=twenty\nInteger floorKey = map.floorKey(25); // 20\n\n// ceilingEntry/ceilingKey: smallest entry ≥ key\nMap.Entry ceiling = map.ceilingEntry(25); // 30=thirty\nInteger ceilingKey = map.ceilingKey(25); // 30\n\n// lowerEntry/lowerKey: greatest entry < key (strictly less)\nMap.Entry lower = map.lowerEntry(30); // 20=twenty\nInteger lowerKey = map.lowerKey(30); // 20\n\n// higherEntry/higherKey: smallest entry > key (strictly greater)\nMap.Entry higher = map.higherEntry(30); // 40=forty\nInteger higherKey = map.higherKey(30); // 40\n\n// firstEntry/lastEntry: extremes\nMap.Entry first = map.firstEntry(); // 10=ten\nMap.Entry last = map.lastEntry(); // 50=fifty\n\n// pollFirstEntry/pollLastEntry: remove and return\nMap.Entry polled = map.pollFirstEntry(); // 10=ten (removed)\n```\n\n### Submap Views\n\n```java\nNavigableMap map = new TreeMap<>();\nmap.put(10, \"A\"); map.put(20, \"B\"); map.put(30, \"C\");\nmap.put(40, \"D\"); map.put(50, \"E\");\n\n// subMap(from, fromInclusive, to, toInclusive)\nNavigableMap sub = map.subMap(20, true, 40, false);\n// Contains: 20=B, 30=C (excludes 40)\n\n// headMap(to, inclusive): all entries < to\nNavigableMap head = map.headMap(30, true);\n// Contains: 10=A, 20=B, 30=C\n\n// tailMap(from, inclusive): all entries ≥ from\nNavigableMap tail = map.tailMap(30, false);\n// Contains: 40=D, 50=E (excludes 30)\n\n// SortedMap legacy methods (exclusive endpoints)\nSortedMap legacySub = map.subMap(20, 40); // [20, 40)\nSortedMap legacyHead = map.headMap(30); // [first, 30)\nSortedMap legacyTail = map.tailMap(30); // [30, last]\n```\n\n### Views Are Live!\n\n```java\nNavigableMap map = new TreeMap<>();\nmap.put(10, \"A\"); map.put(20, \"B\"); map.put(30, \"C\"); map.put(40, \"D\");\n\nNavigableMap sub = map.subMap(20, true, 40, true);\nSystem.out.println(sub); // {20=B, 30=C, 40=D}\n\n// Modify through view - affects original\nsub.put(25, \"NEW\");\nSystem.out.println(map); // {10=A, 20=B, 25=NEW, 30=C, 40=D}\n\n// Modify original - affects view (if in range)\nmap.put(35, \"ALSO_NEW\");\nSystem.out.println(sub); // {20=B, 25=NEW, 30=C, 35=ALSO_NEW, 40=D}\n\n// Adding outside range throws exception\nsub.put(50, \"FAIL\"); // IllegalArgumentException: key out of range\n```\n\n### Descending Views\n\n```java\nNavigableMap map = new TreeMap<>();\nmap.put(10, \"A\"); map.put(20, \"B\"); map.put(30, \"C\");\n\n// Descending map (reverse order view)\nNavigableMap desc = map.descendingMap();\nSystem.out.println(desc); // {30=C, 20=B, 10=A}\n\n// Descending key set\nNavigableSet descKeys = map.descendingKeySet();\n// Iteration: 30, 20, 10\n\n// Changes to descending view affect original\ndesc.put(25, \"X\");\nSystem.out.println(map); // {10=A, 20=B, 25=X, 30=C}\n```\n\n---\n\n## Deep Dive: Real-World Patterns\n\n### Pattern 1: Time-Series Data\n\n```java\npublic class TimeSeriesStore {\n private final NavigableMap data = new TreeMap<>();\n\n public void record(Instant timestamp, T value) {\n data.put(timestamp, value);\n }\n\n public List getRange(Instant from, Instant to) {\n return new ArrayList<>(data.subMap(from, true, to, true).values());\n }\n\n public T getLatest() {\n Map.Entry last = data.lastEntry();\n return last != null ? last.getValue() : null;\n }\n\n public T getClosestTo(Instant timestamp) {\n Map.Entry floor = data.floorEntry(timestamp);\n Map.Entry ceiling = data.ceilingEntry(timestamp);\n\n if (floor == null) return ceiling != null ? ceiling.getValue() : null;\n if (ceiling == null) return floor.getValue();\n\n long floorDiff = Duration.between(floor.getKey(), timestamp).abs().toMillis();\n long ceilingDiff = Duration.between(timestamp, ceiling.getKey()).abs().toMillis();\n\n return floorDiff <= ceilingDiff ? floor.getValue() : ceiling.getValue();\n }\n\n public void removeOlderThan(Instant cutoff) {\n data.headMap(cutoff, false).clear();\n }\n}\n```\n\n### Pattern 2: Autocomplete / Prefix Search\n\n```java\npublic class AutocompleteIndex {\n private final NavigableMap words = new TreeMap<>();\n\n public void addWord(String word, int frequency) {\n words.put(word.toLowerCase(), frequency);\n }\n\n public List getSuggestions(String prefix, int maxResults) {\n String normalizedPrefix = prefix.toLowerCase();\n\n // Find range of words starting with prefix\n String from = normalizedPrefix;\n String to = normalizedPrefix + Character.MAX_VALUE;\n\n return words.subMap(from, true, to, false)\n .entrySet()\n .stream()\n .sorted(Map.Entry.comparingByValue().reversed())\n .limit(maxResults)\n .map(Map.Entry::getKey)\n .collect(Collectors.toList());\n }\n}\n\n// Usage\nAutocompleteIndex index = new AutocompleteIndex();\nindex.addWord(\"java\", 1000);\nindex.addWord(\"javascript\", 800);\nindex.addWord(\"jackson\", 200);\nindex.addWord(\"javalin\", 100);\n\nindex.getSuggestions(\"java\", 3); // [java, javascript, javalin]\n```\n\n### Pattern 3: Interval/Range Lookup\n\n```java\npublic class IPRangeLookup {\n // Maps start of range to (end, metadata)\n private final NavigableMap ranges = new TreeMap<>();\n\n public void addRange(long start, long end, String metadata) {\n ranges.put(start, new IPRange(start, end, metadata));\n }\n\n public String lookup(long ip) {\n // Find the range that might contain this IP\n Map.Entry entry = ranges.floorEntry(ip);\n\n if (entry != null && ip <= entry.getValue().end) {\n return entry.getValue().metadata;\n }\n return null; // IP not in any range\n }\n\n record IPRange(long start, long end, String metadata) {}\n}\n\n// Usage\nIPRangeLookup lookup = new IPRangeLookup();\nlookup.addRange(ipToLong(\"10.0.0.0\"), ipToLong(\"10.255.255.255\"), \"Private Class A\");\nlookup.addRange(ipToLong(\"192.168.0.0\"), ipToLong(\"192.168.255.255\"), \"Private Class C\");\n\nlookup.lookup(ipToLong(\"10.0.1.5\")); // \"Private Class A\"\n```\n\n### Pattern 4: Sliding Window\n\n```java\npublic class SlidingWindowStats {\n private final NavigableMap values = new TreeMap<>();\n private final Duration windowSize;\n\n public SlidingWindowStats(Duration windowSize) {\n this.windowSize = windowSize;\n }\n\n public void add(double value) {\n long now = System.currentTimeMillis();\n values.put(now, value);\n cleanup(now);\n }\n\n private void cleanup(long now) {\n long cutoff = now - windowSize.toMillis();\n values.headMap(cutoff, false).clear();\n }\n\n public double getAverage() {\n if (values.isEmpty()) return 0;\n return values.values().stream()\n .mapToDouble(Double::doubleValue)\n .average()\n .orElse(0);\n }\n\n public double getMax() {\n return values.values().stream()\n .mapToDouble(Double::doubleValue)\n .max()\n .orElse(0);\n }\n}\n```\n\n---\n\n## Deep Dive: Performance Characteristics\n\n### Operation Complexity\n\n| Operation | TreeMap | HashMap |\n|-----------|---------|---------|\n| get(key) | O(log n) | O(1) |\n| put(key, value) | O(log n) | O(1)* |\n| remove(key) | O(log n) | O(1) |\n| containsKey(key) | O(log n) | O(1) |\n| firstKey()/lastKey() | O(log n) | N/A |\n| floorKey()/ceilingKey() | O(log n) | N/A |\n| subMap() | O(log n) | N/A |\n| Iteration | O(n) sorted | O(n) unsorted |\n\n*O(1) amortized, O(n) worst case during resize\n\n### When to Use TreeMap\n\n```java\n// ✅ Use TreeMap when you need:\n\n// 1. Sorted iteration\nfor (Map.Entry entry : treeMap.entrySet()) {\n // Keys in sorted order\n}\n\n// 2. Range queries\ntreeMap.subMap(from, to);\ntreeMap.headMap(key);\ntreeMap.tailMap(key);\n\n// 3. Closest match\ntreeMap.floorKey(target);\ntreeMap.ceilingKey(target);\n\n// 4. First/last access\ntreeMap.firstKey();\ntreeMap.lastKey();\n\n// 5. Navigable operations\ntreeMap.higherKey(key);\ntreeMap.lowerKey(key);\n```\n\n### When to Use HashMap\n\n```java\n// ✅ Use HashMap when you need:\n\n// 1. Fast point lookups (most common case)\nhashMap.get(key); // O(1)\n\n// 2. No ordering requirements\n// Random iteration order is acceptable\n\n// 3. Maximum performance for basic operations\n// HashMap is faster for put/get/remove\n\n// 4. Memory efficiency (slightly less overhead per entry)\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Missing Comparable/Comparator\n\n```java\n// ❌ WRONG: Key class doesn't implement Comparable\npublic class Product {\n private String name;\n private double price;\n}\n\nTreeMap inventory = new TreeMap<>();\ninventory.put(new Product(\"A\", 10), 100); // 💥 ClassCastException\n\n// ✅ CORRECT: Provide Comparator\nTreeMap inventory = new TreeMap<>(\n Comparator.comparing(Product::getName)\n);\n\n// Or implement Comparable\npublic class Product implements Comparable {\n @Override\n public int compareTo(Product other) {\n return this.name.compareTo(other.name);\n }\n}\n```\n\n### Mistake 2: Inconsistent compareTo and equals\n\n```java\n// ❌ WRONG: compareTo returns 0 for different objects\npublic class Item implements Comparable {\n String id;\n int priority;\n\n @Override\n public int compareTo(Item other) {\n return Integer.compare(this.priority, other.priority);\n }\n\n @Override\n public boolean equals(Object o) {\n return this.id.equals(((Item) o).id);\n }\n}\n\nTreeMap map = new TreeMap<>();\nmap.put(new Item(\"A\", 1), \"first\");\nmap.put(new Item(\"B\", 1), \"second\"); // Overwrites! Same priority = \"equal\" to TreeMap\nmap.size(); // 1, not 2!\n\n// ✅ CORRECT: Make compareTo consistent with equals\n@Override\npublic int compareTo(Item other) {\n int priorityCompare = Integer.compare(this.priority, other.priority);\n if (priorityCompare != 0) return priorityCompare;\n return this.id.compareTo(other.id); // Tiebreaker\n}\n```\n\n### Mistake 3: Modifying Keys After Insertion\n\n```java\n// ❌ WRONG: Modifying key after insertion\nTreeMap map = new TreeMap<>();\nStringBuilder key = new StringBuilder(\"abc\");\nmap.put(key, \"value\");\n\nkey.append(\"def\"); // Key is now \"abcdef\"\n// Tree structure is corrupted!\n\nmap.get(new StringBuilder(\"abc\")); // null (might be)\nmap.get(new StringBuilder(\"abcdef\")); // null (might be)\n\n// ✅ CORRECT: Use immutable keys\nTreeMap map = new TreeMap<>();\nmap.put(\"abc\", \"value\");\n```\n\n### Mistake 4: SubMap Range Violations\n\n```java\nNavigableMap map = new TreeMap<>();\nmap.put(10, \"A\"); map.put(20, \"B\"); map.put(30, \"C\");\n\nNavigableMap sub = map.subMap(15, true, 25, true);\n\n// ❌ WRONG: Adding outside range\nsub.put(30, \"X\"); // 💥 IllegalArgumentException: key out of range\nsub.put(10, \"Y\"); // 💥 IllegalArgumentException: key out of range\n\n// ✅ CORRECT: Only add within range\nsub.put(20, \"updated\"); // OK\nsub.put(22, \"new\"); // OK\n```\n\n### Mistake 5: Null Keys\n\n```java\n// ❌ WRONG: TreeMap doesn't allow null keys (usually)\nTreeMap map = new TreeMap<>();\nmap.put(null, 1); // 💥 NullPointerException\n\n// HashMap allows null keys\nHashMap hashMap = new HashMap<>();\nhashMap.put(null, 1); // OK\n\n// TreeMap with null-safe Comparator (not recommended)\nTreeMap nullSafe = new TreeMap<>(\n Comparator.nullsFirst(Comparator.naturalOrder())\n);\nnullSafe.put(null, 1); // Works, but null keys are usually a design smell\n```\n\n---\n\n## 🐛 Debug This\n\n### Challenge 1: The Missing Entry\n\n```java\nTreeMap map = new TreeMap<>();\nmap.put(1.0, \"one\");\nmap.put(2.0, \"two\");\nmap.put(Double.NaN, \"nan\");\nmap.put(3.0, \"three\");\n\nSystem.out.println(map.get(2.0));\nSystem.out.println(map.size());\n```\n\n**✅ Answer:**\n\nOutput is unpredictable! `Double.NaN` violates comparison contract because `NaN.compareTo(x)` is always inconsistent (NaN is not equal to anything, including itself).\n\nThe tree structure becomes corrupted. You might get wrong results or exceptions.\n\n**Fix**: Never use NaN as a TreeMap key.\n\n### Challenge 2: The Overwritten Entry\n\n```java\nrecord Key(int id, String name) implements Comparable {\n @Override\n public int compareTo(Key other) {\n return this.name.compareTo(other.name);\n }\n}\n\nTreeMap map = new TreeMap<>();\nmap.put(new Key(1, \"Alice\"), \"first\");\nmap.put(new Key(2, \"Alice\"), \"second\");\n\nSystem.out.println(map.size());\nSystem.out.println(map.get(new Key(1, \"Alice\")));\n```\n\n**✅ Answer:**\n\nOutput:\n```text\n1\nsecond\n```\n\nBoth keys have name \"Alice\", so `compareTo` returns 0. TreeMap considers them equal and overwrites the first entry. The id field is ignored because it's not in compareTo.\n\n### Challenge 3: The Submap Surprise\n\n```java\nTreeMap map = new TreeMap<>();\nfor (int i = 1; i <= 10; i++) {\n map.put(i, \"v\" + i);\n}\n\nNavigableMap sub = map.subMap(3, true, 7, true);\nsub.clear();\n\nSystem.out.println(map);\n```\n\n**✅ Answer:**\n\nOutput: `{1=v1, 2=v2, 8=v8, 9=v9, 10=v10}`\n\nThe submap is a live view. Clearing it removes entries 3-7 from the original map!\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Price Band Lookup\n\nImplement a price band system that returns the discount for a given order amount:\n\n```java\npublic class PriceBandDiscounts {\n // $0-99: 0%, $100-499: 5%, $500-999: 10%, $1000+: 15%\n public int getDiscountPercent(double orderAmount);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class PriceBandDiscounts {\n private final NavigableMap bands = new TreeMap<>();\n\n public PriceBandDiscounts() {\n bands.put(0.0, 0); // $0+: 0%\n bands.put(100.0, 5); // $100+: 5%\n bands.put(500.0, 10); // $500+: 10%\n bands.put(1000.0, 15); // $1000+: 15%\n }\n\n public int getDiscountPercent(double orderAmount) {\n Map.Entry entry = bands.floorEntry(orderAmount);\n return entry != null ? entry.getValue() : 0;\n }\n}\n```\n\n### Exercise 2: Version Range Finder\n\nImplement a system that finds the latest compatible version:\n\n```java\npublic class VersionCompatibility {\n // Add compatible version range\n public void addCompatibility(String minVersion, String maxVersion, String feature);\n // Find all features compatible with given version\n public Set getCompatibleFeatures(String version);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class VersionCompatibility {\n private record VersionRange(String minVersion, String maxVersion, String feature) {}\n private final NavigableMap> byMinVersion = new TreeMap<>();\n\n public void addCompatibility(String minVersion, String maxVersion, String feature) {\n byMinVersion.computeIfAbsent(minVersion, k -> new ArrayList<>())\n .add(new VersionRange(minVersion, maxVersion, feature));\n }\n\n public Set getCompatibleFeatures(String version) {\n Set features = new HashSet<>();\n\n // Check all ranges that might include this version\n for (var entry : byMinVersion.headMap(version, true).entrySet()) {\n for (VersionRange range : entry.getValue()) {\n if (version.compareTo(range.minVersion) >= 0 &&\n version.compareTo(range.maxVersion) <= 0) {\n features.add(range.feature);\n }\n }\n }\n return features;\n }\n}\n```\n\n### Exercise 3: Rate Limiter with Time Windows\n\nImplement a rate limiter using TreeMap:\n\n```java\npublic class RateLimiter {\n public RateLimiter(int maxRequests, Duration window);\n public boolean allowRequest(String clientId);\n public int getRemainingRequests(String clientId);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class RateLimiter {\n private final int maxRequests;\n private final long windowMs;\n private final Map> clientRequests = new ConcurrentHashMap<>();\n\n public RateLimiter(int maxRequests, Duration window) {\n this.maxRequests = maxRequests;\n this.windowMs = window.toMillis();\n }\n\n public synchronized boolean allowRequest(String clientId) {\n long now = System.currentTimeMillis();\n NavigableMap requests = clientRequests.computeIfAbsent(\n clientId, k -> new TreeMap<>()\n );\n\n // Clean old entries\n requests.headMap(now - windowMs, false).clear();\n\n // Count requests in window\n int count = requests.values().stream().mapToInt(Integer::intValue).sum();\n\n if (count < maxRequests) {\n requests.merge(now, 1, Integer::sum);\n return true;\n }\n return false;\n }\n\n public int getRemainingRequests(String clientId) {\n NavigableMap requests = clientRequests.get(clientId);\n if (requests == null) return maxRequests;\n\n long now = System.currentTimeMillis();\n int count = requests.tailMap(now - windowMs, true)\n .values().stream().mapToInt(Integer::intValue).sum();\n\n return Math.max(0, maxRequests - count);\n }\n}\n```\n\n### Exercise 4: Calendar Event Finder\n\nImplement a calendar that finds events overlapping with a time range:\n\n```java\npublic class Calendar {\n public void addEvent(Instant start, Instant end, String title);\n public List getEventsOverlapping(Instant queryStart, Instant queryEnd);\n public String getEventAt(Instant time); // Event containing this time\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class Calendar {\n private record Event(Instant start, Instant end, String title) {}\n private final NavigableMap eventsByStart = new TreeMap<>();\n\n public void addEvent(Instant start, Instant end, String title) {\n eventsByStart.put(start, new Event(start, end, title));\n }\n\n public List getEventsOverlapping(Instant queryStart, Instant queryEnd) {\n List result = new ArrayList<>();\n\n // Events that start before queryEnd and might overlap\n for (Event event : eventsByStart.headMap(queryEnd, false).values()) {\n // Check if event overlaps with query range\n if (event.end.isAfter(queryStart)) {\n result.add(event.title);\n }\n }\n return result;\n }\n\n public String getEventAt(Instant time) {\n Map.Entry entry = eventsByStart.floorEntry(time);\n if (entry != null && entry.getValue().end.isAfter(time)) {\n return entry.getValue().title;\n }\n return null;\n }\n}\n```\n\n### Exercise 5: Nearest Neighbor Search\n\nImplement a 1D nearest neighbor search:\n\n```java\npublic class NearestNeighbor {\n public void addPoint(double x, String label);\n public String findNearest(double x);\n public List findKNearest(double x, int k);\n}\n```\n\n**✅ Solution:**\n\n```java\npublic class NearestNeighbor {\n private final NavigableMap points = new TreeMap<>();\n\n public void addPoint(double x, String label) {\n points.put(x, label);\n }\n\n public String findNearest(double x) {\n Map.Entry floor = points.floorEntry(x);\n Map.Entry ceiling = points.ceilingEntry(x);\n\n if (floor == null) return ceiling != null ? ceiling.getValue() : null;\n if (ceiling == null) return floor.getValue();\n\n return Math.abs(x - floor.getKey()) <= Math.abs(ceiling.getKey() - x)\n ? floor.getValue()\n : ceiling.getValue();\n }\n\n public List findKNearest(double x, int k) {\n if (points.isEmpty()) return Collections.emptyList();\n\n PriorityQueue> pq = new PriorityQueue<>(\n Comparator.comparingDouble(e -> Math.abs(e.getKey() - x))\n );\n pq.addAll(points.entrySet());\n\n List result = new ArrayList<>();\n while (!pq.isEmpty() && result.size() < k) {\n result.add(pq.poll().getValue());\n }\n return result;\n }\n}\n```\n\n---\n\n## 🎤 Senior-Level Interview Questions\n\n### Question 1: TreeMap vs HashMap Performance\n\n**Q: When would you choose TreeMap over HashMap despite the O(log n) vs O(1) difference?**\n\n**A:**\n\nChoose TreeMap when:\n1. **Range queries needed**: subMap, headMap, tailMap are O(log n) in TreeMap, require O(n) scan in HashMap\n2. **Sorted iteration**: TreeMap iterates in key order naturally\n3. **Proximity queries**: floorKey, ceilingKey have no HashMap equivalent\n4. **First/last access**: firstKey, lastKey are O(log n)\n\n```java\n// TreeMap wins for time-series: \"Get all events from 10am to 2pm\"\ntreeMap.subMap(time10am, time2pm); // O(log n + k)\n\n// HashMap requires full scan\nhashMap.entrySet().stream()\n .filter(e -> e.getKey().isAfter(time10am) && e.getKey().isBefore(time2pm))\n .collect(toList()); // O(n)\n```\n\n### Question 2: Red-Black Tree Properties\n\n**Q: Why does TreeMap use a Red-Black tree instead of an AVL tree?**\n\n**A:**\n\nRed-Black trees have:\n1. **Faster insertion/deletion**: Fewer rotations needed (at most 2 rotations per operation vs O(log n) for AVL)\n2. **Slightly slower lookup**: AVL is more strictly balanced\n3. **Better for modification-heavy workloads**: Java collections often modify frequently\n\nTrade-off: Red-Black trees have height up to 2*log(n), AVL trees have height exactly log(n). This means RB lookups can be up to 2x slower in worst case, but modifications are faster.\n\n### Question 3: NavigableMap Memory Views\n\n**Q: Are NavigableMap submaps views or copies? What are the implications?**\n\n**A:**\n\nThey are **views** backed by the original map:\n\n```java\nNavigableMap sub = map.subMap(from, to);\n\n// Implications:\n// 1. Changes to sub affect map (and vice versa)\nsub.put(key, value); // Also in map!\n\n// 2. No additional memory for the range itself\n// Only wrapper object, not copies of entries\n\n// 3. Concurrent modification during iteration\nfor (K key : sub.keySet()) {\n map.remove(key); // ConcurrentModificationException\n}\n\n// 4. Range restrictions enforced\nsub.put(outsideRangeKey, value); // IllegalArgumentException\n```\n\n### Question 4: TreeMap Comparator Consistency\n\n**Q: What happens if compareTo/Comparator is inconsistent with equals?**\n\n**A:**\n\nTreeMap uses compareTo for all key equality, ignoring equals():\n\n```java\nclass Person implements Comparable {\n int age;\n String name;\n\n int compareTo(Person o) { return Integer.compare(age, o.age); }\n boolean equals(Object o) { return name.equals(((Person)o).name); }\n}\n\n// Two people with same age but different names:\nTreeMap map = new TreeMap<>();\nmap.put(new Person(30, \"Alice\"), \"A\");\nmap.put(new Person(30, \"Bob\"), \"B\"); // Overwrites Alice!\n\nmap.size(); // 1, not 2\n\n// The TreeMap considers them equal because compareTo returns 0\n// even though equals would return false\n```\n\n### Question 5: Submap Thread Safety\n\n**Q: If you create a submap view and another thread modifies the original map, what happens?**\n\n**A:**\n\nTreeMap (and its views) are not thread-safe:\n\n```java\nNavigableMap map = new TreeMap<>();\nNavigableMap sub = map.subMap(from, to);\n\n// Thread 1: iterating sub\n// Thread 2: modifying map\n\n// Result: ConcurrentModificationException or corrupted state\n\n// Solutions:\n// 1. External synchronization\nsynchronized (map) {\n for (K key : sub.keySet()) { ... }\n}\n\n// 2. Use ConcurrentSkipListMap\nNavigableMap concurrent = new ConcurrentSkipListMap<>();\n// Views are weakly consistent, no CME but might miss updates\n```\n\n### Question 6: Ceiling vs Floor Use Cases\n\n**Q: Give a real-world example where you'd use ceilingEntry vs floorEntry.**\n\n**A:**\n\n```java\n// floorEntry: \"What's the highest discount tier I qualify for?\"\nNavigableMap discountTiers = new TreeMap<>();\ndiscountTiers.put(0, 0); // $0+: 0%\ndiscountTiers.put(100, 5); // $100+: 5%\ndiscountTiers.put(500, 10); // $500+: 10%\n\nint discount = discountTiers.floorEntry(orderAmount).getValue();\n// Order of $350 → floor($350) = $100 tier → 5% discount\n\n// ceilingEntry: \"What's the next tier I need to reach?\"\nMap.Entry nextTier = discountTiers.higherEntry(orderAmount);\n// Order of $350 → next tier is $500 for 10%\n// \"Spend $150 more to get 10% off!\"\n```\n\n---\n\n## 📝 Summary & Key Takeaways\n\n### TreeMap Fundamentals\n- Red-Black tree: O(log n) for all operations\n- Keys must be Comparable or provide Comparator\n- No null keys (usually), null values allowed\n- Sorted iteration order\n\n### NavigableMap Operations\n- `floorEntry/ceilingEntry`: Closest match ≤ / ≥\n- `lowerEntry/higherEntry`: Strictly < / >\n- `subMap/headMap/tailMap`: Range views (live!)\n- `descendingMap`: Reverse order view\n\n### Performance Trade-offs\n- TreeMap: O(log n) everything, sorted, range queries\n- HashMap: O(1) point operations, unsorted, no ranges\n- Choose based on query patterns, not just storage\n\n### Common Patterns\n- Time-series: subMap for time ranges\n- Autocomplete: subMap for prefix matching\n- Price bands: floorEntry for threshold lookup\n- Nearest neighbor: floor + ceiling comparison\n\n---\n\n## 🏁 Conclusion\n\nTreeMap is the go-to collection when you need sorted key-value storage with range query capabilities. The NavigableMap interface provides elegant solutions to problems that would require complex code with HashMap.\n\nKey takeaways:\n1. **TreeMap excels at range queries** - O(log n) vs O(n) for HashMap\n2. **NavigableMap operations are powerful** - floor, ceiling, subMap enable elegant solutions\n3. **Views are live** - changes propagate bidirectionally\n4. **compareTo consistency matters** - TreeMap ignores equals()\n5. **Use HashMap for point queries** - when you don't need sorting or ranges\n\nIn the next article, we'll explore LinkedHashMap - the hybrid that combines HashMap's O(1) performance with predictable iteration order, plus the secret to implementing LRU caches.\n\n---\n\n## 📅 Review Schedule\n\nTo solidify your understanding, review this material:\n- **Tomorrow**: Re-read NavigableMap operations section\n- **In 3 days**: Implement Exercise 3 (Rate Limiter) again\n- **In 1 week**: Explain TreeMap vs HashMap trade-offs to a colleague\n- **In 2 weeks**: Review the time-series production story\n\n---\n\n**Next in Series**: [Part 15: LinkedHashMap & LRU Cache](/articles/java-collections-part-15-linkedhashmap-lru)\n\n**Series Navigation**: [Part 0: How to Use This Series](/articles/java-collections-part-0-how-to-use-this-series) | [Full Index](/articles/java-collections-compendium)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:26.014486Z","createdAt","2026-06-10T07:19:26.015272Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",18,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Java","readingTime","seriesId",5,"seriesOrder",14,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":62,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Java Collections Compendium: From Fundamentals to Production Mastery","java-collections-compendium","description","A comprehensive 30-part series covering everything about Java Collections Framework. From foundational concepts like generics and equals/hashCode contract, through deep dives into ArrayList, LinkedList, HashMap, TreeMap, ConcurrentHashMap, to modern features like immutable collections, Java 21 sequenced collections, streams & collectors, and production patterns with JPA, Jackson & Spring. Includes real production stories, mental models, exercises, and 50+ interview questions.","isActive",{"_31":64,"_73":59,"_35":96},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},349,"Treemap","treemap",351,"Sortedmap","sortedmap",343,"Red-black Tree","red-black-tree",350,"Navigablemap","navigablemap","java","Category for Java","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]