60 java集合和泛型_10 _Set实现类 _TreeSet

来源：互联网收集：自由互联发布时间：2022-07-13

文章目录 Set实现类 TreeSet存储结构：红黑树 TreeSet的使用 Comparator 接口 TreeSet案例 Set实现类 HashSet 【重点】 : 基于HashCode计算元素存放位置，

文章目录

Set实现类
TreeSet存储结构：红黑树
TreeSet的使用
Comparator 接口
TreeSet案例

Set实现类

HashSet 【重点】 :

基于HashCode计算元素存放位置，实现元素不重复。（存储结构是一个哈希表）
当存入元素的哈希码相同时，会调用equals进行确认，如结果为true, 则拒绝后者存入。

TreeSet：（set集合是无序的，而TreeSet，对元素进行了排序）

基于排列顺序实现元素不重复。
实现了SortedSet接口，对集合元素自动排序。
元素对象的类型必须实现Comparable接口，指定排序规则。（否则它并不知道怎么去判断大小）
通过CompareTo方法确定是否为重复元素。

TreeSet存储结构：红黑树

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

红黑树是在1972年由[Rudolf Bayer](https://baike.baidu.com/item/Rudolf Bayer/3014716)发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

简介：

红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树.。
红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低，其平均统计性能要强于 AVL 。
由于每一颗红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
左边的节点是要比右边的节点小的

60 java集合和泛型_10 _Set实现类 _TreeSet_java

TreeSet的使用

代码1：

package com.wlw.collection.set;

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

/**
* TreeSet的使用
* 存储结构：红黑树
*/
public class TreeSet_Demo01 {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>();

//1.添加
treeSet.add("xvy");
treeSet.add("ade");
treeSet.add("hello");
//treeSet.add("ade"); //不会添加
System.out.println("元素个数："+treeSet.size());
System.out.println(treeSet.toString());

//2.删除
/*
treeSet.remove("hello");
System.out.println("删除之后，元素个数："+treeSet.size());
System.out.println(treeSet.toString());
*/

//3.遍历
//3.1 增强for
System.out.println("----------3.1 增强for---------");
for (String s : treeSet) {
System.out.println(s);
}

//3.2迭代器
System.out.println("----------3.2迭代器---------");
Iterator<String> iterator = treeSet.iterator();
while (iterator.hasNext()){
String s = iterator.next();
System.out.println(s);
}

//4.判断
System.out.println(treeSet.contains("asd")); //false
System.out.println(treeSet.isEmpty()); //false
}
}
/*
元素个数：3
[ade, hello, xvy]
----------3.1 增强for---------
ade
hello
xvy
----------3.2迭代器---------
ade
hello
xvy
false
false
*/

代码2：

package com.wlw.collection.set;

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

/**
* TreeSet保存数据
* 存储结构：红黑树
* 元素对象的类型必须实现Comparable接口，重写compareTo()方法,指定排序规则。
* 如果compareTo()方法返回值为0，则认为是重复元素
*/
public class TreeSet_Demo02 {
public static void main(String[] args) {
TreeSet<Person> treeSet = new TreeSet<>();

Person p1 = new Person("zhangsan",10);
Person p2 = new Person("hello",20);
Person p3 = new Person("xyz",30);
Person p4 = new Person("zhangsan",40);
//1.添加
treeSet.add(p1);
treeSet.add(p2);
treeSet.add(p3);
treeSet.add(p4);
System.out.println("元素个数："+treeSet.size());
System.out.println(treeSet.toString());
/*
*第一次运行报类型转换异常：无法比较，这是因为我们存储的元素类型没有实现Comparable接口，指定排序规则。
* Exception in thread "main" java.lang.ClassCastException: com.wlw.collection.set.Person cannot be cast to java.lang.Comparable
*/

//2.删除

/*
//treeSet.remove(p4);
treeSet.remove(new Person("zhangsan",40)); //也是可以删除的，因为我们重写了比较CompareTo()方法，判断它两是一样的
System.out.println("删除之后，元素个数："+treeSet.size());
System.out.println(treeSet.toString());
*/

//3.遍历
//3.1 增强for
System.out.println("----------3.1 增强for---------");
for (Person person : treeSet) {
System.out.println(person.toString());
}

//3.2迭代器
System.out.println("----------3.2迭代器---------");
Iterator<Person> iterator = treeSet.iterator();
while (iterator.hasNext()){
Person person = iterator.next();
System.out.println(person.toString());
}
//4.判断
System.out.println(treeSet.contains(p1)); //true
System.out.println(treeSet.contains(new Person("zhangsan",10)));//true,因为我们重写了比较CompareTo()方法，判断它两是一样的
System.out.println(treeSet.isEmpty()); //false
}
}

/*
元素个数：4
[Person{name='hello', age=20}, Person{name='xyz', age=30}, Person{name='zhangsan', age=10}, Person{name='zhangsan', age=40}]
----------3.1 增强for---------
Person{name='hello', age=20}
Person{name='xyz', age=30}
Person{name='zhangsan', age=10}
Person{name='zhangsan', age=40}
----------3.2迭代器---------
Person{name='hello', age=20}
Person{name='xyz', age=30}
Person{name='zhangsan', age=10}
Person{name='zhangsan', age=40}
true
true
false

*//*
元素对象的类型必须实现Comparable接口，重写compareTo()方法,指定排序规则。
* 如果compareTo()方法返回值为0，则认为是重复元素
*/
package com.wlw.collection.set;

import java.util.Objects;

public class Person implements Comparable<Person>{
private String name;
private int age;

//无参构造
public Person() {
}

//有参构造
public Person(String name, int age) {
this.name = name;
this.age = age;
}

public String getName() {
return name;
}

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

public int getAge() {
return age;
}

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

@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}

//自动生成的
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return age == person.age &&
Objects.equals(name, person.name);
}

//自动生成的
@Override
public int hashCode() {
return Objects.hash(name, age);
}

//重写compareTo,定义排序规则
//先按名字比，再按年龄比
@Override
public int compareTo(Person o) {
int n1 = this.getName().compareTo(o.getName());
int n2 = this.getAge() - o.getAge();

return n1==0?n2:n1;
}

/* 自己写的
@Override
public int hashCode() {
int i1 = this.name.hashCode();
int i2 = this.name.hashCode();
return i1 + i2;
}

@Override
public boolean equals(Object o) {
//1.判断是否一样
if (this == o){
return true;
}
//2.判断是否为空
if (o == null){
return false;
}
//3.判断是否是Person类型
if(this.getClass() == o.getClass()){

}
if(o instanceof Person){
//4.类型转换
Person p = (Person) o;
//5.比较数据
if(this.name.equals(p.getName()) && this.age == p.getAge()){
return true;
}
}
return false;

}
*/

}

Comparator 接口

Comparator：实现定制比较（比较器）

Comparable：可比较的

package com.wlw.collection.set;

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

/**
* TreeSet保存数据
* 存储结构：红黑树
* 1. Comparator：实现定制比较（比较器）
* 2. Comparable：可比较的
*/
public class TreeSet_Demo03 {
public static void main(String[] args) {
//创建集合，并指定比较规则
TreeSet<Person> treeSet = new TreeSet<>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
//先按年龄，再按名字
int n1 = o1.getAge() - o2.getAge();
int n2 = o1.getName().compareTo(o2.getName());
return n1==0?n2:n1;
}
});

Person p1 = new Person("zhangsan",10);
Person p2 = new Person("hello",20);
Person p3 = new Person("xyz",30);
Person p4 = new Person("zhangsan",20);
//1.添加
treeSet.add(p1);
treeSet.add(p2);
treeSet.add(p3);
treeSet.add(p4);
System.out.println("元素个数："+treeSet.size());
System.out.println(treeSet.toString());

}
}

/*
元素个数：4
[Person{name='zhangsan', age=10}, Person{name='hello', age=20}, Person{name='zhangsan', age=20}, Person{name='xyz', age=30}]
*/

TreeSet案例

案例要求：

使用TreeSet集合实现字符串按长度进行排序
helloworld wangweu zhangsan lisi beijing xian nanjing
Comparator：实现定制比较（比较器）

代码：

package com.wlw.collection.set;

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

/**
* 案例：
* 要求：使用TreeSet集合实现字符串按长度进行排序
* helloworld wangweu zhangsan lisi beijing xian nanjing
* Comparator：实现定制比较（比较器）
*/
public class TreeSet_Demo04 {
public static void main(String[] args) {
//创建集合，并制定比较规则
TreeSet<String> strings = new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int n1 = o1.length()-o2.length();
int n2 = o1.compareTo(o2);
return n1==0?n2:n1;
}
});
strings.add("helloworld");
strings.add("wangweu");
strings.add("zhangsan");
strings.add("lisi");
strings.add("beijing");
strings.add("xian");
strings.add("nanjing");
System.out.println(strings.toString());
}
}
/*
[lisi, xian, beijing, nanjing, wangweu, zhangsan, helloworld]
*/

【文章出处:香港cn2服务器 http://www.558idc.com/st.html 复制请保留原URL】

上一篇：65 java集合和泛型_15 _Collections工具类
下一篇：没有了