java中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 实现，理解如何高效使用避免重复和排序元素

原文链接

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,732评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,496评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,264评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,807评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,806评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,675评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,029评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,683评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,704评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,666评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,773评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,413评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,016评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,204评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,083评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,503评论 2赞 343