一文带你了解 TreeMap ，LinkedHashMap 的主要特点
最近写了这个 HashMap , 那么接下来简单讲讲 TreeMap ，LinkedHashMap ,ConcurrentHashMap
必备知识点
一. Comparable, Comparator这两个有什么不同？
可以看到一个是 java.lang 包的，一个是 util 包的。
代码如下，很明显， 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
解析：
如图所示 TreeMap 实现了这个 SrotedMap 接口，SortMap 接口中定义了这个 Comparator 外部比较器。
我们可以在创建 TreeMap 时传入~ ，不传入的话时没有这个外部比较器 Comparator 的。
那么问题来啦！为什么 key 不能是null 呢？
请看下图分析~
序号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
看看它滴类图~ 可以看到它 继承了 HashMap 。
可以看到这里在说它是在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)
最后
我是4ye 咱们下期应该……很快再见！！
喜欢的话可以关注下 头条号 和 公众号 Jav***e 支持下 4ye 呀
