The problem
(1) Does TreeSet really use TreeMap to store elements?
(2) Is TreeSet in order?
(3) What is the difference between TreeSet and LinkedHashSet?
Introduction to the
The underlying TreeSet is a Set implemented in TreeMap, so it is ordered and also non-thread-safe.
Source code analysis
After studying HashSet and LinkedHashSet, we have basically mastered the Set implementation.
So, also no nonsense, directly on the source code:
package java.util;
// TreeSet implements the NavigableSet interface, so it is ordered
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable.java.io.Serializable
{
// Elements are stored in NavigableMap
// Note that it is not necessarily TreeMap
private transient NavigableMap<E,Object> m;
// A virtual element that is stored as a value in the map
private static final Object PRESENT = new Object();
// Store elements directly using the NavigableMap passed in
// This is not a deep copy. If there are additions or deletions in the external map, they will be reflected here
// Also, this method is not public, indicating that it can only be used by the same package
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
// Use TreeMap to initialize
public TreeSet(a) {
this(new TreeMap<E,Object>());
}
// Initialize using TreeMap with comparator
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
// Add all the elements in collection C to the TreeSet
public TreeSet(Collection<? extends E> c) {
this(a); addAll(c); }// Add all the elements in SortedSet to TreeSet
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
/ / the iterator
public Iterator<E> iterator(a) {
return m.navigableKeySet().iterator();
}
// Reverse iterator
public Iterator<E> descendingIterator(a) {
return m.descendingKeySet().iterator();
}
// Return a new TreeSet in reverse order
public NavigableSet<E> descendingSet(a) {
return new TreeSet<>(m.descendingMap());
}
// Number of elements
public int size(a) {
return m.size();
}
// Check whether it is null
public boolean isEmpty(a) {
return m.isEmpty();
}
// Determine whether an element is included
public boolean contains(Object o) {
return m.containsKey(o);
}
// Add the element and call map's put() method with value PRESENT
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
// Delete elements
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
// Clear all elements
public void clear(a) {
m.clear();
}
// Add all the elements in collection C
public boolean addAll(Collection<? extends E> c) {
// If certain conditions are met, the addAllForTreeSet() method of TreeMap is directly called to add elements
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceofTreeMap) { SortedSet<? extends E> set = (SortedSet<? extends E>) c; TreeMap<E,Object> map = (TreeMap<E, Object>) m; Comparator<? > cc = set.comparator(); Comparator<?super E> mc = map.comparator();
if(cc==mc || (cc ! =null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true; }}// If the above conditions are not met, addAll() of the parent class is called to add elements one by one through a traversal
return super.addAll(c);
}
// Subset (method in NavigableSet)
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
E toElement, boolean toInclusive) {
return new TreeSet<>(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
// set (NavigableSet)
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive));
}
// End set (NavigableSet)
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
// subset (method in SortedSet interface)
public SortedSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
}
// header set (method in SortedSet interface)
public SortedSet<E> headSet(E toElement) {
return headSet(toElement, false);
}
// tail set (SortedSet method)
public SortedSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
}
/ / the comparator
public Comparator<? super E> comparator() {
return m.comparator();
}
// Return the smallest element
public E first(a) {
return m.firstKey();
}
// Return the largest element
public E last(a) {
return m.lastKey();
}
// Return the largest element less than e
public E lower(E e) {
return m.lowerKey(e);
}
// Returns the largest element less than or equal to e
public E floor(E e) {
return m.floorKey(e);
}
Return the smallest element greater than or equal to e
public E ceiling(E e) {
return m.ceilingKey(e);
}
Return the smallest element greater than e
public E higher(E e) {
return m.higherKey(e);
}
// Pop up the smallest element
public E pollFirst(a) { Map.Entry<E,? > e = m.pollFirstEntry();return (e == null)?null : e.getKey();
}
public E pollLast(a) { Map.Entry<E,? > e = m.pollLastEntry();return (e == null)?null : e.getKey();
}
// Clone method
@SuppressWarnings("unchecked")
public Object clone(a) {
TreeSet<E> clone;
try {
clone = (TreeSet<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
clone.m = new TreeMap<>(m);
return clone;
}
// serialize the write method
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden stuff
s.defaultWriteObject();
// Write out Comparator
s.writeObject(m.comparator());
// Write out size
s.writeInt(m.size());
// Write out all elements in the proper order.
for (E e : m.keySet())
s.writeObject(e);
}
// Serialize the write method
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// Read in Comparator
@SuppressWarnings("unchecked")
Comparator<? super E> c = (Comparator<? super E>) s.readObject();
// Create backing TreeMap
TreeMap<E,Object> tm = new TreeMap<>(c);
m = tm;
// Read in size
int size = s.readInt();
tm.readTreeSet(size, s, PRESENT);
}
// A separable iterator
public Spliterator<E> spliterator(a) {
return TreeMap.keySpliteratorFor(m);
}
// serialize the ID
private static final long serialVersionUID = -2479143000061671589L;
}
Copy the codeThe source code is relatively simple, the basic is to call map corresponding methods.
conclusion
(1) TreeSet uses NavigableMap to store elements.
(2) TreeSet is ordered;
(3) TreeSet is non-thread-safe;
(4) TreeSet implements NavigableSet, and NavigableSet inherits from SortedSet;
(5) TreeSet implements SortedSet interface; (Tong Brother was asked the difference between a TreeSet and a SortedSet when he was young.)
eggs
(1) From previous learning, we know that TreeSet and LinkedHashSet are both ordered, so how are they different?
LinkedHashSet does not implement SortedSet interface, and its orderness mainly depends on the orderness of LinkedHashMap, so its orderness refers to the orderness guaranteed by insertion order;
TreeSet implements the SortedSet interface, which relies mainly on the ordering of NavigableMap, which in turn inherits from the SortedMap. The ordering of this interface refers to the order guaranteed by the natural ordering of keys. The natural ordering of keys can be implemented either by the key implementing the Comparable interface or by the constructor passing in the Comparator.
(2) Does TreeSet really use TreeMap to store elements?
TreeSet actually uses NavigableMap to store elements. Most of the time the map is TreeMap, but not all of the time.
Because one constructor is TreeSet(NavigableMap
m), and this is a non-public method, we can see that this constructor is used in our own class, such as the following:
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new TreeSet<>(m.tailMap(fromElement, inclusive));
}
Copy the codeThe tailMap() method calls TreeMap:
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
return new AscendingSubMap<>(this.false, fromKey, inclusive,
true.null.true);
}
Copy the codeAs you can see, AscendingSubMap is returned. What is the inheritance chain for this class?
As you can see, this class does not inherit TreeMap, but you can see from the source code analysis that this class is a combination of TreeMap. It is also related to TreeMap, but not inherited.
So the underlying TreeSet is not implemented entirely using TreeMap, but rather NavigableMap.
Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
