由于其源码并不是很长，直接贴出来:
-
可以看到LinkedHashMap继承自HashMap，同时实现map接口最新JDK 1.8 HashMap的数据结构为数组+链表+红黑树。
-
LinkedHashMap基于HashMap的数据结构，新增了一条双向链表
-
HashMap是无序的，而LinkedHashMap就弥补了该缺点，默认为插入顺序，即最后插入的key-value会加到双向链表的尾部，若定义accessOrder为true的话，则为访问顺序，即put key-value后，调用get，replace等方法，都会将节点放到链表尾部，即符合LRU算法，经常使用的数据放在链表尾部。
-
这里可以通过实现removeEldestEntry接口来自定义自己的LRU算法，即put一个key-value后，根据自己业务的LRU需求，将最旧的数据节点(即双向链表节点的头节点)删除。
package java.util;import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.io.IOException;public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>
{
//LinkedHashMap新增双向链表维护的链表条目，这里称其为链表节点static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
//比HashMap.Node多了两个节点before，afterLinkedHashMapEntry<K,V> before, after;LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);}}private static final long serialVersionUID = 3801124242820219131L;//双向链表的头节点transient LinkedHashMapEntry<K,V> head;//双向链表的尾节点transient LinkedHashMapEntry<K,V> tail;//迭代顺序(例如调用entrySet)：//accessOrder=true时为访问顺序//access-order=false为插入顺序final boolean accessOrder;//将p放到链表的末尾private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail; //旧的链表尾节点tail = p; //新的链表尾节点//若旧的链表尾节点为null//证明链表为null//将链表头节点赋值为pif (last == null)head = p;//若旧的链表尾节点不为nullelse {
//将新的链表尾节点连接到旧的链表尾节点p.before = last;last.after = p;}}//将dst节点的前后节点替换为src节点的前后节点private void transferLinks(LinkedHashMapEntry<K,V> src,LinkedHashMapEntry<K,V> dst) {
LinkedHashMapEntry<K,V> b = dst.before = src.before;LinkedHashMapEntry<K,V> a = dst.after = src.after;//若dst的后节点为nullif (b == null)//将链表头节点赋值为dst节点head = dst;//若dst的后节点不为nullelse//将dst前节点的后节点赋值为dst节点b.after = dst;//若dst的前节点为nullif (a == null)//将链表尾节点赋值为dst节点tail = dst;//若dst的前节点不为null else//将dst后节点的前节点赋值为dst节点a.before = dst;}//重置为初始默认状态。 由clone和readObject调用void reinitialize() {
super.reinitialize();head = tail = null;}//覆盖HashMap的创建普通节点方法//创建一个新的链表节点Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//创建一个双向链表节点LinkedHashMapEntry<K,V> p =new LinkedHashMapEntry<K,V>(hash, key, value, e);//将其加到链表尾部 linkNodeLast(p);return p;}//覆盖HashMap的红黑树节点转换为普通单链表节点方法Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;//将红黑树节点转换为双链表节点LinkedHashMapEntry<K,V> t =new LinkedHashMapEntry<K,V>(q.hash, q.key, q.value, next);//节点转换完成后，将新的节点的前后节点指向原本节点的前后节点transferLinks(q, t);return t;}//覆盖HashMap的创建红黑树节点方法TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
//创建红黑树节点TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);//创建节点完成后将其插入到双向链表尾部//这里可以直接将TreeNode强转为LinkedHashMapEntry//是因为在HashMap中://TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> linkNodeLast(p);return p;}//覆盖HashMap的普通单链表节点转换为红黑树节点方法TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
//由上面newNode接口我们可以知道，创建的节点都为LinkedHashMapEntryLinkedHashMapEntry<K,V> q = (LinkedHashMapEntry<K,V>)p;TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);//节点转换完成后，将新的节点的前后节点指向原本节点的前后节点//这里可以直接将TreeNode强转为LinkedHashMapEntry//是因为在HashMap中://TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> transferLinks(q, t);return t;}//下面三个接口为HashMap预留个LinkedHashMap的接口//HashMap移除节点的时候会回调该接口void afterNodeRemoval(Node<K,V> e) {
//声明当前要移除的节点p = e//声明b = p的前一个节点//声明a = p的后一个节点LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;//因为p节点要移除，这里将其前后节点都置为nullp.before = p.after = null;//如果b为null，证明要删除的节点为链表头节点if (b == null)//这里要将链表头节点赋值为p的后一个节点head = a;//如果b不为null，证明要删除的节点不是链表头节点else//将b的后一个节点赋值为ab.after = a;//如果a为null，证明要删除的节点为链表尾节点if (a == null)//这里要将链表尾节点赋值为p的前一个节点tail = b;//如果a不为null，证明要删除的节点不是链表尾节点 else//将a的前一个节点赋值为ba.before = b;}//HashMap插入一个节点后会回调此接口//evict = false的话，处于创建模式void afterNodeInsertion(boolean evict) {
// possibly remove eldest//声明双向链表头节点LinkedHashMapEntry<K,V> first;//只有处于创建模式且头节点不为null且removeEldestEntry接口返回true的时候//会删除最旧的数据if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;removeNode(hash(key), key, null, false, true);}}//HashMap调用put、replace等接口后会回调此接口//在LinkedHashMap中意义为将put，replace，get视为访问，每次访问结束都会将对应的//节点放到链表后面void afterNodeAccess(Node<K,V> e) {
//声明上一个尾节点为lastLinkedHashMapEntry<K,V> last;//如果accessOrder为true且e不是双向链表的最后一个节点if (accessOrder && (last = tail) != e) {
//声明当前节点p = e//声明当前节点b = p的前节点//声明当前节点a = p的后节点LinkedHashMapEntry<K,V> p =(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;//因为要将p加到链表最后，因此这里要将p的后一个节点置为nullp.after = null;//如果b为null的话，证明p就是头节点if (b == null)//因此这里需要将头节点赋值为p的后节点head = a;else//否则将b的后节点赋值为ab.after = a;//如果a不为null，if (a != null)//将a的前节点赋值为ba.before = b;else//如果a为null，证明p就是尾节点//这里将last赋值为blast = b;//上一个尾节点为null的话，证明链表为nullif (last == null)//这里将头节点赋值为phead = p;else {
//否则将p的前节点赋值为lastp.before = last;//last的后节点赋值为plast.after = p;}//将双向链表尾节点赋值为p，即将e加到了双向链表尾部tail = p;++modCount; //修改次数加1}}//------------------------------------------------------------//内部序列化写入void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
s.writeObject(e.key);s.writeObject(e.value);}}//构造函数//initialCapacity：初始容量//loadFactor：加载因子//且默认accessOrder为falsepublic LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);accessOrder = false;}//构造函数//initialCapacity：初始容量//且默认accessOrder为falsepublic LinkedHashMap(int initialCapacity) {
super(initialCapacity);accessOrder = false;}//构造函//且默认accessOrder为falsepublic LinkedHashMap() {
super();accessOrder = false;}//构造函数//m：要拷贝的map//且默认accessOrder为falsepublic LinkedHashMap(Map<? extends K, ? extends V> m) {
super();accessOrder = false;putMapEntries(m, false);}//构造函数//initialCapacity：初始容量//loadFactor：加载因子//accessOrder：链表顺序public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}//是否包含某个value//这里会遍历查找双向链表，因此查找的时间复杂度为O(n)public boolean containsValue(Object value) {
for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
V v = e.value;if (v == value || (value != null && value.equals(v)))return true;}return false;}//重写的get方法//会调用HashMap的getNode方法//getNode不为null且accessOrder为true的话，则将对应节点放到链表尾部public V get(Object key) {
Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;if (accessOrder)afterNodeAccess(e);return e.value;}//重写的getOrDefault方法//会调用HashMap的getNode方法//getNode不为null且accessOrder为true的话，则将对应节点放到链表尾部public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return defaultValue;if (accessOrder)afterNodeAccess(e);return e.value;}//清空数据，包括头尾节点public void clear() {
super.clear();head = tail = null;}//获取最旧的数据，即头节点public Map.Entry<K, V> eldest() {
return head;}//LinkedHashMap默认总是返回false//即不删除最旧的节点，如果需要删除最旧节点，继承LinkedHashMap，//然后重写removeEldestEntry方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;}//获取key集合public Set<K> keySet() {
Set<K> ks = keySet;if (ks == null) {
ks = new LinkedKeySet();keySet = ks;}return ks;}//自定义KeySetfinal class LinkedKeySet extends AbstractSet<K> {
public final int size() {
return size; }public final void clear() {
LinkedHashMap.this.clear(); }//这里的迭代器也是LinkedHashMap自定义的迭代器public final Iterator<K> iterator() {
return new LinkedKeyIterator();}public final boolean contains(Object o) {
return containsKey(o); }public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;}public final Spliterator<K> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED |Spliterator.DISTINCT);}//遍历顺序：双向链表的头->尾 public final void forEach(Consumer<? super K> action) {
if (action == null)throw new NullPointerException();int mc = modCount;//遍历for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)action.accept(e.key);//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 if (modCount != mc)throw new ConcurrentModificationException();}}//value集合public Collection<V> values() {
Collection<V> vs = values;if (vs == null) {
vs = new LinkedValues();values = vs;}return vs;}//自定义value集合final class LinkedValues extends AbstractCollection<V> {
public final int size() {
return size; }public final void clear() {
LinkedHashMap.this.clear(); }//这里的迭代器也是LinkedHashMap自定义的迭代器public final Iterator<V> iterator() {
return new LinkedValueIterator();}public final boolean contains(Object o) {
return containsValue(o); }public final Spliterator<V> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED);}public final void forEach(Consumer<? super V> action) {
if (action == null)throw new NullPointerException();int mc = modCount;// 遍历for (LinkedHashMapEntry<K,V> e = head; (e != null && modCount == mc); e = e.after)action.accept(e.value);//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 if (modCount != mc)throw new ConcurrentModificationException();}}//所有条目集合public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;}//自定义条目结合final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() {
return size; }public final void clear() {
LinkedHashMap.this.clear(); }//这里的迭代器也是LinkedHashMap自定义的迭代器public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();}public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Node<K,V> candidate = getNode(hash(key), key);return candidate != null && candidate.equals(e);}public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;Object key = e.getKey();Object value = e.getValue();return removeNode(hash(key), key, value, true, true) != null;}return false;}public final Spliterator<Map.Entry<K,V>> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |Spliterator.ORDERED |Spliterator.DISTINCT);}//遍历public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMapEntry<K,V> e = head; (e != null && mc == modCount); e = e.after)action.accept(e);//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 if (modCount != mc)throw new ConcurrentModificationException();}}// Map overridespublic void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)action.accept(e.key, e.value);//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 if (modCount != mc)throw new ConcurrentModificationException();}public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
if (function == null)throw new NullPointerException();int mc = modCount;for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)e.value = function.apply(e.key, e.value);//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)，抛出异常 if (modCount != mc)throw new ConcurrentModificationException();}//自定义迭代器abstract class LinkedHashIterator {
//声明next节点LinkedHashMapEntry<K,V> next;//声明当前节点LinkedHashMapEntry<K,V> current;//预期修改次数//该变量用于判断当前迭代器在迭代的时候是否被修改过(例如put, remove方法)//若迭代时被改过，那么expectedModCount != modCount，抛出异常int expectedModCount;LinkedHashIterator() {
next = head; //从双向链表头节点开始expectedModCount = modCount; //expectedModCount为当前总的修改次数current = null; //还没开始，当前节点为null}//是否还有下一个节点public final boolean hasNext() {
return next != null;}//寻找下一个节点final LinkedHashMapEntry<K,V> nextNode() {
//声明当前节点LinkedHashMapEntry<K,V> e = next;//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)if (modCount != expectedModCount)throw new ConcurrentModificationException();//当前节点为null，抛出异常 if (e == null)throw new NoSuchElementException();//当前节点赋值current = e;//next赋值next = e.after;return e;}//移除当前节点public final void remove() {
//声明当前节点Node<K,V> p = current;if (p == null)throw new IllegalStateException();//证明迭代的时候LinkedHashMap被修改过(例如put, remove方法)if (modCount != expectedModCount)throw new ConcurrentModificationException();//当前节点赋值为nullcurrent = null;//删除节点K key = p.key;removeNode(hash(key), key, null, false, false);//删除节点后重新赋值修改次数expectedModCount = modCount;}}//key的迭代器final class LinkedKeyIterator extends LinkedHashIteratorimplements Iterator<K> {
public final K next() {
return nextNode().getKey(); }}//value的迭代器final class LinkedValueIterator extends LinkedHashIteratorimplements Iterator<V> {
public final V next() {
return nextNode().value; }}//Entry的迭代器final class LinkedEntryIterator extends LinkedHashIteratorimplements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() {
return nextNode(); }}
}