LinkedHashMap继承自HashMap
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
它的数据结构与HashMap的类似，数组+链表+红黑树，不同的是LinkedHashMap的节点
Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
多了两个指针，before与after，LinkedHashMap就是利用这两个指针来实现顺序性，这个顺序可以指插入时的顺序：before代表之前于你的节点，after代表之后；也可以代表LRU：此时最新被改动的节点(新插入的，节点value被替换的，被get访问的）将在末尾，头节点代表最少被改动访问的节点，所以LinkedHashMap可用来实现LRUCache。
Entry继承图
在分析HashMap源码时，发现
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>，为什么不直接继承Node，而且在相关方法中也没有用到Entry的before与after指针？因为LinkedHashMap也要使用TreeNode，利用linkNodeLast来调整TreeNode的before与after指针
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);
linkNodeLast(p);
return p;
}
成员变量与构造函数
头节点
transient LinkedHashMap.Entry<K,V> head;
尾节点
transient LinkedHashMap.Entry<K,V> tail;
true代表LRU顺序；false代表插入顺序
final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
可以看到前四个构造器accessOrder都为false，也就是保持插入顺序；最后一个提供了设置accessOrder值的机会。LinkedHashMap的构造函数基本上是调用HashMap的，加上accessOrder的设置。
插入操作
LinkedHashMap并没有put方法，插入操作交给了HashMap，通过重写newNode方法来插入自己的节点，并对before与after进行操作
LinkedHashMap重写的newNode方法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
newNode方法再HashMap创建新节点时被调用。
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
无论是插入顺序还是LRU顺序，新插入的节点都将被放在末尾。
在HashMap的putVal方法末尾有这两个判断
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
第一段代码：意思是如果e不为null，代表key重复新value值替换了旧值，afterNodeAccess(e)被调用，该方法在HashMap中为空，在LinkedHashMap实现，作用就是对accessOrder为true情况下将该节点调到末尾，因为它被改动了。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
将e节点的前一个节点b与后一个节点a连在一起，将e调到末尾。LRU顺序下，末尾节点代表着最新的节点，意思是要么是新插入的，被更改的，被get访问到的。
第二段代码：插入新节点后，对于LinkedHashMap来说要进行afterNodeInsertion操作，作用是判断是否要删除head节点。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
关于evict
HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
在HashMap的put方法里，调用putVal传的是true，那么决定是否删除head节点的操作就取决于removeEldestEntry方法，其在LinkedHashMap的实现返回的是false，也就是不执行删除头节点的操作。那么这个默认返回false的removeEldestEntry意义在哪？当你要实现LRUCache时可以重写该方法，实现自己的逻辑，例如当节点数查过最大值就删除访问最少的节点。
get
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;
}
具体实现在HashMap的getNode方法里，可以看到若是LRU顺序，则被访问的节点会被放入到末尾。
remove
具体操作仍然在HashMap里实现，同putVal一样，留了一个钩子
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
................
afterNodeRemoval(node);
................
来看看
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
就是将该节点的前后连在一起，链表的删除操作。
迭代器
Iterator
主要是LinkedHashIterator
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
各自实现自己的next()方法。
网友评论