java中treeset使用

作者: 左洁 | 来源:发表于2019-08-29 19:27 被阅读0次

java中treeset使用
TreeSet
java TreeSet错误使用
Java中TreeSet的三种比较规则
深入了解TreeSet
java8中treeset源码分析
java集合中的TreeSet
一起学习集合框架之 TreeSet
Java TreeSet
JAVA8 TreeSet学习笔记

java中treeset使用

环境:jdk8

1:简介

这篇文章讲解java集合框架中实现set接口-TreeSet

2:介绍TreeSet

TreeSet 是继承AbstractSet 有序集合并且实现NavigableSet 接口

下面是一些重要总结:

不能存放相同元素
不保存插入元素顺序
默认排序是升序(treeSet#add()增加元素小在左边大在右边迭代从左边读取)
非线程安全

TreeSet实现中，对象是按照自然序升序存储，TreeSet 使用平衡二叉搜索树，简单说平衡二叉搜索树，每个节点有额外字节做特殊标记，标记红色和黑色，在删除和插入时候，标记字节确保剩下数还是平衡树，因此让我们创建一个TreeSet实例

Set<String> treeSet = new TreeSet();

2.1:TreeSet带参数构造方法

带参数构造方法可以自定义排序方法

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

即使TreeSet 线程不安全，在外部可以使用Collections.synchronizedSet()包装起来

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

现在已经知道如何创建TreeSet 实例，下面看下常用操作

3: TreeSet 增加元素 add()

TreeSet#add()可以增加元素，元素增加成功放回true否则false

add()方法增加只有TreeSet不存相同元素 ，下面例子:

@Test
public void whenAddingElement_shouldAddElement() {
    Set<String> treeSet = new TreeSet();
 
    assertTrue(treeSet.add("String Added"));
 }

add方法是非常重要下面是实现细节

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

m变量是TreeMap(注意Treemap实现NavigableMap 接口)

/**
  * The backing map.
  */
private transient NavigableMap<E,Object> m;

因此，TreeSet 内部依赖NavigableMap 实例化TreeMap当TreeSet被创建时

4: TreeSet contains()

contains()方法用于检查给定元素是否存在TreeSet中,如果元素存在返回true，否则false，下面例子:

@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中大小，这个是基本方法在接口中:

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() 方法返回升序迭代器,迭代器实现fail-fast失败，下面观察升序迭代器:

@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可以降序排序输出，下面例子:

@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());
    }
}

迭代器抛出ConcurrentModificationException如果set被修改在迭代创建之后，除非使用迭代器删除remove()方法，下面例子:

@Test(expected = ConcurrentModificationException.class)
public void whenModifyingTreeSetWhileIterating_shouldThrowException() {
    Set<String> treeSet = new TreeSe();
    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 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()

和上面例子相似，方法返回最后一个元素如果set不为空

@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小于指定元素set：

@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()

方法返回大于或等于元素后面set

@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元素排序

java7之前，增加null元素到空TreeSet是可以的，然而这样会造成一次bug，因此TreeSet不在支持添加空元素，当添加元素到TreeSet时，元素按照自然排序或者按照自定义comparator ,因此增加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) or comparator.compare(e1, e2) 不能抛出异常

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性能进行比较，TreeSet性能低，像增加删除和搜时间复杂度O(logn) 当打印n个元素时间复杂度是O(n),HashSet操作新增删除和contains方法都是O(1)

TreeSet应该是我们主要选择如果想要保持元素有序并且升序和降序访问遍历，升序操作比降序要快

以下有一些规则-如果相同值现象或者和本地存储频繁访问依靠于内存模式

相似数据经常访问被应用程序一样快
If two entries are nearby given an ordering, a TreeSet places them near each other in the data structure, and hence in memory

A TreeSet being a data-structure with greater locality we can, therefore, conclude in accordance to the Principle of Locality, that we should give preference to a TreeSet if we're short on memory and if we want to access elements that are relatively close to each other according to their natural ordering.

In case data needs to be read from the hard drive (which has greater latency than data read from the cache or memory) then prefer TreeSet as it has greater locality（英文中不能理解，希望有大神知道，请告知下，谢谢）

17：总结

本文重点理解如何使用标准TreeSet 实现，理解如何高效使用避免重复和排序元素

原文链接

java中treeset使用
java中treeset使用环境:jdk8 1:简介这篇文章讲解java集合框架中实现set接口-TreeSe...
TreeSet
TreeSet如何比较自定义对象 Java中的TreeSet是Set的一个子类，TreeSet集合是用来对象元素进...
java TreeSet错误使用
与HashSet是基于HashMap实现一样，TreeSet同样是基于TreeMap实现的。在大神的Java提高篇...
Java中TreeSet的三种比较规则
Java中TreeSet使用Comparator进行比较的三种方法让元素具备比较性元素自身具备比较性，需要元素实...
深入了解TreeSet
Java中的TreeSet是Set的一个子类，TreeSet集合是用来对象元素进行排序的,同样他也可以保证元素的唯...
java8中treeset源码分析
大纲 treeset原理分析 treeset源码分析 1. treeset原理分析 treeset中的数据是唯一的...
java集合中的TreeSet
底层：树红黑树/二叉树/平衡树优缺点：维护数据的大小时是有序的；添加速度和删除速度高于ArrayList...
一起学习集合框架之 TreeSet
什么是 TreeSet TreeSet 是一个具有唯一元素的二叉树的集合，又被翻译为树集。Java 中的 Tre...
Java TreeSet
TreeSet简介 TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSe...
JAVA8 TreeSet学习笔记
TreeSet TreeSet是基于TreeMap的NavigableSet实现。使用元素的自然顺序对元素进行排序...

java中treeset使用