Have you ever encountered LinkedHashMap?

Yes, I have encountered it. LinkedHashMap in Java and Kotlin is an implementation of the Map interface. It combines the properties of HashMap (fast access by key O(1) on average) and LinkedList (preserves insertion order of elements).

Main features:

• Preservation of order: Iteration over elements occurs in the order they were added.
• Performance: Adding, removing, and searching for elements are performed with amortized constant complexity (O(1)), like HashMap.
• Memory: Compared to HashMap, LinkedHashMap uses slightly more memory to store links between elements.
• Access mode: Can be configured to preserve access order (most recently accessed elements are moved to the end), which is useful for implementing caches with a least recently used (LRU) eviction policy.

Example of usage for an LRU cache:

// Create a cache with a maximum size of 5
// true in the constructor enables access order mode
LinkedHashMap<String, String> lruCache = new LinkedHashMap<>(5, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        // Remove the oldest element if size exceeds 5
        return size() > 5;
    }
};

lruCache.put("key1", "value1");
lruCache.put("key2", "value2");
lruCache.put("key3", "value3");
System.out.println(lruCache.get("key1")); // Access to key1, it moves to the end
lruCache.put("key4", "value4");
lruCache.put("key5", "value5");
lruCache.put("key6", "value6"); // Cache exceeds size, oldest is removed (key2 if no access; key3 if accessed to key1)

System.out.println(lruCache);

// Create a cache with access mode enabled (true)
val lruCache = object : LinkedHashMap<String, String>(5, 0.75f, true) {
    override fun removeEldestEntry(eldest: Map.Entry<String, String>?): Boolean {
        // Remove the oldest element if size exceeds 5
        return size > 5
    }
}

lruCache["key1"] = "value1"
lruCache["key2"] = "value2"
lruCache["key3"] = "value3"
println(lruCache["key1"]) // Access to key1, it moves to the end
lruCache["key4"] = "value4"
lruCache["key5"] = "value5"
lruCache["key6"] = "value6" // Cache exceeds size, oldest is removed

println(lruCache)

LinkedHashMap is useful when the iteration order of elements is important, as well as for implementing simple LRU caches.