TreeMap的实现原理

实现是通过红黑二叉树来实现的，这个看他的Entry的数据结构就可以体现出来。

 static final class Entry<K, V> implements java.util.Map.Entry<K, V> {
        K key;
        V value;
        TreeMap.Entry<K, V> left;
        TreeMap.Entry<K, V> right;
        TreeMap.Entry<K, V> parent;
        boolean color = true;

        Entry(K var1, V var2, TreeMap.Entry<K, V> var3) {
            this.key = var1;
            this.value = var2;
            this.parent = var3;
        }

在插入K，V时他会根据红黑树的特性，根据compare方法返回的值在left,right中遍历找到对应的位置插入Entry或替换V。

public V put(K var1, V var2) {
        TreeMap.Entry var3 = this.root;
        if (var3 == null) {
            this.compare(var1, var1);
            this.root = new TreeMap.Entry(var1, var2, (TreeMap.Entry)null);
            this.size = 1;
            ++this.modCount;
            return null;
        } else {
            Comparator var6 = this.comparator;
            int var4;
            TreeMap.Entry var5;
            if (var6 != null) {
                 //根据Comparator的比较结果在红黑树中确定Key的位置插入或者替换Value
                do {
                    var5 = var3;
                    var4 = var6.compare(var1, var3.key);
                    if (var4 < 0) {
                        var3 = var3.left;
                    } else {
                        if (var4 <= 0) {
                            return var3.setValue(var2);
                        }
                        var3 = var3.right;
                    }
                } while(var3 != null);
            } else {
                   //这里是Key实现了Comparable接口，在红黑树中确定Key的位置插入或者替换Value
                if (var1 == null) {
                    throw new NullPointerException();
                }

                Comparable var7 = (Comparable)var1;

                do {
                    var5 = var3;
                    var4 = var7.compareTo(var3.key);
                    if (var4 < 0) {
                        var3 = var3.left;
                    } else {
                        if (var4 <= 0) {
                            return var3.setValue(var2);
                        }

                        var3 = var3.right;
                    }
                } while(var3 != null);
            }
           //后面是插入元素后可能导致红黑树不自平衡，重新是红黑树平衡
            TreeMap.Entry var8 = new TreeMap.Entry(var1, var2, var5);
            if (var4 < 0) {
                var5.left = var8;
            } else {
                var5.right = var8;
            }
      
            this.fixAfterInsertion(var8);
            ++this.size;
            ++this.modCount;
            return null;
        }
    }

TreeSet 是根据TreeMap来实现的，直接看他的构造函数就可以只知道

，他的Set性质是通过Map的Key唯一来实现的。

public TreeSet() {
        this((NavigableMap)(new TreeMap()));
    }

    public TreeSet(Comparator<? super E> var1) {
        this((NavigableMap)(new TreeMap(var1)));
    }

    public TreeSet(Collection<? extends E> var1) {
        this();
        this.addAll(var1);
    }

// 添加元素的方法是通过，把元素通过Map的Key的方式添加进map中
  public boolean add(E var1) {
        return this.m.put(var1, PRESENT) == null;
    }