Map 是 Java collection framework 中重要的组成部分, 特别是 HashMap 是在我们在日常的开发的过程中使用的最多的一个集合. 但是遗憾的是, 存放在 HashMap 中元素都是无序的, 原因是我们在 put 或 get 数据的时候都是根据 key 的 hash 值来确定元素的位置. 在具体的业务场景中, 我们更多的希望对于 HashMap 集合能够进行顺序访问, 好在 jdk 中已经给我们提供了一种解决方案, 那就是 LinkedHashMap. 该类继承与 HashMap, 因此 HashMap 拥有的特性它都有, 同时还具备其他的特性, 比如实现了插入顺序排序和访问顺序排序, 默认以插入顺序排序. 同时也能够利用 LinkedHashMap 实现 LRU 算法. LinkedHashMap API 很少, 基本都是调用 HashMap 的方法, 所以建议熟悉 HashMap 源码之后再来看这篇文章, 我之前也写过 [HashMap 源码分析笔记] , 大家可以点进去参考一下.
LRU 算法: LRU 是 Least Recently Used 的缩写, 即最近最少使用, 也就是说将热点数据放到最前面, 冷门数据放到最后, 当达到一定条件后会删除冷门数据, 在一个缓存系统中经常会用到该算法.
一, LinkedHashMap 与 HashMap 数据结构对比
从上图可以看到 HashMap 的数据结构位数组 + 单向链表, 数据存放在链表的 node 节点上, 每个 node 节点上都有一个指针指向下一个节点, 每个数组 index 上的链表跟其他的 index 上面的链表是部相互链接的. LinkedHashMap 在部破坏 HashMap 的结构基础之上, 每个 node 节点都额外增加了两个指针, 分别指向了前一个节点和下一个节点, 所以在 HashMap 上所有的 node 节点形成了一条双向链表, 每次添加往 LinkedHashMap put 数据的时候都将节点放在双向链表的最后位置, 从而实现了插入顺序排序. 在 LinkedHashMap 中, 节点的定义如下:
- /**
- * HashMap.Node subclass for normal LinkedHashMap entries.
- */
- 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);
- }
- }
节点继承与 HashMap 的 Node 内部类, 但是又额外添加了两个属性, before 和 after, 分别指向前一个节点和后一个节点, 形成一个双向链表.
二, LinkedHashMap 类结构
- public class LinkedHashMap<K,V>
- extends HashMap<K,V>
- implements Map<K,V>
- {
- .......
- }
LinkedHashMap 继承了 HashMap, 所以拥有 HashMap 的所有特性.
三, 成员变量
- /**
- * The head (eldest) of the doubly linked list.
- */
- transient LinkedHashMap.Entry<K,V> head;
- /**
- * The tail (youngest) of the doubly linked list.
- */
- transient LinkedHashMap.Entry<K,V> tail;
- /**
- * The iteration ordering method for this linked hash map: <tt>true</tt>
- * for access-order, <tt>false</tt> for insertion-order.
- *
- * @serial
- */
- final boolean accessOrder;
LinkedHashMap 在 HashMap 的基础之上添加了 head,tail 和 accessOrder 属性:
head: 双向链表的表头
tail: 双向链表的表尾
accessOrder: 排序的标志. 默认为 false, 按插入顺序排序. 可以通过构造方法设置为 true, 按访问顺序排序.
四, 构造方法
- /**
- * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
- * with the specified initial capacity and load factor.
- *
- * @param initialCapacity the initial capacity
- * @param loadFactor the load factor
- * @throws IllegalArgumentException if the initial capacity is negative
- * or the load factor is nonpositive
- */
- public LinkedHashMap(int initialCapacity, float loadFactor) {
- super(initialCapacity, loadFactor);
- accessOrder = false;
- }
- /**
- * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
- * with the specified initial capacity and a default load factor (0.75).
- *
- * @param initialCapacity the initial capacity
- * @throws IllegalArgumentException if the initial capacity is negative
- */
- public LinkedHashMap(int initialCapacity) {
- super(initialCapacity);
- accessOrder = false;
- }
- /**
- * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
- * with the default initial capacity (16) and load factor (0.75).
- */
- public LinkedHashMap() {
- super();
- accessOrder = false;
- }
- /**
- * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
- * the same mappings as the specified map. The <tt>LinkedHashMap</tt>
- * instance is created with a default load factor (0.75) and an initial
- * capacity sufficient to hold the mappings in the specified map.
- *
- * @param m the map whose mappings are to be placed in this map
- * @throws NullPointerException if the specified map is null
- */
- public LinkedHashMap(Map<? extends K, ? extends V> m) {
- super();
- accessOrder = false;
- putMapEntries(m, false);
- }
- /**
- * Constructs an empty <tt>LinkedHashMap</tt> instance with the
- * specified initial capacity, load factor and ordering mode.
- *
- * @param initialCapacity the initial capacity
- * @param loadFactor the load factor
- * @param accessOrder the ordering mode - <tt>true</tt> for
- * access-order, <tt>false</tt> for insertion-order
- * @throws IllegalArgumentException if the initial capacity is negative
- * or the load factor is nonpositive
- */
- public LinkedHashMap(int initialCapacity,
- float loadFactor,
- boolean accessOrder) {
- super(initialCapacity, loadFactor);
- this.accessOrder = accessOrder;
- }
5 个构造方法都是直接调用父类 HashMap 的构造方法.
五, 添加数据 put(Object key,V value)
LinkedHashMap 中并没有对 HashMap 进行复写, 也就是说添加数据的时候其实就是调用的 HashMap 的 put 方法, 那么它是怎么进行排序的呢? 下面我们一起来看看 HashMap 中是怎么添加数据的吧.
- 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;
- /**
- * 通过位与的方式来确定下标位置, 判断当前下标位置是否为空, 如果为空直接放入到该位置上
- * 不为空则通过 equals 方法来寻找当前位置上面的元素, 如果有相同的 key, 则将覆盖掉, 如果没有则将 node 放置在对应
- * 位置上面
- */
- 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))))// 已存在相同的 key 的数据, 将其覆盖
- e = p;
- else if (p instanceof TreeNode)// 当前位置是红黑树, 将 Node 节点放到红黑树中
- 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))))// 覆盖相同 key 的 node
- break;
- p = e;
- }
- }
- //map 中已经存在了相同的 key, 将原来的数据替换掉
- 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 插入数据的核心方法为 putVal 方法, 每次插入数据都调用 newNode 方法, 这个方法 LinkedHashMap 中已经重写了:
- 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;
- }
第一: 因为已经重写了父类的 newNode 方法, 所以在插入数据时创建新节点实际是调用了 LinkedHashMap 的 newNode 方法, 该方法中每次创建新节点都想 LinkedHashMap 自身维护的双向链表的尾部添加一个当前新创节点, 我们继续看看 linkNodeLast 方法:
- private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
- LinkedHashMap.Entry<K,V> last = tail;
- tail = p;
- if (last == null)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- }
这个方法很简单, 如果链表为空则将新节点设置为头部和尾部, 否则将新节点放到链表的最后, 将新节点的前指针指向原尾部的节点, 原尾部节点的后指针指向新节点. 如果不明白具体的插入流程, 可参考我之前的 [ArrayList 源码阅读笔记] , 里面有详细插入各个位置的流程.
第二: 创建新节点完成后, 将新节点放入对象的链表或树中, 如果新节点的 key 在 HashMap 中已经存在, 那么就会原来的 value 覆盖掉, 此时被视为修改了节点, 调用 afterNodeAccess(e) 方法, LinkedHashMap 对这个方法进行了重写, 我们看一下源码:
- /**
- * 每次访问节点后将该节点放在最后
- * @param e
- */
- void afterNodeAccess(Node<K,V> e) { // move node to last
- LinkedHashMap.Entry<K,V> 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)
- head = p;
- else {
- p.before = last;
- last.after = p;
- }
- tail = p;
- ++modCount;
- }
- }
该方法中, 如果 accessOrder 为 true 并且访问节点不为空, 那么就会将访问过的节点移动到最后. 这也就是实现了 LRU 算法, 具体移动路程如下:
第三: 插入数据全部完成之后, 执行 afterNodeInsertion(evict) 方法, evict 为 true,LinkedHashMap 重写的该方法:
- 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);
- }
- }
- protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
- return false;
- }
afterNodeInsertion 方法是用来删除最旧最少使用的数据, 上面提到过, 每次访问, 修改 map 中的数据的时候都会将该节点放在链表的最后面, 因此约靠前的数据使用的频率的越低, 我们称之为冷数据, 该方法就是将最冷门的数据删除掉. removeEldestEntry 方法默认返回 false, 所以 LinkedHashMap 本身并不提供 LRU 算法, 需要自己手动实现 LinkedHashMap, 然后重写 removeEldestEntry 方法, 根据自己具体的业务决定何时删除冷数据.
总结: 这里只总结 LinkedHashMap 实现部分. 在 put 数据的时候, LinkedHashMap 不仅将数据放在 HashMap 中, 同时也将该数据放在自己维护的双向链表的最后, 以实现顺序排序. 如果 put 进去的数据的 key 已经存在与 Map 中, 则将该数据移动到链表的最后位置. 插入数据完成后, 根据子类具体实现情况是否将第一个数据删除.
六, 获取数据 get(key)
- /**
- * Returns the value to which the specified key is mapped,
- * or {@code null} if this map contains no mapping for the key.
- *
- * <p>More formally, if this map contains a mapping from a key
- * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
- * key.equals(k))}, then this method returns {@code v}; otherwise
- * it returns {@code null}. (There can be at most one such mapping.)
- *
- * <p>A return value of {@code null} does not <i>necessarily</i>
- * indicate that the map contains no mapping for the key; it's also
- * possible that the map explicitly maps the key to {@code null}.
- * The {@link #containsKey containsKey} operation may be used to
- * distinguish these two cases.
- */
- 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, 即按访问顺序排序, 那个每次都将该数据放到链表的最后面.
七, 其他方法
LinkedHashMap 本身的方法比较少, 而且大部分都是调用父类的方法, 所以在这里就不说了, 可以看看 HashMap 的源码.
八, 总结
LinkedHashMap 继承与 HashMap, 因此它有 HashMap 一样的特性. 同时也弥补了 HashMap 无法顺序遍历的缺点. LinkedHashMap 可以实现插入顺序排序 (默认排序), 也可以根据访问顺序排序, 也就是访问的元素次数越多, 该元素就越靠前. 实现顺序遍历的底层原理是, LinkedHashMap 自身维护了一张双向链表, 为此插入, 访问或修改数据的时候都将该节点放在链表最后面. 按默认排序方式的话, 在遍历的时候就从表头开始遍历, 按访问顺序排序就从链表表尾开始遍历. 另外, LinkedHashMap 也可以用来搭建一个缓存系统底层存储结构, 后面如果我有空的话, 可能也会手写一个简单的缓存 demo. 最后, 如果文章有什么写的不对的地方, 欢迎大家提出来
来源: https://www.cnblogs.com/rainple/p/9953596.html