一、LinkedHashMap的属性
二、LinkedHashMap的构造方法
三、LinkedHashMap的重要函数
1. afterNodeAccess函数
2. afterNodeInsertion函数
3. afterNodeRemoval函数
4. transferLinks函数
5. linkNodeLast函数
6. 其他方法
四、LinkedHashMap的迭代器
1. 基础迭代器--LinkedHashIterator
2. 键迭代器--LinkedKeyIterator
3. 值迭代器--LinkedValueIterator
4. 结点迭代器--LinkedEntryIterator
LinkedHashMap<K,V>继承HashMap<K,V>类，实现了 Map<K,V>接口。
LinkedHashMap是HashMap的子类，与HashMap有着同样的存储结构，但它加入了一个双向链表的头结点，将所有put到LinkedHashmap的节点一一串成了一个双向循环链表，因此它保留了节点插入的顺序，可以使节点的输出顺序与输入顺序相同。
LinkedHashMap可以用来实现LRU算法（这会在下面的源码中进行分析）。
LinkedHashMap同样是非线程安全的，只在单线程环境下使用。
1. LinkedHashMap的属性
/**
* 静态内部类Entry表示双向链表，继承自HashMap的Node，在其基础上加上了before和after两个指针
* 双向循环链表的头结点，整个LinkedHashMap中只有一个header
* 它将哈希表中所有的Entry贯穿起来，header中不保存key-value对，只保存前后节点的引用
*/
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);
}
}
- private static final long serialVersionUID = 3801124242820219131L;
序列化 - transient LinkedHashMap.Entry<K,V> head;
链表头结点 - transient LinkedHashMap.Entry<K,V> tail;
链表尾结点 - final boolean accessOrder;
双向链表中元素排序规则的标志位；
false：表示按插入顺序排序；true：表示按访问顺序排序
2. LinkedHashMap的构造方法
2.1 LinkedHashMap(int, float)型构造函数
/**
* 总是会在构造函数的第一行调用父类构造函数，使用super关键字，
* accessOrder默认为false，access为true表示之后访问顺序按照元素的访问顺序进行
* 即不按照之前的插入顺序了，access为false表示按照插入顺序访问。
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
2.2 LinkedHashMap(int)型构造函数
/**
* 加载因子取默认的0.75f
*/ public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
2.3 LinkedHashMap()型构造函数
/**
* 加载因子取默认的0.75f，容量取默认的16
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
2.4 LinkedHashMap(Map<? extends K, ? extends V>)型构造函数
/**
* putMapEntries是调用到父类HashMap的构造函数
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
2.5 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)型构造函数
/**
* 可以指定accessOrder的值，从而控制访问顺序
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
3. LinkedHashMap的重要函数
- afterNodeAccess、afterNodeInsertion、afterNodeRemoval这三个方法都是重写父类HashMap的方法。
3.1 afterNodeAccess函数
/**
* 把当前节点e放到双向链表尾部
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
/* accessOrder就是我们前面说的LRU控制，当它为true，同时e对象不是尾节点
（如果访问尾节点就不需要设置，该方法就是把节点放置到尾节点）
*/
if (accessOrder && (last = tail) != e) {
// 用a和b分别记录该节点前面和后面的节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 释放当前节点与后节点的关系
p.after = null;
// 如果当前节点的前节点是空
if (b == null)
// 那么头节点就设置为a
head = a;
else
// 如果b不为null，那么b的后节点指向a
b.after = a;
// 如果a节点不为空
if (a != null)
// a的后节点指向b
a.before = b;
else
// 如果a为空，那么b就是尾节点
last = b;
// 如果尾节点为空
if (last == null)
// 那么p为头节点
head = p;
else {
// 否则就把p放到双向链表最尾处
p.before = last;
last.after = p;
}
// 设置尾节点为P
tail = p;
// LinkedHashMap对象操作次数+1
++modCount;
}
}
此函数在很多函数（如put）中都会被回调，LinkedHashMap重写了HashMap中的此函数。若访问顺序为true，且访问的对象不是尾结点
访问结点3的前后状态
从图中可以看到，结点3链接到了尾结点后面
LinkedHashMap重写了HashMap的get方法：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder) // 如果启用了LRU规则
afterNodeAccess(e); // 那么把该节点移到双向链表最后面
return e.value;
}
- 注： LinkedHashMap压根没有重写put方法，每次用LinkedHashMap的put方法的时候，其实你调用的都是HashMap的put方法。但它也会执行afterNodeAccess()方法，因为这个方法HashMap就是存在的，但是没有实现，LinkedHashMap重写了afterNodeAccess()这个方法。
3.2 afterNodeInsertion函数
/**
* 在哈希表中插入了一个新节点时调用的，它会把链表的头节点删除掉，删除的方式是通过调用HashMap的removeNode方法
*/
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);
}
}
3.3 afterNodeRemoval函数
/**
* 当HashMap删除一个键值对时调用的，它会把在HashMap中删除的那个键值对一并从链表中删除，保证了哈希表和链表的一致性。
*/
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);
}
}
3.4 transferLinks函数
/**
* 用dst替换src
*/
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
使用结点7替换结点3
3.5 linkNodeLast函数
在看linkNodeLast函数之前先看看newNode和newTreeNode这两个函数
3.5.1 newNode函数
/**
* 当桶中结点类型为HashMap.Node类型时，调用此函数
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 生成Node结点
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 将该结点插入双链表末尾
linkNodeLast(p);
return p;
}
3.5.2 newTreeNode函数
/**
* 当桶中结点类型为HashMap.TreeNode时，调用此函数
*/
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
// 生成TreeNode结点
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
// 将该结点插入双链表末尾
linkNodeLast(p);
return p;
}
3.5.3 linkNodeLast函数
/**
* 把新加的节点放在链表的最后面
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 将tail给临时变量last
LinkedHashMap.Entry<K,V> last = tail;
// 把new的Entry给tail
tail = p;
// 若没有last，说明p是第一个节点，head=p
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
3.6 其他方法
- internalWriteEntries方法
/**
* 该方法也是重写父类HashMap的方法，也是为了LinkedHashMap键和值被序列化的存储顺序
*/
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
其他方法就不一一介绍的官方API中都有详细的说明。
4. LinkedHashMap的迭代器
4.1基础迭代器--LinkedHashIterator
为抽象类，用于对LinkedHashMap进行迭代
/**
* LinkedHashIterator是LinkedHashMap的迭代器，为抽象类，用于对LinkedHashMap进行迭代
*/
abstract class LinkedHashIterator {
// 下一个结点
LinkedHashMap.Entry<K,V> next;
// 当前结点
LinkedHashMap.Entry<K,V> current;
// 期望的修改次数
int expectedModCount;
LinkedHashIterator() {
// next赋值为头结点
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;
}
}
4.2 键迭代器--LinkedKeyIterator
继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的键进行迭代
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
4.3 值迭代器--LinkedValueIterator
继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的值进行迭代
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
4.4 结点迭代器--LinkedEntryIterator
继承自LinkedHashIterator，实现了Iterator接口，对LinkedHashMap中的结点进行迭代
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
网友评论