# 前言

首先， TreeMap 与哈希没有任何关系，其次，哈希和 Map 也不是一回事，请不要先入为主。Map 只是一个键值对的数据结构，哈希是将对象计算哈希码的一种算法。 TreeMap 只是通过红黑树将键值对存起来，一方面实现了二叉搜索树的排序性，另一方面维护了整棵树的平衡性，防止树退化为链表增大查询 / 插入的时间复杂度。

# 排序方式

TreeMap 对插入数据实现了排序，如果是自定义数据，要么该类实现 Comparable 接口，要么 TreeMap 在构造方法中传入 Comparator 接口。

# Comparable

以 Student 类来说明，继承 Comparable 并重写 compareTo() 方法。

	public class Student implements Comparable<Student> {
	public int id;// 为了简单，就写一个 id 属性，并设为 public 方便获取

	public Student(int id) {this.id = id;}

	// 对比方法
	@Override
	public int compareTo(Student o) {
	// 按照 id 从小到大排序
	return this.id - o.id;
	}
	}

在 CompareTo() 中，是传入的对象和当前对象进行对比：

如果对比大于 0，降序排序。
如果对比小于 0，升序。

其实记住当前对象 - 传入对象就是升序，反之则降序。

# Comparator

通过外部类的方式进行编写，对于 Comparator 接口的传入也可以用 Lambda 表达式

	Collections.sort(list,new Comparator<Student>() {
	@Override
	public int compare(Student o1,Student o2) {
	// 第一个参数 - 第二个参数：升序
	return (int)(o1.id - o2.id);
	}
	});

	// 也可以传入 Lambda 表达式
	Collections.sort(list,(Student o1,Student 02) -> o1.id - o2.id);

我们看一下 TreeMap 的部分属性和构造方法：

	public class TreeMap<K,V>
	extends AbstractMap<K,V>
	implements NavigableMap<K,V>, Cloneable, java.io.Serializable
	{
	private final Comparator<? super K> comparator;

	// 传入一个 Comparator 接口
	public TreeMap() {comparator = null;}

	public TreeMap(Comparator<? super K> comparator) {
	this.comparator = comparator;
	}
	}

如果没有传入 Comparator 接口实现，那么传入的 Key 必须实现 Comparable 。

TreeMap 底层用红黑树，红黑树近似平衡，最长路径不超过最短路径的 2 倍。

# TreeMap

TreeMap 的 UML 类图：

因为底层使用了红黑树，所以节点就是 Entry ，记录了左右节点和父节点指针，以及节点颜色。

	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;
	// 构造方法，此处不写
	}

关于红黑树，详细的实现，也就是节点如何变色，如何左旋右旋来维持近似平衡，可以看《算法导论》，本文不会详细去讲，作者曾经也自己看着书写过红黑树，当成 C++ 期末作业交上去了，但是过了两三天又忘了，这玩意吧，看个人兴趣吧，hhhhhh。

# put()

直接给出 put 的执行流程：

判断当前根节点为 null，那么插入的第一个元素就是根节点。
如果存在根节点，判断插入元素在左侧还是右侧，如果对比为 0，说明当前元素存在于 TreeMap 中，将其覆盖：在 TreeMap 中，不会存在重复元素。
找到插入位置，插入。
节点变色和旋转操作。

代码太长了，要看源码自己打开 IDEA 查看。从 put 流程也可知，时间复杂度为 logN。

# get()

也就是不断地对比，在红黑树中查找节点。

# TreeSet

这个就是对 TreeMap 进行了简单包装，不过多讲解

额，其实关于 TreeMap 的详解应该是对红黑树的详解，但是我真的不想写，啊啊啊啊啊，以后有时间就单独写一篇博客解释一下红黑树，顺便放一个源码模板方便各位使用（等我想起了再说吧）。

# 参考

https://blog.csdn.net/weixin_51192504/article/details/109775797
https://pdai.tech/md/java/collection/java-map-TreeMap&TreeSet.html

Java基础