一、概述
- LinkedHashMap是HashMap的子类，一些基本方法LinkedHashMap都没有实现，所以集合-HashMap解析这篇文章是必读的。
- 它是HashMap的子类，所以底层数据结构是和HashMap完全相同的，只是新增了一个双向链表来维护插入顺序，这个链表在增加、修改、删除数据是会维护链表的顺序，Android中则是采用的双向循环链表，但是不提供双向循环的API。
- 它也是线程不安全的，允许key为null，value为null
- 关于数据遍历时顺序有两种方式，一种是插入顺序，一种是访问顺序。使用了accessOrder来控制是使用哪种顺序。accessOrder默认为false来表示插入顺序，如果设置为true，那么在使用get方法时，会修改链表中最后访问元素的顺序。
二、构造函数和节点信息
2.1 构造函数
相比于HashMap的构造函数，就多了一个accessOrder参数及相关的构造函数
Java
基本上都是调用了HashMap的相关构造函数，然后设置数据的最终遍历顺序。
transient LinkedHashMap.Entry<K,V> head;//头结点
transient LinkedHashMap.Entry<K,V> tail;//尾节点
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;//使用自定义的顺序
}
Android
transient LinkedEntry<K, V> header;//节点信息，类似于在LinkedList中voidLink
private final boolean accessOrder;//数据的遍历顺序，默认是插入顺序
public LinkedHashMap() {
init();
accessOrder = false;//默认值
}
public LinkedHashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用下一个构造函数
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, false);//调用下一个构造函数
}
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);//调用父类的构造方法
init();//初始化
this.accessOrder = accessOrder;//设置数据遍历顺序
}
public LinkedHashMap(Map<? extends K, ? extends V> map) {
this(capacityForInitSize(map.size()));//调用第二个构造函数
constructorPutAll(map);//参考父类具体方法
}
@Override
void init() {
header = new LinkedEntry<K, V>();//初始化header节点
}
2.2 节点信息
Java
另有HashMap中TreeNode继承了该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);
}
}
Android
static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
LinkedEntry<K, V> nxt;//后节点
LinkedEntry<K, V> prv;//前节点
/** Create the header entry */
LinkedEntry() {//专用于创建Header使用
super(null, null, 0, null);
nxt = prv = this;
}
/** Create a normal entry *///创建一个普通的键值对使用
LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
super(key, value, hash, next);
this.nxt = nxt;
this.prv = prv;
}
}
三、增加条目
Java
在新增一个节点，并将该节点放置在链表的尾部
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;
}
//创建一个新的树节点，并将树节点放在链表的末尾，树节点是节点子类
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;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)//表示链表为空
head = p;
else {//不为空，将p的前节点设为原尾节点，将原尾节点后节点设为p
p.before = last;
last.after = p;
}
}
//插入后修改
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//evict大多数情况都是true，默认put方法也是使用的true
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
//移除最老的方法，这个方法默认返回false，但是可以被覆盖
//如果覆盖可以设置在身份情况下删除最老的节点信息
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
Android
//添加节点
@Override
void addNewEntry(K key, V value, int hash, int index) {
LinkedEntry<K, V> header = this.header;//void头结点
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;//最老节点
//removeEldestEntry，是否需要一次最老的节点
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;//老的尾部
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);//新的尾部节点
//在HashMap哈希桶中链表头部添加数据
//在LinkedHashMap中链表尾部添加新的尾部
//将void的前节点设置为新的尾节点
table[index] = oldTail.nxt = header.prv = newTail;
}
//添加空节点
@Override
void addNewEntryForNullKey(V value) {
LinkedEntry<K, V> header = this.header;//头结点
// Remove eldest entry if instructed to do so.
LinkedEntry<K, V> eldest = header.nxt;//最老的节点
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// Create new entry, link it on to list, and put it into table
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
null, value, 0, null, header, oldTail);
//空节点，指向了新创建的尾节点
entryForNullKey = oldTail.nxt = header.prv = newTail;
}
四、删除条目
在节点(条目)删除后，修复链表的相关关系
Java
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;//将p与链表的前后管理关系移除
if (b == null)//如果前节点为空，表示删除节点是头结点
head = a;//将头结点指向删除节点的后节点
else//如果前节点不为空，将前节点后节点指向删除节点的后节点
b.after = a;
if (a == null)//如果后节点为空，表示删除的节点是尾节点
tail = b;//将尾节点指向删除节点的前节点
else//如果后节点不为空，将后节点的前节点置为删除节点的前节点
a.before = b;
}
Android
@Override
void postRemove(HashMapEntry<K, V> e) {
LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
//不存在le.prv和le.nxt为空的情况，因为有header。
le.prv.nxt = le.nxt;//修复链接关系
le.nxt.prv = le.prv;//修复链接关系
le.nxt = le.prv = null; // Help the GC (for performance)
}
五、修改条目
Java
替换条目后，会调用afterNodeAccess这个访问后修改方法，因为修改也算是访问的一种
重写了父类的replaceAll方法，因为使用链表全遍历比HashTable遍历效果更好
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
if (function == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
e.value = function.apply(e.key, e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
Android
虽然没有Replace相关的API，但是有预修改
这个API也是判断是否是访问顺序
@Override
void preModify(HashMapEntry<K, V> e) {
if (accessOrder) {
makeTail((LinkedEntry<K, V>) e);
}
}
六、查询条目
Java
查询后，判断遍历顺序，然后决定是否移动最新访问的节点到尾部
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;
}
//获取带有默认值的节点
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;
}
//节点访问后
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;//最后的节点
//将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)//如果last==null，表示尾节点为空或者刚访问的节点为空，此时将头结点指向p即可，这种情况一般不会发生，因为空链表才会出这种情况，为了保证不出异常，才如此做。
head = p;
else {//将p放置到最后访问的尾部
p.before = last;
last.after = p;
}
tail = p;//将尾部设为p
++modCount;//增加修改次数
}
}
Android
重写了get方法，加入了遍历顺序是访问顺序情况下，修改链表的情况
@Override
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
private void makeTail(LinkedEntry<K, V> e) {
// Unlink e，将e从链表中移除
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// Relink e as tail，将e链接到链表中
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
七、包含元素
因为containsValue有可能需要遍历整个哈希桶，所以使用链表遍历更方便、快捷、高效
Java
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<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;
}
Android
@Override
public boolean containsValue(Object value) {
if (value == null) {
for (LinkedEntry<K, V> header = this.header, e = header.nxt;
e != header; e = e.nxt) {
if (e.value == null) {
return true;
}
}
return false;
}
// value is non-null
for (LinkedEntry<K, V> header = this.header, e = header.nxt;
e != header; e = e.nxt) {
if (value.equals(e.value)) {
return true;
}
}
return false;
}
八、遍历
关于Map的遍历都是使用相应的迭代器进行相应的遍历
迭代器优化过，不在使用哈希桶的迭代器，因为哈希桶的迭代方式太复杂了。
而采用链表的迭代器方法，更加的高效
在Java中通过重写entrySet()等相关方法来实现新的迭代器
在Android中则是通过直接重写构造迭代器的方法实现迭代器的重构，但是原理相似
8.1 键值对迭代器
Java
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; }//返回Map的Size
public final void clear() { LinkedHashMap.this.clear(); }//清空
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);
}
//lambda循环使用
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
Android
@Override
Iterator<Map.Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
private final class EntryIterator
extends LinkedHashIterator<Map.Entry<K, V>> {
public final Map.Entry<K, V> next() { return nextEntry(); }
}
8.2 Key迭代器
和键值对迭代器相似
Java
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new LinkedKeySet()) : ks;
}
final class LinkedKeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
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 (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.key);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
Android
private final class KeyIterator extends LinkedHashIterator<K> {
public final K next() { return nextEntry().key; }
}
@Override Iterator<K> newKeyIterator() {
return new KeyIterator();
}
8.3 值迭代器
Java
public Collection<V> values() {
Collection<V> vs;
return (vs = values) == null ? (values = new LinkedValues()) : vs;
}
final class LinkedValues extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
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 (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
Android
private final class ValueIterator extends LinkedHashIterator<V> {
public final V next() { return nextEntry().value; }
}
@Override Iterator<V> newValueIterator() {
return new ValueIterator();
}
8.4 公共方法
采用链表的方式来迭代器数据，相比迭代哈希桶，这样更加高效
Java
//抽象的hash迭代器，返回的LinkedHashMap的键值对对象
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;
}
}
Android
链表的迭代器
private abstract class LinkedHashIterator<T> implements Iterator<T> {
LinkedEntry<K, V> next = header.nxt;
LinkedEntry<K, V> lastReturned = null;
int expectedModCount = modCount;
public final boolean hasNext() {
return next != header;
}
final LinkedEntry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedEntry<K, V> e = next;
if (e == header)
throw new NoSuchElementException();
next = e.nxt;
return lastReturned = e;
}
public final void remove() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (lastReturned == null)
throw new IllegalStateException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
}
九、总结
- 相比于HashMap增加了链表来存储数据的顺序，这个顺序用于遍历
- 数据的顺序有两种：插入顺序和访问顺序
- 相对来说优化了遍历功能，毕竟链表的迭代效率高于哈希桶的。
- 关于链表的维护，则是在每次插入数据、删除数据、修改数据和查询数据后判断是否进行数据的修改。如果数据需要移动(插入、修改、查询)一般移动(插入、修改、查询)到末尾。
- 关于contains相关的方法，只重写了containsValue方法，因为这个方法在HashMap中需要遍历整个哈希桶，遍历的效率比较低。containsKey方法则是使用哈希值进行定位的，查找起来如果hash值的算法比较高效的话，查找效率是优于整个hash表的遍历的。
其他文章
容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析
