Java集合之LinkedHashMap详解

时间:2022-03-22 18:02:17

简介

LinkedHashMap继承自HashMap,与HashMap有着类似的存储结构,LinkedHashMap类声明如下:

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

它继承于HashMap,实现了Map接口。

LinkedHashMap是非线程安全的,只是用于单线程环境下。

LinkedHashMap与HashMap的核心结构都相同,但是HashMap是无序的,即我们通过迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。而有时,我们却希望使用一个能够保持插入顺序的Map,LinkedHashMap就是为此设计的。

LinkedHashMap源码详解

LinkedHashMap是基于数组+双向链表+红黑树来实现的,其整体结构类似于下图:

Java集合之LinkedHashMap详解

因为LinkedHashMap继承自HashMap,故常用属性和HashMap都一样,比如具有相同的默认容量以及负载因子等属性。LinkedHashMap中的节点默认都被封装成为了Entry类型数据,它是LinkedHashMap对应的链表节点,Entry类继承自HashMap的Node类:

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节点,LinkedHashMap的Entry节点多了before和after两个属性,其中Entry节点的next属性用于维护HashMap各个桶中的Entry链,before和after属性则用于维护LinkedHashMap的双向链表。

上图中,实线即为next指针,虚线即为before和after指针,如果没有虚线的话,则上图是一个正常的HashMap结构,加上虚线,即增加了一个双向链表,head和tail分别为双向链表的首尾节点。

LinkedHashMap还增加了几个成员变量:

// 双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;

// 双向链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;

// 双向链表中元素排序规则的标志位
// accessOrder为false,表示按插入顺序排序
// accessOrder为true,表示按访问顺序排序
final boolean accessOrder;

根据accessOrder的值,LinkedHashMap可以实现LRU算法,若accessOrder为true,则表示按entry的访问顺序进行排序,此时,最新访问的entry将会被修改到双向链表的尾部。

LinkedHashMap具有五个构造方法:

// 参数指定了HashMap初始化时的容量以及负载因子,accessOrder默认为false,即按照节点的插入顺序排序
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 参数指定了HashMap初始化时的容量,负载因子使用默认负载因子0.75,accessOrder默认为false,即按照节点的插入顺序排序
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

// 无参构造方法,默认的初始化容量为16,负载因子为默认的0.75,accessOrder默认为false,即按照节点的插入顺序排序
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 根据其他Map来创建HashMap,负载因子为0.75,accessOrder默认为false,即按照节点的插入顺序排序
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

// 参数指定了HashMap初始化时的容量、负载因子以及accessOrder
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

我们下面来看LinkedHashMap的几个关键方法:put方法、get方法和remove方法。

put(K key, V value)方法

LinkedHashMap并没有重写HashMap的put(K key, V value)方法,HashMap的该方法实际上是调用了putVal方法:

// onlyIfAbsent为true时,则不覆盖key对应的value值,但是put在调用这个方法时,赋值为false,说明会覆盖原始value
// evict为false时,table处于创建模式,put在调用这个方法时,赋值为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;
    // table为null或者table长度为0,则通过resize方法来初始化table,其中,n为数组的长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash是计算出的节点在数组中的下标,若数组对应下标为null,则直接将节点赋值到tab[i]
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 若数组对应下标不为null,则表明发生了哈希冲突,其中,p为table[i]中的第一个节点
    else {
        Node<K,V> e; K k;
        // 如果p节点与插入节点的hash和key相同,则e = p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 否则,判断p节点是否为TreeNode,即判断链表是否已经调整为红黑树,若是的话,则通过putTreeVal来添加红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 否则,p为链表节点
        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;
                }
                // 如果插入节点和原链表中的某个key具有相同的hash且key相同,则停止查找
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e != null表明哈希表中已经存在键为key的节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 若允许覆盖value值,或旧值为null,则更新key所对应的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // HashMap结构修改次数加1
    ++modCount;
    // 若节点个数 > threshold,则对table进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

虽然LinkedHashMap没有重写HashMap的put方法和putVal方法,但是LinkedHashMap修改了newNode方法,来将原来的Node节点替换为Entry节点,并维护了节点的顺序:

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 创建新增节点,该节点不再是Node类型,而是Entry类型
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // 将新节点链接到链表尾部
    linkNodeLast(p);
    return p;
}

创建节点后,会调用linkNodeLast(LinkedHashMap.Entry<K,V>)方法将新节点链接到链表尾部:

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 获取双向链表的尾节点
    LinkedHashMap.Entry<K,V> last = tail;
    // 将新节点p设置为尾节点
    tail = p;
    // 若之前的双向链表为空,则初始化双向链表的头结点head
    if (last == null)
        head = p;
    // 否则,将新节点p链接到双向链表尾部
    else {
        p.before = last;
        last.after = p;
    }
}

每次put到LinkedHashMap中的Entry都放在双向链表尾部,这样遍历双向链表时,Entry的输出顺序就会和插入的顺序一致,这也是默认的双向链表的存储顺序。

同样,LinkedHashMap重写了HashMap中定义的afterNodeAccess、afterNodeInsertion两个方法,在HashMap中这两个方法的实现都为空,其实还有一个afterNodeRemoval方法:

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

若哈希表中不存在要插入的key对应的节点,则在新节点插入之后,putVal会调用afterNodeInsertion方法;若key对应的节点已经存在,则putVal会调用afterNodeAccess方法,我们来看一下LinkedHashMap对这两个方法的实现:

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 如果evict为true、双向链表头结点不为null,且removeEldestEntry返回true,则删除首节点
    // LinkedHashMap中的removeEldestEntry方法一直返回false,即不会删除节点
    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;
}

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 若accessOrder为true,且双向链表尾结点不为e,则将e置为双向链表的尾节点
    if (accessOrder && (last = tail) != e) {
        // 将e强制转换为Entry节点p,b为p的前驱节点,a为p的后继节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 将p的后继节点置为null,因为p要成为尾节点,尾节点是没有后继节点的
        p.after = null;
        // 如果p的前驱节点是null,即p以前是头结点head,所以现在要将头结点置为p的后继节点a
        if (b == null)
            head = a;
        // 否则,直接b的后继节点设置为p的后继节点a
        else
            b.after = a;
        // 如果p的后继节点a不是null,则直接将a的前驱节点置为b
        if (a != null)
            a.before = b;
        // 否则,p的后置节点是null,即p就是尾节点,此时将last置为b
        else
            last = b;
        // 如果双向链表尾节点是null,则链表中就一个节点,将head置为p
        if (last == null)
            head = p;
        // 否则,将p的前驱节点置为last,将last的后继节点置为p
        else {
            p.before = last;
            last.after = p;
        }
        // 将尾节点置为p
        tail = p;
        ++modCount;
    }
}

这两个方法是用来实现的实现LRU算法的。我们可以重写removeEldestEntry方法,来自动移除过期的节点,若双向链表按插入顺序排序,则删除最早插入双向链表的节点;若双向链表按访问顺序排序,则为删除最近最少访问的节点,这两种节点在不同的排序方式下都是首节点。

put方法的主要内容我们也就介绍到这,下面看get方法。

get(Object key)方法

LinkedHashMap重写了get(Object key)方法:

public V get(Object key) {
    Node<K,V> e;
    // 调用getNode方法获取对应节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

get(Object key)方法首先会通过getNode方法来获取key相应的节点,LinkedHashMap没有重写getNode方法,所以,getNode方法采用了HashMap的实现:

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table不为null且长度不为0,且存在哈希值为hash的节点,first为对应下标的首节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 总是先检查first节点是否符合条件,若符合,则直接返回first节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 否则,若首节点存在后继节点
        if ((e = first.next) != null) {
            // 若首节点是TreeNode类型节点,则从红黑树中查找节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 从链表中查找节点
            do {
                // 若找到符合条件的节点,则直接返回节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 否则返回null
    return null;
}

在获取到节点之后,若节点为null,则直接返回null,否则,根据accessOrder来判断是否调用afterNodeAccess方法,然后返回节点的value。

remove(Object key)方法

LinkedHashMap同样没有重写remove(Object key)方法,LinkedHashMap使用HashMap的默认实现来删除节点:

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
// matchValue如果为true,则表示删除一个node的条件是:key和value都一致才删除
// movable如果为false,则表示删除当前节点时,不会移动其它节点
final Node<K,V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // table不为null且长度不为0,且存在哈希值为hash的节点,p为对应下标的首节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 总是先检查首节点p是否符合条件,若符合,则node = p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 否则,若首节点存在后继节点
        else if ((e = p.next) != null) {
            // 若首节点是TreeNode类型节点,则从红黑树中查找节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 从链表中查找节点
            else {
                do {
                    // 若找到符合条件的节点,则node = e,退出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // 更新p
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 如果找到指定key与哈希值的node,且保证了删除策略matchValue,则可以删除
        if (node != null && (!matchValue || (v = node.value) == value ||
                                (value != null && value.equals(v)))) {
            // node为红黑树节点,则调用红黑树节点删除方法
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 否则,node节点是链表节点,若node == p,p为node的前驱节点,则说明node为首节点,直接更新数组对应下标的首节点
            else if (node == p)
                tab[index] = node.next;
            // 否则,更新p.next = node.next,删除node节点
            else
                p.next = node.next;
            // HashMap结构修改次数加1
            ++modCount;
            // 元素个数减1
            --size;
            afterNodeRemoval(node);
            // 返回删除节点
            return node;
        }
    }
    // 返回null
    return null;
}

但LinkedHashMap重写了afterNodeRemoval方法,在删除节点之后,会调用该方法:

void afterNodeRemoval(Node<K,V> e) { // unlink
    // 将e强制转换为Entry节点p,b为p的前驱节点,a为p的后继节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将p的前驱节点和后继节点都置为null
    p.before = p.after = null;
    // 如果b为null,即p为头结点,那么现在的头结点应该是p的后继节点a
    if (b == null)
        head = a;
    // 否则将b的后继节点置为a
    else
        b.after = a;
    // 如果a为null,即p为尾结点,那么现在的尾结点应该是p的前驱节点b
    if (a == null)
        tail = b;
    // 否则将a的前驱节点置为b
    else
        a.before = b;
}

该方法就是将节点删除时,同步将该节点从双向链表上删除。

LinkedHashMap其他相关方法

和HashMap一样,LinkedHashMap的key和value都可以为null,要判断一个key在LinkedHashMap中是否存在,是不可以用get(Object)方法来判断的,我们可以用containsKey(Object)方法来判断,LinkedHashMap没有重写该方法,采用了HashMap的实现方式:

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

containsValue(Object value)方法

LinkedHashMap重写了containsValue(Object value)方法:

public boolean containsValue(Object value) {
    // 遍历双向链表
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        // 若找到匹配的节点,则直接返回true
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    // 返回false
    return false;
}

LinkedHashMap重写的containsValue(Object value)方法要比HashMap的containsValue(Object value)方法效率高一点,HashMap查找value时用了两个for循环,即使数组中的某一下标没有对应的链表,也要去查找,而LinkedHashMap查找value时,是通过双向链表来查找的,链表中的每一个节点都是有效地,而不用再去查找整个哈希表。

那为什么LinkedHashMap没有重写containsKey(Object)方法呢?

因为HashMap的containsKey(Object)方法已经很高效了,HashMap的containsKey(Object)方法是通过getNode方法来完成的,getNode方法会去key对应的数组链表中去查找,其节点个数可能远远小于双向链表的节点个数,所以LinkedHashMap采用HashMap实现的containsKey(Object)方法就可以了。

clear()方法

public void clear() {
    // 调用HashMap的clear()方法
    super.clear();
    // 将双向链表的头尾节点置为null
    head = tail = null;
}

利用LinkedHashMap实现LRU算法

从上面的源码中,我们知道,根据accessOrder的值,LinkedHashMap可以实现LRU算法,若accessOrder为true,则表示按entry的访问顺序进行排序,此时,最新访问的entry将会被修改到双向链表的尾部。下面我们来看一个例子:

public class LinkedHashMapTest {
	static class LRUCache<K, V> extends LinkedHashMap<K, V> {
		private static final long serialVersionUID = -2856190955107642776L;
		private int maxSize;
		
		public LRUCache(int maxSize) {
			super(maxSize, 0.75f, true);
			this.maxSize = maxSize;
		}
		
		@Override
		protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
			return size() > maxSize;
		}
	}

	public static void main(String[] args) {
		LRUCache<Integer, Integer> lCache = new LRUCache<>(3);
		
		lCache.put(1, null);
		lCache.put(2, null);
		lCache.put(3, null);
		printEntry(lCache);
		
		lCache.put(4, null);
		printEntry(lCache);
		
		lCache.put(1, null);
		printEntry(lCache);
		
		lCache.put(4, null);
		printEntry(lCache);
		
		lCache.put(2, null);
		printEntry(lCache);
		
		lCache.put(5, null);
		printEntry(lCache);
	}
	
	private static void printEntry(LRUCache<Integer, Integer> lCache) {
		Set<Entry<Integer,Integer>> entrySet = lCache.entrySet();
		String s = "";
		
		for (Entry<Integer,Integer> entry : entrySet) {
			s += entry.getKey() + " ";
		}
		
		System.out.println(s);
		System.out.println("------");
	}
}

运行结果:

1 2 3 
------
2 3 4 
------
3 4 1 
------
3 1 4 
------
1 4 2 
------
4 2 5 
------

我们通过继承LinkedHashMap的方式来实现了LRU算法,我们除了要指定accessOrder为true之外,还要重写removeEldestEntry方法,在LinkedHashMap中,该方法一直返回false,我们需要做的就是,判断什么时候需要将最近最少访问的节点删除,我们这里实现的是如果节点数目已经达到了指定个数,那就删除最近最少访问的节点,这个指定个数是通过LRUCache的构造方法指定的。

相关博客

Java集合之ArrayList详解

Java集合之HashMap详解