文档章节

JAVA基础-集合TreeSet介绍

90design
 90design
发布于 2017/04/16 11:32
字数 1046
阅读 24
收藏 0

1. TreeSet简介

TreeSet 是一个有序的集合,它的作用是提供有序的Set集合。它继承于AbstractSet抽象类,实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。
TreeSet 继承于AbstractSet,所以它是一个Set集合,具有Set的属性和方法。
TreeSet 实现了NavigableSet接口,意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
TreeSet 实现了Cloneable接口,意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口,意味着它支持序列化。

TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式:自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作(add、remove 和 contains)提供受保证的 log(n) 时间开销。
另外,TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

TreeSet与Collection关系如下图:

 

2. 排序、存储、查询原理

    首先知道 TreeSet 底层的数据结构使用的是二叉树。

    前面说到,TreeSet中的元素支持2种排序方式:自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序

    2.1 自然排序

  【元素自身具备排序】 实现该对象的类必须实现Comparable 接口,并复写compareTo()方法, TreeSet在存储对象元素时,需要验证两个对象是否相等,避免重复。

    

    2.2 构造方法的Comparator排序

 【集合容器具备排序】 在创建TreeSet集合时,初始化一个对象(TreeSet t = new TreeSet(Object A)),该对象A所在类必须继承Comparator接口 并复写compare()方法。

    注意:如果该结合初始化对象和元素对象都实现了排序接口, 那么以集合容器的排序(比较器)为准。            代码示例:

package com.java.Collection;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * Created by ZongCai on 17/4/14.
 */
public class TreeSetDemo {
    public static void main(String[] args) {
        System.out.println("元素自身具备比较性:age排序");
        method_sort1();

        System.out.println("集合对象自身定义比较器:name排序");
        method_sort2();


    }

    // 2. 元素本身不具备比较性或不是想要的比较方式
    public static void method_sort2() {
        // student按照age比较排序,现在要使用name排序

        TreeSet treeSet = new TreeSet(new MyCompare());
        treeSet.add(new Student("aaa", 10));
        treeSet.add(new Student("bbb", 12));
        treeSet.add(new Student("ccc", 80));
        treeSet.add(new Student("aaa", 30));
        treeSet.add(new Student("ABA", 23));
        treeSet.add(new Student("D001", 1));
        treeSet.add(new Student("D002", 4));
        treeSet.add(new Student("D003", 5));
        treeSet.add(new Student("D003", 5));
        treeSet.add(new Student("D003", 6));

        for (Iterator iterator = treeSet.iterator(); iterator.hasNext(); ) {
            Student s = (Student) iterator.next();
            System.out.println(s.getName() + "==" + s.getAge());
        }
    }

    // 1. 元素自身具备比较性
    public static void method_sort1() {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Student("aaa", 10));
        treeSet.add(new Student("bbb", 12));
        treeSet.add(new Student("ccc", 80));
        treeSet.add(new Student("aaa", 30));
        treeSet.add(new Student("ABA", 23));
        treeSet.add(new Student("D001", 1));
        treeSet.add(new Student("D002", 4));
        treeSet.add(new Student("D003", 5));
        treeSet.add(new Student("D003", 5));
        treeSet.add(new Student("D003", 6));

        for (Iterator iterator = treeSet.iterator(); iterator.hasNext(); ) {
            Student s = (Student) iterator.next();
            System.out.println(s.getName() + "==" + s.getAge());
        }
    }
}


// 比较器类
class MyCompare implements Comparator {
    public int compare(Object o1, Object o2) {
        Student s1 = (Student) o1;
        Student s2 = (Student) o2;


        int num = s1.getName().compareTo(s2.getName());
        if (num == 0) {
            //return s1.getAge()>s2.getAge() ? 1 : (s1.getAge() == s2.getAge() ?0: -1);
            return new Integer(s1.getAge()).compareTo(new Integer(s2.getAge()));
        }
        return num;

    }
}
// 实现元素对象类
class Student implements Comparable {

    private int age;
    private String name;

    Student(String name, int age) {
        this.age = age;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int compareTo(Object o) {
        if (!(o instanceof Student)) {
            throw new ClassCastException("非相同类");
        }
        Student s = (Student) o;
        if (this.age > s.age) {
            return 1;
        }
    
        // 注意验证条件相同时的处理方式
        if (this.age == s.age) {
            return this.name.compareTo(s.name);
        }
        return -1;
    }
}

 

    2.3 TreeSet集合存储示意图

    以上面代码为例:

TreeSet treeSet = new TreeSet();
treeSet.add(new Student("aaa",10) ); // 存储
treeSet.add(new Student("bbb",12) ); // 12>10 靠右存储
treeSet.add(new Student("aaa",30) ); // 30>10, 30>12 靠右存储
treeSet.add(new Student("ABA",23) ); 
treeSet.add(new Student("D002",4) );
treeSet.add(new Student("D003",5) );
treeSet.add(new Student("D001",4) );
treeSet.add(new Student("D004",4) );
treeSet.add(new Student("D003",5) );

    

    2.4 二叉树的查询流程:

        左边的是小的, 最下面最左边最小;

        右边的是大的, 最下面最右边最大

        1. 先从左边最下方的最小的值开始 ;

        2. 节点A右边的分支永远大于A的值,左边的永远小于A的值;

        

 

 

 

© 著作权归作者所有

90design
粉丝 19
博文 56
码字总数 40559
作品 0
潍坊
程序员
私信 提问
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
2018/10/11
0
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
2018/01/25
0
0
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0
java集合入门和深入学习,看这篇就差不多了

集合框架: Java中的集合框架大类可分为Collection和Map;两者的区别: Collection是单列集合;Map是双列集合 Collection中只有Set系列要求元素唯一;Map中键需要唯一,值可以重复 Collecti...

sihailoveyan
2018/05/04
0
0
Java核心(四)你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧! Java中的集合通常指的是Collection下的三个集合框架List、Set、Q...

王磊的博客
2018/11/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

我的程序人生——三年开发的思考,阿里朋友给我总结的“Java架构师技术栈”

想写这篇文章已经很久了,本来计划在3月份,也就是刚好满3年的时候写的,但是因为各种各样的原因推到了现在才开始码字。 小感慨 三年是一段很长的时间,它足够让你从高中毕业进入大学,也能让...

我最喜欢三大框架
14分钟前
0
0
ElasticSearch获取索引信息

检查集群的健康情况 GET /_cat/health?v green:每个索引的primary shard和replica shard都是active状态的 yellow:每个索引的primary shard都是active状态的,但是部分replica shard不是act...

水木星辰
16分钟前
0
0
Cesium中级教程6 - 3D Models 三维模型

Cesium中文网:http://cesiumcn.org/ | 国内快速访问:http://cesium.coinidea.com/ 3D Models 三维模型 本教程将教您如何通过Primitive API转换、加载和使用Cesium中的三维模型。如果你是C...

Cesium中文网
18分钟前
0
0
Elasticsearch简单学习1-用白话文解释原理

由于Elasticsearch在工作中用的越来越多,平时是边学边用,很少记录,读到一些很好的文章时间久了就忘记了。 所以,在此记录一下,希望对更多人的学习有帮助,知识在于分享! ==============...

wind2012
25分钟前
0
0
Spring面试题部分总结【慨念】

什么是Spring? spring是一个企业级应用的开源开发框架,主要用来开发java应用,spring框架目标就是简化企业级应用开发。 Spring用到了那些设计模式? spring里面用到了大量的设计模式,这里...

薛小二
27分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部