LinkedHashMap原理分析
一、前言
我们都知道，HashMap是基于散列表，插入是无序的，但是通过key-value的键值对能非常方便的存取数据。如果我们想既保留键值对的高效数据存取，又能保证键值对按插入顺序或访问顺序排列，如何实现？
就是本篇文章需要分析的：LinkedHashMap。
LinkedHashMap继承自HashMap,保留了其如下特点：
- Key和Value都允许空；
- Key重复会覆盖、Value允许重复；
- 非线程安全。
二、LinkedHashMap解析
两个成员变量：
private transient LinkedHashMapEntry<K,V> header; //双向链表头结点，在init方法里被实例化
private final boolean accessOrder; //控制链表排序方式 ，fasle为按插入顺序，true为按访问顺序，默认为false。
构造方法：
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
有好几个重载的构造方法，只有如上方法可以动态设置accessOrder，其余的accessOrder都为false.
另外还有两个参数顺便了解下：
capacity: HashMap桶的数量，默认16,之后按2的幂扩展.
loadfactor: 装载因子，来衡量HashMap满的程度，默认0.75f.
put方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
// 计算hash值
int hash = hash(key);
// 得到在table数组中的index
int i = indexFor(hash, table.length);
// 遍历table[index]，判断是否key已经存在，存在则替换，并返回旧值
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++;
// 如果key之前在table中不存在，则调用addEntry，LinkedHashMap重写了该方法
addEntry(hash, key, value, i);
return null;
}
LinkedHashMap并没有重写HashMap的put方法，但是重写了put里的recordAccess和addEntry方法。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) { //fasle为按插入顺序，true为按访问顺序
lm.modCount++;
remove(); // 把更新的Entry从双向链表中移除
addBefore(lm.header);// 最近访问的元素被放到了链表头
}
}
private void remove() {
before.after = after;
after.before = before;
}
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
recordAccess：主要针对按访问顺序排序，把当前相同实体从链表中删除，最近访问的元素被加到链表头。
void addEntry(int hash, K key, V value, int bucketIndex) {
// 调用父类的addEntry，增加一个Entry到HashMap中
super.addEntry(hash, key, value, bucketIndex);
...
}
void addEntry(int hash, K key, V value, int bucketIndex) {
...
// LinkedHashMap进行了重写
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
// e就是新创建了Entry，会加入到table[bucketIndex]的表头
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
// 把新创建的Entry，加入到双向链表表头
e.addBefore(header);
size++;
}
addEntry：新的实体，直接创建并加入表头。
get方法：
public V get(Object key) {
// 调用genEntry得到Entry
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序
e.recordAccess(this);
return e.value;
}
LinkedHashMap有对get方法进行了重写，且同样调用recordAccess，重新排列下自己的双向链表。
总结加入元素过程：
遍历：
LinkedHashMap lhm = new LinkedHashMap<>(16, 0.75f, true);
lhm.put("name1", "stan");
lhm.put("name2", "james");
lhm.put("name3", "mario");
//lhm.put("name1", "stan");
Set entrySet = lhm.entrySet();
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
Entry entry = (Entry) iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
如上代码输入结果：
key:name1,value:stan
key:name2,value:james
key:name3,value:mario
如果打开注释项，则结果变为：
key:name2,value:james
key:name3,value:mario
key:name1,value:stan
这个重写插入过程：
先断开Entry1, head before指针指向它，after指向指向Entry2,Entry1 的after指针指向Entry3.这个过程相当于把Entry1从队尾移动到了队头。
那为何是最后打印呢？再看遍历源码：
private abstract class LinkedHashIterator<T> implements Iterator<T> {
// 默认下一个返回的Entry为双向链表表头的下一个元素
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
public boolean hasNext() {
return nextEntry != header;
}
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;
}
...
}
LinkedHashMap的迭代器，很明显看到，他是从head的after指针开始遍历的。新加入的元素放在队头，但是最终从队尾变量，所以既保证了插入顺序，又保证了访问属性，非常灵活，仅仅通过一个双向链表实现。而且并没有破坏HashMap的结构。所以说LinkedHashMap = HashMap + 循环双向链表。
最后一张图对比下HashMap与LinkedHashMap数据结构的区别：
