LinkedHashMap原理分析
众所周知HashMap是无序的，插入的顺序读取的顺序未必相同，但如果选择其他数据结构存储数据又达不到HashMap键值对的存储效果，或者实现起来很麻烦，所以在JDK1.4以后提供LinkedHashMap来帮助我们实现有序的HashMap。
LinkedHashMap概述
LinkedHashMap其实是HashMap的一个子类，实际上就是一个HashMap，拥有HashMap所有特性，不同的地方是LinkedHashMap将HashMap和双向链表合二为一，该双向链表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
另外LinkedHashMap还有一个特点是同步，如果多个线程同事访问链接的哈希映射，而其中至少一个线程从结构上修改了改映射，则它必须保持外部同步。
- 插入顺序
比如，插入A,B,C，那么迭代也是A,B,C - 访问顺序
在迭代前，访问了B，那么迭代的顺序就是A,C,B，比如在迭代前，访问了B，接着又访问了A，那么迭代顺序为C,B,A，比如，在迭代前访问了B，接着又访问了B，然后在访问了A，迭代顺序还是C,B,A。要说明的意思就是不是近期访问的次数最多，就放最后面迭代，而是看迭代前被访问的时间长短决定。
举个栗子
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
上边是一个简单的HashMap代码，通过控制台输出结果，我们可以看出HashMap是没有顺序的。
banana=香蕉
apple=苹果
peach=桃子
watermelon=西瓜
现在我们吧map的实现替换成LinkedHashMap,其他代码都不变:Map<String, String> map = new LinkedHashMap<String, String>();看一下控制台输出:
apple=苹果
watermelon=西瓜
banana=香蕉
peach=桃子
我们可以看到，其输出顺序是完成按照插入顺序的！也就是我们上面所说的保留了插入的顺序。我们不是在上面还提到过其可以按照访问顺序进行排序么？好的，我们还是通过一个例子来验证一下：
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
map.get("banana");
map.get("apple");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
代码与之前的都差不多，但我们多了两行代码，并且初始化 LinkedHashMap 的时候，用的构造函数也不相同，看一下控制台的输出结果：
watermelon=西瓜
peach=桃子
banana=香蕉
apple=苹果
这也就是我们之前提到过的，LinkedHashMap 可以选择按照访问顺序进行排序。
LinkedHashMap源码分析
1.jpeg
从上图我们可以看出，LinkedHashMap中并增加没有额外方法。也就是说，LinkedHashMap与HashMap在操作上大致相同，只是在实现细节上略有不同罢了。LinkedHashMap特有的两个属性：双向列表头结点和迭代顺序。
LinkedHashMap中的Entry增加了两个指针 before 和 after，它们分别用于维护双向链接列表。特别需要注意的是，next用于维护HashMap各个桶中Entry的连接顺序，before、after用于维护Entry插入的先后顺序的，源代码如下：
//LinkedHashMap的entry继承自HashMap的Entry。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
//通过上面这句源码的解释，我们可以知道这两个字段，是用来给迭代时使用的，相当于一个双向链表，实际上用的时候，操作LinkedHashMap的entry和操作HashMap的Entry是一样的，只操作相同的四个属性，这两个字段是由linkedHashMap中一些方法所操作。所以LinkedHashMap的很多方法度是直接继承自HashMap。
//before：指向前一个entry元素。after：指向后一个entry元素
Entry<K,V> before, after;
//使用的是HashMap的Entry构造
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
//下面是维护这个双向循环链表的一些操作。在HashMap中没有这些操作，因为HashMap不需要维护，
/**
* Removes this entry from the linked list.
*/
//我们知道在双向循环链表时移除一个元素需要进行哪些操作把，比如有A,B,C，将B移除，那么A.next要指向c，c.before要指向A。下面就是进行这样的操作，但是会有点绕，他省略了一些东西。
//有的人会问，要是删除的是最后一个元素呢，那这个方法还适用吗？有这个疑问的人应该注意一下这个是双向循环链表，双向，删除哪个度适用。
private void remove() {
//this.before.after = this.after;
//this.after.before = this.before; 这样看可能会更好理解，this指的就是要删除的哪个元素。
before.after = after;
after.before = before;
}
/**
* Inserts this entry before the specified existing entry in the list.
*/
//插入一个元素之后做的一些操作，就是将第一个元素，和最后一个元素的一些指向改变。传进来的existingEntry就是header。
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* This method is invoked by the superclass whenever the value
* of a pre-existing entry is read by Map.get or modified by Map.set.
* If the enclosing Map is access-ordered, it moves the entry
* to the end of the list; otherwise, it does nothing.
*/
//这个方法就是我们一开始说的，accessOrder为true时，就是使用的访问顺序，访问次数最少到访问次数最多，此时要做特殊处理。处理机制就是访问了一次，就将自己往后移一位，这里就是先将自己删除了，然后在把自己添加，
//这样，近期访问的少的就在链表的开始，最近访问的元素就会在链表的末尾。如果为false。那么默认就是插入顺序，直接通过链表的特点就能依次找到插入元素，不用做特殊处理。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
初始化
通过源代码可以看出，在 LinkedHashMap 的构造方法中，实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组，但额外可以增加 accessOrder 这个参数，如果不设置，默认为 false，代表按照插入顺序进行迭代；当然可以显式设置为 true，代表以访问顺序进行迭代。
//使用父类中的构造，初始化容量和加载因子，该初始化容量是指数组大小。
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//一个参数的构造
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//无参构造
public LinkedHashMap() {
super();
accessOrder = false;
}
//这个不用多说，用来接受map类型的值转换为LinkedHashMap
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
//真正有点特殊的就是这个，多了一个参数accessOrder。存储顺序，LinkedHashMap关键的参数之一就在这个，
//true：指定迭代的顺序是按照访问顺序(近期访问最少到近期访问最多的元素)来迭代的。 false：指定迭代的顺序是按照插入顺序迭代，也就是通过插入元素的顺序来迭代所有元素
//如果你想指定访问顺序，那么就只能使用该构造方法，其他三个构造方法默认使用插入顺序。
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
我们已经知道 LinkedHashMap 的 Entry 元素继承 HashMap 的 Entry，提供了双向链表的功能。在上述 HashMap 的构造器中，最后会调用 init() 方法，进行相关的初始化，这个方法在 HashMap 的实现中并无意义，只是提供给子类实现相关的初始化调用。
但在 LinkedHashMap 重写了 init() 方法，在调用父类的构造方法完成构造后，进一步实现了对其元素 Entry 的初始化操作。
//linkedHashMap中的init()方法，就使用header，hash值为-1，其他度为null，也就是说这个header不放在数组中，就是用来指示开始元素和标志结束元素的。
void init() {
header = new Entry<>(-1, null, null, null);
//一开始是自己指向自己，没有任何元素。HashMap中也有init()方法是个空的，所以这里的init()方法就是为LinkedHashMap而写的。
header.before = header.after = header;
}
//在HashMap的构造方法中就会使用到init()，
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
存储（put）
LinkedHashMap 并未重写父类 HashMap 的 put 方法，而是重写了父类 HashMap 的 put 方法调用的子方法void recordAccess(HashMap m) ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。
public V put(K key, V value) {
//刚开始其存储空间啥也没有，在这里初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//key为null的情况
if (key == null)
return putForNullKey(value);
//通过key算hash，进而算出在数组中的位置，也就是在第几个桶中
int hash = hash(key);
int i = indexFor(hash, table.length);
//查看桶中是否有相同的key值，如果有就直接用新植替换旧值，而不用在创建新的entry了
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//最重要的地方来了，就是这个方法，LinkedHashMap执行到这里，addEntry()方法不会执行HashMap中的方法，而是执行自己类中的addEntry方法，这里就要
提一下LinkedHashMap重写HashMap中两个个关键的方法了。看下面的分析。
addEntry(hash, key, value, i);
return null;
}
重写了void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)
//重写的addEntry。其中还是会调用父类中的addEntry方法，但是此外会增加额外的功能，
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
//HashMap的addEntry，就是在将元素加入桶中前判断桶中的大小或者数组的大小是否合适，总之就是做一些数组容量上的判断和hash值的问题。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//这里就是真正创建entry的时候了。也被LinkedHashMap重写了。
createEntry(hash, key, value, bucketIndex);
}
//重写的createEntry，这里要注意的是，新元素放桶中，是放第一位，而不是往后追加，所以下面方法中前面三行应该知道了
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
//这个方法的作用就是将e放在双向循环链表的末尾，需要将一些指向进行修改的操作。。
e.addBefore(header);
size++;
}
迭代器Interator
对双向循环链表的遍历操作。但是这个迭代器是abstract的，不能直接被对象所用，但是能够间接使用，就是通过keySet().interator()，就是使用的这个迭代器
//对双向循环链表进行遍历。
private abstract class LinkedHashIterator<T> implements Iterator<T> {
//先拿到header的after指向的元素，也就是第一个元素。
Entry<K,V> nextEntry = header.after;
//记录前一个元素是谁，因为刚到第一个元素，第一个元素之前的元素理论上就是null。实际上是指向最后一个元素的。知道就行。
Entry<K,V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
//判断有没有到循环链表的末尾，就看元素的下一个是不是header。
public boolean hasNext() {
return nextEntry != header;
}
//移除操作，也就一些指向问题
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
//下一个元素。一些指向问题，度是双向循环链表中的操作。
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
}
读取(get)
LinkedHashMap 重写了父类 HashMap 的 get 方法，实际在调用父类 getEntry() 方法取得查找的元素后，再判断当排序模式 accessOrder 为 true 时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
//关键的就是这个方法
e.recordAccess(this);
return e.value;
}
//这个方法在上面已经分析过了，如果accessOrder为true，那么就会用访问顺序。if条件下的语句会执行，作用就是将最近访问的元素放链表的末尾。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
总结
其实 LinkedHashMap 几乎和 HashMap 一样：从技术上来说，不同的是它定义了一个 Entry<K,V> header，这个 header 不是放在 Table 里，它是额外独立出来的。LinkedHashMap 通过继承 hashMap 中的 Entry<K,V>,并添加两个属性 Entry<K,V> before,after,和 header 结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。了解了LinkedHashMap的实现原理，可以为后面的LruCache打下坚实基础
