一硼控、Set
Set：Collection 的子接口。
Set 規(guī)范的要求：要求 元素?zé)o序请契，不重復(fù)咳榜。
Set：1：HashSet；2：TreeSet爽锥。
二涌韩、HashSet
特點(diǎn)：元素?zé)o序的，唯一的氯夷。
底層使用的數(shù)據(jù)結(jié)構(gòu)：哈希表臣樱、散列表。
例：
import?java.util.HashSet;
import?java.util.Iterator;
public?class?TestHashSet {
public?static?void?main(String[] args) {
HashSet set?= new?HashSet<>();
//HashSet 的基本使用肠槽。
//添加
set.add(new?Person("小張", 23, Gender.MALE));
set.add(new?Person("小餅", 20, Gender.MALE));
set.add(new?Person("靜靜",18,Gender.FEMAL));
set.add(new?Person("靜靜",18,Gender.FEMAL));
//不能通過(guò)容器對(duì)象直接修改容器中的元素的內(nèi)容
//刪除
set.remove(new?Person("小張", 23, Gender.MALE));
//獲得--沒(méi)有提供方法擎淤。
set.contains(new?Person("靜靜",18,Gender.FEMAL));
//set.clear();
//set.size();
//set.isEmpty();
//遍歷??迭代器
Iterator iterator?= set.iterator();
while?(iterator.hasNext()) {
Person person?= iterator.next();
System.out.println(person);
}
//foreach?底層使用迭代器
for?(Person person?: set) {
System.out.println(person);
}
System.out.println(set);
}
}
class?Person{
private?String name;
private?int?age;
private?Gender gender;
public?Person() {
}
Person(String name, int?age, Gender gender) {
super();
this.name?= name;
this.age?= age;
this.gender?= gender;
}
public?String toString() {
return?"\nPerson [name="?+ name?+ ", age="?+ age?+ ", gender="?+ gender?+ "]";
}
@Override
public?int?hashCode() {
System.out.println("Person.hashCode()");
final?int?prime?= 31;
int?result?= 1;
result?= prime?* result?+ age;
result?= prime?* result?+ ((gender?== null) ? 0 : gender.hashCode());
result?= prime?* result?+ ((name?== null) ? 0 : name.hashCode());
return?result;
}
@Override
public?boolean?equals(Object obj) {
System.out.println("Person.equals()");
if?(this?== obj)
return?true;
if?(obj?== null)
return?false;
if?(getClass() != obj.getClass())
return?false;
Person other?= (Person) obj;
if?(age?!= other.age)
return?false;
if?(gender?!= other.gender)
return?false;
if?(name?== null) {
if?(other.name?!= null)
return?false;
} else?if?(!name.equals(other.name))
return?false;
return?true;
}
// public boolean equals(Object o){
// if(o == null)return false;
// if(this == o)return true;
// if(!(o instanceof?Person))return false;
//
// Person p = (Person)o;
// if(!this.name.equals(p.name))
// return false;
// if(!this.gender.equals(p.gender))
// return false;
// if(this.age != p.age)
// return false;
// return true;
// }
}
enum?Gender{
MALE,FEMAL
}
三、HashCode
Object 類(lèi)的 hashCode() :
實(shí)際上秸仙，由Object 類(lèi)定義的 hashCode 方法確實(shí)會(huì)針對(duì)不同的對(duì)象返回不同的整數(shù)。這一般是通過(guò)將該對(duì)象的內(nèi)部地址轉(zhuǎn)換成一個(gè)整數(shù)來(lái)實(shí)現(xiàn)的桩盲。
不同的對(duì)象的哈希碼是不同的寂纪。
?
hashCode 的常規(guī)協(xié)定是：
在Java 應(yīng)用程序執(zhí)行期間，在對(duì)同一對(duì)象多次調(diào)用 hashCode 方法時(shí)，必須一致地返回相同的整數(shù)捞蛋，前提是將對(duì)象進(jìn)行 equals 比較時(shí)所用的信息沒(méi)有被修改孝冒。從某一應(yīng)用程序的一次執(zhí)行到同一應(yīng)用程序的另一次執(zhí)行，該整數(shù)無(wú)需保持一致拟杉。
如果根據(jù)equals(Object) 方法庄涡，兩個(gè)對(duì)象是相等的，那么對(duì)這兩個(gè)對(duì)象中的每個(gè)對(duì)象調(diào)用 hashCode 方法都必須生成相同的整數(shù)結(jié)果搬设。
如果根據(jù)equals(java.lang.Object) 方法穴店，兩個(gè)對(duì)象不相等，那么對(duì)這兩個(gè)對(duì)象中的任一對(duì)象上調(diào)用 hashCode 方法不 要求一定生成不同的整數(shù)結(jié)果拿穴。但是泣洞，程序員應(yīng)該意識(shí)到，為不相等的對(duì)象生成不同整數(shù)結(jié)果可以提高哈希表的性能默色。
?
如果希望HahSet能夠正常的工作球凰，那么我們希望內(nèi)容相同的對(duì)象的哈希碼是一致的。通過(guò)調(diào)用hashCode 方法腿宰，得到的int 值是一樣的呕诉。
需要在HashSet 容器中添加的元素的類(lèi)型中，需要重寫(xiě) hashCode 方法吃度。用以保證相同的對(duì)象的哈希碼是一致的甩挫。
?
如果希望HashSet 可以保證元素的唯一性和無(wú)序性，那么必須在元素對(duì)應(yīng)的類(lèi)型中规肴，重寫(xiě) equals 方法 和 hashCode 方法捶闸。
hashCode 方法 保證了：元素的無(wú)序（通過(guò)哈希碼的值來(lái)確定元素的位置），保證了相同的對(duì)象可以具有相同的哈希碼的值拖刃，保證了可以進(jìn)行 equals 比較的前提删壮。
equals 方法保證了避免相同的對(duì)象 多次添加。
?
總結(jié)：
HashSet 元素唯一性： hashCode() + equals
HashSet 元素?zé)o序性：hashCode()
?
進(jìn)一步理解hashCode():
1:如果兩個(gè)對(duì)象的hashCode 相同兑牡，那么equals 方法比較的結(jié)果不一定是相等央碟。
2：如果兩個(gè)對(duì)象equals 方法比較的結(jié)果是相等的，那么兩個(gè)對(duì)象的hashCode 方法得到的值必須要一致均函。
以上兩點(diǎn)是HashSet 可以正常工作的基礎(chǔ)亿虽，也是hashCode 重寫(xiě)的依據(jù)。
?
哈希碼又稱(chēng)為散列碼：
重寫(xiě)hashCode 的依據(jù)：
1：如果兩個(gè)對(duì)象equals 方法比較的結(jié)果是相等的苞也，那么兩個(gè)對(duì)象的hashCode 方法得到的值必須要一致洛勉。
2：通過(guò)equals 比較是不相等的，那么對(duì)象的hashCode 的值也要盡量的不同如迟，以保證提高哈希表的效率收毫。
3：希望通過(guò)hashCode 得到的值是一個(gè)均勻的散列在 int 的取值范圍內(nèi)的一個(gè)值攻走。來(lái)保證哈希表中的一維數(shù)組的使用率，以及降低鏈表的長(zhǎng)度此再。
?
不同的數(shù)據(jù)類(lèi)型重寫(xiě)hashCode 的策略：
1：Integer ?對(duì)象的哈希碼的值就是 被封裝的 int 的值昔搂。
2：String 使用一個(gè)質(zhì)數(shù) 31 作為基數(shù)，然后和所有的字符值關(guān)聯(lián)输拇。
LinkedHashSet：是 HashSet 的子類(lèi)摘符。
在HashSet 的基礎(chǔ)上，添加了一個(gè)鏈表策吠。用來(lái)維護(hù)了元素添加的一個(gè)順序逛裤。
保證了添加元素的順序和遍歷元素的順序是一致的。但是效率有所降低奴曙。并沒(méi)有提供根據(jù)索引訪問(wèn)元素的方法别凹。
四、TreeSet
TreeSet：底層使用的數(shù)據(jù)結(jié)構(gòu)為 樹(shù) 結(jié)構(gòu) （二叉樹(shù)）洽糟。
特點(diǎn)：唯一炉菲，有序（升序）。元素不能為null.
使用規(guī)則：
創(chuàng)建TreeSet 對(duì)象的時(shí)候坤溃，要么指定容器的外部比較器 java.util.Comparator 的實(shí)現(xiàn)的子類(lèi)拍霜，要么將元素的類(lèi)型實(shí)現(xiàn)內(nèi)部比較接口 java.lang.Comparable.
在添加元素的過(guò)程中，所有的元素的大于小于薪介，等于這些關(guān)系都是通過(guò)比較器的返回值來(lái)決定的祠饺。如果返回0 ，則認(rèn)為兩個(gè)元素是相等的汁政，不再添加道偷。
TreeSet 的執(zhí)行的效率：根據(jù)內(nèi)容查找的效率介于HashSet 和 ArrayList 中間。
例：
import?java.util.Comparator;
import?java.util.TreeSet;
import?com.bjsxt.util.MyUtil;
public?class?TestTreeSet {
public?static?void?main(String[] args) {
test3();
//遍歷方式??迭代器??+ ?foreach
}
static?void?test1(){
TreeSet set?= new?TreeSet<>();
set.add("abc");
set.add("efg");
set.add("cde");
set.add("rhw");
set.add("cjk");
set.add("bihaome");
System.out.println(set);
}
static?void?test2(){
TreeSet set?= new?TreeSet<>();
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
System.out.println(set);
}
static?void?test3(){
TreeSet set??= new?TreeSet<>(new?Comparator() {
@Override
public?int?compare(Person o1, Person o2) {
return?o1.getAge()-o2.getAge();
}
});
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
set.add(new?Person("小剛",MyUtil.getRandomNumber(10, 19) , MyUtil.getRandomNumber(0, 2)==1?Gender.FEMAL?: Gender.MALE));
System.out.println(set);
}
}
class?Person/* implements Comparable*/{
private?String name;
private?int?age;
private?Gender gender;
public?Person() {
}
Person(String name, int?age, Gender gender) {
super();
this.name?= name;
this.age?= age;
this.gender?= gender;
}
public?String toString() {
return?"\nPerson [name="?+ name?+ ", age="?+ age?+ ", gender="?+ gender?+ "]";
}
@Override
public?int?hashCode() {
System.out.println("Person.hashCode()");
final?int?prime?= 31;
int?result?= 1;
result?= prime?* result?+ age;
result?= prime?* result?+ ((gender?== null) ? 0 : gender.hashCode());
result?= prime?* result?+ ((name?== null) ? 0 : name.hashCode());
return?result;
}
// @Override
// public boolean equals(Object obj) {
// System.out.println("Person.equals()");
// if (this == obj)
// return true;
// if (obj?== null)
// return false;
// if (getClass() != obj.getClass())
// return false;
// Person other = (Person) obj;
// if (age != other.age)
// return false;
// if (gender != other.gender)
// return false;
// if (name == null) {
// if (other.name != null)
// return false;
// } else if (!name.equals(other.name))
// return false;
// return true;
// }
// @Override
// public int?compareTo(Person o) {
// return this.age - o.age;
// }
public?int?getAge(){
return?age;
}
// public boolean equals(Object o){
// if(o == null)return false;
// if(this == o)return true;
// if(!(o instanceof?Person))return false;
//
// Person p = (Person)o;
// if(!this.name.equals(p.name))
// return false;
// if(!this.gender.equals(p.gender))
// return false;
// if(this.age != p.age)
// return false;
// return true;
// }
}
五记劈、Map
Map：映射：映射中的所有的元素都被封裝成了一個(gè)Node（鍵+值 ?key+value）一個(gè)Node 包含了一對(duì)數(shù)據(jù)勺鸦。
key：往往是一種數(shù)據(jù)類(lèi)型相對(duì)簡(jiǎn)單的數(shù)據(jù)。
value：往往是更詳細(xì)的數(shù)據(jù)的信息目木。
key：學(xué)號(hào)
value：學(xué)生的信息
key：身份證號(hào)碼
value：人的信息换途。
Map：
--HashMap
--TreeMap
六、HashMap
HashMap:底層使用哈希表實(shí)現(xiàn)刽射。
HashMap的工作原理：
1：將一對(duì)數(shù)據(jù) ?key + value 封裝成一個(gè)Node 對(duì)象军拟。
2：將 Node 對(duì)象 放到哈希表中。通過(guò) key 的hashCode() 得到一個(gè)哈希碼誓禁，來(lái)決定放到 哈希表中的哪個(gè)位置懈息。
通過(guò)Node 中的key 數(shù)據(jù) 來(lái)確定 整個(gè)Node 在哈希表中的位置。
結(jié)論：HashMap 中Node 的key 的特點(diǎn)摹恰，就是 HashSet 中的元素的特點(diǎn)漓拾。 HashMap 中的key 要求無(wú)序的阁最，唯一的戒祠。
HashMap 特點(diǎn)：key 是無(wú)序的骇两，唯一的，Node 是無(wú)序的姜盈，唯一的低千，Value 的無(wú)序的（和key 綁在一起的），不一定了馏颂。
HashMap 中的key 必須重寫(xiě) equals 和 ?hashCode示血。來(lái)保證key 的唯一性 和 無(wú)序性。
HashSet 底層使用 HashMap 實(shí)現(xiàn)救拉。
只使用了HashMap 的key 部分难审。HashSet 元素 作為 HashMap 的 key。所有的元素 都和 另外一個(gè)final static Object PRESENT 對(duì)象亿絮，作為value 被封裝成了一個(gè)Node告喊。
放到哈希表中。所以HashMap key 的特點(diǎn) 和 ?HashSet 元素的特點(diǎn)一致派昧。
public?boolean?add(E e) {
????????return?map.put(e, PRESENT)==null;
}
?
原碼解讀：
static?final?float?DEFAULT_LOAD_FACTOR?= 0.75f;
默認(rèn)的填充因子黔姜。當(dāng)哈希表中的一維數(shù)組的被占用的元素的個(gè)數(shù)占數(shù)組的長(zhǎng)度的比例達(dá)到DEFAULT_LOAD_FACTOR這個(gè)值的，時(shí)候蒂萎，進(jìn)行擴(kuò)容秆吵。
決定了哈希表擴(kuò)容的時(shí)機(jī)。避免鏈表過(guò)長(zhǎng)五慈。
?
//將key 和 value 封裝成的Node 對(duì)象的類(lèi)纳寂。內(nèi)部類(lèi)。Node 包含了指向下一個(gè)節(jié)點(diǎn)的next泻拦。
static?class?Node implements?Map.Entry {
????????final?int?hash;
????????final?K key;
????????V value;
????????Node next;
}
//哈希表的線性表 一維數(shù)組
?transient?Node[] table;
例1：
import?java.util.Collection;
import?java.util.HashMap;
import?java.util.Iterator;
import?java.util.Map.Entry;
import?java.util.Set;
public?class?TestHashMap2 {
public?static?void?main(String[] args) {
HashMap map = new?HashMap<>();
// 添加元素,修改
map.put("cn", "China");
map.put("us", "America");
map.put("uk", "United Kindom");
map.put("uk", "England");
map.put("jp", null);
map.put("fr", "France");
map.put(null, null);
// 刪除 通過(guò)key 的哈希碼找到哈希表中的位置毙芜，然后一次遍歷 當(dāng)前 索引的鏈表中的所有的Node節(jié)點(diǎn)中的所有的key，
// 如果key 和 某一個(gè)Node 中的key 通過(guò)euqals 比較是相等的聪轿，就移除該Node對(duì)象爷肝。
map.remove("jp");
// 獲取 只能通過(guò)key 獲得 對(duì)應(yīng)的Node ，獲取Node 中的value 值陆错。
System.out.println(map.get("cn"));
// 其他的方法
// map.containsKey(key)
// map.clear();
// map.containsValue(value)
// map.size()
System.out.println(map.replace(null, "123"));
// 遍歷 得到map 中所有的key 灯抛。
Set keySet = map.keySet();
Iterator iterator = keySet.iterator();
while?(iterator.hasNext()) {
// 得到一個(gè)key
String key = iterator.next();
// 得到對(duì)應(yīng)的value
String value = map.get(key);
System.out.println(key + "-->"?+ value);
}
// 得到所有的value ，不能得到對(duì)應(yīng)的key
Collection values = map.values();
Iterator iterator2 = values.iterator();
while?(iterator2.hasNext()) {
String value = iterator2.next();
System.out.println("value == "?+ value);
}
// 得到map 的所有的鍵值對(duì)音瓷。每一個(gè)鍵值對(duì)被封裝成了一個(gè)entry
// Entry 是Map 接口的一個(gè)內(nèi)部接口对嚼。一個(gè)Entry 代表了一個(gè)key 和一個(gè)value的組合。
Set> entrySet = map.entrySet();
Iterator> iterator3 = entrySet.iterator();
while?(iterator3.hasNext()) {
Entry entry = iterator3.next();
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key + "-->"?+ value);
}
System.out.println(map);
}
}
例2：
//效率測(cè)試
import?java.util.HashMap;
public?class?TestHashMap1 {
public?static?void?main(String[] args) {
long?time?= System.currentTimeMillis();
HashMap map??=new?HashMap<>();
final?int?COUNT?= 200_0000;
for(int?i=0;i
map.put(Integer.toString(i), Integer.toString(i));
}
long?cost?= System.currentTimeMillis()-time;
System.out.println("cost = "+cost);
//一秒等于1000000000納秒（毫微秒）
time?= System.nanoTime();
System.out.println("--->"+map.get("99999"));
cost?= System.nanoTime()-time;
System.out.println("cost = "+cost);
// cost = 2793微秒
// --->99999
// cost = 90034毫微秒
}
}
?
LinkedHashMap：是在HashMap 的基礎(chǔ)上增加了一個(gè)鏈表绳慎，用于維護(hù)Node 添加的順序纵竖。
用以保證元素Node 添加的順序和 遍歷的順序一致漠烧。但是效率有所降低。
TreeMap：底層使用二叉樹(shù)來(lái)實(shí)現(xiàn)靡砌。
元素特點(diǎn)：
將key 和 value 封裝成了一個(gè)Node已脓。添加到TreeMap 中。
key 的特點(diǎn) 是有序（升序）的通殃，唯一的度液。
和TreeSet 元素特點(diǎn)一致。 ?TreeSet 底層使用TreeMap 實(shí)現(xiàn)画舌。TreeSet 只使用了TreeMap 的key 部分堕担。
所以添加到TreeMap 中的Node 中的key 必須要么實(shí)現(xiàn)內(nèi)部比較器java.lang.Comparable 要么指明TreeMap的外部比較器。
TreeMap 的key 不能為 null.
TreeMap 根據(jù)內(nèi)容查找的效率在ArrayList 和 HashMap(最高)?之間間曲聂。
import?java.util.TreeMap;
public?class?TestTreeMap {
public?static?void?main(String[] args) {
TreeMap map = new?TreeMap<>();
//添加元素,修改
map.put("cn", "China");
map.put("us", "America");
map.put("uk", "United Kindom");
map.put("uk", "England");
map.put("jp", null);
map.put("fr", "France");
System.out.println(map);
}
}
