输出结果：

2022-07-11 18:02:23,871 [INFO] main: {3=sss, 2=ss}

6 重要方法分析

6.1 get方法分析

（实际调用getEntry(Object key)）

• get(Object key)方法是对接口Map的方法实现
• get(Object key)方法转为对getEntry(Object key)方法的实现分析：算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry，再返回entry的value。

源码分析如下：

public V get(Object key) {
    Entry<K,V> p = getEntry(key);  //根据key找到entry，再返回其value
    return (p==null ? null : p.value);
}
//重点分析该方法
final Entry<K,V> getEntry(Object key) {
    if (comparator != null)
        return getEntryUsingComparator(key); 
    if (key == null)
        throw new NullPointerException();  //key非空校验
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;  //自然顺序，使用Comparable的排序接口
    Entry<K,V> p = root; 
    while (p != null) {  //从根节点开始 循环遍历
        int cmp = k.compareTo(p.key);  //compareTo：左边减去右边
        if (cmp < 0) //参数key值小于父节点key
            p = p.left; //取左子节点
        else if (cmp > 0)
            p = p.right;  //参数key值大于父节点key，取右子节点
        else
            return p;  //key相等，则直接返回当前entry
    }
    return null;
}

查询方法说明：

1. 在while循环外，创建动态游标节点，游标首次指向root节点，以游标!=null作为循环条件
2. 在while循环内，根据compareTo结果，取游标的左子节点或右子节点，作为新的游标
3. 找到满足k.compareTo(p.key) == 0的entry，退出循环

getEntryUsingComparator源码：

//提供自定义排序器的查询找方法，原理类似
final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key); //cpr.compare 第一个参数减去第二个参数
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

6.2 put方法分析

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 情况一：根节点为空，将当前key value作为root
    if (t == null) {
        compare(key, key); //key为null则抛异常
        root = new Entry<>(key, value, null);//初始化root
        size = 1;  //叶子个数+1
        modCount++; // 结构修改次数自增
        return null;  //新叶子，所以old value 为空
    }
    // 情况二：如果找到key相同的，则更新value ，过程类似get方法
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    //情况三：没有相同的key，则添加新叶子。
    //经过上面的两种遍历，完成了二分法查找，找到适合插入的地方：parent。
    Entry<K,V> e = new Entry<>(key, value, parent); //创建新的entry
    //确定新增叶子作为parent的左孩子还是右孩子，插入的动作完成
    if (cmp < 0)  
        parent.left = e;  
    else
        parent.right = e;
    fixAfterInsertion(e);  //插入完成后，对二叉树进行调整
    size++;
    modCount++;
    return null;
}
//这个方法实际上是对key做null检查，如果是null会抛出异常（测试代码验证过）
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
  }

put方法说明：