preface

In the last article, we looked at HashSet, which is implemented based on HashMap. How will TreeSet be implemented? That’s right! As you might expect, it’s based on TreeMap. Therefore, the source code of TreeSet is also very simple, mainly to understand TreeMap.

TreeSet inheritance

As usual, let’s look at the inheritance of the TreeSet class:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable.java.io.Serializable
Copy the code
  1. Inherit abstract class AbstracSet, easy to extend;
  2. NavigableSet implements a NavigableSet interface, similar to NavigableMap, which provides various navigation methods.
  3. Cloneable interface can be cloned;
  4. Serializable interface can be serialized;

NavigableSet interface class

public interface NavigableSet<E> extends SortedSet<E>
Copy the code

Familiar taste, inheriting SortedSet interface. SortedSet provides a method to return a comparator:

Comparator<? super E> comparator();
Copy the code

Like SortedMap, both natural and custom sorts are supported. Natural ordering requires that elements added to a Set implement the Comparable interface, and custom ordering requires that a Comparator be implemented.

Source code analysis

The key point

The key point, of course, is how TreeSet ensures that elements are not duplicated and that elements are ordered. It’s based on TreeMap, so let’s take a look.

private transient NavigableMap<E,Object> m; // Ensure order

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object(); / / a fixed Value
Copy the code

A review of the TreeSet source code shows that these are the only two attributes (and a UID, which is not included here). Obviously, M is used to store elements, but M declares NavigableMap instead of TreeMap. As you can guess, TreeMap should be instantiated in the constructor, where NavigableMap makes TreeSet more flexible. PRESENT, like PRESENT in HashSet, is used as a placeholder for a fixed Value. Look again at the add and remove methods:

public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }
Copy the code

Like the implementation of HashSet, it takes advantage of the fact that key-value pairs saved by Map do not have duplicate keys.

The constructor

Sure enough, TreeMap in TreeSet is initialized in the constructor.

public TreeSet(a) {
        this(new TreeMap<>()); // TreeMap is naturally sorted by default
    }

public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // TreeMap for a custom comparator
    }
    
public TreeSet(Collection<? extends E> c) {
        this(a);// Use the default
        addAll(c); // Add elements one by one to TreeMap
    }
 
 public TreeSet(SortedSet<E> s) {
        this(s.comparator()); // Use the comparator of the SortedSet passed in
        addAll(s); // Add elements one by one
    }   
Copy the code

A naturally sorted TreeMap is instantiated by default, and of course we can customize the comparator. Trace the addAll method here:

public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m; // Strong to TreeMapComparator<? > cc = set.comparator(); Comparator<?super E> mc = map.comparator();
            if(cc==mc || (cc ! =null && cc.equals(mc))) { // Make sure that the set and map comparators are the same
                map.addAllForTreeSet(set, PRESENT); // TreeMap is a method specifically prepared for TreeSet
                return true; }}return super.addAll(c);
    }
Copy the code

The addAllForTreeSet method of TreeMap is called:

void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
        }
    }
Copy the code

You should be familiar with buildFromSorted, which you analyzed in the TreeMap article. The method constructs a red-black tree in which the lowest node is red and all other nodes are black.

Navigation methods

Now that NavigableSet is implemented, various navigation methods will naturally follow. Their implementation is also very simple, just call the navigation method corresponding to M. Such as:

public E first(a) {
        return m.firstKey(); Return the first element
    }
    
public E lower(E e) {
        return m.lowerKey(e); // Return the first element less than e
    }
    
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive)); // Take the first few elements to form a subset
    }
    
public E pollFirst(a) { // Pop up the first elementMap.Entry<E,? > e = m.pollFirstEntry();return (e == null)?null : e.getKey();
    }

public NavigableSet<E> descendingSet(a) { / / inverted Set
        return newTreeSet<>(m.descendingMap()); }...Copy the code

Note that the method of returning a subset, for example, headSet. The returned subsets can add and remove elements, but with boundaries, for example.

        // create a Set that stores ints
        // 3, 5, 7, 9
        SortedSet<Integer> subSet = intSet.headSet(8); // The maximum value is 7, exceeding 7 is out of bounds
        for (Integer sub : subSet) {
            System.out.println(sub);
        }

        subSet.add(2);
// subSet.add(8); / / crossing the line
        subSet.remove(3);
        for (Integer sub : subSet) {
            System.out.println(sub);
        }
Copy the code

TreeSet also supports reverse output because of the descendingIterator implementation:

public Iterator<E> descendingIterator(a) {
        return m.descendingKeySet().iterator();
    }
Copy the code

conclusion

  1. TreeSet is implemented based on TreeMap. It supports both natural and custom sorting and can be output in reverse order.
  2. TreeSet does not allow null values;
  3. TreeSet is not thread-safe and can be used in multithreaded environmentsSortedSet s = Collections.synchronizedSortedSet(new TreeSet(...) );

Pay attention to wechat public number, the latest technology dry goods real-time push