聊一聊LRU算法及LinkedHashMap

发表于 | 分类于
字数统计: 2k | 阅读时长 ≈ 9

概述

以前聊过HashMap的数据结构，其实就是一个数组+链表Android内存优化。HashMap是无序的，因为他是按照key值去存放数据的，key值和你put进去的顺序几乎是不会相同的。那怎么能保证我put进去的数据和get出来的数据是相同顺序呢，这就要用到这里的LinkedHashMap。

LinkedHashMap的数据结构

LinkedHashMap是Map接口的哈希表和双向链表实现，继承了HashMap，其基本操作与父类相似，采用的Hash算法和HashMap一样。其实其数据结构基本和HashMap是一样的，只是Entry不一样，除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链表列表。HashMap的Entry是：

1
2
3
4
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;

而LinkedHashMap的Entry则多了before和after：

1
2
3
4
5
6
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
Entry<K, V> before; //上一个元素的引用
Entry<K, V> after; //下一个元素的引用

next指针是每一个数组后面的链表，而before和after则是整个LinkedHashMap的元素顺序，看图可能更好理解：


正是由于拥有before和after指针，所以LinkedHashMap是有序的而HashMap是无序的

使用场景

先来看例子：HashMap是无序的，而LinkedHashMap是有顺序的

1
2
3
4
5
6
7
8
9
10
11
12
Map<String, String> hashMap = new HashMap<String, String>();
hashMap.put("name1", "josan1");
hashMap.put("name2", "josan2");
hashMap.put("name3", "josan3");
Set<Entry<String, String>> set = hashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
    Entry entry = iterator.next();
    String key = (String) entry.getKey();
    String value = (String) entry.getValue();
    System.out.println("key:" + key + ",value:" + value);
}

自己可以打印输出结果看到，它不是按照put顺序的，同样的数据我们换成LinkedHashMap

1
2
3
4
5
6
7
8
9
10
11
12
Map<String, String> hashMap = new LinkedHashMap<String, String>();
hashMap.put("name1", "josan1");
hashMap.put("name2", "josan2");
hashMap.put("name3", "josan3");
Set<Entry<String, String>> set = hashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
    Entry entry = iterator.next();
    String key = (String) entry.getKey();
    String value = (String) entry.getValue();
    System.out.println("key:" + key + ",value:" + value);
}

打印结果完全和put顺序一致。
key：name1，value：josan1
key：name2，value：josan2
key：name3，value：josan3

以上只是LinkedHashMap其中一种双向链表的存储顺序特性：插入顺序(输出完全和插入顺序保持一致)，并且这个为LinkedHashMap的默认顺序。通过默认构造方法实现：

1
Map<String, String> hashMap = new LinkedHashMap<String, String>();

我们看下同样的数据，换一种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Map<String, String> hashMap = new LinkedHashMap<String, String>(16,0.5f,true);
hashMap.put("name1", "josan1");
hashMap.put("name2", "josan2");
hashMap.put("name3", "josan3");

hashMap.get("name1")
Set<Entry<String, String>> set = hashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
    Entry entry = iterator.next();
    String key = (String) entry.getKey();
    String value = (String) entry.getValue();
    System.out.println("key:" + key + ",value:" + value);
}

多了一行代码，先get了一个元素
打印结果:
key：name2，value：josan2
key：name3，value：josan3
key：name1，value：josan1

这就是LinkedMap另一种牛逼的存储特性叫：访问顺序 其通过带参数的构造方法实现：

1
Map<String, String> hashMap = new LinkedHashMap<String, String>(16,0.5f,true);

LinkedHashMap的实现

  • 成员变量

来看下源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* 如果为true，则按照访问顺序；如果为false，则按照插入顺序。（默认为false）
*/
private final boolean accessOrder;
/**
* 双向链表的表头元素。
 */
private transient Entry<K,V> header;

/**
* LinkedHashMap的Entry元素。
* 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。
 */
private static class Entry<K,V> extends HashMap.Entry<K,V> {
    Entry<K,V> before, after;
    ……
}

  • 构造方法
1
2
3
4
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder){
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

从源码可以看出，在LinkedHashMap的构造方法中，实际调用了HashMap的相关构造方法来构造一个底层存放的table数组。（如果没有指定initialCapacity的大小，系统默认是1<<4也就是16），这里需要注意的是accessOrder参数，如果不设置默认为false，代表按照插入顺序迭代，如果为true，则代表可以按照访问顺序进行迭代。（访问顺序迭代这个特性可以用在LRU算法中，这个后面单独弄一期）。

  • 初始化

这一块很多分析源码的都说有init方法，但是看了下发现没找到这个方法，先暂存

  • 存储（PUT）

LinkedHashMap并没有重现父类的put的方法，

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
46
47
48
49
50
51
52
/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

但是重写了当key存在时的afterNodeAccess方法，这个方法在HashMap中是一个空方法，这个操作就是把节点移动到最后（看这个参数accessOrder），实现访问顺序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<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;
        }
    }
  • 读取

LinkedHashMap 重写了父类 HashMap 的 get 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     */
    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，该属性为 boolean 型变量，对于访问顺序，为 true；对于插入顺序，则为 false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。

这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个 LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用带参数的构造方法。

该哈希映射的迭代顺序就是最后访问其条目的顺序，这种特性很适合构建 LRU 缓存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回 false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

参考

LinkedHashMap 的实现原理

图解LinkedHashMap原理

HashMap 最新底层原理分析