How to implement TreeSet in Java? (detailed explanation)

#The content of this article is about how to implement TreeSet in Java? (Detailed explanation) has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

HashSet is implemented based on HashMap, so how is TreeSet implemented? That's right! As everyone thinks, it is implemented based on TreeMap. Therefore, the source code of TreeSet is also very simple. The main thing is to understand TreeMap.

The inheritance relationship of TreeSet

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

public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable

1. Unsurprisingly, it inherits the abstract class AbstractSet, which facilitates expansion;

2. implements a NavigableSet interface, which is similar to the NavigableMap interface and provides various navigation Method;

3. implements the Cloneable interface and can be cloned;

4. implements the Serializable interface and can be serialized;

Here we mainly look at the NavigableSet interface class:

public interface NavigableSet<E> extends SortedSet<E>

Familiar taste, inherit the SortedSet interface. SortedSet provides a method that returns a comparator:

Comparator<? super E> comparator();

, like SortedMap, supports natural sorting and custom sorting. Natural sorting requires the elements added to the Set to implement the Comparable interface, and custom sorting requires implementing a Comparator.

Source code analysis

Key point

The key point is naturally how TreeSet ensures that the elements are not repeated and the elements are ordered. As mentioned earlier, it is based on TreeMap implements it, so let’s take a look.

private transient NavigableMap<E,Object> m; // 保证有序
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object(); // 固定Value

Looking at the TreeSet source code, we found that there are only these two attributes (there is also a uid, which is not included here). Obviously, m is used to save elements, but m declares NavigableMap instead of TreeMap. It can be guessed that TreeMap should be instantiated in the construction method. Using NavigableMap here can make TreeSet more flexible. PRESENT has the same function as PRESENT in HashSet, it serves as a placeholder for a fixed Value value.
Look at the add and remove methods again:

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

is the same as the implementation of HashSet, and also uses the Key-Value key value pair saved by Map. Characteristics that will be repeated.

Constructor

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

public TreeSet() {
        this(new TreeMap<>()); // 默认自然排序的TreeMap
    }
public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // 自定义比较器的TreeMap
    }
public TreeSet(Collection<? extends E> c) {
        this(); // 还是用的默认
        addAll(c); // 将元素一个一个添加到TreeMap中
    }
 public TreeSet(SortedSet<E> s) {
        this(s.comparator()); // 使用传入的SortedSet的比较器
        addAll(s); // 一个一个添加元素
    }

A naturally ordered TreeMap is instantiated by default. Of course, we can customize the comparator.

Track 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; // 强转成TreeMap
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样
                map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法
                return true;
            }
        }
        return super.addAll(c);
    }

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) {
        }
    }

You should be familiar with buildFromSorted. It has been analyzed in the TreeMap article. This method constructs the passed set elements into a red-black tree in which the bottom node is red and the other nodes are black.

Navigation method

Since NavigableSet is implemented, various navigation methods are naturally indispensable. Their implementation is also very simple, just call the navigation method corresponding to m directly. For example:

public E first() {
        return m.firstKey(); // 返回第一个元素
    }
public E lower(E e) {
        return m.lowerKey(e); // 返回小于e的第一个元素
    }
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前几个元素构成子集
    }
public E pollFirst() { // 弹出第一个元素
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
public NavigableSet<E> descendingSet() { // 倒排Set
        return new TreeSet<>(m.descendingMap());
    }
......

What needs to be noted here is the method that returns a sub-set, for example: headSet. The returned subcollection can add and delete elements, but there are boundary restrictions, for example.

        // 前面构造了一个存储Int的Set
        // 3、5、7、9
        SortedSet<Integer> subSet = intSet.headSet(8); // 最大值7，超过7越界
        for (Integer sub : subSet) {
            System.out.println(sub);
        }
        subSet.add(2);
//        subSet.add(8); // 越界了
        subSet.remove(3);
        for (Integer sub : subSet) {
            System.out.println(sub);
        }

TreeSet also supports reverse order output, because there is an implementation of descendingIterator:

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

Summary

1. ##TreeSet is implemented based on TreeMap, supports natural sorting and custom sorting, and can output in reverse order;

2. TreeSet does not allow null values;

3. TreeSet is not thread-safe. SortedSet can be used in a multi-threaded environment. s = Collections.synchronizedSortedSet(new TreeSet(.. .));

The above is the detailed content of How to implement TreeSet in Java? (detailed explanation). For more information, please follow other related articles on the PHP Chinese website!