Java知识总结

LinkedHashSet & LinkHashMap详解

Mr.LR2022年3月13日
大约 3 分钟

LinkedHashSet & LinkHashMap详解

基本介绍

LinkedHashSet和LinkedHashMap在Java里也有着相同的实现，前者仅仅是对后者做了一层包装，也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap。

事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(doubly-linked list)的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。

在LinkedHastMap中维护了一个hash表和双向链表(LinkedHashMap有head和tail)

每一个节点有before和after属性，这样可以形成双向链表，在添加一个元素时，先求hash值，在求索引，确定该元素在table的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加，原则和HashMap一样)。 这样的话，我们遍历LinkedHashMap也能确保插入顺序和遍历顺序一致

LinkedHashMap是线程不安全的

方法剖析

get()操作

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样。

put()操作

插入有两重含义:

  1. 从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
  2. 从header的角度看，新的entry需要插入到双向链表的尾部。

LinkedHashMap_addEntry.png

具体逻辑

  1. LinkedHashMap没有重写HashMap的put方法，所以执行put操作的时候，还是使用的是HashMap的put方法。
  2. 通过对HashMap一些方法的覆盖,例如newNode, replacementNode, replacementTreeNode, newTreeNode，让所有对底层HashMap数据结构修改的同时，维护双链表。

image-20220922145417871

remove()

删除也有两重含义:

从table的角度看，需要将该entry从对应的bucket里删除，如果对应的冲突链表不空，需要修改冲突链表的相应引用。

从header的角度来看，需要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。

image-20220922150856340

具体操作

  1. 和put操作一样，也是直接使用HashMap的方法来完成的：
  2. 重写了HashMap的afterNodeRemoval维护链表

image-20220922151248695

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法，因此LinkedHashSet的实现非常简单

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ......
    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
	......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

LinkedHashMap经典用法

基于按访问顺序存储的方式实现LRU

public class LRUDemo<K, V> extends LinkedHashMap<K, V> {
    private int capacity;
    //当LinkedHashMap的accessOrder参数为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
    public LRUDemo(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > capacity;
    }

}

参考