环境和版本
- Mac M1
- IDEA 2021
-
简介
众所周知，HashMap提供的访问是无序的。而在一些业务场景下，希望提供有序访问的HashMap，那么此时就有2种选择
- TreeMap：安装Key的顺序
- LinkedHashMap：按照Key的插入和访问顺序
- LinkedHashMap，在HashMap的基础上，提供了顺序访问的特性，这里的顺序包括2种
- 按照 key-value 的插入顺序进行访问。关于这一点，相信大多数人都知道
- 按照 key-value 的访问顺序进行访问。通过这个特性，我们实现基于 LRU 算法的缓存。
- LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。
- 事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(doubly-linked list)的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图，主体部分跟HashMap完全一样，多了header指向双向链表的头部(是一个哑元)，该双向链表的迭代顺序就是entry的插入顺序
- 除了可以保迭代历顺序，这种结构还有一个好处 : 迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关
- 有两个参数可以影响LinkedHashMap的性能: 初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数
- 将对象放入到LinkedHashMap或LinkedHashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到LinkedHashMap或LinkedHashSet中，需要@Override hashCode()和equals()方法
属性
```java static class Entry
} }super(hash, key, value, next);
// 头节点
transient LinkedHashMap.Entry
// 尾节点
transient LinkedHashMap.Entry
// 是否按照访问的顺序。 // true ：按照 key-value 的访问顺序进行访问。 // false ：按照 key-value 的插入顺序进行访问。 final boolean accessOrder;
// HashMap的Node节点
transient Node
- head + tail 属性，形成LinkedHashMap的双向链表，而访问的顺序，就是 head => tail
- accessOrder属性，决定了LinkedHashMap的顺序
- true：当Entry节点被访问的时候，放置到链表的尾部，被tail指向
- false：当Entry被添加的的时候，放置到链表的尾部，被tail指向。如果插入的Key对应的Entry已经存在，也会被放到结尾
<a name="X4CvP"></a>
# 构造方法
```java
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;
}
put方法
// put 方法调用父类 HashMap的put方法。然后在本类重写了 newNode 方法
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) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
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;
}
newNode方法
// 子类的node节点
// hash: hash
// key: key
// value: value
// e: 当前node节点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 创建Entry
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 将P元素添加到末尾
linkNodeLast(p);
return p;
}
// 将P元素添加到末尾
// 这样，越是最新的元素，则放在末尾
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// last = tail
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
// 如果last == null
// 说明没有元素 设置为头节点
if (last == null)
head = p;
else {
// 否则 p的前一个节点是last
// last的后一个节点是p
// 此时将链表连接起来
p.before = last;
last.after = p;
}
}
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;
}
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;
}
节点操作回调-afterNodeAccess
// 节点读取回调
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// accessOrder 判断必须是满足按访问顺序
// 判断 e 是否是队尾，如果是，则无需在访问了
// 这里是为了更新，相当于是个LRU算法
if (accessOrder && (last = tail) != e) {
// 将 e 赋值给 p
// b a 分别是e的前驱节点、后置节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将p从链表中移除
p.after = null;
// 处理b的下一个子节点指向a
// 如果e的前一个节点b == null，说明e是第一个节点
// 此时，将头节点设置为e的后一个节点
if (b == null)
head = a;
else
// 否则，b的后一个节点设置为a
b.after = a;
// 如果e的后置节点a不为null，
// 将a的前一个节点指向b
// 这样，a、b就连接起来了，e已经剔除出去了
if (a != null)
a.before = b;
else
// 否则 b就是最后一个节点
last = b;
// 如果 last 还是为null - 此时说明当前是第一次添加节点
if (last == null)
// 将 p 设置给head
head = p;
else {
// 否则连接p的前一个为last节点
// last的后一个节点为p
// 将p加入到最后一个节点
p.before = last;
last.after = p;
}
// p执行最后一个节点
// 为尾节点
tail = p;
++modCount;
}
}
基于LinkedHashMap实现的LUR缓存
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int CACHE_SIZE;
/**
* 传递进来最多能缓存多少数据
*
* @param cacheSize 缓存大小
*/
public LRUCache(int cacheSize) {
// true 表示让 LinkedHashMap 按照访问顺序来进行排序，最近访问的放在头部，最老访问的放在尾部。
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当 map 中的数据量大于指定的缓存个数的时候，就自动删除最老的数据。
return size() > CACHE_SIZE;
}
}
节点操作回调-afterNodeInsertion
// 插入后回调 - 在 putVal
// evict 翻译为驱逐，表示是否允许移除元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
// 头节点
LinkedHashMap.Entry<K,V> first;
// head 为头节点
// emoveEldestEntry(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;
}
节点操作回调-afterNodeRemoval
// 在移除节点的时候，还要维护 双向链表
// 解除去掉的节点的数据
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;
}
转换为集合
public Set<K> keySet() {
// 获得 keySet 缓存
Set<K> ks = keySet;
if (ks == null) {
// LinkedKeySet 是 LinkedHashMap 自定义的
ks = new LinkedKeySet();
keySet = ks;
}
return 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();
}
}
// 获取值
public Collection<V> values() {
// 获得 values 缓存
Collection<V> vs = values;
// 不存则就那些创建
if (vs == null) {
// LinkedValues 是 LinkedHashMap 自定义的
vs = new LinkedValues();
values = vs;
}
return 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();
}
}
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(); }
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 (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
// 上述的 LinkedKeyIterator、LinkedValueIterator、LinkedEntryIterator 都继承了
// LinkedHashIterator 分别用于迭代 Key、Value、Entry
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;
}
}
clear方法
public void clear() {
// 清空
super.clear();
// 标记 head 和 tail 为 null
head = tail = null;
}
序列化和反序列化
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);
}
}
void reinitialize() {
super.reinitialize();
head = tail = null;
}
containsValue查找值
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;
}
总结
- LinkedHashMap 是 HashMap 的子类，增加了顺序访问的特性
- [默认] 当 accessOrder = false 时，按照 key-value 的插入顺序进行访问
- 当 accessOrder = true 时，按照 key-value 的读取顺序[谁读了，谁就更新到tail]进行访问
- LinkedHashMap 的顺序特性，通过内部的双向链表实现，所以我们把它看成是 LinkedList + LinkedHashMap 的组合
- LinkedHashMap 通过重写 HashMap 提供的回调方法，从而实现其对顺序的特性的处理。同时，因为 LinkedHashMap 的顺序特性，需要重写 #keysToArray(T[] a) 等遍历相关的方法
- LinkedHashMap 可以方便实现 LRU 算法的缓存
LinkedHashMap 的本质就是套娃，其在HashMap上包了一层 Entry，然后然后形成双向链表
参考文章
LinkedHashMap：https://www.pdai.tech/md/java/collection/java-map-LinkedHashMap&LinkedHashSet.html
- Java-Review：https://gitee.com/icanci/Java-Review
若有收获，就点个赞吧
0 人点赞
