Java集合框架——Collection接口

Java集合框架总览图

所有的集合类都位于java.util包下。Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口，这两个接口又包含了一些子接口或实现类。
集合接口：Iterator、ListIterator、Collection、List、Set、SortedSet、Queue、Map、SortedMap，表示不同集合类型，是结合框架的基础。
抽象类：AbstractCollection、AbstractList、AbstractSequentialList、AbstractSet、AbstractMap，对集合接口的部分实现，可扩展为自定义集合。
实现类：ArrayList、LinkedList、HashSet、LinkedHashSet、TreeSet、HashMap、LinkedHashMap、TreeMap，对接口的具体实现。
Collection接口是一组允许重复的对象。
Set接口继承Collection，集合元素不重复。
List接口继承Collection，允许重复，维护元素插入顺序。
Map接口是键-值对象，与Collection接口没有什么关系。
Set、List和Map可以看作集合的三大类：

List集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。

Set集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问。

Map集合中保存Key-Value对形式的元素，访问时只能根据每项元素的key来访问其value。

总体分析

Collection是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。Collection包含了List和Set两大分支。List是一个有序的队列，每一个元素有它的索引。List的实现类有ArrayList、LinkedList、Vector、Stack。Set是一个不允许有重复元素的集合。Set的实现类有HashSet和TreeSet，其中HashSet依赖于HashMap，实际上就是通过HashMap来实现的，TreeSet依赖于TreeMap，实际上是通过TreeMap实现的。
Map是一个映射接口，即key-value键值对。AbstractMap是个抽象类，它实现了接口中的大部分API，而HashMap、TreeMap、WeakHashMap都是继承于AbstractMap。HashTable虽然继承于Dictionary，但它实现了Map接口。
Iterator是遍历集合的工具，即我们通常通过Iterator迭代器来遍历集合。Collection的实现类都要实现iterator()函数，返回一个Iterator对象。
Enumeration是JDK1.0引入的抽象类，作用和Iterator一样，也是遍历集合，但是Enumeration的功能要比Iterator少，Enumeration只能在HashTable、Vector、Stack中使用。
Collections和Arrays是操作数组、集合的两个工具类。

Collection接口

Collection接口是处理对象集合的根接口，其中定义了很多对元素进行操作的方法。Collection接口有两个主要的子接口List和Set。Collection接口中的方法如下：

Collection接口中的方法

其中，有几个比较常用的方法，比如方法add()添加一个元素到集合中，addAll()将指定的集合中的所有元素添加到集合中去，contains()方法检测集合中是否包含有指定的元素，toArray()方法返回一个标识集合的数组。

List接口

List接口代表一个有序集合，集合中每个元素都有对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

ArrayList实现原理

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规范的元素插入甚至null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作，所以，add操作以分摊的固定时间运行，也就是说，添加n个元素需要O（n）时间。ArrayList适合随机访问，同时是非同步的。

// 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
// 底层使用数组保存所有元素
transient Object[] elementData;

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    ensureCapacityInternal(size + 1); 
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
       grow(minCapacity);
}
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。 fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

private class Itr implements Iterator<E> {
        protected int limit = ArrayList.this.size;
        int cursor;      
        int lastRet = -1;
        int expectedModCount = modCount;
        public boolean hasNext() {
            return cursor < limit;
        }
        @SuppressWarnings("unchecked")
        public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
                limit--;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            cursor = i;
            lastRet = i - 1;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

LinkedList实现原理

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。

LinkedList底层的数据结构是基于双向链表的，该数据结构我们称为节点，顺序存储。双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。

transient int size;
transient LinkedList.Node<E> first;
transient LinkedList.Node<E> last;
private static class Node<E> {
    E item;
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;
    Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
        this.item = var2;
        this.next = var3;
        this.prev = var1;
    }
}

接下来看一看LinkedList是怎样实现随机访问的。

public E get(int var1) {
    this.checkElementIndex(var1);
    return this.node(var1).item;
}
LinkedList.Node<E> node(int var1) {
    LinkedList.Node var2;
    int var3;
  	// 当index < size/2时，从列表首节点向后查找
    if(var1 < this.size >> 1) {
        var2 = this.first;
        for(var3 = 0; var3 < var1; ++var3) {
            var2 = var2.next;
        }
        return var2;
    } else {  //当index >= size/2时，从列表尾节点向前查找
        var2 = this.last;
        for(var3 = this.size - 1; var3 > var1; --var3) {
            var2 = var2.prev;
        }
        return var2;
    }
}

该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index >= size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历。

LinkedList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

private class ListItr implements ListIterator<E> {
        private LinkedList.Node<E> lastReturned;
        private LinkedList.Node<E> next;
        private int nextIndex;
        private int expectedModCount;
        ListItr(int var2) {
            this.expectedModCount = LinkedList.this.modCount;
            this.next = var2 == LinkedList.this.size?null:LinkedList.this.node(var2);
            this.nextIndex = var2;
        }
        public E next() {
            this.checkForComodification();
            if(!this.hasNext()) {
                throw new NoSuchElementException();
            } else {
                this.lastReturned = this.next;
                this.next = this.next.next;
                ++this.nextIndex;
                return this.lastReturned.item;
            }
        }
        public E previous() {
            this.checkForComodification();
            if(!this.hasPrevious()) {
                throw new NoSuchElementException();
            } else {
                this.lastReturned = this.next = this.next == null?LinkedList.this.last:this.next.prev;
                --this.nextIndex;
                return this.lastReturned.item;
            }
        }
        public void remove() {
            this.checkForComodification();
            if(this.lastReturned == null) {
                throw new IllegalStateException();
            } else {
                LinkedList.Node var1 = this.lastReturned.next;
                LinkedList.this.unlink(this.lastReturned);
                if(this.next == this.lastReturned) {
                    this.next = var1;
                } else {
                    --this.nextIndex;
                }
                this.lastReturned = null;
                ++this.expectedModCount;
            }
        }
        public void set(E var1) {
            if(this.lastReturned == null) {
                throw new IllegalStateException();
            } else {
                this.checkForComodification();
                this.lastReturned.item = var1;
            }
        }
        public void add(E var1) {
            this.checkForComodification();
            this.lastReturned = null;
            if(this.next == null) {
                LinkedList.this.linkLast(var1);
            } else {
                LinkedList.this.linkBefore(var1, this.next);
            }
            ++this.nextIndex;
            ++this.expectedModCount;
        }
        public void forEachRemaining(Consumer<? super E> var1) {
            Objects.requireNonNull(var1);
            while(LinkedList.this.modCount == this.expectedModCount && this.nextIndex < LinkedList.this.size) {
                var1.accept(this.next.item);
                this.lastReturned = this.next;
                this.next = this.next.next;
                ++this.nextIndex;
            }
            this.checkForComodification();
        }
        final void checkForComodification() {
            if(LinkedList.this.modCount != this.expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
  	...
    }

这里列出了iterate的一些相关的方法，每次一个线程调用这些方法的时候会进行checkForComodification()，checkForComodification()方法会在多线程高并发访问链表冲突的时候抛出ConcurrentModificationException异常。

Vector实现原理

与ArrayList相似，但是Vector是同步的，所以说Vector是线程安全的动态数组，但是速度慢，在每个方法前都加上了锁（即synchronized关键字）。它的操作与ArrayList几乎一样。

Vector的数据结构和ArrayList差不多，它包含了3个成员变量：elementData , elementCount， capacityIncrement。

elementData 是”Object[]类型的数组”，它保存了添加到Vector中的元素。elementData是个动态数组，如果初始化Vector时，没指定动态数组的大小，则使用默认大小10。随着Vector中元素的增加，Vector的容量也会动态增长，capacityIncrement是与容量增长相关的增长系数。elementCount 是动态数组的实际大小。capacityIncrement 是动态数组的增长系数。如果在创建Vector时，指定了capacityIncrement的大小；则，每次当Vector中动态数组容量增加时，增加的大小都是capacityIncrement。

当我们构造Vecotr时，若使用默认构造函数，则Vector的默认容量大小是10，默认容量增长系数是0。当Vector容量不足以容纳全部元素时，Vector的容量会增加。若容量增加系数 >0，则将容量的值增加“容量增加系数”；否则，将容量大小增加一倍。Vector的克隆函数，即是将全部元素克隆到一个数组中。

Vector支持4种遍历方式。

①通过迭代器遍历。
1
2
3
4
5
Integer value = null;
int size = vec.size();
for (int i=0; i<size; i++) {
value = (Integer)vec.get(i);
}
②随机访问，通过索引值去遍历。
1
2
3
4
5
Integer value = null;
int size = vec.size();
for (int i=0; i<size; i++) {
value = (Integer)vec.get(i);
}
③foreach循环
1
2
3
4
Integer value = null;
for (Integer integ:vec) {
value = integ;
}
④Enumeration遍历
1
2
3
4
5
Integer value = null;
Enumeration enu = vec.elements();
while (enu.hasMoreElements()) {
value = (Integer)enu.nextElement();
}
遍历Vector，使用索引的随机访问方式最快，使用迭代器最慢。考虑到效率问题，建议使用第二种方式。

Stack实现原理

Stack继承自Vector，包含Vector中的全部API，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。

public class Stack<E> extends Vector<E> {
    private static final long serialVersionUID = 1224463164541339165L;
    public Stack() {
    }
	// 将元素推入栈中,是通过将元素追加到数组的末尾中
    public E push(E var1) {
        this.addElement(var1);
        return var1;
    }
	// 取出栈顶元素，不执行删除，是返回数组末尾的元素
    public synchronized E pop() {
        int var2 = this.size();
        Object var1 = this.peek();
        this.removeElementAt(var2 - 1);
        return var1;
    }
	// 取出栈顶元素，并将该元素从栈中删除，是取出数组末尾的元素，然后该元素从数组中删除
    public synchronized E peek() {
        int var1 = this.size();
        if(var1 == 0) {
            throw new EmptyStackException();
        } else {
            return this.elementAt(var1 - 1);
        }
    }
	// 测试堆栈是否为空
    public boolean empty() {
        return this.size() == 0;
    }
	// 检测一个元素在堆栈中的位置
    public synchronized int search(Object var1) {
        int var2 = this.lastIndexOf(var1);
        return var2 >= 0?this.size() - var2:-1;
    }
}

Set接口

Set是一种不包括重复元素的Collection。它维持它自己的内部排序，所以随机访问没有任何意义。与List一样，它同样允许null的存在但是仅是一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，同样要注意任何可变对象，如果在对集合中元素进行操作时，导致e1.equals(e2) == true，则必定会产生某些问题。Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树型集TreeSet。

HashSett实现原理

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet 的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成。

HashSet的实现方式大致如下，通过一个HashMap存储元素，元素是存放在HashMap的Key中，而Value统一使用一个Object对象。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E, Object> map;
  	// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
    private static final Object PRESENT = new Object();
    /** 
     * 默认的无参构造器，构造一个空的HashSet。 
     * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
     */ 
    public HashSet() {
        this.map = new HashMap();
    }
    public HashSet(Collection<? extends E> var1) {
        this.map = new HashMap(Math.max((int)((float)var1.size() / 0.75F) + 1, 16));
        this.addAll(var1);
    }
    public HashSet(int var1, float var2) {
        this.map = new HashMap(var1, var2);
    }
    public HashSet(int var1) {
        this.map = new HashMap(var1);
    }
    HashSet(int var1, float var2, boolean var3) {
        this.map = new LinkedHashMap(var1, var2);
    }
    public Iterator<E> iterator() {
        return this.map.keySet().iterator();
    }
    /** 
     * 返回此set中的元素的数量（set的容量）。 
     * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。 
     * @return 此set中的元素的数量（set的容量）。 
     */  
    public int size() {
        return this.map.size();
    }
    public boolean isEmpty() {
        return this.map.isEmpty();
    }
    /** 
     * 如果此set包含指定元素，则返回true。 
     * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e)) 
     * 的e元素时，返回true。 
     * 底层实际调用HashMap的containsKey判断是否包含指定key。 
     * @object var 在此set中的存在已得到测试的元素。 
     * @return 如果此set包含指定元素，则返回true。 
     */  
    public boolean contains(Object var1) {
        return this.map.containsKey(var1);
    }
    public boolean add(E var1) {
        return this.map.put(var1, PRESENT) == null;
    }
    public boolean remove(Object var1) {
        return this.map.remove(var1) == PRESENT;
    }
    public void clear() {
        this.map.clear();
    }
	// 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。
    public Object clone() {
        try {
            HashSet var1 = (HashSet)super.clone();
            var1.map = (HashMap)this.map.clone();
            return var1;
        } catch (CloneNotSupportedException var2) {
            throw new InternalError(var2);
        }
    }
    public Spliterator<E> spliterator() {
        return new KeySpliterator(this.map, 0, -1, 0, 0);
    }
  
  	...
}

HashSet是非同步的，如果多个线程同时访问一个哈希set，而其中至少一个线程修改了该set，那么它必须保持外部同步。 HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。

LinkedHashSet实现原理

LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, Serializable {
    private static final long serialVersionUID = -2851667679971038690L;
    public LinkedHashSet(int var1, float var2) {
        super(var1, var2, true);
    }
    public LinkedHashSet(int var1) {
        super(var1, 0.75F, true);
    }
    public LinkedHashSet() {
        super(16, 0.75F, true);
    }
    public LinkedHashSet(Collection<? extends E> var1) {
        super(Math.max(2 * var1.size(), 11), 0.75F, true);
        this.addAll(var1);
    }
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 17);
    }
}

在父类HashSet中，专为LinkedHashSet提供的构造方法如下，该方法为包访问权限，并未对外公开。

1
2
3

HashSet(int var1, float var2, boolean var3) {
    this.map = new LinkedHashMap(var1, var2);
}

对于LinkedHashSet而言，它继承于HashSet、又基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承于HashSet，其所有的方法操作上又与HashSet相同，因此LinkedHashSet 的实现上非常简单，只提供了四个构造方法，并通过传递一个标识参数，调用父类的构造器，底层构造一个LinkedHashMap来实现，在相关操作上与父类HashSet的操作相同，直接调用父类HashSet的方法即可。

LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

LinkedHashSet实现不是同步的。如果多个线程同时访问链接的哈希Set，而其中至少一个线程修改了该Set，则它必须保持外部同步。

TreeSet实现原理

TreeSet是一个有序集合，其底层是基于TreeMap实现的，非线程安全。TreeSet可以确保集合元素处于排序状态，其支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器，若用户需要使用自定义的比较器，则需要使用带比较器的参数。

TreeSet集合不是通过hashcode和equals函数来比较元素的。它是通过compare或者compareTo函数来判断元素是否相等。compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable {
    private transient NavigableMap<E, Object> m;
    private static final Object PRESENT = new Object();
    private static final long serialVersionUID = -2479143000061671589L;
    TreeSet(NavigableMap<E, Object> var1) {
        this.m = var1;
    }
    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);
    }
    public TreeSet(SortedSet<E> var1) {
        this(var1.comparator());
        this.addAll(var1);
    }
    public Iterator<E> iterator() {
        return this.m.navigableKeySet().iterator();
    }
    public Iterator<E> descendingIterator() {
        return this.m.descendingKeySet().iterator();
    }
    public NavigableSet<E> descendingSet() {
        return new TreeSet(this.m.descendingMap());
    }
    public boolean addAll(Collection<? extends E> var1) {
        if(this.m.size() == 0 && var1.size() > 0 && var1 instanceof SortedSet && this.m instanceof TreeMap) {
            SortedSet var2 = (SortedSet)var1;
            TreeMap var3 = (TreeMap)this.m;
            Comparator var4 = var2.comparator();
            Comparator var5 = var3.comparator();
            if(var4 == var5 || var4 != null && var4.equals(var5)) {
                var3.addAllForTreeSet(var2, PRESENT);
                return true;
            }
        }
        return super.addAll(var1);
    }
    public Comparator<? super E> comparator() {
        return this.m.comparator();
    }
    public Object clone() {
        TreeSet var1;
        try {
            var1 = (TreeSet)super.clone();
        } catch (CloneNotSupportedException var3) {
            throw new InternalError(var3);
        }
        var1.m = new TreeMap(this.m);
        return var1;
    }
    public Spliterator<E> spliterator() {
        return TreeMap.keySpliteratorFor(this.m);
    }
  
  	...
}

与HashSet完全类似，TreeSet里面绝大部分方法都是直接调用TreeMap方法来实现的。