横扫Java Collections系列 —— TreeSet

简言之， TreeSet 是一个继承 AbstractSet 类的有序集合类，实现了 NavigableSet 接口，该接口中提供了针对给定搜索目标返回最接近匹配项的系列导航方法。主要有以下特点：

• 其中保存的元素具有唯一性
• 不保证元素的插入顺序
• 对元素进行升序排序
• 非线程安全

在 TreeSet 中，元素按照其自然序升序排列和存储，内部使用了一种自平衡二叉搜索树，也就是红黑树。红黑树作为自平衡二叉搜索树，其中每个节点都额外保有一个比特，用来指示当前的节点颜色是红色或者黑色。这些“颜色”比特在后续的插入或者删除中，有助于确保树结构保持平衡。

创建 TreeSet 实例很简单：

Set<String> treeSet = new TreeSet<>();
复制代码

此外， TreeSet 还提供了一个有参构造器，可以传入一个 Comparable 或者 Comparator 参数，该比较器会决定集合中元素排列的顺序：

Set<String> treeSet = new TreeSet<>(Comparator.comparing(String::length));
复制代码

尽管 TreeSet 不是线程安全的容器，但是可以调用 Collections.synchronizedSet() 装饰方法使其同步化：

Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);
复制代码

常用方法

知道了如何创建 TreeSet 实例之后，接着看一下 TreeSet 中常用的操作。

add()

顾名思义， add() 方法可以向 TreeSet 集合中添加元素，如果元素添加成功，则返回 true ，否则返回 false 。该方法约定，对于某元素而言，只有在集合中不存在相同元素时才可以添加。

让我们向 TreeSet 中加入一个元素：

@Test
public void AddingElement() {
    Set<String> treeSet = new TreeSet<>();
 
    assertTrue(treeSet.add("String Added"));
 }
复制代码

add() 方法非常重要，因为该方法的实现细节说明了 TreeSet 的内部实现原理，即利用 TreeMap 的 put 方法来保存元素：

public boolean add(E e) {
    return m.put(e, PRESENT) == null;
}
复制代码

代码中的变量 m 指向内部的一个 TreeMap 实例（注意 TreeMap 实现了 NavigateableMap 接口）。因此，当 TreeSet 内部依赖于一个 NavigableMap ，当创建一个 TreeSet 实例时，内部会通过一个 TreeMap 实例进行初始化：

public TreeSet() {
    this(new TreeMap<E,Object>());
}
复制代码

contains()

contain() 方法可用于检查给定 TreeSet 中是否包含某特定元素，如果包含则返回 true ，否则返回 false 。

用法很简单：

@Test
public void CheckingForElement() {
    Set<String> treeSetContains = new TreeSet<>();
    treeSetContains.add("String Added");
 
    assertTrue(treeSetContains.contains("String Added"));
}
复制代码

remove()

remove() 方法用于删除集合中的特定元素，如果集合中包含该特定元素，该方法会返回 true 。

用法如下：

@Test
public void RemovingElement() {
    Set<String> removeFromTreeSet = new TreeSet<>();
    removeFromTreeSet.add("String Added");
 
    assertTrue(removeFromTreeSet.remove("String Added"));
}
复制代码

clear()

如果想要清除集合中的所有元素，可以使用 clear() 方法：

@Test
public void ClearingTreeSet() {
    Set<String> clearTreeSet = new TreeSet<>();
    clearTreeSet.add("String Added");
    clearTreeSet.clear();
  
    assertTrue(clearTreeSet.isEmpty());
}
复制代码

size()

size() 方法可以得到 TreeSet 中元素的个数，该方法也是Set API中的基本方法之一：

@Test
public void CheckTheSizeOfTreeSet() {
    Set<String> treeSetSize = new TreeSet<>();
    treeSetSize.add("String Added");
  
    assertEquals(1, treeSetSize.size());
}
复制代码

isEmpty()

isEmpty() 方法可用于验证给定的 TreeSet 实例是否为空：

@Test
public void CheckEmptyTreeSet() {
    Set<String> emptyTreeSet = new TreeSet<>();
     
    assertTrue(emptyTreeSet.isEmpty());
}
复制代码

first()

如果 TreeSet 不为空，该方法会返回其中的第一个元素，否则会抛出 NoSUchElementException 异常。示例如下：

@Test
public void GetFirstElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    
    assertEquals("First", treeSet.first());
}
复制代码

last()

与上面的方法类似，如果 TreeSet 不为空，该方法将返回其中的最后一个元素：

@Test
public void GetLastElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Last");
     
    assertEquals("Last", treeSet.last());
}
复制代码

subSet()

该方法接受 fromElement 和 toElement 两个参数，并返回 TreeeSet 中这两个参数指定索引范围之间的所有元素。注意，该区间中包括 fromElement ，不包括 toElement 。

@Test
public void UseSubSet() {
    SortedSet<Integer> treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);
     
    Set<Integer> expectedSet = new TreeSet<>();
    expectedSet.add(2);
    expectedSet.add(3);
    expectedSet.add(4);
    expectedSet.add(5);
 
    Set<Integer> subSet = treeSet.subSet(2, 6);
  
    assertEquals(expectedSet, subSet);
}
复制代码

headSet()

该方法会返回 TreeSet 中小于指定项的所有元素：

@Test
public void UseHeadSet() {
    SortedSet<Integer> treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);
 
    Set<Integer> subSet = treeSet.headSet(6);
  
    assertEquals(subSet, treeSet.subSet(1, 6));
}
复制代码

tailSet()

该方法返回 TreeSet 中大于或等于指定项的所有元素。

@Test
public void UseTailSet() {
    NavigableSet<Integer> treeSet = new TreeSet<>();
    treeSet.add(1);
    treeSet.add(2);
    treeSet.add(3);
    treeSet.add(4);
    treeSet.add(5);
    treeSet.add(6);
 
    Set<Integer> subSet = treeSet.tailSet(3);
  
    assertEquals(subSet, treeSet.subSet(3, true, 6, true));
}
复制代码

Iterator()

Iterator() 方法会返回一个按照升序对集合中的元素进行迭代的迭代器，且该迭代器具有快速失败机制。

升序迭代如下：

@Test
public void IterateTreeSetInAscendingOrder() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}
复制代码

此外， TreeSet 也允许进行降序迭代：

@Test
public void IterateTreeSetInDescendingOrder() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.descendingIterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}
复制代码

如果迭代器已经创建，并且集合被除迭代器的remove()方法之外的其它方式进行修改，迭代器将会抛出ConcurrentModificationException。

示例如下：

@Test(expected = ConcurrentModificationException.class)
public void ModifyingTreeSetWhileIterating() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.iterator();
    while (itr.hasNext()) {
        itr.next();
        treeSet.remove("Second");
    }
}
复制代码

另外，如果使用迭代器的删除方法，则不会抛出异常：

@Test
public void RemovingElementUsingIterator() {
  
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator<String> itr = treeSet.iterator();
    while (itr.hasNext()) {
        String element = itr.next();
        if (element.equals("Second"))
           itr.remove();
    }
  
    assertEquals(2, treeSet.size());
}
复制代码

TreeSet 无法对迭代器的快速失败机制作出保证，因为在未同步的并发修改场景中，无法作出任何硬性保证。

Null 元素的存储

在 Java 7之前，用户可以向空 TreeSet 对象中添加 null 值 。但是，这个被当做了一个bug，因此在后续的版本中不再支持 null 值的添加。

当我们向 TreeSet 中添加元素时，其中的元素会按照自然序或者指定的 comparator 来进行排序。由于 null 不能与任何值作比较，因此当向 TreeSet 中添加 null 时， null 与已有元素做比较时，会抛出 NullPointerException 。

@Test(expected = NullPointerException.class)
public void AddNullToNonEmptyTreeSet() {
    Set<String> treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add(null);
}
复制代码

所有插入 TreeSet 中的元素要么实现 Comparable 接口，要么可以作为指定比较器的参数。这些元素之间可以互相比较，即 e1.compareTo(e2) 或者 comparator.compare(e1，e2) 都不会抛出 ClassCastException 。

class Element {
    private Integer id;
 
    // Other methods...
}
 
Comparator<Element> comparator = (ele1, ele2) -> {
    return ele1.getId().compareTo(ele2.getId());
};
 
@Test
public void UsingComparator() {
    Set<Element> treeSet = new TreeSet<>(comparator);
    Element ele1 = new Element();
    ele1.setId(100);
    Element ele2 = new Element();
    ele2.setId(200);
     
    treeSet.add(ele1);
    treeSet.add(ele2);
     
    System.out.println(treeSet);
}
复制代码

TreeSet 性能

与 HashSet 相比， TreeSet 的性能稍低些。 add 、 remove 、 search 等操作时间复杂度为 O(log n) ，按照存储顺序打印n个元素则耗时为 O(n) 。

如果我们想要按序保存条目，并且按照升序或者降序对集合进行访问和遍历，那么 TreeSet 就应该作为首选集合。升序方式的操作与视图性能要强于降序方式。

局部性原则——是一个术语，表示根据内存访问模式频繁访问相同值或者相关的存储位置。

当我们说局部性时，表明：

• 相似的数据通常会被程序以相近的频率访问
• 如果两个条目按照给定顺序接近， TreeSet 会在数据结构中将这两个元素放在相近的位置，内存中也同样。

TreeSet 作为一个有着更强局部性特点的数据结构，我们可以根据局部性原理得出结论，如果内存不足并且需要访问自然顺序相对接近的元素，那我们就应该优先考虑 TreeSet 。如果需要从硬盘中读取数据，因为硬盘读取的延时大大超过缓存与内存读取，因此 TreeSet 更加适合，因为其有着更好的局部性。