使用 LinkedHashMap 实现 LRU 算法

上面是 linkedhashmap 的继承结构。然后看下构造方法：

构造方法比较简单，主要是多个两个成员变量，并且构造方法当中多了 accessorder。

下面看下 put 方法，linkedhashmap 并没有重新实现 put 方法，但是重写了 hashmap 当中的几个 put 调用的方法：

下面是 hashmap 的 put 方法：

linkedhashmap 当中重写了 addentry 方法和 createentry 方法。下面看下：

下面的 createentry 方法：

从上面这两个重写的方法来看，在 linkedhashmap 当 put 一组 key - value 的时候，我们会在 hashmap 的结构当中添加一个元素，并且会在自己的特有的链表当中添加一个元素。

看下 linkedhashmap 内部的 entry 实现代码：

lru 算法就是近期最少使用算法。当我们要用 linkedhashmap 来实现的时候，其实我们就是用他内部的双向链表，每次 put 的时候我们把这个元素加入到链表尾部，然后 get 的时候也会把元素重新添加到尾部，这样就简单的描述了一个 lru 算法。

那么实现代码如下：

看代码实现的很简单，只需要重写一个 removeeldestentry 就行，这个方法只需要判断当前的 size 是不是大于最大容量，那么我们重新看下这是为什么：

首先我们创建的 linkedhashmap 第 3 个参数传的是 true 。这样 accessorder 就是 addentry 了，那么就重新看下 put 方法。

我们看下 linkedhashmap.entry 的 recordremoval 实现：

代码实现很简单，想当于把链表的当前元素来删掉。

既然上面在 put 的时候会根据最大容量来判断是否需要移除最不常用的元素了，下面我们就分析最常用的元素如何处理。内部原理就是当每次 get 的时候，如果找到了元素就把元素重新添加到链表的头部。

代码超级简单， linkedhashmap.entry 重写了 recordaccess 方法，如下：

可以看到先判断 accessorder 这个成员变量，我们创建 linkedhashmap 对象时候传入的是 true。里面的内部结构也很简单，先把自己移除，然后在把自己添加进去。