How TreeMap Works Internally in Java

在Java面试题中，最常被问到的问题是Java中TreeMap的内部工作原理，或者TreeMap的内部实现是什么。

在本节中，我们将学习Java中TreeMap的内部工作原理。在深入了解内部工作原理之前，首先要理解什么是TreeMap。

Java中的TreeMap

TreeMap是Java集合框架的成员类。它实现了Map, NavigableMap, Sorted, Cloneable和Serializable接口。它继承了AbstractMap类。与HashMap一样，它也以键值对的形式存储数据。HashMap和TreeMap的区别在于HashMap不对键排序，而TreeMap则按照自然顺序（升序）对键进行排序。我们也可以使用Comparator来自定义排序。

与HashMap和LinkedHashMap相比，它的速度较慢。它的类方法如get(), put(), containsKey()等提供了O(log n)的复杂度。它本质上是非线程安全的，意味着它不是线程安全的。对于多线程环境，我们可以使其线程安全。

我们知道，在树中，一个节点有三个引用：父节点、右子节点和左子节点。在下面的图中，我们展示了TreeMap中节点的结构。

树数据结构遵循以下属性：

• 左子节点的值将始终小于父节点的值。
• 右子节点的值将始终大于或等于父节点的值。
• 对象的逻辑比较是通过自然顺序完成的。

TreeMap的内部工作原理

与HashMap和LikedHasMap不同，它不使用哈希来存储键值对。在内部，它使用一种称为红黑树的数据结构。换句话说，它使用红黑树算法对TreeMap对象的键进行排序。为了理解TreeMap的内部工作原理，我们必须理解红黑树算法。

红黑树算法

红黑树是一种自平衡二叉搜索树（BST）。它具有以下属性：

• 在红黑树中，节点的颜色是红色或黑色。
• 根节点始终是黑色。
• 红节点不能有相同颜色的相邻节点。
• 从根节点到null的所有路径都应包含相同数量的黑色节点。

让我们通过一个例子来理解TreeMap的实现。

TreemapExample.java

输出

B Delhi
D Jaipur
F Agra
H Ahmedabad 
P Patna

让我们看看这些元素是如何按照自然顺序存储在TreeMap中的。

添加第一个元素

在上面的代码片段中，我们插入了第一个元素(H, Ahmedabad)。其中H是键，Ahmedabad是值。它将成为TreeMap的根节点。TreeMap将按如下方式存储它。

添加第二个元素

我们插入了第二个元素(D, Jaipur)。其中D是键，Jaipur是值。键D在逻辑上小于键H。根据规则，较小的值将放在父节点的左侧。因此，值Jaipur将放在Ahmedabad的左侧，而Ahmedabad成为Jaipur的父节点。Jaipur的值将存储在TreeMap中，如下所示。

添加第三个元素

我们插入了第三个元素(B, Delhi)。其中B是键，Delhi是值。键B小于键D。因此，它将被添加到Jaipur的左侧，Jaipur成为Delhi的父节点。Delhi的值将存储在TreeMap中，如下所示。

添加第四个元素

我们插入了第四个元素(F, Agra)。其中F是键，Agra是值。键F大于键B和D。因此，它将被存储在Jaipur的右侧，如下所示。Jaipur也将是Agra的父节点。

添加第五个元素

我们插入了第五个元素(P, Patna)。其中P是键，Patna是值。键P大于键B、D和F。因此，它将被存储在Ahmedabad的右侧，如下所示。Ahmedabad也将是Patna的父节点。

在将所有元素插入树之后，排序后的TreeMap如下所示：

上面的树表示了排序后的键。我们可以按顺序读出这些键：B, D, F, H, P。