Set
- 元素是無(wú)序(存儲(chǔ)順序和取出順序不一致),元素是唯一的，不可重復(fù)的
我們來(lái)看一下API
這里寫(xiě)圖片描述
我們寫(xiě)一個(gè)簡(jiǎn)單的Demo看看它的元素是不是無(wú)序和唯一的
public class SetDemo {
public static void main(String[] args) {
// 創(chuàng)建集合對(duì)象
Set<String> set = new HashSet<String>();
// 創(chuàng)建并添加元素
set.add("hello");
set.add("java");
set.add("world");
set.add("java");
set.add("world");
// 增強(qiáng)for遍歷
for (String s : set) {
System.out.println(s);
}
//迭代器遍歷
Iterator it = set.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
}
我們先來(lái)看結(jié)果：
這里寫(xiě)圖片描述
在這里想給大家說(shuō)一個(gè)要注意的地方雖然Set集合的元素?zé)o序逛绵，但是怀各，作為集合來(lái)說(shuō)，它肯定有它自己的存儲(chǔ)順序术浪，而你的順序恰好和它的存儲(chǔ)順序一致瓢对，這代表不了有序，你可以多存儲(chǔ)一些數(shù)據(jù)胰苏，就能看到效果硕蛹。
- 增強(qiáng)for
增強(qiáng)for:是for循環(huán)的一種。
格式：
for(元素?cái)?shù)據(jù)類(lèi)型 變量 : 數(shù)組或者Collection集合) {
使用變量即可硕并，該變量就是元素
}
好處：簡(jiǎn)化了數(shù)組和集合的遍歷法焰。弊端： 增強(qiáng)for的目標(biāo)不能為null。如何解決呢?對(duì)增強(qiáng)for的目標(biāo)先進(jìn)行不為null的判斷倔毙，然后在使用壶栋。
HashSet類(lèi)
什么是HashSet？我們先來(lái)了解他的概述
-
HashSet類(lèi)概述
- 不保證 set 的迭代順序
- 特別是它不保證該順序恒久不變普监。
-
HashSet如何保證元素唯一性
- 底層數(shù)據(jù)結(jié)構(gòu)是哈希表(元素是鏈表的數(shù)組)
- 哈希表依賴(lài)于哈希值存儲(chǔ)
- 添加功能底層依賴(lài)兩個(gè)方法：
- int hashCode()
- boolean equals(Object obj)
public class HashSetDemo {
public static void main(String[] args) {
// 創(chuàng)建集合對(duì)象
HashSet<String> hs = new HashSet<String>();
// 創(chuàng)建并添加元素
hs.add("hello");
hs.add("world");
hs.add("java");
hs.add("world");
// 遍歷集合(這里可以用增強(qiáng)for也可以用迭代器贵试，但是增強(qiáng)for比較簡(jiǎn)單點(diǎn))
for (String s : hs) {
System.out.println(s);
}
}
}
輸出結(jié)果：這里寫(xiě)圖片描述
為什么存儲(chǔ)字符串的時(shí)候，字符串內(nèi)容相同的只存儲(chǔ)了一個(gè)呢?
我們可以查看add方法的源碼凯正，就可以知道這個(gè)方法底層依賴(lài) 兩個(gè)方法：hashCode()和equals()毙玻。
步驟：
首先比較哈希值
如果相同，繼續(xù)走廊散，比較地址值或者走equals()
如果不同,就直接添加到集合中
按照方法的步驟來(lái)說(shuō)：
先看hashCode()值是否相同
相同:繼續(xù)走equals()方法
返回true： 說(shuō)明元素重復(fù)桑滩，就不添加
返回false：說(shuō)明元素不重復(fù)，就添加到集合
不同：就直接把元素添加到集合
如果類(lèi)沒(méi)有重寫(xiě)這兩個(gè)方法允睹，默認(rèn)使用的Object()运准。一般來(lái)說(shuō)不同相同幌氮。
而String類(lèi)重寫(xiě)了hashCode()和equals()方法，所以胁澳，它就可以把內(nèi)容相同的字符串去掉该互。只留下一個(gè)。
存儲(chǔ)自定義對(duì)象
我們存儲(chǔ)自定義對(duì)象韭畸，并保證元素的唯一性宇智，
要求：如果兩個(gè)對(duì)象的成員變量值都相同，則為同一個(gè)元素胰丁。
public class HashSetDemo {
public static void main(String[] args) {
// 創(chuàng)建集合對(duì)象 HashSet<Student>
hs = new HashSet<Student>();
// 創(chuàng)建學(xué)生對(duì)象
Student s1 = new Student("朱婷", 22);
Student s2 = new Student("惠若琪", 22);
Student s3 = new Student("徐云麗", 21);
Student s4 = new Student("朱婷", 22);
Student s5 = new Student("郎平", 55);
Student s6 = new Student("郎平", 57);
// 添加元素
hs.add(s1);
hs.add(s2);
hs.add(s3);
hs.add(s4);
hs.add(s5);
hs.add(s6);
// 遍歷集合
for (Student s : hs) {
System.out.println(s.getName() + "---" + s.getAge());
}
}
}
/** * 存儲(chǔ)對(duì)象 */
public class Student {
private String name;
private int age;
public Student() {
super();
}
public Student(String name, int age) {
super();
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;
}
}
輸出結(jié)果：這里寫(xiě)圖片描述我們看輸出結(jié)果随橘，很明顯不符合我的要求。因?yàn)槲覀冎繦ashSet底層依賴(lài)的是hashCode()和equals()方法锦庸。而這兩個(gè)方法我們?cè)趯W(xué)生類(lèi)中沒(méi)有重寫(xiě)机蔗，所以，默認(rèn)使用的是Object類(lèi)甘萧。這個(gè)時(shí)候蜒车，他們的哈希值是不會(huì)一樣的，根本就不會(huì)繼續(xù)判斷幔嗦，執(zhí)行了添加操作酿愧。
所以我們要在Student類(lèi)中重寫(xiě)hashCode()和equals()這兩個(gè)方法
這兩個(gè)方法都是重寫(xiě)的，不用自己去寫(xiě)
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null) return false;
if (getClass() != obj.getClass()) return false;
Student other = (Student) obj;
if (age != other.age) return false;
if (name == null) {
if (other.name != null) return false;
} else if (!name.equals(other.name)) return false;
return true;
}
LinkedHashSet類(lèi)
- 概述
- 底層數(shù)據(jù)結(jié)構(gòu)由哈希表和鏈表組成
- 由鏈表保證元素有序(存儲(chǔ)和取出是一致)
- 由哈希表保證元素唯一性
public class LinkedHashSetDemo {
public static void main(String[] args) {
// 創(chuàng)建集合對(duì)象
LinkedHashSet<String> hs = new LinkedHashSet<String>();
// 創(chuàng)建并添加元素
hs.add("hello");
hs.add("world");
hs.add("java");
hs.add("world");
hs.add("java");
// 遍歷
for (String s : hs) {
System.out.println(s);
}
}
}
TreeSet類(lèi)
- 概述
- 使用元素的自然順序?qū)υ剡M(jìn)行排序
- 或者根據(jù)創(chuàng)建 set 時(shí)提供的 Comparator 進(jìn)行排序
- 所以排序有兩種方式
- 自然排序
- 比較器排序
- 所以排序有兩種方式
- 具體取決于使用的構(gòu)造方法邀泉。
public class TreeSetDemo {
public static void main(String[] args) {
// 創(chuàng)建集合對(duì)象
// 自然順序進(jìn)行排序
TreeSet<Integer> ts = new TreeSet<Integer>();
// 創(chuàng)建元素并添加
// 20,18,23,22,17,24,19,18,24
ts.add(20); ts.add(18); ts.add(23); ts.add(22); ts.add(17); ts.add(24);
ts.add(19); ts.add(18); ts.add(24);
// 遍歷
for (Integer i : ts) {
System.out.println(i);
}
}
}
- TreeSet是如何保證元素的排序和唯一性的
- 底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹(shù)(紅黑樹(shù)是一種自平衡的二叉樹(shù))
二叉樹(shù)
那么二叉樹(shù)是怎么把元素存進(jìn)去嬉挡，又是怎么取出來(lái)的呢？
如果你弄懂了這個(gè)問(wèn)題汇恤，那么你就明白了二叉樹(shù)了
我們先來(lái)了解元素是如何存儲(chǔ)進(jìn)去的庞钢？
第一個(gè)元素存儲(chǔ)的時(shí)候，直接作為根節(jié)點(diǎn)存儲(chǔ)因谎。從第二個(gè)元素開(kāi)始基括，每個(gè)元素從根節(jié)點(diǎn)開(kāi)始比較比根節(jié)點(diǎn)元素大，就放在右邊比根節(jié)點(diǎn)元素小财岔，就放在左邊相等的話就忽略风皿。
我們以上面的存儲(chǔ)的元素20,18,23,22,17,24,19,18,24來(lái)畫(huà)一個(gè)圖幫助大家理解
這里寫(xiě)圖片描述
元素是如何取出來(lái)的呢？
從根節(jié)點(diǎn)開(kāi)始匠璧，按照左桐款、中、右的原則依次取出元素即可夷恍。
Comparator 排序
/* * 需求：請(qǐng)按照姓名的長(zhǎng)度排序 */
public class TreeSetDemo {
public static void main(String[] args) {
// 創(chuàng)建集合對(duì)象
TreeSet<Student> ts = new TreeSet<Student>();
// 創(chuàng)建元素
Student s1 = new Student("朱婷", 22);
Student s2 = new Student("惠若琪", 22);
Student s3 = new Student("徐云麗", 21);
Student s4 = new Student("朱婷婷", 22);
Student s5 = new Student("郎平", 55);
Student s6 = new Student("林丹", 34);
Student s7 = new Student("李宗偉", 33);
Student s8 = new Student("阿杜", 23);
// 添加元素
ts.add(s1); ts.add(s2); ts.add(s3); ts.add(s4); ts.add(s5); ts.add(s6); ts.add(s7); ts.add(s8);
// 遍歷
for (Student s : ts) {
System.out.println(s.getName() + "---" + s.getAge());
}
}
}
/* * 如果一個(gè)類(lèi)的元素要想能夠進(jìn)行自然排序魔眨，就必須實(shí)現(xiàn)自然排序接口 */
public class Student implements Comparable<Student> {
private String name;
private int age;
public Student() {
super();
}
public Student(String name, int age) {
super();
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 int compareTo(Student s) {
// 主要條件 姓名的長(zhǎng)度
int num = this.name.length() - s.name.length();
// 姓名的長(zhǎng)度相同，不代表姓名的內(nèi)容相同
int num2 = num == 0 ? this.name.compareTo(s.name) : num;
// 姓名的長(zhǎng)度和內(nèi)容相同，不代表年齡相同遏暴，所以還得繼續(xù)判斷年齡
int num3 = num2 == 0 ? this.age - s.age : num2;
return num3;
}
}
- TreeSet集合保證元素排序和唯一性的原理
- 唯一性：是根據(jù)比較的返回是否是0來(lái)決定侄刽。
- 排序：
- A:自然排序(元素具備比較性)
- 讓元素所屬的類(lèi)實(shí)現(xiàn)自然排序接口 Comparable
- B:比較器排序(集合具備比較性)
- 讓集合的構(gòu)造方法接收一個(gè)比較器接口的子類(lèi)對(duì)象 Comparator
- A:自然排序(元素具備比較性)
