close

Mr.Muzi

一只很安静的monkey

Java Map 04 - LinkedHashMap

字数统计: 3.8k 阅读时长: 16 mins • 分类: 源码阅读 • 标签: JDK 1.7, Java集合

  关于 java.util.LinkedHashMap<K, V> 的部分笔记，LinkedHashMap是HashMap的扩展，底层依赖数组+双向链表的形式完成了元素的存储和查找，并且该实现返回的元素是有序的。本文演示代码段的执行环境基于JDK版本1.7。

概述

  LinkedHashMap是一个可预先确定键值对遍历顺序的map集合实现。直接继承于HashMap，但是和HashMap不同的是，LinkedHashMap底层多了一个双向链表来链接所有的键值对实体对象。于是乎， LinkedHashMap的元素迭代顺序是由双向链表决定和维护的，而双向链表的顺序也反映了键值对被加入集合时的顺序，所以也可以理解成元素的插入顺序。如果向LinkedHashMap集合中插入一个已经存在的键值对，那么其在集合中的顺序不会因此而改变。

  LinkedHashMap提供了一个特殊的构造方法：

1
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

该方法决定了元素的遍历顺序，因此该构造方法可以被用于LRU算法中。如果accessOrder被定义为true，那么在迭代时将不会按照插入顺序来遍历访问，而是按照访问顺序来遍历迭代。访问顺序的特点是最近访问的元素会最后被遍历到。这个构造方法在LRU相关实现中有用，就LinkedHashMap本身而言，用途不是特别大。

  LinkedHashMap提供的removeEldestEntry(Entry eldest)方法可以被子类覆盖，以便更好的实现移除最旧的键值对实体。除此之外，LinkedHashMap提供并实现了Map接口声明的所有方法，也允许null的加入。和HashMap一样，LinkedHashMap保证了插入，是否存在判断和移除操作可以在常量时间内完成。

  和HashMap一样，LinkedHashMap的性能影响因子也是两个参数：initialCapacity和loadFactor。但是initialCapacity对LinkedHashMap的查询/遍历性能影响小于HashMap，因为LinkedHashMap底层存在一个双向链表，该双向链表链接了map集合中的所有元素，所以迭代器在遍历时不会与数组进行交互而是直接遍历双向链表中的键值对实体，所以initialCapacity对LinkedHashMap无影响。

  LinkedHashMap是一个非线程安全的实现类。所以如果需要在多线程环境中使用LinkedHashMap，需要付诸额外的操作来保证多线程环境下的线程安全特性。一个常用的执行方式如下：

1
Map m = Collections.synchronizedMap(new LinkedHashMap(...));

  LinkedHashMap同样支持快速失败检查，但是并不保证可以一定捕捉到快速失败检查。

  LinkedHashMap的底层数据结构关系如图1所示：

图 - 1
 

 

继承关系

1
2
3
4
5
// LinkedHashMap<E>
--java.lang.Object
  --java.util.AbstractMap<K,V>
    --java.util.HashMap<K,V>
      --java.util.LinkedHashMap<K,V>

 

实现接口

类名 实现接口
LinkedHashMap<E> Serializable, Cloneable,Map<K,V>

 

LinkedHashMap

Constructor Summary

public LinkedHashMap(int initialCapacity, float loadFactor)

1
2
3
4
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

  初始化一个空HashMap集合，集合的初始容量和加载因子由initialCapacity和loadFactor确认。调用父类HashMap的同名构造方法完成初始化操作。通过当前构造方法得到的map集合按照键值对实体插入顺序进行访问。

public LinkedHashMap(int initialCapacity)

1
2
3
4
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

  初始化一个空HashMap集合，集合的初始容量由initialCapacity和确认，加载因子默认为0.75。调用父类HashMap的同名构造方法完成初始化操作。通过当前构造方法得到的map集合按照键值对实体插入顺序进行访问。

public LinkedHashMap()

1
2
3
4
public LinkedHashMap() {
    super();
    accessOrder = false;
}

  初始化一个空HashMap集合，集合的初始容量默认为16，加载因子默认为0.75。调用父类HashMap的同名构造方法完成初始化操作。通过当前构造方法得到的map集合按照键值对实体插入顺序进行访问。

public LinkedHashMap(Map<? extends K, ? extends V> m)

1
2
3
4
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}

  初始化一个空HashMap集合，并将m中的键值对保存到初始化的map中。在初始化过程中，集合的容量大小由m存储的键值对数量决定，保证空map集合可以将m中的键值对全部存储下来，且默认加载因子是0.75。调用父类HashMap的同名构造方法完成初始化操作。通过当前构造方法得到的map集合按照键值对实体插入顺序进行访问。

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

1
2
3
4
5
public LinkedHashMap(int initialCapacity, float loadFactor, 
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

  初始化一个空HashMap集合，集合的初始容量和加载因子由initialCapacity和loadFactor确认。调用父类HashMap的同名构造方法完成初始化操作。调用该构造方法返回的LinkedHashMap实例会按照访问顺序而不是插入顺序来完成键值对实体元素的迭代。

部分方法

void init()

1
2
3
4
5
@Override
void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header;
}

  在构造方法或者clone、readObject等方法执行过程中调用，用来完成LinkedHashMap底层双向链表的初始化操作。

  该方法执行过程中会首先实例化一个双向链表的头部节点，然后将头部节点的前驱和后继节点都指向自身。

void transfer(HashMap.Entry[] newTable, boolean rehash)

1
2
3
4
5
6
7
8
9
10
11
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e = header.after; e != header; e = e.after) {
        if (rehash)
            e.hash = (e.key == null) ? 0 : hash(e.key);
        int index = indexFor(e.hash, newCapacity);
        e.next = newTable[index];
        newTable[index] = e;
    }
}

  完成键值对实体从旧数组到新数组的迁移。

  整个过程相对来说还是比较简单的。具体流程如下：

  1. 从头部节点开始遍历，取得一个键值对实体对象，根据其hash值计算在新数组中的下标位置（如果有必要的话重新计算hash）；
  2. 如果该下标位置尚未指向链表集合，那么该节点就是该下标位置的第一个节点；
  3. 否则将该节点加入到该下标位置的链表集合的头部位置上。

  对所有节点执行上述流程，直至头部节点header的前驱节点也被加入到了新数组中的某个位置，此时认为旧数组上的所有元素都被加入到了新数组上，执行结束返回。

public boolean containsValue(Object value)

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean containsValue(Object value) {
    // Overridden to take advantage of faster iterator
    if (value==null) {
        for (Entry e = header.after; e != header; e = e.after)
            if (e.value==null)
                return true;
    } else {
        for (Entry e = header.after; e != header; e = e.after)
            if (value.equals(e.value))
                return true;
    }
    return false;
}

  如果当前map集合中存在匹配value的键值对实体，那么返回true，否则返回false。

  从header节点指向的第一个节点开始遍历，根据value是否为null执行不同的判断条件查找可以和value吻合的键值对实体。

public V get(Object key)

1
2
3
4
5
6
7
public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}

  返回当前map集合中匹配key的键值对实体，如果未找到可以匹配的对象，那么返回null。

  如果可以找到匹配的键值对实体，那么会把该键值对实体移到双向链表的结尾位置（也就是header节点的前驱节点位置上）。

public void clear()

1
2
3
4
public void clear() {
    super.clear();
    header.before = header.after = header;
}

  清空当前map集合，同时将header指针初始化。

Iterator<K> newKeyIterator()

1
2
3
4
5
Iterator<K> newKeyIterator()   { return new KeyIterator();   }

private class KeyIterator extends LinkedHashIterator<K> {
    public K next() { return nextEntry().getKey(); }
}

  构建一个遍历当前map集合中key的迭代器。KeyIterator基于LinkedHashMap.LinkedHashIterator<V>实现。

Iterator<V> newValueIterator()

1
2
3
4
5
Iterator<V> newValueIterator() { return new ValueIterator(); }

private class ValueIterator extends LinkedHashIterator<V> {
    public V next() { return nextEntry().value; }
}

  构建一个遍历当前map集合中value的迭代器。ValueIterator基于LinkedHashMap.LinkedHashIterator<V>实现。

Iterator<Map.Entry<K,V>> newEntryIterator()

1
2
3
4
5
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() { return nextEntry(); }
}

  构建一个遍历当前map集合中键值对的迭代器。EntryIterator基于LinkedHashMap.LinkedHashIterator<V>实现。

void addEntry(int hash, K key, V value, int bucketIndex)

1
2
3
4
5
6
7
8
9
void addEntry(int hash, K key, V value, int bucketIndex) {
    super.addEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}

  构建一个键值对实体并加入到map集合中对应下标位置上的链表集合中。调用的是HashMap同名方法。在执行过程中，如果空间不足会调用resize(int newCapacity)进行扩容，扩容完成后将旧数组上的键值对实体迁移到新数组上时，调用的是LinkedHashMap覆盖的transfer(HashMap.Entry[] newTable, boolean rehash)方法。最后加入键值对实体时，调用LinkedHashMap覆盖的createEntry(int hash, K key, V value, int bucketIndex)方法完成操作。

  在将该键值对接入双向链表的过程中，该键值对会被加入到双向链表的尾部节点（即header的前驱节点）。

  最后删除当前map集合中存在时间最久的键值对实体，由于LinkedHashMap实现类中的方法removeEldestEntry(Map.Entry<K,V> eldest)直接返回false，所以第7行代码不会真正执行。

void createEntry(int hash, K key, V value, int bucketIndex)

1
2
3
4
5
6
7
void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}

  创建一个键值对实体并将该实体加入到当前map集合中。第2 ~4行代码将实体加入到当前map集合中底层数组对应下标位置上的链表集合中。第5行代码将当前新创建的节点加入到双向链表的尾部位置。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

1
2
3
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

  如果当前map集合需要移除存在时间最久远的键值对实体就返回true，否则返回false。该方法被put或者putAll调用，用来在加入元素的过程中删除存在时间最久的元素。在LinkedHashMap中，该方法简单的返回false表示不会删除当前集合的双向链表中的尾部元素节点。

 

Entry<K,V>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;

    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }

    /**
     * Removes this entry from the linked list.
     */
    private void remove() {
        before.after = after;
        after.before = before;
    }

    /**
     * Inserts this entry before the specified existing entry in the list.
     */
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }

    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}

  LinkedHashMap中的内部静态类Entry在继承了HashMap.Entry内容的基础上多了两个字段—Entry before和Entry after。这两个字段是LinkedHashMap底层双向链表结构实现的基础。具体结构如图2所示：

图 - 2
 

  LinkedHashMap.Entry的构造方法直接调用其父类的同名方法完成键值对实体实例化操作。

  通过调用remove()方法可以将当前键值对节点从map集合的双向链表中移除，实现思想主要参考了双向链表关于节点移除的操作思想。

  addBefore(Entry<K,V> existingEntry)方法用来将当前键值对节点加入到existingEntry节点之前。

  recordAccess(HashMap<K,V> m)方法会在键值对实体加入map集合或者通过LinkedHashMap.get(Object key)方法访问某个键值对实体时调用。如果当前LinkedHashMap的访问顺序不是插入顺序，那么该方法会将被插入的（或者被访问的）键值对实体对象从当前位置删除并移动到双向链表的尾部位置（也就是header的前驱）。如果当前map集合的访问顺序是插入顺序，那么不做任何处理。

  在通过key或键值对自身从map集合中删除某个键值对实体时，会调用recordRemoval(HashMapm)方法，该方法会将被删除键值对实体与其前驱、后继节点的关系断开，保证双向链表的连接性。

 

LinkedHashIterator<E>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
private abstract class LinkedHashIterator<T> implements Iterator<T> {
    Entry<K,V> nextEntry    = header.after;
    Entry<K,V> lastReturned = null;

    /**
     * The modCount value that the iterator believes that the backing
     * List should have.  If this expectation is violated, the iterator
     * has detected concurrent modification.
     */
    int expectedModCount = modCount;

    public boolean hasNext() {
        return nextEntry != header;
    }

    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();

        LinkedHashMap.this.remove(lastReturned.key);
        lastReturned = null;
        expectedModCount = modCount;
    }

    Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (nextEntry == header)
            throw new NoSuchElementException();

        Entry<K,V> e = lastReturned = nextEntry;
        nextEntry = e.after;
        return e;
    }
}

  LinkedHashIterator是基于当前map集合的键值对实体的一个迭代器实现。该迭代器任何时候都会从header节点的后继节点开始迭代访问。

  判断是否可以继续向后遍历通过判断下一个节点是否等于header来判定，如果等于表示无法继续向后遍历。

 

涉及基础知识点

  1. LinkedHashMap实现LRU算法场景

      实现一个LinkedHashMap的子类，子类中需要有方法指定一个当前集合中可以容纳的元素上限值，覆盖重新实现方法removeEldestEntry(Map.Entry eldest) ，实现思路如下：

    1
    2
    3
    protected boolean removeEldestEntry(Map.Entry eldest) {
    	return size() > MAX_ENTRIES;
    }

      若当前集合容量大于上限，则返回true。在方法addEntry(int hash, K key, V value, int bucketIndex)中：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

      第6行代码执行覆盖以后的removeEldestEntry(Map.Entry eldest)方法，如果返回true，那么就删除当前集合中双向链表的首部节点以保证元素数量满足要求（默认双向链表中长时间未被访问的元素位置越靠前）。

 

参考文献

  1. NIL

 
 
 
 

------------- End of this article, thanks! -------------
 


  版权声明：本文由N.C.Lee创作和发表，采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可，转载请注明作者及出处。
  本文作者为 N.C.Lee
  本文标题为 Java Map 04 - LinkedHashMap
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-LinkedHashMap.html