一文带你了解 TreeMap ，LinkedHashMap 的主要特点

最近写了这个 HashMap ,  这篇就简单讲讲 TreeMap ，LinkedHashMap 的特点~ 

内功加一 !😝

必备知识点

一. Comparable  ,   Comparator 这两个有什么不同？

可以看到一个是 java.lang 包的，一个是 util 包的。

image-20210315063954892

代码如下，很明显， Comparable 属于 内部比较器， 而 Comparator 属于 外部比较器 。

外部比较器的好处 是我们可以有很多这种比较器，可以按排序的要求去选择 ，便于解耦。

而内部比较器也比较简单，只要实现了该  Comparable   接口就可以进行比较了。

class B implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1-o2;
    }
}
class C implements Comparable<Integer>{
    private final int num;
    public C(int num){
        this.num=num;
    }
    @Override
    public int compareTo(Integer o) {
        return this.num-o;
    }
}

接着让我们来看看这个 TreeMap~ 😝

TreeMap 特点

1. 有序

2. key 不能为 null

解析：

image-20210315065029960

image-20210315065312593

如图所示  TreeMap 实现了这个 SrotedMap 接口，SortMap 接口中定义了这个 Comparator 外部比较器。

image-20210315072710203

我们可以在创建 TreeMap 时传入~  ，不传入的话时没有这个外部比较器  Comparator  的。

那么问题来啦！为什么 key 不能是null 呢？

请看下图分析~😋

image-20210315070116514

image-20210315070150795

序号1，这里表示当你第一次put 时，会进入 compare 方法，源码如下：

/**
 * Compares two keys using the correct comparison method for this TreeMap.
 */
@SuppressWarnings("unchecked")
final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

可以发现如果你木有定义这个 外部比较器的话，它会转化为这个 内部比较器 Comparable 进行比较 。

可以看到当你传进来的 key 为 null 时，即 k1 为 null，此时调用 compareTo 方法就会抛出 NullPointerException  。效果等于  null.compareTo(k2)  。

当你自定义了 外部比较器的 话， 还得看看这个 比较器中 compare 方法的写法，稍不注意也会抛出空指针异常

如果在这里有加入 非空判断的话，是不会抛出空指针异常的~  (序号2 可以参考这里)

class B implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        if (o1==null||o2==null){
            return -1;
        }
        return o1-o2;
    }
}

图中序号3，可以看到直接抛出空指针异常啦~

所以，真正的答案应该是

当你自定义了 外部比较器 Comparator 时，你可以允许 key 为null ，不过一般不建议~ 。😝

当你没有自定义 外部比较器 Comparator 时， TreeMap 会为 key 使用 内部比较器 Comparable ，此时不允许 key 为 null  😝

总结：

TreeMap 的特点是有序，默认情况下会根据 key 进行自然排序，此时 key 不能为 null ，而 自定义 外部比较器 Comparator 时 ，是可以允许 key 为 null 的

---

嘿嘿 趁热打铁，让我们把 目光 移动到另外一个和 顺序有关的 Map —— LinkedHashMap

LinkedHashMap

---

img

看看它滴类图~  可以看到它 继承了 HashMap 。

image-20210315080630294

image-20210315081400764

可以看到这里在说它是在HashMap的基础上维护了一个双向链表，后面是在说它的作用是保证 插入的有序

这一部分就不展开啦，主要重写了 newNode 等方法，去 维护这个双链表~

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

总结

LinkedHashMap 的 特点是 双向链表，插入有序

而且遍历时也是直接遍历双向链表的，插入时间复杂度为O(1)，查找时间复杂度O(n)

---

完结~ 撒花★,°:.☆(￣▽￣)/$:.°★ 。

👉 下一篇再写写这最后一个 ConcurrentHashMap ，然后是 锁 ~ 部分的知识点 ! ！！

创作不易， 点个赞，关注下  交个朋友可好! xiexie~ 😝

谢谢可爱又帅气的大佬们的观看！祝您 天天开心！😄  

感谢您的关注！您的每个关注，都是博主 肝肝肝的动力 😝

点个“在看”表示朕