java 集合中Set接口、数据结构_java中集合set是哪些数据结构

.Set接口

特点：无序、不允许重复，是Collection接口的子接口

没有定义新方法，所有的方法都是Collection接口中所定义的方法

实现类

HashSet不保证元素的添加顺序，底层采用哈希表算法，查询效率高

判断两个元素是否相等equals() 方法返回为 true要求hashCode() 值必须相等

要求存入 HashSet 中的元素要覆盖 equals() 方法和 hashCode()方法

LinkedHashSet是HashSet的子类，在HashSet的基础上添加了额外的链表，底层采用了哈希表算法以及链表算法，既保证了元素的添加顺序，也保证了查询效率。但是整体性能要低于HashSet

判断两个元素是否相等equals() 方法返回为 true要求hashCode() 值必须相等

要求存入 HashSet 中的元素要覆盖 equals() 方法和 hashCode()方法

TreeSet不保证元素的添加顺序，但是会对集合中的元素进行排序。底层采用红-黑树算法（树结构比较适合查询）,但是添加的效率较低

存放的元素需要进行大小比较，所以类必须实现Comparable接口。必须同一类型

HashSet

类定义

数据的存储方式

底层实现方法：存储到Set中的所有数据最终都存储在一个HashMap中，其中存储的数据采用key的方式进行存储，值为PRESENT常量

常用算法

boolean add(E e)向集合Set中添加元素，注意不保证顺序

同一个内容的对象，为什么没有出现覆盖的效果？

• 设置hashCode和equals方法的调用

• 
  比对两个对象相等，调用流程为：
  1、调用对象的hashcode方法，如果hashCode不相等则返回，认为两个对象不相等。
  2、如果hash值相等则调用equals判断

  潜规则要求：定义类时需要定义对应的hashCode和equals方法，要求：当equals为true时，hash值必须相等；当hash值相等时不一定equals为true
  
  选择参与比较的属性值即可，IDE工具自动生成对应的方法
  
  boolean remove(Object o) 删除指定对象，同样需要hashCode和equals方法

void clear()清空集合中的所有元素

boolean contains(Object o)判断集合中是否有指定的对象，同样需要hashCode和equals方法

int size()获取集合中的元素个数

Iterator iterator()用于遍历所存储的数据

Set<String> set = new LinkedHashSet<>();
		set.add("abcd");
		set.add("123");
		Iterator<String> it=set.iterator();
		while(it.hasNext()) {
			String tmp=it.next();
			System.out.println(tmp);
		}

1
2
3
4
5
6
7
8
9

HashSet的特征

无序：不仅不能保证元素插入的顺序（如果需要顺序则可以使用LinkedHashSet），而且在元素在以后的顺序中也可能变化（这是由HashSet按HashCode存储对象（元素）决定的，对象变化则可能导致HashCode变化）

如果需要访问的顺序和插入的顺序一致，可以使用HashSet的子类LinkedHashSet不允许重复 [equals和hashcode]

**结论：**当HashSet判定对象重复时，首先调用的是对象的hashCode方法，如果两个对象的hashCode值相同时，才调用equals进行判定。如果hashCode值不相等则不会调用equals判断。如果 hashcode相等而且equals为true，则后盖前

HashSet是线程非安全的，方法上没有同步约束
HashSet元素值可以为NULL

LinkedHashSet

类定义

没有什么新方法，仅仅只是在HashSet的基础上添加了一个链表结构记录存取的顺序

LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素

TreeSet

TreeSet实现了SortedSet接口，顾名思义这是一种排序的Set集合

数据存储采用的是

在map中以key为需要存放的数据，以PERSENT常量为值存放数据

内部实现
底层是用TreeMap实现的，本质上是一个红黑树原理。正因为它是排序了的，所以相对HashSet来说，TreeSet提供了一些额外的按排序位置访问元素的方法，例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet()

基本用法

Set<Integer> set = new TreeSet<Integer>();
Random r = new Random();
for (int i = 0; i < 10; i++)
	set.add(r.nextInt(100));
set.forEach(System.out::println);

1
2
3
4
5
6

TreeSet的排序分两种类型，一种是自然排序，另一种是定制排序。
编程使用TreeSet

执行报错

原因是：添加到TreeSet中要求对象必须是可比较的

• 要求添加到TreeSet中的元素类型必须实现Comparable接口

public class A {
	public static void main(String[] args) {
		Set<Person> set=new TreeSet<Person>();
		Person p1=new Person(1L,"能能");
		Person p2=new Person(1L,"能能");
set.add(p1);
		set.add(p2);
		System.out.println(set.size());
		System.out.println(p1==p2);
		System.out.println(p1.equals(p2));
	}
}

class Person implements Comparable<Person>{
	private Long id;
	private String name;
	public Person(long l, String string) {
		this.id=l;
		this.name=string;
	}
	@Override
	public int compareTo(Person o) {
		//判空处理省略
		int res=name.compareTo(o.name);
		if(res==0) {
			res=id.compareTo(o.id);
		}
		return res;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

如果使用TreeSet时不会依靠hashcode和equals进行比较，相等性判断是依靠compareTo实现的

自然排序

（在元素中写排序规则）

TreeSet 会调用compareTo方法比较元素大小，然后按升序排序（从小到达）。所以自然排序中的元素对象，都必须实现了Comparable接口，否则会抛出异常。对于TreeSet判断元素是否重复的标准，也是调用元素从Comparable接口继承而来compareTo方法，如果返回0则是重复元素。Java的常见类都已经实现了Comparable接口

给Person类上添加针对Comparable接口的实现：考虑具体的业务规则，按照类中什么属性进行排序比较

数据结构

哈希表

Hash一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值

简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。例如使用指纹数据保证数据传输的可靠性

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

在Java中任意一个对象都有一个hashCode()方法，可以获取任意一个对象的hash值

哈希冲突

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，就把它叫做碰撞（哈希碰撞）。

散列算法

散列法Hashing是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，称为散列法，也叫哈希法。

由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中

String类型的定义

具体的字符串值是采用char[]进行存储，而且一旦创建则不能修改。真正的修改操作都会引发对象的新建

String类型中的hashCode方法的实现：

abc （97*31+98）*31+99

二叉树

二叉搜索树（Binary Search Tree，简称 BST），BST是一种很常用的的二叉树。它的定义是：一个二叉树中，任意节点的值要大于等于左子树所有节点的值，且要小于等于右边子树的所有节点的值

主要针对链表的插入和删除很快，但是是查找数据却很慢的特点。树状结构最大的优势在于查找，但是插入和删除的效率都不太高

二叉树的特点：
左子树上所有结点的值均小于或等于它的根结点的值
右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉排序树

• 中序遍历:左子树——》根节点——》右子树
• 前序遍历:根节点——》左子树——》右子树
• 后序遍历:左子树——》右子树——》根节点
  
  中序遍历 1 2 3 4 5 6 7
  前序遍历 5 2 1 4 3 6 7
  后序遍历 1 3 4 2 7 6 5

二叉树在极端情况下会退化为链表结构，为了避免出现这个问题，引入平衡树

AVL 树是一种平衡二叉树，平衡二叉树递归定义如下：

• 左右子树的高度差小于等于1。
• 其每一个子树均为平衡二叉树。

AVL树引入了所谓监督机制，就是在树的某一部分的不平衡度超过一个阈值后触发相应的平衡操作。保证树的平衡度在可以接受的范围内。

引入红黑树。

红黑树是一种近似平衡的二叉查找树，查找、删除、插入都快，树经常需要进行旋转达到平衡，但是平衡算法很复杂。

红黑树特征：

• 每个节点不是红色就是黑色的；
• 根节点总是黑色的；
• 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）,(也就是从每个叶子到根的所有路径上不能有两个连续的红色节点)；
• 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

各种Set集合性能分析

HashSet和TreeSet是Set集合中用得最多的集合。HashSet总是比TreeSet集合性能好，因为HashSet不需要额维护元素的顺序。

LinkedHashSet需要用额外的链表维护元素的插入顺序，因此在插入时性能比HashSet低，但在迭代访问（遍历）时性能更高。因为插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。

EnumSet元素是所有Set元素中性能最好的，但是它只能保存枚举类型的元素。

相关的集合计算

addAll将指定集合中的所有元素都添加到此集合中，如果在进行此操作的同时修改了指定的集合，那么将不能保证操作的正确性

removeAll从指定的集合中移除包含在另一个集合中的元素，返回值为boolean，如果包含了要移除的对象则返回true否则false

retainAll仅仅保留集合中同时包含在指定集合的对象，其它的全部移除

containsAll用来查看在该集合中是否存在在指定集合中的所有对象，返回true表示存在，否则false

Collection和Collections的区别

Collection是java.util下的接口，它是各种集合的父接口，继承于它的接口主要有Set 和List

Collections是个java.util下的类，是针对集合的帮助类，提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作

练习题

用程序给出随便大小的10 个整数，序号为1-10，【序号是存储时产生的序号】按从小到大顺序输出，并输出相应的序号
1、定义类用于封装产生的序号和对应的数据。
2、因为需要对数据进行排序，则必须是可比较的。实现方法可以是类实现Comparable接口，还可以额外定义比较器

3、生成数据并存入到TreeSet中即可

• 方法1

• 方法2

存储到List中进行排序

由于contains存在性判定需要使用equals方法，所以需要在Num类添加equals方法

• 方法3

存储在List中使用自定义比较器，类并没有实现Comparable接口