TreeMap的put源码详解

1.TreeMap中每一个节点的内部属性
K key;				//键
V value;			//值
Entry&lt;K,V&gt; left;		//左子节点
Entry&lt;K,V&gt; right;		//右子节点
Entry&lt;K,V&gt; parent;	//父节点
boolean color;			//节点的颜色




2.TreeMap类中中要知道的一些成员变量
public class TreeMap&lt;K,V&gt;{
   
    //比较器对象
    private final Comparator&lt;? super K&gt; comparator;

	//根节点
    private transient Entry&lt;K,V&gt; root;

	//集合的长度
    private transient int size = 0;

   

3.空参构造
	//空参构造就是没有传递比较器对象
	 public TreeMap() {
        comparator = null;
    }
	
	
	
4.带参构造
	//带参构造就是传递了比较器对象。
	public TreeMap(Comparator&lt;? super K&gt; comparator) {
        this.comparator = comparator;
    }
	
	
5.添加元素
	public V put(K key, V value) {
        return put(key, value, true);
    }

参数一：键
参数二：值
参数三：当键重复的时候，是否需要覆盖值
		true：覆盖
		false：不覆盖
		
	private V put(K key, V value, boolean replaceOld) {
		//获取根节点的地址值，赋值给局部变量t
        Entry&lt;K,V&gt; t = root;
		//判断根节点是否为null
		//如果为null，表示当前是第一次添加，会把当前要添加的元素，当做根节点
		//如果不为null，表示当前不是第一次添加，跳过这个判断继续执行下面的代码
        if (t == null) {
			//方法的底层，会创建一个Entry对象，把他当做根节点
            addEntryToEmptyMap(key, value);
			//表示此时没有覆盖任何的元素
            return null;
        }
		//表示两个元素的键比较之后的结果
        int cmp;
		//表示当前要添加节点的父节点
        Entry&lt;K,V&gt; parent;
		
		//表示当前的比较规则
		//如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null
		//如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器
        Comparator&lt;? super K&gt; cpr = comparator;
		//表示判断当前是否有比较器对象
		//如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准
		//如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准
        if (cpr != null) {
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp &lt; 0)
                    t = t.left;
                else if (cmp &gt; 0)
                    t = t.right;
                else {
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        } else {
			//把键进行强转，强转成Comparable类型的
			//要求：键必须要实现Comparable接口，如果没有实现这个接口
			//此时在强转的时候，就会报错。
            Comparable&lt;? super K&gt; k = (Comparable&lt;? super K&gt;) key;
            do {
				//把根节点当做当前节点的父节点
                parent = t;
				//调用compareTo方法，比较根节点和当前要添加节点的大小关系
                cmp = k.compareTo(t.key);
				
                if (cmp &lt; 0)
					//如果比较的结果为负数
					//那么继续到根节点的左边去找
                    t = t.left;
                else if (cmp &gt; 0)
					//如果比较的结果为正数
					//那么继续到根节点的右边去找
                    t = t.right;
                else {
					//如果比较的结果为0，会覆盖
                    V oldValue = t.value;
                    if (replaceOld || oldValue == null) {
                        t.value = value;
                    }
                    return oldValue;
                }
            } while (t != null);
        }
		//就会把当前节点按照指定的规则进行添加
        addEntry(key, value, parent, cmp &lt; 0);
        return null;
    }	
	
	
	
	 private void addEntry(K key, V value, Entry&lt;K, V&gt; parent, boolean addToLeft) {
        Entry&lt;K,V&gt; e = new Entry&lt;&gt;(key, value, parent);
        if (addToLeft)
            parent.left = e;
        else
            parent.right = e;
		//添加完毕之后，需要按照红黑树的规则进行调整
        fixAfterInsertion(e);
        size++;
        modCount++;
    }
	
	
	
	private void fixAfterInsertion(Entry&lt;K,V&gt; x) {
		//因为红黑树的节点默认就是红色的
        x.color = RED;

		//按照红黑规则进行调整
		
		//parentOf:获取x的父节点
		//parentOf(parentOf(x)):获取x的爷爷节点
		//leftOf:获取左子节点
        while (x != null && x != root && x.parent.color == RED) {
			
			
			//判断当前节点的父节点是爷爷节点的左子节点还是右子节点
			//目的：为了获取当前节点的叔叔节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
				//表示当前节点的父节点是爷爷节点的左子节点
				//那么下面就可以用rightOf获取到当前节点的叔叔节点
                Entry&lt;K,V&gt; y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
					//叔叔节点为红色的处理方案
					
					//把父节点设置为黑色
                    setColor(parentOf(x), BLACK);
					//把叔叔节点设置为黑色
                    setColor(y, BLACK);
					//把爷爷节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);
					
					//把爷爷节点设置为当前节点
                    x = parentOf(parentOf(x));
                } else {
					
					//叔叔节点为黑色的处理方案
					
					
					//表示判断当前节点是否为父节点的右子节点
                    if (x == rightOf(parentOf(x))) {
						
						//表示当前节点是父节点的右子节点
                        x = parentOf(x);
						//左旋
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
				//表示当前节点的父节点是爷爷节点的右子节点
				//那么下面就可以用leftOf获取到当前节点的叔叔节点
                Entry&lt;K,V&gt; y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
		
		//把根节点设置为黑色
        root.color = BLACK;
    }

TreeMap 是一种基于红黑树实现的 NavigableMap 接口的 Map 实现类，它保证了键值对的顺序是有序的。TreeMap 中的每个节点是一个 Entry，而它们之间通过红黑树的结构来连接，保证了在插入、删除、查找等操作时的对数时间复杂度。

1. `TreeMap` 节点的内部属性

每个节点（Entry）包含以下属性：

K key：节点的键。
V value：节点的值。
Entry<K,V> left：左子节点。
Entry<K,V> right：右子节点。
Entry<K,V> parent：父节点。
boolean color：节点的颜色，红黑树会使用红色和黑色来平衡树的结构。

2. `TreeMap` 类中的一些成员变量

Comparator<? super K> comparator：用于比较键的比较器。默认情况下，TreeMap 会使用自然顺序（即 Comparable 接口），如果传入了自定义比较器，则使用该比较器。
Entry<K,V> root：根节点，用于存储树的最上层节点。
int size：TreeMap 中元素的数量。

3. 构造方法

空参构造： public TreeMap() { comparator = null; // 默认使用自然顺序比较键 }
带参构造： public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; // 使用自定义的比较器 }

4. 添加元素

TreeMap 的 put 方法用来插入元素。我们首先来看 put(K key, V value) 的实现：

1
2
3

public V put(K key, V value) {
    return put(key, value, true);
}

这个方法会调用下面的 put(K key, V value, boolean replaceOld) 方法。第二个参数 replaceOld 表示当键重复时是否覆盖值。

`put` 方法的核心部分：

首先判断是否是空树：
如果根节点为空（即 root == null），说明这是第一次添加元素，此时直接调用 addEntryToEmptyMap 将新节点添加为根节点。
非空树的情况

：

如果树不为空，会进入循环判断新节点应该插入的位置。插入的位置由比较器或者自然顺序决定：
- 如果使用了比较器，就通过 comparator.compare() 来比较。
- 如果没有比较器，则使用键的 compareTo 方法进行比较。
键是否已存在

：
- 如果找到相同的键，且 replaceOld 为 true，则覆盖旧的值；否则，保持原值不变。
插入新节点：
如果没有找到相同的键，则会调用 addEntry 方法将新节点插入到合适的位置，并调用 fixAfterInsertion 方法来进行红黑树的平衡操作。

5. 插入节点方法

private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (addToLeft) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
}

该方法会创建一个新的 Entry 对象，并将其插入到父节点的左子节点或右子节点。插入后，需要调用 fixAfterInsertion 来确保红黑树的平衡。

6. 红黑树的平衡（`fixAfterInsertion`）

在 TreeMap 中，红黑树的平衡操作是通过 fixAfterInsertion 来完成的。此方法确保树的红黑性质在插入节点后得到修复。

红黑树的修复遵循如下规则：

节点的颜色初始为红色。
如果父节点是红色的，则需要进行调整。
- 情况1：父节点是左子节点，叔叔节点是红色，则将父节点和叔叔节点颜色设置为黑色，祖父节点设置为红色，并将当前节点向上移动。
- 情况2：父节点是左子节点，叔叔节点是黑色，当前节点是右子节点，则需要左旋父节点。
- 情况3：父节点是右子节点，叔叔节点是红色，则处理方式与情况1类似；父节点是右子节点，叔叔节点是黑色，当前节点是左子节点，则需要右旋父节点。

每次修复完成后，根节点的颜色会被设置为黑色。

7. 旋转操作

红黑树的旋转操作用于调整树的结构，常见的旋转操作包括左旋和右旋。这些操作有助于保持树的平衡。

左旋：如果当前节点是父节点的右子节点且不满足红黑树的性质，就需要进行左旋。
右旋：如果当前节点是父节点的左子节点且不满足红黑树的性质，就需要进行右旋。

这些旋转操作的目的是保持树的平衡，使得树的高度不会过高，从而保证查找、插入和删除操作的时间复杂度为 O(log N)。

8.课堂思考问题

8.1 TreeMap 添加元素时，键是否需要重写 `hashCode` 和 `equals` 方法？

答案：不需要。

解析：

TreeMap 是基于红黑树实现的，元素的排序是根据键的比较结果来决定的，不是基于键的哈希值。所以在 TreeMap 中，并不需要重写 hashCode 和 equals 方法。
TreeMap 会通过 Comparator（如果传入了比较器）或者键实现的 Comparable 接口来决定键的顺序，而不是依赖于哈希值。
这与 HashMap 不同，HashMap 是基于哈希表实现的，依赖于 hashCode 和 equals 方法来定位键的位置。

8.2 HashMap 是哈希表结构的，JDK 8 开始由数组、链表、红黑树组成的。既然有红黑树，`HashMap` 的键是否需要实现 `Comparable` 接口或者传递比较器对象呢？

答案：不需要。

解析：

HashMap 内部使用的是哈希值来决定元素的存储位置。哈希值是在 hashCode 方法中计算的，所以不需要使用 Comparable 接口或者传递比较器。
在 HashMap 中，红黑树的引入是为了优化链表的查找性能。当哈希冲突发生时，如果链表长度超过某个阈值（8），链表就会转换成红黑树。
红黑树的引入仅仅是为了提高插入和查找的效率，特别是在哈希冲突严重时，转换为红黑树会使得查找的复杂度从 O(n) 降低到 O(log n)。
由于 HashMap 只关心哈希值和 equals 方法来确定键的位置，所以并不需要 Comparable 接口或比较器对象来进行排序。

8.3 `TreeMap` 和 `HashMap` 谁的效率更高？

答案：HashMap 的效率一般更高，但在特定的情况下，TreeMap 可能会更高。

解析：

HashMap：基于哈希表实现，平均情况下 put、get 操作的时间复杂度为 O(1)。但在最坏情况下，如果发生严重的哈希冲突（例如所有元素都映射到同一个桶），就会退化成链表，时间复杂度为 O(n)。
TreeMap：基于红黑树实现，所有操作（put、get 等）的时间复杂度都是 O(log n)。即使哈希冲突严重，TreeMap 也能保持稳定的性能。

在最坏情况下，如果 TreeMap 中的节点构成链表（例如所有元素的比较结果相同），其效率会比 HashMap 更高，但这种情况非常少见。一般情况下，HashMap 的效率更高，特别是在没有严重哈希冲突的情况下。

8.4 你觉得在 Map 集合中，Java 会提供一个如果键重复了，不会覆盖的 `put` 方法吗？

答案：putIfAbsent 本身并不重要，关键是传递了“如果键重复了，是否覆盖”的思想。

解析：

putIfAbsent 方法的作用是：如果键不存在，则插入键值对；如果键已存在，则不做任何操作。这可以避免键重复时覆盖值的情况。
这个问题的背后，实际上是在思考如何控制逻辑中的“覆盖”行为。在实际编程中，我们经常需要根据不同的需求来决定是否允许覆盖现有值，putIfAbsent 提供了一种不覆盖的方案。
这里提到的“代码中的逻辑都有两面性”，可以理解为在实际开发中，我们常常需要控制一些操作的“行为”，而 boolean 和 int 类型的变量常常用来控制这种行为的不同状态。比如 replaceOld 参数控制了是否替换旧值，而 putIfAbsent 则是控制是否仅在键不存在时插入值。

8.5 三种双列集合，如何选择？（`HashMap`，`LinkedHashMap`，`TreeMap`）

答案：选择不同的集合取决于你的需求：

HashMap

：
- 默认选择：当我们只关心元素的插入和查询效率，并不关心元素的顺序时，HashMap 是最合适的选择。
- 效率：HashMap 的查询和插入操作的时间复杂度是 O(1)，适用于大多数场景。
LinkedHashMap

：
- 当需要保证元素的插入顺序时使用：LinkedHashMap 保证了插入顺序或访问顺序（通过构造器指定）。在某些场景下，我们需要根据插入顺序或访问顺序来处理元素，LinkedHashMap 便提供了这一功能。
- 适用场景：如缓存实现、LRU（最近最少使用）缓存、处理顺序敏感的数据时。
TreeMap

：
- 当需要保证元素的顺序时使用：TreeMap 会按照键的自然顺序或通过传入的比较器进行排序。如果需要一个排序的映射，TreeMap 是最好的选择。
- 适用场景：如实现排序后的数据存储，或者需要按照某种规则对元素进行顺序遍历时。

总结：

TreeMap 用于需要顺序排序的场景。
LinkedHashMap 用于需要保持元素插入顺序的场景。
HashMap 用于大多数普通的 Map 使用场景，提供了最好的性能（除非有特殊的顺序需求）。

这就是对课堂思考问题的详细解答，希望对你有帮助！如果有任何问题，随时向我提问！

9.总结

TreeMap 是通过红黑树来维护元素的有序性，并保证了操作的对数时间复杂度。它提供了一个有序的 Map，并且允许根据自然顺序或者自定义比较器进行排序。插入元素时，红黑树的平衡操作确保了树的高度不会过高，从而保持较高的性能。

如果你对其中某个部分的实现有疑问，或者希望我更详细地解释某个步骤，随时告诉我！

1. TreeMap 节点的内部属性

2. TreeMap 类中的一些成员变量

3. 构造方法

4. 添加元素

put 方法的核心部分：

5. 插入节点方法

6. 红黑树的平衡（fixAfterInsertion）