书签

Java中的TreeSet 指南

评论 0 浏览 0 2018-01-03

1.概述

在这篇文章中，我们将看看Java集合框架的一个组成部分，以及最受欢迎的Set实现之一 – TreeSet。

2.介绍树集的情况

简单地说，TreeSet是一个排序的集合，它扩展了AbstractSet类，并实现了NavigableSet接口。

下面是对这一实现的最重要方面的快速总结。

  • 它存储了独特的元素
  • 它并不保留元素的插入顺序
  • 它按升序对元素进行排序
  • 这不是线程安全的。

在这个实现中，对象被排序并按照其自然顺序升序存储。TreeSet使用了一个自平衡的二进制搜索树，更确切地说，是一个红-黑树。

简单地说，作为一个自我平衡的二进制搜索树，二进制树的每个节点都包括一个额外的位，用来识别节点的颜色，即红色或黑色。在随后的插入和删除过程中，这些“颜色”位有助于确保树保持或多或少的平衡。

所以，让我们创建一个TreeSet的实例。

Set<String> treeSet = new TreeSet<>();

2.1.带有构造函数比较器参数的TreeSet

另外，我们可以用一个构造函数来构造一个TreeSet，让我们通过使用Comparable或Comparator来定义元素的排序顺序：

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

虽然TreeSet 不是线程安全的，但它可以使用Collections.synchronizedSet()包装器在外部进行同步。

Set<String> syncTreeSet = Collections.synchronizedSet(treeSet);

好了，现在我们对如何创建一个TreeSet实例有了清晰的概念，让我们来看看我们可用的常见操作。

3. TreeSet add()

add()方法，正如预期的那样，可以用来向TreeSet添加元素。如果有元素被添加，该方法将返回true，否则 – false。

该方法的约定规定，只有在Set中不存在相同的元素时，才会被添加。

让我们在TreeSet中添加一个元素。

@Test
public void whenAddingElement_shouldAddElement() {
    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）。

private transient NavigableMap<E, Object> m;

因此，TreeSet 在内部依赖于一个支持的NavigableMap，当TreeSet的实例被创建时，该实例被初始化为TreeMap的实例。

public TreeSet() {
    this(new TreeMap<E,Object>());
}

关于这一点的更多信息可以在这篇文章中找到。

4. TreeSet contains()

contains() 方法用于检查给定的元素是否存在于给定的 TreeSet 中。 如果找到该元素，则返回 true，否则返回 false。

让我们来看看contains()的实际应用。

@Test
public void whenCheckingForElement_shouldSearchForElement() {
    Set<String> treeSetContains = new TreeSet<>();
    treeSetContains.add("String Added");

    assertTrue(treeSetContains.contains("String Added"));
}

5. TreeSet remove()

remove()方法用于从集合中移除指定的元素（如果它存在的话）。

如果一个集合包含指定的元素，该方法将返回true.。

让我们看看它的实际效果：

@Test
public void whenRemovingElement_shouldRemoveElement() {
    Set<String> removeFromTreeSet = new TreeSet<>();
    removeFromTreeSet.add("String Added");

    assertTrue(removeFromTreeSet.remove("String Added"));
}

6. TreeSet clear()

如果我们想从一个集合中删除所有的项目，我们可以使用clear()方法。

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

7. TreeSet size()

size() 方法是用来确定TreeSet中存在的元素数量。它是API中的基本方法之一。

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

8. TreeSet isEmpty()

isEmpty()方法可以用来计算一个给定的TreeSet实例是否为空。

@Test
public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty() {
    Set<String> emptyTreeSet = new TreeSet<>();
    
    assertTrue(emptyTreeSet.isEmpty());
}

9. TreeSet iterator()

iterator()方法返回一个迭代器，以升序迭代Set中的元素。这些迭代器是快速失败的。

我们可以在这里观察到升序的迭代顺序。

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() {
    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 使我们能够以降序的方式迭代Set。

让我们看看这一点在行动中的表现。

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() {
    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 whenModifyingTreeSetWhileIterating_shouldThrowException() {
    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");
    }
}

另外，如果我们使用了迭代器的remove方法，那么我们就不会遇到这个异常了。

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
 
    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());
}

对于迭代器的故障快速行为没有任何保证，因为在存在非同步的并发修改的情况下，不可能做出任何硬性的保证。

关于这个问题的更多信息可以在这里找到。

10. TreeSet first()

如果TreeSet不是空的，这个方法将返回第一个元素。否则，它会抛出一个NoSuchElementException。

让我们来看看一个例子。

@Test
public void whenCheckingFirstElement_shouldReturnFirstElement() {
    TreeSet<String> treeSet = new TreeSet<>();
    treeSet.add("First");
   
    assertEquals("First", treeSet.first());
}

11. TreeSet last()

与上面的例子类似，如果这个集合不是空的，这个方法将返回最后一个元素。

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

12. TreeSet subSet()

这个方法将返回从fromElement到toElement之间的元素。注意，fromElement是包容的，toElement是排斥的。

@Test
public void whenUsingSubSet_shouldReturnSubSetElements() {
    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);
}

13. TreeSet headSet()

此方法将返回TreeSet中比指定元素小的元素。

@Test
public void whenUsingHeadSet_shouldReturnHeadSetElements() {
    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));
}

14. TreeSet tailSet()

这个方法将返回TreeSet中大于或等于指定元素的元素。

@Test
public void whenUsingTailSet_shouldReturnTailSetElements() {
    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));
}

15 储存Null 元素

在Java 7之前，可以在空的TreeSet中添加 null 元素。

然而，这被认为是一个错误。因此，TreeSet 不再支持添加null。

当我们向TreeSet添加元素时，元素会根据它们的自然顺序或比较器所指定的顺序进行排序。因此，添加一个null，当与现有元素比较时，会导致NullPointerException ，因为null不能与任何值进行比较。

@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
    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 whenUsingComparator_shouldSortAndInsertElements() {
    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);
}

16.TreeSet的性能

与HashSet 相比，TreeSet的性能就比较低。像add，remove和search这样的操作需要O(log n)的时间，而像按排序顺序打印n元素这样的操作需要O(n)的时间。

如果我们想保持我们的条目排序，TreeSet应该是我们的主要选择，因为TreeSet可以按升序或降序访问和遍历，而且升序操作和视图的性能可能比降序操作和视图的性能更快。

局部性原则（The Principle of Locality）–– 是指根据内存访问模式，频繁访问相同值或相关存储位置的现象的术语。

当我们说到局部的时候。

  • 类似的数据经常被一个应用程序以类似的频率访问
  • 如果两个条目在给定的排序中是相近的，那么TreeSet就会在数据结构中把它们放在相近的位置，因此在内存中也是如此。

TreeSet 是一个具有更大局部性的数据结构，因此，根据局部性原则，我们可以得出结论，如果我们的内存不足，并且我们想要访问那些根据自然排序相对接近的元素，我们应该优先选择TreeSet。

如果数据需要从硬盘中读取（比从缓存或内存中读取的数据有更大的延迟），那么最好选择TreeSet，因为它有更大的定位性。

17.结语

在这篇文章中，我们重点了解如何使用Java中的标准TreeSet实现。我们看到了它的目的，以及鉴于其避免重复和对元素进行排序的能力，它在可用性方面的效率如何。

像往常一样，可以在GitHub上找到代码片段。

最后更新2023-03-11
0 个评论
标签
Java Set