康夺的个人博客

半日闲来半日谈

0%

Java集合分析之Map-这个Map有顺序（LinkedHashMap 和 TreeMap）

发表于 分类于 阅读次数： Valine：

​ 前文已经分析了 HashMap ，根据其实现，了解到其元素无序特性。今天来分析下两个能保证元素顺序的 Map —— 保证插入顺序的 LinkedHashMap 和可自定义排序规则的 TreeMap ，来看看到底是怎么实现有序的。

注：本文基于jdk_1.8.0_162

Map家族谱

LinkedHashMap

内部结构

总览

​ LinkedHashMap 是继承自 HashMap 的，或重写或实现了父类中的部分方法，在一定程度上体现了多态。LinkedHashMap 通过多维护了一个插入顺序的链表，保证了元素的访问顺序。同时，属性 accessOrder 可以设置调节元素顺序，便于实现 LRU 算法。

LinkedList = HashMap + LinkedList

主要成员

​ 主要成员如下：

1
2
3
4
5
6
7
8
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
    //元素头节点
    transient LinkedHashMap.Entry<K,V> head;
    //元素尾节点
    transient LinkedHashMap.Entry<K,V> tail;
    //是否维护访问顺序，true 则按访问顺序，false 则按插入顺序
    final boolean accessOrder;
}

其中，Entry 的结构如下，继承自 HashMap.Node ，并维护了元素的前后节点信息：

1
2
3
4
5
6
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);
    }
}

父类埋点之重点方法

​ LinkedHashMap 继承自 HashMap ，基本实现上复用父类，具体可参考：Java集合分析之Map-从HashMap说起 。LinkedHashMap 主要实现了 HashMap 中定义了，但是未实现的三个方法：

void afterNodeAccess(Node<K,V> p) { }

void afterNodeInsertion(boolean evict) { }

void afterNodeRemoval(Node<K,V> p) { }

afterNodeAccess 方法

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
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // accessOrder 为 true ，且该元素不是尾节点
    if (accessOrder && (last = tail) != e) {
        // p 是当前节点 ，b 是前一个节点 ，a 是后一个节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<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;
    }
}

​ 此方法在 put 和 get 操作时会调用。如果 accessOrder == true ，在 put 之后就算是对元素进行了访问，这时就会更新链表，把该元素放至链表最后。

afterNodeInsertion 方法

1
2
3
4
5
6
7
8
9
10
11
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //首节点存在，且定义的移除规则满足，则移除首节点
    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;
}

这个就是实现 LRU 算法的关键地方了，要实现移除规则，需将 accessOrder 设置为 true 。

afterNodeRemoval 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

​ 此方法会在移除元素时调用。由于 LinkedHashMap 同时维护了一个双向链表来记录元素顺序，所以，在移除元素的时候，会调整此链表。

​ 这三个方法，就是比 HashMap 多出来的用于维护访问顺序的方法，保证了链表元素从前到后依次是从旧到新。

元素存取方法

put 方法

​ put 方法并没重写，只是在实现了 afterNodeInsertion 后，记录了元素的插入顺序。有兴趣的可以回看之前的 HashMap 分析文章。

get 方法

1
2
3
4
5
6
7
8
9
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;
}

​ get 操作就没什么特别的了，和 HashMap 一样的方式取到元素节点。如果设置了 accessOrder ，则维护链表的顺序。

LRU算法

通过上文的分析，我们可以利用 LinkedHashMap 很轻松的实现 LRU 算法。

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
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    // 最大容量
    private Integer maxSize;

    public LRUCache(Integer maxSize, int initCapacity, float loadFactor) {
        super(initCapacity, loadFactor, true);
        this.maxSize = maxSize;
    }

    public LRUCache(int maxSize) {
        this(maxSize, 16, 0.75f);
    }

    public LRUCache() {
        this(Integer.MAX_VALUE);
    }

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

    public static void main(String[] args) {
        Map<String, Integer> cache = new LRUCache<>(3);
        cache.put("aaa", 1);
        cache.put("bbb", 1);
        System.out.println(cache);
        cache.put("ccc", 1);
        cache.get("aaa");
        System.out.println(cache);
        cache.put("ddd", 1);
        System.out.println(cache);
    }
}

运行结果如下，可以看出，元素顺序会在访问时调整，同时也会淘汰最不常用数据。

{aaa=1, bbb=1}
{bbb=1, ccc=1, aaa=1}
{ccc=1, aaa=1, ddd=1}

TreeMap

内部构造

总览

​ TreeMap 继承自 AbstractMap ，实现了 NavigableMap ，根据用户自定义的比较器或者 Key.compareTo 作为排序依据，并使用红黑树来进行实现。

主要成员

1
2
3
4
5
6
7
8
9
10
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    //比较器，用于排序，如果无比较器则使用 key 的比较规则来排序
    private final Comparator<? super K> comparator;
    //存放数据的节点entry, root 是要节点
    private transient Entry<K,V> root;
    private transient int size = 0;
    private transient int modCount = 0;
}

​ TreeMap 排序首先看比较器，如果无比较器才会再使用 Key 的比较规则来排序，下文会讲。 Entry 存放的是红黑树的节点数据，数据结构如下：

1
2
3
4
5
6
7
8
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

​ 节点包含了键值对、父节点、左子节点、右子节点，以及红黑树相关信息。本文只研究 TreeMap 的实现，不具体研究红黑树相关知识。

构造器

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
//默认构造器，比较器初始化为空，但是要求Key实现Comparable接口，不然无法put数据
public TreeMap() {
    comparator = null;
}

//带有比较器的构造器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

//带有集合元素的构造器，但是如果不是SortedMap，
//且Key没实现Comparable，仍然会报错，因为会调用put方法
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

//带有集合元素的构造器，会使用sortedMap的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

元素存取方法

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        //校验基本条件，即必须可比较
        compare(key, key);
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    
    //比较结果，即应该在父节点的左子节点还是或子节点
    int cmp;
    //父节点到底在哪
    Entry<K,V> parent;
    
    //将 Comparator 和 Comparable 进行分开操作，可见 Comparator 优先级高
    Comparator<? super K> cpr = comparator;
    //如果有比较器 Comparator
    if (cpr != null) {
        //循环确定父节点的位置，同时确定自己在左子节点还是右子节点
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            //划重点，这里是根据 compare 方法来判断是不是同一个元素
            //而不是 hashcode 和 equals
            else
                return t.setValue(value);
        } while (t != null);
    }
    //这里只能是无Comparator而有Comparable的了
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        //同Comparator
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
    } while (t != null);
    }
    //新建节点插入到正确位置
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    //红黑树处理
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

//compare 方法，会进行校验，要求要么传递比较器，要么 Key 实现 Comparable
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

​ 从 put 方法可以看出，对于 TreeMap 而言，在使用的时候，要么 Key 实现了 Comparable ，要么传入了 Comparator ，这点很重要。同时，其它的一系列操作，基本都会分这两种情况做处理。同时，Comparator 的优先级是高于 Comparable 的。

get 方法

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
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

//根据key找到对应的树节点
final Entry<K,V> getEntry(Object key) {
    // 传入了Comparator的，根据比较器来找
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    //从要节点开始树查找，compareTo的结果为0是目标节点
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

//根据Comparator来找树节点
final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        //从要节点开始进行树查找，compare的结果为0是目标节点
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

​ get 方法再次印证了，Comparator 的优先级是高于 Comparable 的。

remove 方法

1
2
3
4
5
6
7
8
9
10
11
12
public V remove(Object key) {
    //找至对应的树节点
    Entry<K,V> p = getEntry(key);
    //key不存在则返回null
    if (p == null)
        return null;
    V oldValue = p.value;
    //删除节点，维护节点关系，并做红黑树处理
    deleteEntry(p);
    //返回key对应的value
    return oldValue;
}

总结

  • LinkedHashMap 实际是 HashMap + LinkedList
  • LinkedHashMap 可用来实现 LRU 算法
  • TreeMap 根据使用者定义的排序规则来进行排序，并使用 红黑树 来进行实现
  • TreeMap 的 Key 不可为空，因为需要调用比较器或者 Key 的 compareTo 方法
  • TreeMap 判断是否同一个元素是根据 Comparator 或 Comparable ，而不是 hashcode 和 equals
  • TreeMap 如果定义了比较器，Key 可以不实现 Comparable 接口
  • TreeMap 比较器规则优先于 Key 的比较规则