Set集合
set接口
特点
- Set集合: 可以保证元素的唯一性 , 但是不保证有序(有序: 指的是存储和取出的顺序一致)
注意:set集合在存储元素的时候,需要对元素进行处理,按照一定的算法对元素进行排序,而有的时候我们的添加元素的顺序巧号是set集合计算完毕以后的顺序,但是这也不能说明是有序的
获取7个不重复的随机数
(int)(Math.rando*(n-m+1)+m)产生任意范围内[m,n]的随机数
1
2
3
4
5
6
7
8
9
10
11
12
13
14//获取7个不重复的随机数
public static void main(String[] args) {
// Set
Set<Integer> set = new HashSet<>();
int r;
while(true) {
r = (int)(Math.random()*(30-1+1)+1);
set.add(r);// int ->Integer
if(set.size() == 7) {
break;
}
}
set.forEach(System.out::println);
}
HashSet
特点
- 底层数据结构是哈希表，哈希表结构底层依赖:hashCode()和equals()方法。
- HashSet集合保证元素的唯一性依赖于两个方法一个是hashCode方法,一个是equals方法如果，你认为对象的成员变量值相同即为同一个对象的话，你就应该重写这两个方法。
- HashSet 实现了 Set 接口，不允许插入重复的元素，允许包含一个 null 元素，且不保证元素迭代顺序，特别是不保证该顺序恒久不变。Set集合的元素无序,但是,作为集合来说,它肯定有自己的存储顺序。
- HashSet 的代码十分简单，去掉注释后的代码不到两百行。HashSet 底层是通过 HashMap 来实现的。
- 在进行比较的时候先比较的是对象的hashCode值,如果对象的hashCode值是相同的,那么在调用equals方法比较.
1
2
3
4
5
6
7
8
9
10
11
12
13
public int hashCode() {
// 哈希地址
return name.hashCode() + no;
}
public boolean equals(Object obj) {
// this ,obj
// obj _ > Employee
Employee e = (Employee)obj;
return this.no == e.no && this.name.equals(e.name);
}如何保证元素唯一性
- 而我们的字符串是重写hashCode方法和equals方法,那么在这里相同的字符串的hashCode值就是相同的,并且equals方法比较是内容。当hashCode值相同,并且调用equals方法返回的是true的时候,说明两个对象是同一个,于是不进行存储,即就保证了元素的唯一性
使用HashSet集合存储自定义对象,保证元素的唯一性
- 如果两个对象的成员变量是相同的,那么我们认为就是同一个对象
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// 创建集合对象
Set<String> set = new HashSet<String>();
// 添加元素
set.add("hello");
set.add("java");
set.add("world");
set.add("java");
set.add("world");
// 遍历
// 方式一:迭代器
Iterator<String> it = set.iterator();
while (it.hasNext()) {
String s = it.next();
System.out.println(s);
}
//方式二:
for(String s : set){
System.out.println(s);
}
结果:
java
world
hello
// 无序 唯一
HashSet如何去重
- 在向 HashSet 添加元素时，HashSet 会将该操作转换为向 HashMap 添加键值对，
- 如果 HashMap 中包含 key 值与待插入元素相等的键值对
- （hashCode() 方法返回值相等，通过 equals() 方法比较也返回 true）
- 则待添加的键值对的 value 会覆盖原有数据，但 key 不会有所改变，
- 因此如果向 HashSet 添加一个已存在的元素时，元素不会被存入 HashMap 中，从而实现了 HashSet 元素不重复的特征。
hashCode()方法
由于成员变量值影响了哈希值，所以我们把成员变量值相加即可
this.name.hashCode() + this.age;可能出现下面情况,对象不同,但hashCode一样,会进入equals方法
// s1:name.hashCode()=40,age=30// s2:name.hashCode()=20,age=50尽可能的区分,我们可以把它们乘以一些整数
1
2
3
4
5
6
7
8
9
10
11
12
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
System.out.println("hello".hashCode()); //99162322
System.out.println("hello".hashCode()); //99162322
System.out.println("world".hashCode()); //113318802
equals方法
- 先比较对象地址值，类名，最后属性的值。
1 |
|
HashSet源码分析
源码分析如下所示
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable{
//序列化ID
static final long serialVersionUID = -5024744406713321676L;
//HashSet 底层用 HashMap 来存放数据
//Key值由外部传入，Value则由 HashSet 内部来维护
private transient HashMap<E,Object> map;
//HashMap 中所有键值对都共享同一个值
//即所有存入 HashMap 的键值对都是使用这个对象作为值
private static final Object PRESENT = new Object();
//无参构造函数，HashMap 使用默认的初始化大小和装载因子
public HashSet() {
map = new HashMap<>();
}
//使用默认的装载因子，并以此来计算 HashMap 的初始化大小
//+1 是为了弥补精度损失
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
//为 HashMap 自定义初始化大小和装载因子
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
//为 HashMap 自定义初始化大小
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//此构造函数为包访问权限，只用于对 LinkedHashSet 的支持
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//将对 HashSet 的迭代转换为对 HashMap 的 Key 值的迭代
public Iterator<E> iterator() {
return map.keySet().iterator();
}
//获取集合中的元素数量
public int size() {
return map.size();
}
//判断集合是否为空
public boolean isEmpty() {
return map.isEmpty();
}
//判断集合是否包含指定元素
public boolean contains(Object o) {
return map.containsKey(o);
}
//如果 HashSet 中不包含元素 e，则添加该元素，并返回 true
//如果 HashSet 中包含元素 e，则不会影响 HashSet ，并返回 false
//该方法将向 HashSet 添加元素 e 的操作转换为向 HashMap 添加键值对
//如果 HashMap 中包含 key 值与 e 相等的结点（hashCode() 方法返回值相等，通过 equals() 方法比较也返回 true）
//则新添加的结点的 value 会覆盖原有数据，但 key 不会有所改变
//因此如果向 HashSet 添加一个已存在的元素时，元素不会被存入 HashMap 中
//从而实现了 HashSet 元素不重复的特征
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//移除集合中的元素 o
//如果集合不包含元素 o，则返回 false
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//清空集合中的元素
public void clear() {
map.clear();
}
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out HashMap capacity and load factor
s.writeInt(map.capacity());
s.writeFloat(map.loadFactor());
// Write out size
s.writeInt(map.size());
// Write out all elements in the proper order.
for (E e : map.keySet())
s.writeObject(e);
}
/**
* Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read capacity and verify non-negative.
int capacity = s.readInt();
if (capacity < 0) {
throw new InvalidObjectException("Illegal capacity: " +
capacity);
}
// Read load factor and verify positive and non NaN.
float loadFactor = s.readFloat();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// Read size and verify non-negative.
int size = s.readInt();
if (size < 0) {
throw new InvalidObjectException("Illegal size: " +
size);
}
// Set the capacity according to the size and load factor ensuring that
// the HashMap is at least 25% full but clamping to maximum capacity.
capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
HashMap.MAXIMUM_CAPACITY);
// Create backing HashMap
map = (((HashSet<?>)this) instanceof LinkedHashSet ?
new LinkedHashMap<E,Object>(capacity, loadFactor) :
new HashMap<E,Object>(capacity, loadFactor));
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
E e = (E) s.readObject();
map.put(e, PRESENT);
}
}
//为了并行遍历数据源中的元素而设计的迭代器
public Spliterator<E> spliterator() {
return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
}
}
LinkedHashSet
特点
- LinkedHashSet: 底层的数据结构是链表和哈希表
- 元素唯一 ,并且有序(根据插入的顺序)，哈希表保证元素的唯一性。链表保证元素有素。(存储和取出是一致)
- LinkedHashSet 的内部实现都是来自于HashMap 、HashSet 和 LinkedHashMap容器类，其内部源码十分简单，简单到它只有一个成员变量、四个构造函数、一个 Set 接口的方法。
示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17LinkedHashSet<String> hs = new LinkedHashSet<String>();
// 创建并添加元素
hs.add("hello");
hs.add("world");
hs.add("java");
hs.add("world");
hs.add("java");
// 遍历
for (String s : hs) {
System.out.println(s);
}
结果:
hello
world
java
LinkedHashSet源码分析
LinkedHashSet的所有源码如下所示
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
33
34
35public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
//序列化ID
private static final long serialVersionUID = -2851667679971038690L;
//自定义初始容量与装载因子
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
//自定义初始容量
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
//使用默认的初始容量以及装载因子
public LinkedHashSet() {
super(16, .75f, true);
}
//使用初始数据、默认的初始容量以及装载因子
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
//并行遍历迭代器
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
}
}LinkedHashSet 继承于 HashSet，而 LinkedHashSet 调用的父类构造函数均是
1
2
3
4
5private transient HashMap<E,Object> map;
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}即 LinkedHashSet 底层是依靠 LinkedHashMap 来实现数据存取的，而 LinkedHashMap 继承于 HashMap，在内部自己维护了一条双向链表用于保存元素的插入顺序。
因此使得 LinkedHashSet 也具有了存取有序，元素唯一的特点。
TreeSet
TreeSet集合特点
- TreeSet存储对象的时候, 可以排序, 但是需要指定排序的算法。
- 底层数据结构是红黑树(自平衡二叉树，也就是TreeMap, 放入数据不能重复且不能为null
- 保证元素唯一性，依赖于compareTo方法的返回值是否为0.
排序
- Integer能排序(有默认顺序), String能排序(有默认顺序), 自定义的类存储的时候出现异常(没有顺序)。
- 自然排序(元素具备比较性)那么必须实现Comparable接口
- 比较器排序:让集合的构造方法接收一个比较器的子类对象Comparator
- 可以重写compareTo()方法来确定元素大小，从而进行升序排序。
- 二叉树不需要重写hashCode()和equals()
- 定义比较器是实现Comparator接口,重写compare方法和equals方法,但是由于所有的类默认继承Object,而Object中有equals方法,所以自定义比较器类时,不用重写equals方法,只需要重写compare方法
1
2
3
4
5compareTo()方法中:
return 0: 不添加到集合
return正数: 作为右孩子
return 负数: 作为左孩子
通过中序遍历可以得到有序去重复
产生10个1-20之间的随机数要求随机数不能重复案例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/**
* 产生10个1-20之间的随机数,要求不能重复
* 分析:
* 1: 创建一个HashSet集合对象 , 作用: 存储产生的随机数
* 2: 生成随机数 , 把随机数添加到集合中
* 3: 使用循环,当集合的长度大于等于10退出循环 , 小于10就一直循环
*/
// 创建一个HashSet集合对象 , 作用: 存储产生的随机数
HashSet<Integer> hs = new HashSet<Integer>() ;
while(hs.size() < 10) {
// 使用Random类
Random random = new Random() ;
int num = random.nextInt(20) + 1 ;
// 把num添加到集合中
hs.add(num) ;
}
// 遍历
for(Integer i : hs) {
System.out.println(i);
}
如何进行排序
- 集合可以对元素进行排序,而排序有两种方式一种是自然排序,一种是比较强器排序
- 到底使用的是自然排序还是比较器排序,主要取决于我们使用的构造方法
1
2public TreeSet(): 使用自然排序
public TreeSet(Comparator<? super E> comparator) 使用的就是比较器排序
TreeSet排序
自然排序
使用TreeSet集合存储自定义对象,并排序案例
- 基本数据类型都实现了自然排序接口(Comparable)
Student implements Comparable<Student>TreeSet ts = new TreeSet(); //自然排序
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
33
34
35
36
37
38/**
* 需求: 使用TreeSet集合存储自定义对象,并排序
*/
// 创建自定义对象
Student s1 = new Student("刘亦菲" , 18) ;
Student s2 = new Student("貂蝉" , 16) ;
Student s3 = new Student("杨玉环" , 22) ;
Student s4 = new Student("王昭君" , 14) ;
Student s5 = new Student("西施" , 25) ;
Student s6 = new Student("范冰冰" , 25) ;
// 创建TreeSet集合对象
TreeSet<Student> ts = new TreeSet<Student>() ; // 自然排序
// 添加元素
ts.add(s1) ;
ts.add(s2) ;
ts.add(s3) ;
ts.add(s4) ;
ts.add(s5) ;
ts.add(s6) ;
// 遍历集合
for(Student s : ts) {
System.out.println(s.getName() + "---" + s.getAge());
}
//在student类中
public class Student implements Comparable<Student>{
//省略部分代码
public int compareTo(Student o) {
/**
* 按照年龄进行排序
*/
int num = this.age - o.age ;
// 比较姓名
int num2 = num == 0 ? this.name.compareTo(o.name) : num ;
return num2;
}
}使用TreeSet集合存储自定义对象,安排姓名的长度进行排序
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
33
34
35
36
37
38
39
40
41
42
43
44/**
* 需求: 使用TreeSet集合存储自定义对象,安排姓名的长度进行排序
*/
// 创建自定义对象
Student s1 = new Student("liubei" , 23) ;
Student s2 = new Student("guanyunchang" , 21) ;
Student s3 = new Student("zhangfei" , 18) ;
Student s4 = new Student("lvbu" , 25) ;
Student s5 = new Student("zhugeliang" , 23) ;
Student s6 = new Student("guanyu" , 23) ;
Student s7 = new Student("guanyu" , 25) ;
// 创建集合对象
TreeSet<Student> ts = new TreeSet<Student>() ;
// 添加元素
ts.add(s1) ;
ts.add(s2) ;
ts.add(s3) ;
ts.add(s4) ;
ts.add(s5) ;
ts.add(s6) ;
ts.add(s7) ;
// 增强for遍历
for(Student s : ts) {
System.out.println(s.getName() + "---" + s.getAge());
}
//-------------------------
public class Student implements Comparable<Student>{
public int compareTo(Student o) {
/**
* 比较姓名的长度
*/
int num = this.name.length() - o.name.length() ;
// 比较内容
int num2 = (num == 0) ? this.name.compareTo(o.name) : num ;
// 比较年龄
int num3 = (num2 == 0) ? this.age - o.age : num2 ;
return num3;
}
}
比较器排序
public TreeSet(Comparator comparator(接口)) //比较器排序示例：
TreeSet<Student> ts = new TreeSet<Student>(new MyComparator());通过匿名内部类
1
2
3
4
5
6
7
8
9
10
11
12
13TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>(){
public int compare(Student s1, Student s2){
// 姓名长度
int num = s1.getName().length() - s2.getName().length();
// 姓名内容
int num2 = num == 0 ? s1.getName().compareTo(s2.getName())
: num;
// 年龄
int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
return num3;
}
});自己写一个实现了Comparator接口的类
1
2
3
4
5
6
7
8
9
10public class Mycomparator implements Comparator<Student>{
public int compare(Student s1,Stuedent s2){
int num = s1.getAge()-s2.getAge();
// 年龄大小
int num2 = num==0?s1.getName().compareTo(s2.getName()):num;
// 年龄相同,比较姓名
return num2;
}
}
SortedSet接口
是Set的子接口,
实现类TreeSet;
底层数据结构是 二叉树
- first() 获得第一个元素
. last() 获得最后一个元素
. subSet(start, end) 得到子集,[起始元素,终止元素)
1 | public static void main(String[] args) { |
数:表示层次结构的
树：是由节点集及连接每对节点的有向边集组成。
二叉树：树形结构任意节点不能超过两个孩子。
- 根节点
- 枝节点
- 叶节点
- 中序遍历: 左中右
- 要管理树(维持持续),效率不如hashSet
NavigableSet接口
是sortedSet的子类接口
提供了接近匹配原则的检索元素的方法
- floor(e):小于 等于 指定参数 的最大元素
- ceiling:大于等于 指定参宿的 最小元素
- descendingSet():集合元素降序排序
- descendingIterator():降序的迭代器
- pollFirst():移除第一个元素
- pollLast(): 移除最后一个元素
1 | public static void main(String[] args) { |
TreeSet
真正的比较是依赖于元素的compareTo()方法，而这个方法是定义在 Comparable里面的。
所以，你要想重写该方法，就必须是先 Comparable接口。这个接口表示的就是自然排序。
二叉树不需要重写hashCode()和equals()
1 |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 凉月の博客！
评论