Java中LinkedHashMap源码解析

时间:2021-05-20

概述:

LinkedHashMap实现Map继承HashMap,基于Map的哈希表和链该列表实现,具有可预知的迭代顺序。

LinedHashMap维护着一个运行于所有条目的双重链表结构,该链表定义了迭代顺序,可以是插入或者访问顺序。

LintHashMap的节点对象继承HashMap的节点对象,并增加了前后指针 before after:

/** * LinkedHashMap节点对象 */ 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); } }

lintHashMap初始化:

accessOrder,简单说就是这个用来控制元素的顺序,
accessOrder为true: 表示按照访问的顺序来,也就是谁最先访问,就排在第一位
accessOrder为false表示按照存放顺序来,就是你put元素的时候的顺序。

public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } /** * 生成一个空的LinkedHashMap,并指定其容量大小,负载因子使用默认的0.75, * accessOrder为false表示按照存放顺序来,就是你put元素的时候的顺序 * accessOrder为true: 表示按照访问的顺序来,也就是谁最先访问,就排在第一位 */ public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } /** * 生成一个空的HashMap,容量大小使用默认值16,负载因子使用默认值0.75 * 默认将accessOrder设为false,按插入顺序排序. */ public LinkedHashMap() { super(); accessOrder = false; } /** * 根据指定的map生成一个新的HashMap,负载因子使用默认值,初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY) * 默认将accessOrder设为false,按插入顺序排序. */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; putMapEntries(m, false); } /** * 生成一个空的LinkedHashMap,并指定其容量大小和负载因子, * 默认将accessOrder设为true,按访问顺序排序 */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }

putMapEntries(m,false)调用父类HashMap的方法,继而根据HashMap的put来实现数据的插入:

/** * Implements Map.putAll and Map constructor * * @param m the map * @param evict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { if (table == null) { // pre-size float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) threshold = tableSizeFor(t); } else if (s > threshold) resize(); for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }

存储:

put调用的HashMap的put方法,调用两个空方法,由LinkedHashMap实现

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; }

在hashmap中红色部分为空实现:

void afterNodeAccess(Node<K,V> p) { } void afterNodeInsertion(boolean evict) { }

然后看下LinkedHashMap怎么实现这两方法:

将当前节点e移动到双向链表的尾部。每次LinkedHashMap中有元素被访问时,就会按照访问先后来排序,先访问的在双向链表中靠前,越后访问的越接近尾部。当然只有当accessOrder为true时,才会执行这个操作。

void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; // 若访问顺序为true,且访问的对象不是尾结点 if (accessOrder && (last = tail) != e) { // 向下转型,记录p的前后结点 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p的后结点为空 p.after = null; // 如果p的前结点为空 if (b == null) // a为头结点 head = a; else // p的前结点不为空 // b的后结点为a b.after = a; // p的后结点不为空 if (a != null) // a的前结点为b a.before = b; else // p的后结点为空 // 后结点为最后一个结点 last = b; // 若最后一个结点为空 if (last == null) // 头结点为p head = p; else { // p链入最后一个结点后面 p.before = last; last.after = p; } // 尾结点为p tail = p; // 增加结构性修改数量 ++modCount; } }

afterNodeInsertion方法 evict为true时删除双向链表的头节点

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); } }

删除操作调用HashMap的remove方法实现元素删除,remove调用removeNode,而removeNode有一个方法需要LinkedHashMap来实现:

将e节点从双向链表中删除,更改e前后节点引用关系,使之重新连成完整的双向链表。

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; }

读取:

e不为空,则获取e的value值并返回。

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; }

accessOrder为true,也就是说按照访问顺序获取内容。

void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; // 若访问顺序为true,且访问的对象不是尾结点 if (accessOrder && (last = tail) != e) { // 向下转型,记录p的前后结点 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p的后结点为空 p.after = null; // 如果p的前结点为空 if (b == null) // a为头结点 head = a; else // p的前结点不为空 // b的后结点为a b.after = a; // p的后结点不为空 if (a != null) // a的前结点为b a.before = b; else // p的后结点为空 // 后结点为最后一个结点 last = b; // 若最后一个结点为空 if (last == null) // 头结点为p head = p; else { // p链入最后一个结点后面 p.before = last; last.after = p; } // 尾结点为p tail = p; // 增加结构性修改数量 ++modCount; } }

LinkedHashMap的几个迭代器:

抽象类LinkedHashIterator 实现具体删除,判断是否存在下个结点,迭代的逻辑。

LinkedKeyIterator 继承自LinkedHashIterator,实现了Iterator接口,对LinkedHashMap中的key进行迭代。
LinkedValueIterator 继承自LinkedHashIterator,实现了Iterator接口,对LinkedHashMap中的Value进行迭代
LinkedEntryIterator 继承自LinkedHashIterator,实现了Iterator接口,对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(); //结点为null NoSuchElementException if (e == null) throw new NoSuchElementException(); //不为null,赋值当前节点 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(); } }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章