TreeSet源码分析

treeset源码分析

-----废话不多说先看一段代码

public class treesettest {
    public static void main(string[] args) {
        treeset<integer> treeset = new treeset<>();
        treeset.add(3);
        treeset.add(1);
        treeset.add(2);
        treeset.add(4);
        system.out.println(treeset);
    }
}

打印结果：

[1, 2, 3, 4]

       通过结果我们发现treeset自动帮我们把传入的数据排序了，那底层源码是如何实现的呢？

源码分析核心步骤

1.treeset源码

public class treeset{
    
  private transient navigablemap<e,object> m;
  private static final object present = new object();
    
  public treeset() {
        this(new treemap<e,object>());
  } 
  
   public boolean add(e e) {
        return m.put(e, present)==null;
    }
}

 

通过这里的代码片段，我们发现treeset的add(e e)的传入值其实保存到treemap的

key，而treemap的value只是一个object,那我们看treemap的源码的put(key,value)

2.treemap源码

class treemap{
​
   public v put(k key, v value) {
        entry<k,v> 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<k,v> parent;
        // split comparator and comparable paths
        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);
        }
        entry<k,v> e = new entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        fixafterinsertion(e);
        size++;
        modcount++;
        return null;
    }
    
    
     static final class entry<k,v> implements map.entry<k,v> {
        k key;
        v value;
        entry<k,v> left;
        entry<k,v> right;
        entry<k,v> parent;
        boolean color = black;
     }
}

 

这里我们发现do{}while{}循环里面有个compareto()不断比较，通过entry的left和right进行设置顺序

 

总结：

1.treeset存储的数据不能重复，不然会被后添加的数据覆盖，应该值保存到treemap里面的key中

2.treeset存储的数据会自动排序，应为treemap的put方法里面有自动排序的功能