LinkedHashMap源码浅析（一）：集合的基本操作
LinkedHashMap继承了HashMap，所以HashMap的一些方法或者属性也会被继承；同时也实现了Map结构,
LinkedHashMap数据结构相比较于HashMap来,添加了双向指针,分别指向前一个节点——before和后一个节点——after
LinkedHashMap的迭代器为遍历节点提供了自己的实现——LinkedHashIterator，对于Key、Value、Entry的3个迭代器
具有访问顺序和插入顺序两种
插入元素,调用的是HashMap的put(),添加成功之后,重写了newNode()方法,将插入成功的元素插入到双向链表当中
删除元素,同样调用的是HashMap的remove(),删除成功之后,重写了afterNodeRemoval(),将删除的元素从双向链表中剔除,
获取指定元素,获取成功之后,如果设置的linkedhashMap的顺序是访问顺序,则将获取成功的元素插入到双向链表的链尾
lru缓存 最近最少原则
LinkedHashMap继承于HashMap,在HashMap的基础上(主要是数组和链表的结构基础上)其内部还维护了一个双向链表,在每次插入数据或者访问数据、修改数据时,会跳转链表的节点顺序,以此来决定迭代时输入的顺序
// 因为是继承了HashMap,所以构造方法里面调用了HashMap的构造方法,入参同HashMap一样,初始容量和加载因子
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);
}
// 前面我们说过,LinkedHashMap相对于HashMap是有序的,或插入顺序或访问顺序,而选择那种顺序的标识就是accessOrder,默认为false(插入顺序)
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
put
LinkedHashMap并没有重写put(),所以添加数据的时候用的是HashMap的put(),不过重写的是创建节点的方法newNode(),在创建头结点或者添加尾节点时会用到这个方法，统一的说就是创建新节点的时候会用到:
LinkedHashMap#newNode()
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;
}
因为LinkedHashMap中使用的节点是LinkedHashMapEntry,所以这里重写也在情理之中,但是前面有说过LinkedHashMap是有顺序的,所以这里面肯定是有排序的逻辑的:
LinkedHashMap#linkNodeLast():
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
LinkedHashMapEntry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
首先将新创建的节点指向尾节点,这个没有问题,LinkedHashMap本身就是双链表,新节点加入链表是要加入尾节点的,然后判断原先的尾节点是否为空,如果为空的话,则说明当前节点为头结点,所以,你懂得,将新建的节点再次指向头结点,如果插入的节点非头结点,就会走下面的else,然后完成两个节点的相互关联。
因为LinkedHashMapEntry代码比较简单,这里就一并说了,LinkedHashMapEntry继承于HashMap,并且拥有两个成员变量before和after用于维护双链表
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
在HashMap的putVal()中的倒是第二行代码：
HashMap#putVal():
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
// 代码省略
...
afterNodeInsertion(evict);
return null;
}
这里调用了afterNodeInsertion()，但是这个方法在HashMap中是个空方法,而在LinkedHashMap才重写实现这个方法
HashMap#afterNodeInsertion():
void afterNodeInsertion():(boolean evict) { }
LinkedHashMap#afterNodeInsertion():
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMapEntry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
afterNodeInsertion方法的evict参数如果为false，表示哈希表处于创建模式。只有在使用Map集合作为构造器创建LinkedHashMap或HashMap时才会为false,这是第一个条件,第二个条件则是,集合不能为空，第三个条件是removeEldestEntry()的返回值。
LinkedHashMap#removeEldestEntry():
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
此方法在LinkedHashMap中的实现默认返回false，所以这个判断体一般进不来,如果为true的话,我们可以看到通过removeNode()删除了头结点,头结点有两种意义,一种是插入顺序下的头结点,此时的头结点作为集合中最先插入的元素,同时也是集合中最老的元素,删除头结点代表删除集合中最老的元素,结合调用此方法的情景是在添加新元素之后,因为使用这个方法的场景就呼之欲出了,集合添加了新元素,但是由于某种原因,不得不删除集合中的最老的元素；另一种意义就是访问顺序下的头结点,此时的头结点代表刚刚被访问过的的元素,删除头结点代表删除刚刚访问过的元素,个人觉得这种情况下的删除头结点相对于上一种情况毫无道理可言。当然第一种的情况适合在构建缓存时使用,添加新元素,因为空间不够了，所以需要移除集合中最老的元素,但是这个方法是在添加完元素之后才被调用的,所以只能确定要被添加的元素的大小,并且保证一定能被添加进去,这个方法才能被调用到,所以现在的这个方法并不特别是实用.
在HashMap中的putVal中还有一个方法afterNodeAccess()，在HashMap中依旧是空实现,LinkedHashMap中实现这个方法，这个方法跟访问顺序有关系会在下一张中进行介绍,这里就不多说了
get
获取数据用的是自己的方法():
LinkedHashMap#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;
}
如果能够根据key值获取到节点,则直接返回,如果该节点为null,则返回null,如果需要对链表进行访问排序,则调用afterNodeAccess(),关于排序我会单独来说这里就不多说了。
remove
LinkedHashMap没有重写remove方法,也没有重写removeNode(),不过在HashMap中的removeNode()的最后,会调用afterNodeRemoval(),这个方法是够空方法
HashMap#afterNodeRemoval():
void afterNodeRemoval(Node<K,V> p) { }
不过这个方法在LinkedHashMap中进行了重写:
LinkedHashMap#afterNodeRemoval():
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<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;
}
afterNodeRemoval()在LinkedHashMap的作用是使要删除的节点脱离双链表,虽然在HashMap中进行了处理,但只是脱离了HashMap的单链表或者红黑树,LinkedHashMap中的双链表则需要单独的实现,
这个方法其实也很简单,主要是获取到要删除节点的前后节点,然后使这两个节点相互关联
迭代器
LinkedHashMap中的迭代器与HashMap一样有三种,但是确实跟HashMap中的迭代器没有关系
LinkedKeySet
size当前集合的元素数量
iterator得到一个迭代器
remove()删除当前遍历到的节点
LinkedHashMap#LinkedKeySet#iterator()
public final Iterator<K> iterator() {
return new LinkedKeyIterator();
}
LinkedKeyIterator继承于LinkedHashIterator
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
LinkedHashIterator的属性:
next当前节点的下一节点
current当前节点
expectedModCount修改次数
方法:
hasNext()是否具有下一节点
nextNode()获取下一节点
remove删除当前节点
我们先看构造器:
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
首先初始化next赋值为头结点,
final LinkedHashMapEntry<K,V> nextNode() {
LinkedHashMapEntry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
每次调用此方法都会返回原先的next节点,然后更新next节点为after节点.
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;
}
直接通过removeNode进行删除,双链表的脱离在上面已经说过了,
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(); }
}
相等的还有另外两个迭代器,逻辑一样 ,代码如上
