LinkedHashMap

1、概述

签名:

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{

}

LinkedHashMap是HashMap的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap。

LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。注意,此实现不是同步的。如果多个线程同时访问链接的哈希映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步。

根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用get方法)的链表。

默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。 可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素;

对于LinkedHashMap而言,它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似,它通过重写父类相关的方法,来实现自己的链接列表特性

2、LinkedHashMap链表结构

其在HashMap的基础上增加了如下属性:

// 链表头
transient LinkedHashMap.Entry<K,V> head;
// 链表尾
transient LinkedHashMap.Entry<K,V> tail;
// 继承 Node,为数组的每个元素增加了 before 和 after 属性
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);
    }
}
// 控制两种访问模式的字段,默认false;true按照访问顺序,会把经常访问的 key 放到队尾;false按照插入顺序提供访问
final boolean accessOrder;

3、如何按照顺序新增

LinkeHashMap初始化时,默认 accessOrder 为false,是按照插入顺序提供访问

public LinkedHashMap() {
    super();
    accessOrder = false;
}

插入方法是使用的是父类的put方法,不过重写了 put方法调用执行的newNode\newTreeNode 和 afterNodeAccess 方法:

// 新增节点,并追加到链表的尾部
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;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    // 新增节点等于位节点
    tail = p;
    // last 为空,说明链表为空,首尾节点相等
    if (last == null)
        head = p;
    // 链表有数据,直接建立新增节点和上个尾节点之间的前后关系即可
    else {
        p.before = last;
        last.after = p;
    }
}

LinkedHashMap 通过新增头节点、尾节点,给每个节点增加 before、after 属性,每次新增时,都把节点追加到尾节点等手段,在新增的时候,就已经维护了按照插入顺序的链表结构了。

4、按照顺序访问

LinkedHashMap只提供单向访问,即按照插入的顺序从头到尾访问,不能像LinkedList那样可以双向访问;

访问主要是通过迭代器进行访问,迭代器初始化时,默认从头结点开始访问,在迭代过程中,不断访问当前节点的after节点即可;

Map 对 key、value 和 entity(节点) 都提供出了迭代的方法,假设我们需要迭代 entity,就可使用 LinkedHashMap.entrySet().iterator() 这种写法直接返回 LinkedHashIterator ,LinkedHashIterator 是迭代器,我们调用迭代器的 nextNode 方法就可以得到下一个节点,迭代器的源码如下:

// 初始化时,默认从头节点开始访问
LinkedHashIterator() {
    // 头节点作为第一个访问的节点
    next = head;
    expectedModCount = modCount;
    current = 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; // 通过链表的 after 结构,找到下一个迭代的节点
    return e;
}

5、访问最少删除策略(LRU)

5.1、如何实现

重写 removeEldestEntry方法即可

// 新建 LinkedHashMap
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4,0.75f,true) {
    {
      put(10, 10);
      put(9, 9);
      put(20, 20);
      put(1, 1);
    }
    @Override
    // 覆写了删除策略的方法,我们设定当节点个数大于 3 时,就开始删除头节点
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
      return size() > 3;
    }
};

当我们调用 map.get(9) 方法时,元素 9 移动到队尾,调用 map.get(20) 方法时, 元素 20 被移动到队尾,这个体现了经常被访问的节点会被移动到队尾。

5.2、get时为什么元素会放到队尾

public V get(Object key) {
    Node<K,V> e;
    // 调用 HashMap  get 方法
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果设置了 LRU 策略
    if (accessOrder)
    // 这个方法把当前 key 移动到队尾
        afterNodeAccess(e);
    return e.value;
}

从上述源码中,可以看到,如果 accessOrder 为true的话通过 afterNodeAccess 方法把当前访问节点移动到了队尾,其实不仅仅是 get 方法,执行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法时,也会这么做,通过不断的把经常访问的节点移动到队尾,那么靠近队头的节点,自然就是很少被访问的元素了。

5.3、删除策略

在执行 put 方法时,发现队头元素被删除了,LinkedHashMap 本身是没有 put 方法实现的,调用的是 HashMap 的 put 方法,但 LinkedHashMap 实现了 put 方法中的调用 afterNodeInsertion 方法,这个方式实现了删除,我们看下源码:

// 删除很少被访问的元素,被 HashMap 的 put 方法所调用
void afterNodeInsertion(boolean evict) { 
    // 得到元素头节点
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry 来控制删除策略,如果队列不为空,并且删除策略允许删除的情况下,删除头节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // removeNode 删除头节点
        removeNode(hash(key), key, null, false, true);
    }
}
  • http://www.cnblogs.com/children/archive/2012/10/02/2710624.html
  • http://www.tuicool.com/articles/IRBNB3v
  • LRU算法:http://woming66.iteye.com/blog/1284326
  • LRU算法:http://tomyz0223.iteye.com/blog/1035686
LinkedHashMapLinkedHashMap 码农阳神 发布了41 篇原创文章 · 获赞 6 · 访问量 1364 私信 关注
上一篇:javascript-如何从onchange获得价值?


下一篇:剑指Offer-54.字符流中第一个不重复的字符(C++/Java)