一吞加,Set
Set:注重獨一無二的性質(zhì),該體系集合可以知道某物是否已近存在于集合中,不會存儲重復(fù)的元素
用于存儲無序(存入和取出的順序不一定相同)元素裙犹,值不能重復(fù)。
對象的相等性
引用到堆上同一個對象的兩個引用是相等的衔憨。如果對兩個引用調(diào)用hashCode方法叶圃,會得到相同的結(jié)果,如果對象所屬的類沒有覆蓋Object的hashCode方法的話践图,hashCode會返回每個對象特有的序號(java是依據(jù)對象的內(nèi)存地址計算出的此序號)掺冠,所以兩個不同的對象的hashCode值是不可能相等的。
如果想要讓兩個不同的Person對象視為相等的码党,就必須覆蓋Object繼下來的hashCode方法和equals方法德崭,因為Object hashCode方法返回的是該對象的內(nèi)存地址,所以必須重寫hashCode方法揖盘,才能保證兩個不同的對象具有相同的hashCode眉厨,同時也需要兩個不同對象比較equals方法會返回true
該集合中沒有特有的方法,直接繼承自Collection兽狭。
---| Itreable 接口 實現(xiàn)該接口可以使用增強for循環(huán)
---| Collection 描述所有集合共性的接口
---| List接口 可以有重復(fù)元素的集合
---| ArrayList
---| LinkedList
---| Set接口 不可以有重復(fù)元素的集合
案例:set集合添加元素并使用迭代器迭代元素憾股。
public class Demo4 {
public static void main(String[] args) {
//Set 集合存和取的順序不一致鹿蜀。
Set hs = new HashSet();
hs.add("世界軍事");
hs.add("兵器知識");
hs.add("艦船知識");
hs.add("漢和防務(wù)");
System.out.println(hs);
// [艦船知識, 世界軍事, 兵器知識, 漢和防務(wù)]
Iterator it = hs.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
二,HashSet
---| Itreable 接口 實現(xiàn)該接口可以使用增強for循環(huán)
---| Collection 描述所有集合共性的接口
---| List接口 可以有重復(fù)元素的集合
---| ArrayList
---| LinkedList
---| Set接口 不可以有重復(fù)元素的集合
---| HashSet 線程不安全荔燎,存取速度快耻姥。底層是以哈希表實現(xiàn)的。
哈希表邊存放的是哈希值有咨。HashSet存儲元素的順序并不是按照存入時的順序(和List顯然不同) 是按照哈希值來存的所以取數(shù)據(jù)也是按照哈希值取得。
HashSet不存入重復(fù)元素的規(guī)則.使用hashcode和equals
由于Set集合是不能存入重復(fù)元素的集合蒸健。那么HashSet也是具備這一特性的座享。HashSet如何檢查重復(fù)?HashSet會通過元素的hashcode()和equals方法進行判斷元素師否重復(fù)似忧。
當(dāng)你試圖把對象加入HashSet時渣叛,HashSet會使用對象的hashCode來判斷對象加入的位置。同時也會與其他已經(jīng)加入的對象的hashCode進行比較盯捌,如果沒有相等的hashCode淳衙,HashSet就會假設(shè)對象沒有重復(fù)出現(xiàn)。
簡單一句話饺著,如果對象的hashCode值是不同的箫攀,那么HashSet會認為對象是不可能相等的。
因此我們自定義類的時候需要重寫hashCode幼衰,來確保對象具有相同的hashCode值靴跛。
如果元素(對象)的hashCode值相同,是不是就無法存入HashSet中了? 當(dāng)然不是,會繼續(xù)使用equals 進行比較.如果 equals為true 那么HashSet認為新加入的對象重復(fù)了,所以加入失敗。如果equals 為false那么HashSet 認為新加入的對象沒有重復(fù).新元素可以存入.
總結(jié):
元素的哈希值是通過元素的hashcode方法 來獲取的, HashSet首先判斷兩個元素的哈希值渡嚣,如果哈希值一樣梢睛,接著會比較equals方法 如果 equls結(jié)果為true ,HashSet就視為同一個元素识椰。如果equals 為false就不是同一個元素绝葡。
哈希值相同equals為false的元素是怎么存儲呢,就是在同樣的哈希值下順延(可以認為哈希值相同的元素放在一個哈希桶中)。也就是哈希一樣的存一列腹鹉。
hashtable
圖1:hashCode值不相同的情況
圖2:hashCode值相同赞弥,但equals不相同的情況。
HashSet:通過hashCode值來確定元素在內(nèi)存中的位置房午。一個hashCode位置上可以存放多個元素媚创。
當(dāng)hashcode() 值相同equals() 返回為true 時,hashset 集合認為這兩個元素是相同的元素.只存儲一個(重復(fù)元素?zé)o法放入)。調(diào)用原理:先判斷hashcode 方法的值,如果相同才會去判斷equals 如果不相同,是不會調(diào)用equals方法的航瞭。
HashSet到底是如何判斷兩個元素重復(fù)诫硕。
通過hashCode方法和equals方法來保證元素的唯一性,add()返回的是boolean類型
判斷兩個元素是否相同刊侯,先要判斷元素的hashCode值是否一致章办,只有在該值一致的情況下,才會判斷equals方法,如果存儲在HashSet中的兩個對象hashCode方法的值相同equals方法返回的結(jié)果是true藕届,那么HashSet認為這兩個元素是相同元素挪蹭,只存儲一個(重復(fù)元素?zé)o法存入)。
注意:HashSet集合在判斷元素是否相同先判斷hashCode方法休偶,如果相同才會判斷equals梁厉。如果不相同,是不會調(diào)用equals方法的踏兜。
HashSet 和ArrayList集合都有判斷元素是否相同的方法词顾,
boolean contains(Object o)
HashSet使用hashCode和equals方法,ArrayList使用了equals方法
案例:
使用HashSet存儲字符串碱妆,并嘗試添加重復(fù)字符串
回顧String類的equals()肉盹、hashCode()兩個方法。
public class Demo4 {
public static void main(String[] args) {
// Set 集合存和取的順序不一致疹尾。
Set hs = new HashSet();
hs.add("世界軍事");
hs.add("兵器知識");
hs.add("艦船知識");
hs.add("漢和防務(wù)");
// 返回此 set 中的元素的數(shù)量
System.out.println(hs.size()); // 4
// 如果此 set 尚未包含指定元素上忍,則返回 true
boolean add = hs.add("世界軍事"); // false
System.out.println(add);
// 返回此 set 中的元素的數(shù)量
System.out.println(hs.size());// 4
Iterator it = hs.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
使用HashSet存儲自定義對象,并嘗試添加重復(fù)對象(對象的重復(fù)的判定)
public class Demo4 {
public static void main(String[] args) {
HashSet hs = new HashSet();
hs.add(new Person("jack", 20));
hs.add(new Person("rose", 20));
hs.add(new Person("hmm", 20));
hs.add(new Person("lilei", 20));
hs.add(new Person("jack", 20));
Iterator it = hs.iterator();
while (it.hasNext()) {
Object next = it.next();
System.out.println(next);
}
}
}
class Person {
private String name;
private int age;
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 int hashCode() {
System.out.println("hashCode:" + this.name);
return this.name.hashCode() + age * 37;
}
@Override
public boolean equals(Object obj) {
System.out.println(this + "---equals---" + obj);
if (obj instanceof Person) {
Person p = (Person) obj;
return this.name.equals(p.name) && this.age == p.age;
} else {
return false;
}
}
@Override
public String toString() {
return "Person@name:" + this.name + " age:" + this.age;
}
}
問題:現(xiàn)在有一批數(shù)據(jù)纳本,要求不能重復(fù)存儲元素窍蓝,而且要排序。ArrayList 饮醇、 LinkedList不能去除重復(fù)數(shù)據(jù)它抱。HashSet可以去除重復(fù),但是是無序朴艰。
所以這時候就要使用TreeSet了
三观蓄,TreeSet
案例:使用TreeSet集合存儲字符串元素,并遍歷
public class Demo5 {
public static void main(String[] args) {
TreeSet ts = new TreeSet();
ts.add("ccc");
ts.add("aaa");
ts.add("ddd");
ts.add("bbb");
System.out.println(ts); // [aaa, bbb, ccc, ddd]
}
}
---| Itreable 接口 實現(xiàn)該接口可以使用增強for循環(huán)
---| Collection 描述所有集合共性的接口
---| List接口 有序祠墅,可以重復(fù)侮穿,有角標(biāo)的集合
---| ArrayList
---| LinkedList
---| Set接口 無序,不可以重復(fù)的集合
---| HashSet 線程不安全毁嗦,存取速度快亲茅。底層是以hash表實現(xiàn)的。
---| TreeSet 紅-黑樹的數(shù)據(jù)結(jié)構(gòu)狗准,默認對元素進行自然排序(String)克锣。如果在比較的時候兩個對象返回值為0,那么元素重復(fù)腔长。
紅-黑樹
紅黑樹是一種特定類型的二叉樹
紅黑樹算法的規(guī)則: 左小右大袭祟。
既然TreeSet可以自然排序,那么TreeSet必定是有排序規(guī)則的。
1:讓存入的元素自定義比較規(guī)則捞附。
2:給TreeSet指定排序規(guī)則巾乳。
方式一:元素自身具備比較性
元素自身具備比較性您没,需要元素實現(xiàn)Comparable接口,重寫compareTo方法胆绊,也就是讓元素自身具備比較性氨鹏,這種方式叫做元素的自然排序也叫做默認排序。
方式二:容器具備比較性
當(dāng)元素自身不具備比較性压状,或者自身具備的比較性不是所需要的仆抵。那么此時可以讓容器自身具備。需要定義一個類實現(xiàn)接口Comparator何缓,重寫compare方法肢础,并將該接口的子類實例對象作為參數(shù)傳遞給TreeMap集合的構(gòu)造方法。
注意:當(dāng)Comparable比較方式和Comparator比較方式同時存在時碌廓,以Comparator的比較方式為主;
注意:在重寫compareTo或者compare方法時剩盒,必須要明確比較的主要條件相等時要比較次要條件谷婆。(假設(shè)姓名和年齡一直的人為相同的人,如果想要對人按照年齡的大小來排序辽聊,如果年齡相同的人纪挎,需要如何處理?不能直接return 0跟匆,因為可能姓名不同(年齡相同姓名不同的人是不同的人)异袄。此時就需要進行次要條件判斷(需要判斷姓名),只有姓名和年齡同時相等的才可以返回0.)
通過return 0來判斷唯一性玛臂。
問題:為什么使用TreeSet存入字符串,字符串默認輸出是按升序排列的?因為字符串實現(xiàn)了一個接口,叫做Comparable 接口.字符串重寫了該接口的compareTo 方法,所以String對象具備了比較性.那么同樣道理,我的自定義元素(例如Person類,Book類)想要存入TreeSet集合,就需要實現(xiàn)該接口,也就是要讓自定義對象具備比較性.
存入TreeSet集合中的元素要具備比較性.
比較性要實現(xiàn)Comparable接口烤蜕,重寫該接口的compareTo方法
TreeSet屬于Set集合,該集合的元素是不能重復(fù)的迹冤,TreeSet如何保證元素的唯一性
通過compareTo或者compare方法中的來保證元素的唯一性讽营。
添加的元素必須要實現(xiàn)Comparable接口。當(dāng)compareTo()函數(shù)返回值為0時泡徙,說明兩個對象相等橱鹏,此時該對象不會添加進來。
比較器接口
----| Comparable
compareTo(Object o) 元素自身具備比較性
----| Comparator
compare( Object o1, Object o2 ) 給容器傳入比較器
TreeSet集合排序的兩種方式:
一堪藐,讓元素自身具備比較性莉兰。
也就是元素需要實現(xiàn)Comparable接口,覆蓋compareTo 方法礁竞。
這種方式也作為元素的自然排序糖荒,也可稱為默認排序。
年齡按照搜要條件苏章,年齡相同再比姓名寂嘉。
public class Demo4 {
public static void main(String[] args) {
TreeSet ts = new TreeSet();
ts.add(new Person("aa", 20, "男"));
ts.add(new Person("bb", 18, "女"));
ts.add(new Person("cc", 17, "男"));
ts.add(new Person("dd", 17, "女"));
ts.add(new Person("dd", 15, "女"));
ts.add(new Person("dd", 15, "女"));
System.out.println(ts);
System.out.println(ts.size()); // 5
}
}
class Person implements Comparable {
private String name;
private int age;
private String gender;
public Person() {
}
public Person(String name, int age, String gender) {
this.name = name;
this.age = age;
this.gender = gender;
}
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;
}
public String getGender() {
return gender;
}
public void setGender(String gender) {
this.gender = gender;
}
@Override
public int hashCode() {
return name.hashCode() + age * 37;
}
public boolean equals(Object obj) {
System.err.println(this + "equals :" + obj);
if (!(obj instanceof Person)) {
return false;
}
Person p = (Person) obj;
return this.name.equals(p.name) && this.age == p.age;
}
public String toString() {
return "Person [name=" + name + ", age=" + age + ", gender=" + gender
+ "]";
}
@Override
public int compareTo(Object obj) {
Person p = (Person) obj;
System.out.println(this+" compareTo:"+p);
if (this.age > p.age) {
return 1;
}
if (this.age < p.age) {
return -1;
}
return this.name.compareTo(p.name);
}
}
二奏瞬,讓容器自身具備比較性,自定義比較器泉孩。
需求:當(dāng)元素自身不具備比較性硼端,或者元素自身具備的比較性不是所需的。
那么這時只能讓容器自身具備寓搬。
定義一個類實現(xiàn)Comparator 接口珍昨,覆蓋compare方法。
并將該接口的子類對象作為參數(shù)傳遞給TreeSet集合的構(gòu)造函數(shù)句喷。
當(dāng)Comparable比較方式镣典,及Comparator比較方式同時存在,以Comparator
比較方式為主唾琼。
public class Demo5 {
public static void main(String[] args) {
TreeSet ts = new TreeSet(new MyComparator());
ts.add(new Book("think in java", 100));
ts.add(new Book("java 核心技術(shù)", 75));
ts.add(new Book("現(xiàn)代操作系統(tǒng)", 50));
ts.add(new Book("java就業(yè)教程", 35));
ts.add(new Book("think in java", 100));
ts.add(new Book("ccc in java", 100));
System.out.println(ts);
}
}
class MyComparator implements Comparator {
public int compare(Object o1, Object o2) {
Book b1 = (Book) o1;
Book b2 = (Book) o2;
System.out.println(b1+" comparator "+b2);
if (b1.getPrice() > b2.getPrice()) {
return 1;
}
if (b1.getPrice() < b2.getPrice()) {
return -1;
}
return b1.getName().compareTo(b2.getName());
}
}
class Book {
private String name;
private double price;
public Book() {
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getPrice() {
return price;
}
public void setPrice(double price) {
this.price = price;
}
public Book(String name, double price) {
this.name = name;
this.price = price;
}
@Override
public String toString() {
return "Book [name=" + name + ", price=" + price + "]";
}
}
四兄春,LinkedHashSet
會保存插入的順序。
看到array锡溯,就要想到角標(biāo)赶舆。
看到link,就要想到first祭饭,last芜茵。
看到hash,就要想到hashCode,equals.
看到tree倡蝙,就要想到兩個接口九串。Comparable,Comparator寺鸥。