美文网首页
Java1.8-LinkedHashMap源码分析

Java1.8-LinkedHashMap源码分析

作者: 骑着乌龟去看海 | 来源:发表于2018-01-14 11:06 被阅读60次

概述

  API文档中介绍,LinkedHashMap是基于Hash表和链表来实现的一种数据结构,并且依靠着双向链表保证了插入数据的顺序。

LinkedHashMap继承自HashMap,有着和HashMap一样的数据结构,即数组+链表+红黑树+双向链表,LinkedHashMap会将所有插入的节点连接成一个双向链表,因此它可以保证数据的插入顺序。

继承关系
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

  由于LinkedHashMap继承自HashMap,所以HashMap中除了私有的方法与属性,其他的都可以在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);
    }
}

/**
 * 链表头节点
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 链表尾节点
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 控制访问顺序
 */
final boolean accessOrder;
方法
put方法

LinkedHashMap的put方法并没有重写,而是直接使用HashMap的put方法,而是重写了put方法中回调的afterNodeAccess和afterNodeInsertion方法。

/**
 * 节点访问之后,也就是说put之后就相当于访问节点了,这时候就
 * 更新双向链表,将最近访问的节点放到最后,保证链表的顺序
 */
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果访问顺序为true,并且访问的不是尾节点
    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;
    }
}
/**
 * 如果设置了evict属性,也就是移除的规则,就执行相应的移除操作
 */
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);
    }
}
get方法
/**
 * 这里就用到了accessOrder,如果accessOrder是true,将该节点移到链表尾部
 */
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;
}

  上面这些方法,其实就是LinkedHashMap为了维护双向链表中的节点顺序所做的事情。

其中,要注意一下属性:accessOrder。通过设置该属性为true或者false,我们可以控制双向链表是按照访问顺序排列还是按照插入顺序排列。

我们通过一个小例子简单看一下该属性的应用:

public static void main(String[] args) {
    Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put("A", 1);
    linkedHashMap.put("B", 2);
    linkedHashMap.put("C", 3);
    System.out.println(linkedHashMap);
    
    // 通过调用LinkedHashMap的构造方法,设置accessOrder的值
    Map<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
    map.put("A", 1);
    map.put("B", 2);
    map.put("C", 3);
    map.get("A");
    System.out.println(map);
}

打印结果:

{A=1, B=2, C=3}
{B=2, C=3, A=1}

  其实,LinkedHashMap比较简单,说白了就是在原先HashMap的基础上再加一个双向链表,维护数据的顺序而已。LinkedHashMap中的大部分方法就是为了维护这个顺序。

相关文章

网友评论

      本文标题:Java1.8-LinkedHashMap源码分析

      本文链接:https://www.haomeiwen.com/subject/xxckoxtx.html