LinkedHashMap

使用场景

使用HashMap无法保证遍历顺序：遍历顺序与插入（put）顺序不一致。但是有时我们需要保证遍历顺序与插入顺序的一致性。

例如，xx做过一个压缩图片大小的功能，要求当图片大于1000KB时，按10%的比例进行压缩；当图片大于500KB，按50%的比例进行压缩；当图片大于300KB时，按80%比例进行压缩；当图片大于100KB时，按90%比例进行压缩。她的代码大概其是这样的(大意如此，不要追究细节)：

Image image = xxxx;
Map<Integer, Float> map = new LinkedHashMap();
// 这里必须保证写入顺序
map.put(1000,0.1);
map.put(500,0.5);
map.put(300,0.8);
map.put(100,0.9);

for(Entry entry : map.entrySet()){
    // 如果图片大于指定大小
    if(image.size() > entry.getKey()){
        // 按指定倍数进行压缩
        image.resize(entry.getValue());
   } 
}

如果使用普通的HashMap，那么上面的代码显然会有问题，因为对map做for循环的顺序与map.put的顺序不一定一样。为了保证顺序一样，这里应该使用LinkedHashMap。

使用示例

LinkedHashMap的使用其实很简单：

Map<String, String> map = new LinkedHashMap();
map.put("first","第一个");
map.put("seconde","第二个");
map.put("third","第三个");

for(Entry entry: map.entrySet()){
    System.out.print(entry.getKey());
    System.out.print(entry.getValue());
}

for(String key: map.keySet()){
    System.out.print(key);
}

for(String value: map.values()){
    System.out.print(value);
}

map.foreach((k,v)->System.out.print(k+":"+v));

原理

数据结构

本质上来说，LinkedHashMap保证操作顺序的办法就是把存入Map中的Entry、Key和Value分别用链表串联起来：

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
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的Entry不仅是个链表，而且还是双向链表。双向链表的好处主要有两个，一是可以逆序查找，二是可以提高查询性能。如果关注一下LinkedList，可以发现它的“链表”也是双向链表。

不仅如此，LinkedHashMap还专门为entrySet、keySet和values实现了几个不同的子类：

final class LinkedKeySet extends AbstractSet<K> {}

final class LinkedValues extends AbstractCollection<V> {}

final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {}

此外还有对应的Iterator，用于处理各自的foreach循环：

abstract class LinkedHashIterator {
    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {}

    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {}

    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {}

排序逻辑

LinkedHashMap是继承自HashMap的。当HashMap执行了put、remove或者其它的修改数据的方法后，会执行一些“callback”方法，用于触发LinkedHashMap中的一些处理逻辑，如：

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删除某个元素时，用来重新排序的方法。其中的代码逻辑很简单，就是一个双向链表的删除操作。

上面是删除元素时的重排序；那么，在新增元素时是怎样做的呢？先看下面这个方法：

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);
    }
}

上面这个方法看起来像是在新增元素时做重排序的方法。但是，由于LinkedHashMap中removeEldestEntry()方法默认永远返回false，所以实际上这个方法中不会做任何处理。新增元素时的排序方法实际是在这里：

// HashMap中：
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);
// 下略
}

// LinkedHashMap中
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

在Java8以后，HashMap中的Entry有可能是TreeNode。LinkedHashMap也实现了对应的newTreeNode方法，并在这个方法中调用了linkNodeLast方法。两段代码都很简单，就不解释了。

另外，在HashMap扩容时，虽然需要对元素做重哈希，但是并不需要对链表做重排序。

“高级”特性

排序规则

默认情况下，LinkedHashMap是按照插入顺序进行排序的。但是，我们可以指定它按照“访问”顺序进行排序。这段逻辑可以参见这段代码：

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        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;
    }
}

其中的accessOrder默认为false，但是可以通过构造方法来设定为true。如果将这个字段设置为true，每当一个元素被访问到，LinkedHashMap都会把它挪到链表的末尾去。这样，LinkedHashMap的遍历顺序就变成了“最近最少访问”顺序了。如下面的代码：

// 指定accessOrder为true
Map<String, String> map = new LinkedHashMap(10,1,true);
map.put("a","a");
map.put("b","b");
map.put("c","c");
map.get("b");
map.get("a");
// 问题1：这里会按什么顺序打印出来？
map.foreach((k,v)->System.out::println);

这个accessOrder有什么用呢？看到“最近最少访问”应该就能想到了：做简易的缓存。而且，如果要用作简易缓存，还可以通过重写removeEldestEntry()方法，来让LinkedHashMap在插入新元素时，删除Map中最“老”的元素，实际上也就是删除链表的头结点。

问题：为什么LinkedHashMap中，“最老”的元素一定是链表的头结点？

性能比较

虽然说LinkedHashMap在增删改数据时需要重新维护链表顺序，但是由于链表的增删改操作性能非常好（时间复杂度是常数级别的，一般可以认为是O(1)），所以并不会有太大的额外损耗。

遍历操作上，如果都是对entrySet做遍历，LinkedHashMap与HashMap也相去无几。但是如果对keySet或者values做遍历，这就不一定了。

TreeMap

HashMap的基本结构是数组，但是无法保证遍历顺序。LinkedHashMap的在数组基础上增加了链表，从而使得遍历有序。但是，LinkedHashMap只能按操作（插入或访问）顺序来遍历。如果我们需要按其它顺序来遍历，要怎么办？

TreeMap提供了一个可用的选项：它提供按key值排序的遍历顺序，而排序规则可以自己制定。

使用场景和示例

同样以xx要做的那个功能举例。如果用TreeMap，那么我们大概需要这样写：

Image image = xxxx;
Map<Integer, Float> map = new TreeMap(new Comparator<Integer>{
int compare(Integer o1, Integer o2){
// 之所以取负数，是为了逆序排列
return -(o1.compareTo(o2));
}
});
// 使用TreeMap，这里就可以乱序put了。
map.put(100,0.9);
map.put(1000,0.1);
map.put(300,0.8);
map.put(500,0.5);

for(Entry entry : map.entrySet()){
    // 如果图片大于指定大小
    if(image.size() > entry.getKey()){
        // 按指定倍数进行压缩
        image.resize(entry.getValue());
   } 
}

之所以可以这样使用，是因为TreeMap会将放入其中的元素按key值进行排序，排序规则有两种：在构造TreeMap时指定一个非null的Comparator，或者保证放入其中的Key值都实现了Comparable接口。如果二者同时符合要求，会以Comparator为准。

原理

TreeMap的底层数据结构是红黑树。所以要理解TreeMap的原理，得先把红黑树搞清楚。这里不多说。

性质

底层结构决定了红黑树的性质：有序；增、删、改、查时间复杂度为O(logN)。

EnumMap

使用场景

当key值是某个枚举类时，推荐使用EnumMap。如，我们声明了一个产品代码的枚举ProjectCode，要求每种产品都使用一个不同的还款计算器，这时我们可以这样：

public enum ProjectCode{
    P1,P2,P3;
}

public class Order{
    private ProjectCode projectCode;
}

public interface RepayCalculator{
    void calculate(Order);
}

public class RepayCalculatorAsDispatcher implements{
    private Map<ProjectCode, RepayCalculator> repayCalculatorMap
         = new EnumMap<>(ProjectCode.class);
    
    public void calculate(Order){
        repayCalculatorMap.get(order.getProjectCode())
            .calculate(order);
    }
}

诚然，这里的repayCalculatorMap也可以用一个HashMap。但是由于我们的key值是枚举类，HashMap的空间和时间复杂度其实都不如EnumMap。

原理

EnumMap比HashMap强的原因，是因为它的底层是一个简单的一维数组。虽然HashMap的底层也是一个数组，但是它的数组实际上是一个二维数组。HashMap要使用二维数组的原因是：它要处理的key值可能有无限多个，无论分配多大的哈希桶，都存在哈希碰撞的风险；但EnumMap没有这个风险：枚举值个数是有限的，是固定的，初始化时分配对应个数的“哈希桶”，就永远不会有哈希碰撞风险。

因为没有哈希碰撞，所以EnumMap的效率比HashMap要高：它的时间复杂度是严格的O(1)。而即使是HashMap，也有可能在某些攻击面前退化为O(n)。 HashMap退化为O(n)的问题在Java8以后已经得到了改进，现在的最差情况是O(logN)。猜猜看为什么。