TreeMap源码分析

一.TreeMap的特性

TreeMap是有序的，可以自定义排序规则，如果不指定则按照默认的规则排序

二.TreeMap的底层结构

采用了红黑树作为底层的数据结构

三.源码分析

public V put(K key, V value) {

//头结点

Entry t =root;

//头结点为空的情况下

    if (t ==null) {

       compare(key, key); // type (and possibly null) check

        root =new Entry<>(key, value, null);

        size =1;

        modCount++;

        return null;

    }

    int cmp;

    Entry parent;

    // split comparator and comparable paths

    Comparator 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 k = (Comparable) 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);

    }

     Entry e =new Entry<>(key, value, parent);

    if (cmp <0)

        parent.left = e;

else

        parent.right = e;

     //插入节点后，调整红黑树

      fixAfterInsertion(e);

    size++;

    modCount++;

    return null;

}