【零基础学java】（TreeMap源码解析，包含面试题）

前言

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

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

  private transient Entry<K,V> root;    //根节点

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

空参构造

 //空参构造就是没有传递比较器对象      public TreeMap() {         comparator = null;     }

带参构造

//带参构造就是传递了比较器对象。     public TreeMap(Comparator<? super K> comparator) {         this.comparator = comparator;     }

添加元素

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

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

红黑规则底层源码    

    private void fixAfterInsertion(Entry<K,V> 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<K,V> 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<K,V> 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;   //把根节点设置为黑色     }

面试问题

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

此时是不需要重写的。

2HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。

既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？ 不需要的。 因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的

3TreeMap和HashMap谁的效率更高？

如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高 但是这种情况出现的几率非常的少。 一般而言，还是HashMap的效率要更高。

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

此时putIfAbsent本身不重要。 传递一个思想：   代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生。     那么该逻辑一定会有B面。     习惯：         boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值         int类型的变量控制，一般至少有三面，因为int可以取多个值。

5三种双列集合，以后如何选择？  HashMap LinkedHashMap TreeMap  默认：HashMap（效率最高） 如果要保证存取有序：LinkedHashMap 如果要进行排序：TreeMap