本文主要是介绍TreeMap 和 LinkedHashMap--8，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.TreeMap
Comparable 和 Comparator 两者进行排序的方式，而 TreeMap 利用的也是此原理，从而实现了对 key 的排序。
TreeMap 底层的数据结构就是红黑树，和 HashMap 的红黑树结构一样。
不同的是，TreeMap 利用了红黑树左节点小，右节点大的性质，根据 key 进行排序，使每个元素能够插入到红黑树大小适当的位置，维护了 key 的大小关系，适用于 key 需要排序的场景。
因为底层使用的是平衡红黑树的结构，所以 containsKey、get、put、remove 等方法的时间复杂度都是 log(n)。
1.1新增节点
我们来看下 TreeMap 新增节点的步骤：
判断红黑树的节点是否为空，为空的话，新增的节点直接作为根节点，代码如下：
Entry<K,V> t = root;
//红黑树根节点为空，直接新建
if (t == null) {// compare 方法限制了 key 不能为 nullcompare(key, key); // type (and possibly null) check// 成为根节点root = new Entry<>(key, value, null);size = 1;modCount++;return null;
}
根据红黑树左小右大的特性，进行判断，找到应该新增节点的父节点，代码如下：
Comparator<? super K> cpr = comparator;
if (cpr != null) {//自旋找到 key 应该新增的位置，就是应该挂载那个节点的头上do {//一次循环结束时，parent 就是上次比过的对象parent = t;// 通过 compare 来比较 key 的大小cmp = cpr.compare(key, t.key);//key 小于 t，把 t 左边的值赋予 t，因为红黑树左边的值比较小，循环再比if (cmp < 0)t = t.left;//key 大于 t，把 t 右边的值赋予 t，因为红黑树右边的值比较大，循环再比else if (cmp > 0)t = t.right;//如果相等的话，直接覆盖原值elsereturn t.setValue(value);// t 为空，说明已经到叶子节点了} while (t != null);
}
在父节点的左边或右边插入新增节点，代码如下：
//cmp 代表最后一次对比的大小，小于 0 ，代表 e 在上一节点的左边
if (cmp < 0)parent.left = e;
//cmp 代表最后一次对比的大小，大于 0 ，代表 e 在上一节点的右边，相等的情况第二步已经处理了。
elseparent.right = e;
着色旋转，达到平衡，结束。
从源码中，我们可以看到：
1.新增节点时，就是利用了红黑树左小右大的特性，从根节点不断往下查找，直到找到节点是 null 为止，节点为 null 说明到达了叶子结点；
2.查找过程中，发现 key 值已经存在，直接覆盖；
3.TreeMap 是禁止 key 是 null 值的。
TreeMap 相对来说比较简单，红黑树和 HashMap 比较类似，比较关键的是通过 compare 来比较 key 的大小，然后利用红黑树左小右大的特性，为每个 key 找到自己的位置，从而维护了 key 的大小排序顺序。
2.1LinkedHashMap 整体架构
LinkedHashMap 本身是继承 HashMap 的，所以它拥有 HashMap 的所有特性，再此基础上，还提供了两大特性：
1.按照插入顺序进行访问；
2.实现了访问最少最先删除功能，其目的是把很久都没有访问的 key 自动删除。
LinkedHashMap 新增了哪些属性，以达到了链表结构：
// 链表头
transient LinkedHashMap.Entry<K,V> head;// 链表尾
transient LinkedHashMap.Entry<K,V> tail;// 继承 Node，为数组的每个元素增加了 before 和 after 属性
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);}
}// 控制两种访问模式的字段，默认 false
// true 按照访问顺序，会把经常访问的 key 放到队尾
// false 按照插入顺序提供访问
final boolean accessOrder;
LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，每次新增时，都把节点追加到尾节点等手段，在新增的时候，就已经维护了按照插入顺序的链表结构了。
LinkedHashMap 只提供了单向访问，即按照插入的顺序从头到尾进行访问，不能像 LinkedList 那样可以双向访问。
我们主要通过迭代器进行访问，迭代器初始化的时候，默认从头节点开始访问，在迭代的过程中，不断访问当前节点的 after 节点即可。
Map 对 key、value 和 entity（节点） 都提供出了迭代的方法，假设我们需要迭代 entity，就可使用 LinkedHashMap.entrySet().iterator() 这种写法直接返回 LinkedHashIterator ，LinkedHashIterator 是迭代器，我们调用迭代器的 nextNode 方法就可以得到下一个节点，迭代器的源码如下：
// 初始化时，默认从头节点开始访问
LinkedHashIterator() {// 头节点作为第一个访问的节点next = head;expectedModCount = modCount;current = null;
}final LinkedHashMap.Entry<K,V> nextNode() {LinkedHashMap.Entry<K,V> e = next;if (modCount != expectedModCount)// 校验throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();current = e;next = e.after; // 通过链表的 after 结构，找到下一个迭代的节点return e;
}
访问最少删除策略
这种策略也叫做 LRU（Least recently used,最近最少使用），大概的意思就是经常访问的元素会被追加到队尾，这样不经常访问的数据自然就靠近队头，然后我们可以通过设置删除策略，比如当 Map 元素个数大于多少时，把头节点删除，我们写个 demo 方便大家理解。demo 如下，完整代码可到 github 上查看
这篇关于TreeMap 和 LinkedHashMap--8的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
