简介

• HashMap：数组+单向链表
• LinkedHashMap： HashMap + 双向循环链表
• LruCache：基于

LinkedMap实现原理

• 原理图解

第一张图是LinkedHashMap的全部数据结构，包含散列表和循环双向链表，由于循环双向链表线条太多了，不好画，简单的画了一个节点(黄色圈出来的)示意一下，注意左边的红色箭头引用为Entry节点对象的next引用(散列表中的单链表)，绿色线条为Entry节点对象的before, after引用(循环双向链表的前后引用)；

• 第二张图专门把循环双向链表抽取出来，直观一点，注意该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口；

LinkedHashMap继承于HashMap，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表, 它使用了一个双向链表来存储Map中的Entry顺序关系，这种顺序有两种，一种是LRU顺序，一种是插入顺序。所以，对于get、put、remove等操作，LinkedHashMap除了要做HashMap做的事情，还做些调整Entry顺序链表的工作。

• 特点：
  可以按照从近期访问最少到近期访问最多的顺序（即访问顺序）来排序，也可以按照插入顺序排序；这个特性有利于实现LruCache。

• 按插入排序（默认）

• 按访问排序

LruCache分析

LruCache中将LinkedHashMap的顺序设置为LRU顺序来实现LRU缓存，每次调用get(也就是从内存缓存中取图片)，则将该对象移到链表的尾端。调用put插入新的对象也是存储在链表尾端，这样当内存缓存达到设定的最大值时，将链表头部的对象（近期最少用到的）移除。

LruCache源码解析