Java集合类-LinkedHashMap

LinkedHashMap特点

作用：记录HashMap插入元素的顺序或访问元素的顺序

原理：双向链表和哈希表的结合

使用场景：适用于实现缓存，用空间换时间，如LRU

继承HashMap，大部分操作和HashMap实现一致

元素的顺序在访问时是怎样体现的？

构造函数可以指定accessOrder：

• true表示记录元素访问顺序。
• false表示记录元素插入的顺序，默认为false。

创建一个记录元素访问顺序的LinkedHashMap：
new LinkedHashMap(16, 0.75f, true)

• 记录元素插入顺序时，通过迭代器遍历时，先插入的元素会先访问到。
• 记录元素访问顺序时，刚访问过的元素会调整到链表末尾，通过迭代器遍历时，先遍历到的是最久没有被访问过的元素。

为什么最新插入和最后访问的要放在末尾？

插入新元素默认就是在链表尾部插入，是符合常规逻辑的，最新访问的放在末尾也就是统一这个规则了。

LinkedHashMap实现原理？

双向链表的结点类继承HashMap桶中链表的结点类，增加了前后指针，实际效果如下：

LinkedHashMap有什么应用？

LRU缓存。

用LinkedHashMap手撕 LeetCode.146. LRU 缓存机制（难度：中等）

class LRUCache(private val capacity: Int) {
    private val map = LinkedHashMap<Int, Int>(16, 0.75f, true)

    fun get(key: Int): Int {
        return map[key] ?: -1
    }

    fun put(key: Int, value: Int) {
        if (map.size == capacity && !map.containsKey(key)) {
            val oldest = map.iterator().next()
            map.remove(oldest.key)
        }
        map[key] = value
    }
}