@[toc]
集合
一把跨、集合框架體系圖
二人弓、數(shù)組和集合的區(qū)別
-
數(shù)組在存儲多個數(shù)據(jù)方面的特點：
數(shù)組一旦初始化好之后，其長度就已經(jīng)確定了
數(shù)組聲明的類型着逐，就決定了進行元素初始化時的類型崔赌，也就只能操作指定類型的數(shù)據(jù)了。例如：
String[] arr;int[] arr1;Object[] arr2;
- 數(shù)組能存放基本數(shù)據(jù)類型和對象耸别，而集合類中只能放對象健芭。
-
數(shù)組在存儲多個數(shù)據(jù)方面的弊端：
一旦初始化以后，其長度就不可修改秀姐，不便于擴展慈迈，集合類容量動態(tài)改變摹菠。
數(shù)組存儲的數(shù)據(jù)是有序的坑质、可以重復(fù)的，對于無序骨坑、不可重復(fù)的需求锥咸，不能滿足---->存儲數(shù)據(jù)的特點單一
數(shù)組中提供的方法非常有限狭瞎，對于添加、刪除搏予、插入數(shù)據(jù)等操作熊锭，非常不便，同時效率不高雪侥。
數(shù)組無法判斷其中實際存有多少元素碗殷，length只告訴了array的容量就是數(shù)組的長度。<u>而集合size()方法可以知道容器中存放了多少個數(shù)據(jù)</u>**速缨，而不是集合的長度
三锌妻、Java集合框架的概述：集合的使用場景
四、集合框架
Java集合可分為Collection和Map兩種體系
Collection 接口 ：單列數(shù)據(jù)旬牲，定義了<u>存取一組對象</u>的方法的集合
List：元素有序仿粹、可重復(fù)的集合
Set：元素?zé)o序搁吓、不可重復(fù)的集合
Map 接口：雙列數(shù)據(jù)，保存具有映射關(guān)系“key-value對”的集合
Collection接口繼承樹
Map接口繼承樹
五吭历、Collection接口方法
5.1堕仔、Collection接口
Collection 接口是 List、Set 和 Queue 接口的父接口晌区，該接口里定義的方法既可用于操作 Set 集合摩骨，也可用于操作 List 和 Queue 集合。
JDK不提供此接口的任何直接實現(xiàn)朗若，而是提供更具體的子接口(如：Set和List)實現(xiàn)恼五。
在 Java5 之前，Java 集合會丟失容器中所有對象的數(shù)據(jù)類型哭懈，把所有對象都當(dāng)成 Object 類型處理灾馒；從 JDK5.0 增加了 泛型以后，Java 集合可以記住容器中對象的數(shù)據(jù)類型银伟。
<u>Collection中存儲的如果是自定義類的對象時，類中需要重寫equals()方法</u>**
5.2绘搞、Collection接口方法
- 添加
add(Object obj)：添加一個元素
addAll(Collection coll)：添加coll集合中的所有元素
- 獲取有效元素的個數(shù)
int size()
- 清空集合
void clear()
- 是否是空集合
boolean isEmpty()
- 是否包含某個元素
boolean contains(Object obj)：是通過元素的equals方法來判斷是否是同一個對象彤避；obj對象需要重寫equals()方法
boolean containsAll(Collection c)：也是調(diào)用元素的equals方法來比較的。拿兩個集合的元素挨個比較夯辖。obj對象需要重寫equals()方法
- 刪除
boolean remove(Object obj)：通過元素的equals方法判斷是否是要刪除的那個元素琉预。只會刪除找到的第一個元素；obj對象需要重寫equals()方法
boolean removeAll(Collection coll)：取當(dāng)前集合的差集
- 取兩個集合的交集
boolean retainAll(Collection c)：把交集的結(jié)果存在當(dāng)前集合中蒿褂，不影響c
- 集合是否相等
boolean equals(Object obj)：obj對象需要重寫equals()方法
- 轉(zhuǎn)成對象數(shù)組
Object[] toArray()
-
獲取集合對象的哈希值
hashCode() -
遍歷
iterator()：返回迭代器對象圆米，用于集合遍歷
5.3、Iterator迭代器接口（遍歷集合元素）
Iterator對象稱為迭代器(設(shè)計模式的一種)啄栓，主要用于遍歷 Collection 集合中的元素
Collection接口繼承了java.lang.Iterable接口娄帖，該接口有一個iterator()方法，那么所有實現(xiàn)了Collection接口的集合類都有一個iterator()方法昙楚，用以返回一個實現(xiàn)了Iterator接口的對象近速。
Iterator 僅用于遍歷集合，Iterator 本身并不提供承裝對象的能力堪旧。如果需要創(chuàng)建Iterator 對象削葱，則必須有一個被迭代的集合
-
集合對象每次調(diào)用iterator()方法都得到一個全新的迭代器對象，默認(rèn)游標(biāo)都在集合的第一個元素之前淳梦。給個案例如下：
public class Test { public static void main(String[] args) { Collection coll = new ArrayList(); coll.add(123); coll.add(345); coll.add(456); //錯誤方式: //集合對象每次調(diào)用iterator()方法都得到一個全新的迭代器對象析砸，默認(rèn)游標(biāo)都在集合的第一個元素之前。 while (coll.iterator().hasNext()){ System.out.println(coll.iterator().next());//死循環(huán) } } }
5.4爆袍、Iterator迭代器接口的方法（jdk1.8之后的增加了default方法）
在調(diào)用it.next()方法之前必須要調(diào)用it.hasNext()進行檢測首繁。若不調(diào)用作郭，且下一條記錄無效，直接調(diào)用it.next()會拋出NoSuchElementException異常蛮瞄。代碼如下：
public class Test {
public static void main(String[] args) {
Collection coll = new ArrayList();
coll.add(123);
coll.add(345);
coll.add(456);
//錯誤方式:
Iterator iterator = coll.iterator();
while((iterator.next()) != null){
System.out.println(iterator.next());//這里會拋出NoSuchElementException異常
}
}
}
結(jié)果如下（會出現(xiàn)以下異常問題）：
`345
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayList$Itr.next(ArrayList.java:969)
at com.bjsxt.demo12.Test.main(Test.java:20)`
5.5所坯、Iterator迭代器的執(zhí)行原理
5.6、Iterator接口中的remove()方法
public class Demo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
Iterator<Integer> ite = list.iterator();
while (ite.hasNext()) {
if (1 == ite.next()) {
//迭代器中的remove方法
ite.remove();
}
}
System.out.println(list);//[2,3,4,5]
}
}
注意：
Iterator可以刪除集合的元素挂捅，但是是遍歷過程中通過迭代器對象的remove方法芹助，不是集合對象的remove方法。
-
如果還未調(diào)用next()或在上一次調(diào)用 next 方法之后已經(jīng)調(diào)用了 remove 方法闲先，再調(diào)用remove都會報IllegalStateException状土。案例如下：
public class Test { public static void main(String[] args) { Collection coll = new ArrayList(); coll.add("張三"); coll.add("李四"); coll.add("王五"); //錯誤方式: Iterator iterator = coll.iterator(); while(iterator.hasNext()){ //iterator.remove();這里會報IllegalStateException異常 Object o = iterator.next(); if ("張三".equals(o)){ iterator.remove(); //iterator.remove();這里會報IllegalStateException異常 } } } }
5.7、使用foreach循環(huán)遍歷集合元素
Java 5.0 提供了 foreach 循環(huán)迭代訪問 Collection和數(shù)組伺糠。
遍歷操作不需獲取Collection或數(shù)組的長度蒙谓，無需使用索引訪問元素。
遍歷集合的底層調(diào)用Iterator完成操作训桶。
foreach還可以用來遍歷數(shù)組累驮。
-
使用foreach循環(huán)需要注意的點：
public class ForTest { @Test public void test1() { String[] arr = new String[]{"MM", "MM", "MM"}; //方式一:普通for循環(huán)賦值 // for (int i = 0; i < arr.length ; i++) { // arr[i] = "GG"; // } //打印,結(jié)果如何 // for (int i = 0; i < arr.length ; i++) { // System.out.println(arr[i]); // // /** // * 打印結(jié)果如下：成功賦值，改變的數(shù)組的值 // * GG // * GG // * GG // */ // } //方式二:增強for循環(huán) for (String s : arr) { s = "GG"; } //打印舵揭，結(jié)果如何谤专？ for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); /** * 打印結(jié)果如下：沒有成功賦值，原因：foreach循環(huán)底層采用Iterator迭代方式, * 將遍歷出來的值賦值給變量s,只是改變變量s的值午绳，其數(shù)組的值是沒有變的 * MM * MM * MM */ } } }
5.8置侍、Collection集合與數(shù)組之間的轉(zhuǎn)換
-
數(shù)組轉(zhuǎn)集合
Arrays.asList(T ...);代碼如下：public class CollectionTest { @Test public void test4() { List<String> list = Arrays.asList(new String[]{"aa", "bb", "cc"}); System.out.println(list); /** * 打印結(jié)果如下： * [aa, bb, cc] */ } } -
集合轉(zhuǎn)數(shù)組
coll.toArray();代碼如下：public class CollectionTest { @Test public void test4() { Collection coll = new ArrayList(); coll.add(123); coll.add(456); coll.add(new Person("Jerry", 20)); coll.add(new String("Tom")); coll.add(false); Object[] arr = coll.toArray(); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); /** * 打印結(jié)果如下 * 123 * 456 * Person{name='Jerry', age=20} * Tom * false */ } } -
數(shù)組轉(zhuǎn)集合需要注意的點，代碼如下：
public class CollectionTest { @Test public void test4() { List<int[]> list1 = Arrays.asList(new int[]{1, 2, 3, 4}); //出現(xiàn)了該問題拦焚，把上面只當(dāng)成了一個數(shù)據(jù)[[I@3f0ee7cb]蜡坊，因為上面的元素為int類型的1、2赎败、3秕衙、4而不是對象沒有裝箱，然而它就把整體當(dāng)作一個對象進行存儲 System.out.println(list1); //長度只為1僵刮，而不是4 System.out.println(list1.size()); //解決方法如下： List<Integer> list2 = Arrays.asList(new Integer[]{1, 2, 3, 4, 5}); //上面的元素均為Integer包裝類對象進行存儲 System.out.println(list2); } }
六灾梦、Collection子接口之一：List接口
6.1、List接口
鑒于Java中數(shù)組用來存儲數(shù)據(jù)的局限性妓笙，我們通常使用List替代數(shù)組
List集合類中 元素有序若河、且可重復(fù)，集合中的每個元素都有其對應(yīng)的順序索引寞宫。
List容器中的元素都對應(yīng)一個整數(shù)型的序號記載其在容器中的位置萧福，可以根據(jù)序號存取容器中的元素。
JDK API中List接口的實現(xiàn)類常用的有：ArrayList辈赋、LinkedList和Vector鲫忍。
6.2膏燕、List接口方法
List除了從Collection集合繼承的方法外，List 集合里添加了一些根據(jù)索引來操作集合元素的方法悟民。
void add(int index, Object ele): 在index 位置插入eleboolean addAll(int index, Collection coll): 從index 位置開始將coll中的所有元素添加進來Object get(int index): 獲取指定index位置的元素int indexOf(Object obj): 返回obj在集合中首次出現(xiàn)的位置int lastIndexOf(Object obj): 返回obj 在當(dāng)前集合中末次出現(xiàn)的位置Object remove(int index): 移除指定index 位置的元素坝辫，并返回此元素Object set(int index, Object ele): 設(shè)置指定index 位置的元素為eleList subList(int fromIndex, int toIndex): 返回從fromIndex 到toIndex位置的子集合，遵循左閉右開的原則
6.3射亏、List實現(xiàn)類之一：ArrayList
ArrayList 是 List 接口的主要實現(xiàn)類
ArrayList存儲有序的近忙、可重復(fù)的數(shù)據(jù)
ArrayList底層使用Object[] elementData存儲，也可以說是一個”動態(tài)“數(shù)組智润，長度是可以變的
ArrayList線程不安全的及舍，查詢、獲取數(shù)據(jù)效率高
-
ArrayList 的JDK1.8 之前與之后的實現(xiàn)區(qū)別窟绷？
JDK7情況下：
-
ArrayList list = new ArrayList();//底層初始化時創(chuàng)建了長度是10的Object[]數(shù)組elementData
-
list.add(123);//添加元素相當(dāng)于elementData[0] = new Integer(123);
-
list.add(124);//如果此次的添加導(dǎo)致底層elementData數(shù)組容量不夠锯玛，則擴容。 默認(rèn)情況下兼蜈，擴容為原來的容量的1.5倍攘残，同時需要將原有數(shù)組中的數(shù)據(jù)復(fù)制到新的數(shù)組中。
- 結(jié)論：建議開發(fā)中使用帶參的構(gòu)造器：
ArrayList list = new ArrayList(int capacity)
JDK8中ArrayList的變化：
-
ArrayList list = new ArrayList();//底層Object[] elementData初始化為{}.并沒有創(chuàng)建長度為10的數(shù)組
-
list.add(123);//第一次調(diào)用add()時为狸，底層才創(chuàng)建了長度10的數(shù)組歼郭，并將數(shù)據(jù)123添加到elementData[0]
- 后續(xù)的添加和擴容操作與jdk 7 無異
- 結(jié)論：jdk7中的ArrayList的對象的創(chuàng)建類似于單例的餓漢式
? jdk8中的ArrayList的對象的創(chuàng)建類似于單例的懶漢式，延遲了數(shù)組的創(chuàng)建钥平，節(jié)省內(nèi)存实撒。
-
Arrays.asList(…) 方法返回的 List 集合姊途，既不是 ArrayList 實例涉瘾，也不是Vector 實例。 Arrays.asList(…) 返回值是一個固定長度的 List 集合
6.4捷兰、List實現(xiàn)類之二：LinkedList
LinkedList存儲有序的立叛、可重復(fù)的數(shù)據(jù)，線程是不安全的
LinkedList是 List 接口的實現(xiàn)類
LinkedList對于頻繁的插入贡茅、刪除操作秘蛇，使用此類效率比ArrayList高
LinkedList底層使用雙向鏈表存儲
6.5、新增方法
void addFirst(Object obj)void addLast(Object obj)Object getFirst()Object getLast()Object removeFirst()Object removeLast()
6.6顶考、LinkedList的概述
-
LinkedList： 雙向鏈表赁还，內(nèi)部沒有聲明數(shù)組，而是定義了Node類型的first和last驹沿，用于記錄首末元素艘策。同時，定義內(nèi)部類Node渊季，作為LinkedList中保存數(shù)據(jù)的基本結(jié)構(gòu)朋蔫。Node除了保存數(shù)據(jù)罚渐，還定義了兩個變量：
prev變量記錄前一個元素的位置
next變量記錄下一個元素的位置，源碼如下：
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
6.7驯妄、List實現(xiàn)類之三：Vector
Vector存儲有序的荷并、可重復(fù)的數(shù)據(jù)
Vector是List接口古老的實現(xiàn)類，在jdk1.0就有了
Vector線程安全的青扔，效率低源织；
Vector底層使用Object[] elementData存儲數(shù)據(jù)
在各種list中，最好把ArrayList作為缺省選擇赎懦。當(dāng)插入雀鹃、刪除頻繁時，使用LinkedList励两；Vector總是比ArrayList慢黎茎，所以盡量避免使用
Vector在jdk7和jdk8中通過Vector()構(gòu)造器創(chuàng)建對象時，底層都創(chuàng)建了長度為10的數(shù)組当悔。在擴容方面傅瞻，默認(rèn)擴容為原來的數(shù)組長度的2倍。
6.8盲憎、新增方法
void addElement(Object obj)void insertElementAt(Object obj,int index)void setElementAt(Object obj,int index)void removeElement(Object obj)void removeAllElements()
6.9嗅骄、ArrayList、Vector饼疙、LinkedList三者中的區(qū)別
-
ArrayList和LinkedList的異同：
相同點：二者都線程不安全溺森，相對線程安全的Vector，執(zhí)行效率高窑眯。都是List接口的實現(xiàn)類屏积，都可以存儲有序、可重復(fù)的數(shù)據(jù)
不同點：ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)磅甩，每次擴容為原來容量的1.5倍炊林；LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)，不需要擴容卷要；ArrayList對于查詢渣聚、獲取數(shù)據(jù)效率高，因為LinkedList需要移動指針僧叉；LinkedList對于頻繁的插入奕枝、刪除操作，效率比ArrayList高瓶堕，因為ArrayList要移動數(shù)據(jù)
-
ArrayList和Vector的異同：
相同點：存儲有序的隘道、可重復(fù)的數(shù)據(jù)；都是List接口的實現(xiàn)類；都實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)
不同點：ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)薄声，每次擴容為原來容量的1.5倍当船；Vector是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，每次擴容為原來容量的2倍默辨；ArrayList是線程不安全的德频，Vector是線程安全的；
ArrayList查詢效率比Vector要高
7.0缩幸、關(guān)于以上總結(jié)知識壹置，面試題（區(qū)分list中的remove(int index)和remove(Object obj)）
public class ListExer {
@Test
public void testListRemove() {
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
updateList(list);
System.out.println(list);
}
public void updateList(List list) {
//該remove方法調(diào)用的是remove(int index)方法;該如何調(diào)用remove(Object obj)方法呢？
list.remove(2);
//解決方法:使用包裝類,將它轉(zhuǎn)換成包裝類Integer類型
list.remove(new Integer(2));
}
}
七表谊、Collection子接口之二：Set接口
7.1钞护、Set接口
Set接口是Collection的子接口，set接口沒有提供額外的方法爆办，使用的都是Collection中聲明過的方法难咕。
Set接口存儲無序的、不可重復(fù)的數(shù)據(jù)
對于存放在Set容器中的對象距辆， 對應(yīng)的類一定要重寫equals() 和hashCode(Object obj) 方法余佃，以實現(xiàn)對象相等規(guī)則 。即： “<u>相等的對象必須具有相等的散列碼</u>**”
7.2跨算、Set實現(xiàn)類之一：HashSet
HashSet底層：數(shù)組+鏈表的結(jié)構(gòu)爆土。
HashSet 無序性：不能保證元素的排列順序，存儲的數(shù)據(jù)在底層數(shù)組中并非按照數(shù)組索引的順序添加诸蚕，而是根據(jù)數(shù)據(jù)的哈希值決定的步势。
HashSet 不可重復(fù)性：保證添加的元素按照equals()判斷時，不能返回true.即：相同的元素只能添加一個背犯。
HashSet 集合判斷兩個元素相等的標(biāo)準(zhǔn)：兩個對象通過 hashCode() 方法比較相等坏瘩，并且兩個對象的 equals() 方法返回值也相等。
HashSet 不是線程安全的
HashSet 集合元素可以是 null
HashSet 是 Set 接口的典型實現(xiàn)類
7.3媳板、HashSet中添加元素的過程
當(dāng)向 HashSet 集合中存入一個元素時桑腮，HashSet 會調(diào)用該對象的 hashCode() 方法來得到該對象的hashCode 值泉哈，然后根據(jù) hashCode 值蛉幸，通過某種散列函數(shù)決定該對象在 HashSet <u>底層數(shù)組中的存儲位置。</u>**
-
如果兩個元素的hashCode()值相等丛晦，會再繼續(xù)調(diào)用equals方法奕纫，如果equals方法結(jié)果為true，添加失斕躺场匹层；如果為false，那么會保存該元素，但是該數(shù)組的位置已經(jīng)有元素了升筏，那么會<u>通過鏈表的方式繼續(xù)鏈接</u>**撑柔。
<u>通過鏈表的方式繼續(xù)鏈接分為兩種情況</u>**：
- jdk1.7：新增的元素放到數(shù)組中，指向原來的元素
- jdk1.8：原來的元素放在數(shù)組中您访，指向新增的元素
如果兩個元素的 equals() 方法返回 true铅忿，但它們的 hashCode() 返回值不相等，hashSet 將會把它們存儲在底層數(shù)組的不同的位置灵汪，但依然可以添加成功檀训。
HashSet底層存儲數(shù)據(jù)結(jié)構(gòu)圖
-
存儲數(shù)據(jù)案例<u>代碼如下：</u>**
public class SetTest { @Test public void test1() { Set set = new HashSet(); set.add(456); set.add(123); set.add(123); set.add("AA"); set.add("CC"); set.add(new User("Tom", 12)); set.add(new User("Tom", 12)); set.add(129); Iterator iterator = set.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); /** * 結(jié)果如下：由于User類中沒有重寫equals()方法和hashCode()方法,所以他們存儲的時候調(diào)用了 * Object的hashCode()方法，所產(chǎn)生的hash值是不相同的享言。導(dǎo)致這認(rèn)為這兩個數(shù)據(jù)User{name='Tom', age=12}峻凫、 * User{name='Tom', age=12}不相同。 * 而123只打印了一個览露，為什么呢荧琼？因為HashSet底層存儲數(shù)據(jù)時都需調(diào)用equals()進行比較 * AA * CC * 129 * 456 * User{name='Tom', age=12} * User{name='Tom', age=12} * 123 */ } } }
7.4、重寫hashCode()方法的基本準(zhǔn)則
在程序運行時差牛，同一個對象多次調(diào)用 hashCode() 方法應(yīng)該返回相同的值
當(dāng)兩個對象的 equals() 方法比較返回 true 時铭腕，這兩個對象的 hashCode()方法的返回值也應(yīng)相等
對象中用作 equals() 方法比較的 Field，都應(yīng)該用來計算 hashCode 值多糠。
-
注意：在自定義類中可以調(diào)用工具自動重寫equals和hashCode累舷，問題：為什么用Eclipse/IDEA復(fù)寫hashCode方法，<u>有31這個數(shù)字夹孔？</u>**
public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; }選擇系數(shù)的時候要選擇盡量大的系數(shù)被盈。因為如果計算出來的hash地址越大，所謂的“沖突”就越少搭伤，查找起來效率也會提高只怎。（減少沖突）
并且31只占用5bits,相乘造成數(shù)據(jù)溢出的概率較小。
31可以 由i*31== (i<<5)-1來表示,現(xiàn)在很多虛擬機里面都有做相關(guān)優(yōu)化怜俐。（提高算法效率）
31是一個素數(shù)身堡，素數(shù)作用就是如果我用一個數(shù)字來乘以這個素數(shù)，那么最終出來的結(jié)果只能被素數(shù)本身和被乘數(shù)還有1來整除拍鲤！(減少沖突)
7.5贴谎、重寫 equals() 方法的基本原則
以自己定義的類為例，何時需要重寫equals()方法季稳？
必須遵守<u>相等的對象必須具有相等的散列碼</u>**
結(jié)論：復(fù)寫equals方法的時候一般都需要同時復(fù)寫hashCode方法擅这。通常參與計算hashCode 的對象的屬性也應(yīng)該參與到equals()中進行計算
7.6、Set實現(xiàn)類之二：LinkedHashSet
LinkedHashSet 是 HashSet 的子類
LinkedHashSet 根據(jù)元素的 hashCode 值來決定元素在底層數(shù)組的存儲位置景鼠，但它<u>同時使用雙向鏈表維護元素的次序</u>仲翎，這使得元素看起來是以插入順序保存的**
對于頻繁的遍歷操作，LinkedHashSet效率高于HashSet，但是插入性能HashSet略高于LinkedHashSet
LinkedHashSet 不允許集合元素重復(fù)溯香。
<img src="https://imgkr.cn-bj.ufileos.com/e89a129b-423e-464b-9f08-426a2278e6b1.png" />
-
存儲數(shù)據(jù)<u>代碼如下：</u>**
public class SetTest { @Test public void test2() { Set set = new LinkedHashSet(); set.add(456); set.add(123); set.add(123); set.add("AA"); set.add("CC"); set.add(new User("Tom", 12)); set.add(new User("Tom", 12)); set.add(129); Iterator iterator = set.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); /** * 打印結(jié)果如下：看起來是以插入的順序保存的鲫构，是因為它底層同時使用雙向鏈表維護元素的次序 * 456 * 123 * AA * CC * User{name='Tom', age=12} * User{name='Tom', age=12} * 129 */ } } }
7.7、Set實現(xiàn)類之三：TreeSet
向TreeSet中添加的數(shù)據(jù)玫坛，要求是相同類的對象芬迄。
TreeSet 是 SortedSet 接口的實現(xiàn)類，TreeSet 可以確保集合元素處于排序狀態(tài)昂秃。
TreeSet底層使用 紅黑樹結(jié)構(gòu)存儲數(shù)據(jù)
TreeSet 兩種排序方法： 自然排序和 定制排序禀梳。默認(rèn)情況下，TreeSet 采用自然排序肠骆。
TreeSet有序算途，查詢速度比List快
7.8、新增方法
Comparator comparator()Object first()Object last()Object lower(Object e)Object higher(Object e)SortedSet subSet(fromElement, toElement)SortedSet headSet(toElement)SortedSet tailSet(fromElement)
TreeSet中元素排序注意的點：
自然排序：
如果試圖把一個對象添加到 TreeSet 時蚀腿，則該對象的類必須實現(xiàn) Comparable接口
實現(xiàn) Comparable 的類必須實現(xiàn) compareTo(Object obj) 方法嘴瓤，兩個對象即通過compareTo(Object obj) 方法的返回值來比較大小。
只有相同類的兩個實例才會比較大小莉钙，所以向 TreeSet 中添加的應(yīng)該是同一個類的對象廓脆。
代碼如下：
public class User implements Comparable {
private String name;
private int age;
@Override
public int compareTo(Object o) {
if (o instanceof User) {
User user = (User) o;
int compare = -this.name.compareTo(user.name);
if (compare != 0) {
return compare;
} else {
return Integer.compare(this.getAge(), user.getAge());
}
} else {
throw new RuntimeException("輸入的類型不匹配");
}
}
}
public class TreeSet {
@Test
public void test1() {
java.util.TreeSet set = new java.util.TreeSet<>();
set.add(new User("Tom", 12));
set.add(new User("Jerry", 32));
set.add(new User("Jim", 2));
set.add(new User("Mike", 65));
set.add(new User("Jack", 33));
set.add(new User("Jack", 56));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
/**
* 打印結(jié)果如下：如果名字相同，就按年齡排序
* User{name='Tom', age=12}
* User{name='Mike', age=65}
* User{name='Jim', age=2}
* User{name='Jerry', age=32}
* User{name='Jack', age=33}
* User{name='Jack', age=56}
*/
}
}
}
定制排序：
只能向TreeSet中添加類型相同的對象磁玉。否則發(fā)生ClassCastException異常停忿。
要實現(xiàn)定制排序，需要將實現(xiàn)Comparator接口的實例作為形參傳遞給TreeSet的構(gòu)造器
當(dāng)元素的類型實現(xiàn)java.lang.Comparable 接口蚊伞，而你又使用了定制排序席赂，那就按照定制排序設(shè)定的來排序記住要將實現(xiàn)Comparator接口的實例作為形參傳遞給TreeSet的構(gòu)造器
代碼如下：
public class User implements Comparable {
private String name;
private int age;
@Override
public int compareTo(Object o) {
if (o instanceof User) {
User user = (User) o;
int compare = -this.name.compareTo(user.name);
if (compare != 0) {
return compare;
} else {
return Integer.compare(this.getAge(), user.getAge());
}
} else {
throw new RuntimeException("輸入的類型不匹配");
}
}
}
public class TreeSet {
@Test
public void test2() {
Comparator com = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof User && o2 instanceof User) {
User u1 = (User) o1;
User u2 = (User) o2;
int compare = Integer.compare(u1.getAge(), u2.getAge());
if (compare != 0) {
return compare;
} else {
return -u1.getName().compareTo(u2.getName());
}
} else {
throw new RuntimeException("輸入的數(shù)據(jù)類型不匹配");
}
}
};
java.util.TreeSet set = new java.util.TreeSet<>(com);
set.add(new User("Tom", 12));
set.add(new User("Jerry", 32));
set.add(new User("Jim", 2));
set.add(new User("Mike", 65));
set.add(new User("Mary", 33));
set.add(new User("Jack", 33));
set.add(new User("Jack", 56));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
/**
* 打印結(jié)果：先按年齡從小到大排序，如果年齡相同时迫，就按名字從大到小排序
User{name='Jim', age=2}
User{name='Tom', age=12}
User{name='Jerry', age=32}
User{name='Mary', age=33}
User{name='Jack', age=33}
User{name='Jack', age=56}
User{name='Mike', age=65}
*/
}
}
}
7.9颅停、關(guān)于以上set集合知識點的運用（面試題）
- 關(guān)于Set接口中的HashSet存儲數(shù)據(jù)的一道面試題；代碼如下：
public class Person {
int id;
String name;
@Override
public String toString() {
return "Person{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person person = (Person) o;
return getId() == person.getId() &&
Objects.equals(getName(), person.getName());
}
@Override
public int hashCode() {
return Objects.hash(getId(), getName());
}
}
public class CollectionTest {
@Test
public void test3(){
HashSet set = new HashSet();
Person p1 = new Person(1001,"AA");
Person p2 = new Person(1002,"BB");
set.add(p1);
set.add(p2);
// 1掠拳、 打印結(jié)果如下:[Person{id=1002, name='BB'}, Person{id=1001, name='AA'}]
System.out.println(set);
p1.name = "CC";
set.remove(p1);
// 2癞揉、 打印結(jié)果如下:[Person{id=1002, name='BB'}, Person{id=1001, name='CC'}]
// 為啥是這樣的結(jié)果呢？
// 答：這就關(guān)系到HashSet底層存儲數(shù)據(jù)的特點溺欧，首先存儲new Person(1001,"AA")數(shù)據(jù)時根據(jù)Hash值來判斷存儲在數(shù)組中的哪個位置喊熟，當(dāng)把其中的值改變后又 需要根據(jù)計算Hash值來判斷存儲位置與之前的newPerson(1001,"AA")數(shù)據(jù)的位置不同，但其值是空的胧奔，然后再去刪除的時候是空的逊移，未刪除掉。
System.out.println(set);
set.add(new Person(1001,"CC"));
// 3、 打印結(jié)果如下:[Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}]
// 此時添加的位置就是上面刪除時為空的那個位置
System.out.println(set);
set.add(new Person(1001,"AA"));
// 4菊匿、 打印結(jié)果如下:[Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}, Person{id=1001, name='AA'}]
// 此時添加的元素new Person(1001,"AA")位置的hash值跟這個元素中new Person(1001,"AA")的值改變后的位置是一樣的适贸，然后再根據(jù)equals()方法來判 斷厨幻，發(fā)現(xiàn)值不相同則就存儲
System.out.println(set);
}
}
- 關(guān)于List中去除重復(fù)數(shù)據(jù)的一道練習(xí)題找田，代碼如下：
public class CollectionTest {
//第一種方式去重
@Test
public void test2(){
List list = new ArrayList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(2));
list.add(new Integer(4));
list.add(new Integer(4));
List list1 = duplicateList(list);
for(Object obj : list1){
System.out.println(obj);
}
}
public List duplicateList (List list){
HashSet set = new HashSet(list);
return new ArrayList(set);
}
//第二種方式去重
@Test
public void test2(){
List list = new ArrayList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(2));
list.add(new Integer(4));
list.add(new Integer(4));
List list1 = duplicateList(list);
for(Object obj : list1){
System.out.println(obj);
}
}
public List duplicateList (List list){
HashSet set = new HashSet();
set.addAll(list);
return new ArrayList(set);
}
//第三種方式去重
@Test
public void test2(){
List list = new ArrayList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(2));
list.add(new Integer(4));
list.add(new Integer(4));
List list1 = duplicateList(list);
for(Object obj : list1){
System.out.println(obj);
}
}
public List duplicateList (List list){
HashSet set = new HashSet(list);
list.clear();
list.addAll(set);
return list;
}
}
8.0毒姨、比較器（排序）
1. Java中的對象冤竹，正常情況下宿礁，只能進行比較：== 或 != 案铺。不能使用 > 或 < ，但需要對多個對象進行排序就要使用Comparable 和Comparator兩個接口
<u>2.像String梆靖、包裝類等實現(xiàn)了Comparable接口控汉，重寫了compareTo(obj)方法，默認(rèn)是自然排序返吻，從小到大排</u>
<u>3.</u>**對于自定義類來說姑子，如果需要排序，我們可以讓自定義類實現(xiàn)Comparable接口测僵，重寫compareTo(obj)方法街佑。在compareTo(obj)方法中指明如何排序
Java實現(xiàn)對象排序的方式有兩種：
自然排序：java.lang.Comparable ------>重寫compareTo(Object obj) 方法
定制排序：java.util.Comparator -------->重寫compare(Object o1,Object o2)方法
Comparable接口與Comparator接口的使用的對比
Comparable接口的方式一旦定制下來，保證Comparable接口實現(xiàn)類的對象在任何位置都可以比較大小捍靠。
Comparator接口屬于臨時性的比較
8.1沐旨、自然排序：java.lang.Comparable
Comparable接口強行對實現(xiàn)它的每個類的對象進行整體排序。這種排序被稱為類的自然排序
實現(xiàn) Comparable 的類必須實現(xiàn) compareTo(Object obj) 方法榨婆，兩個對象即通過 compareTo(Object obj) 方法的返回值來比較大小磁携。如果<u>當(dāng)前對象this大于形參對象obj，則返回正整數(shù)</u>良风，如果<u>當(dāng)前對象this小于形參對象obj颜武，則返回負(fù)整數(shù)</u>，如果<u>當(dāng)前對象this等于形參對象obj拖吼，則返回零</u>鳞上。
對于類 C 的每一個 e1 和 e2 來說，當(dāng)且僅當(dāng)
e1.compareTo(e2) == 0與e1.equals(e2)具有相同的 boolean 值時吊档，類 C 的自然排序才叫做與 equals一致篙议。<u>最好使自然排序與 equals 一致。</u>實現(xiàn)Comparable接口的對象列表（和數(shù)組）可以通過 Collections.sort 或Arrays.sort進行自動排序怠硼。實現(xiàn)此接口的對象可以用作有序映射中的鍵或有序集合中的元素鬼贱，無需指定比較器
-
Comparable 的典型 實現(xiàn)：(默認(rèn)都是從小到大排列的)
- String：按照字符串中字符的Unicode值進行比較
- Character：按照字符的Unicode值來進行比較
- 數(shù)值類型對應(yīng)的包裝類以及BigInteger、BigDecimal：按照它們對應(yīng)的數(shù)值大小進行比較
- Boolean：true 對應(yīng)的包裝類實例大于 false 對應(yīng)的包裝類實例
- Date香璃、Time等：后面的日期時間比前面的日期時間大
<u>代碼案例如下：</u>**
public class Goods implements Comparable {
private String name;
private double price;
//重寫compareTo方法
@Override
public int compareTo(Object o) {
if (o instanceof Goods) {
Goods goods = (Goods) o;
////按照價格從高到低排序
if (this.price > goods.price) {
return 1;
//按照價格從低到高排序
} else if (this.price < goods.price) {
return -1;
} else {
//按照產(chǎn)品名稱從高到低排序
return -this.name.compareTo(goods.name);
}
}
throw new RuntimeException("傳入的數(shù)據(jù)類型不一致这难！");
}
}
public class CompareTest {
@Test
public void test2(){
Goods[]arr = new Goods[5];
arr[0] = new Goods("lenovoMouse",34);
arr[1] = new Goods("dellMouse",43);
arr[2] = new Goods("xiaomiMouse",12);
arr[3] = new Goods("huaweiMouse",65);
arr[4] = new Goods("microsoftMouse",43);
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
//打印結(jié)果如下，價格相同按名稱排序
//[Goods{name='xiaomiMouse', price=12.0}, Goods{name='lenovoMouse', price=34.0}, Goods{name='microsoftMouse', price=43.0}, Goods{name='dellMouse', price=43.0}, Goods{name='huaweiMouse', price=65.0}]
}
}
8.2葡秒、定制排序：java.util.Comparator
當(dāng)元素的類型沒有實現(xiàn)java.lang.Comparable 接口而又不方便修改代碼姻乓，了 或者實現(xiàn)java.lang.Comparable 接口的排序規(guī)則不適合當(dāng)前的操作嵌溢，那用 么可以考慮使用 Comparator 的對象來 排序，強行對多個對象進行整體排序的比較蹋岩。
重寫compare(Object o1,Object o2)方法赖草，比較o1和o2的大小： 如果方法返示 回正整數(shù)剪个，則表示o1 大于o2 如果返回0 秧骑，表示相等；返回負(fù)整數(shù)扣囊，表示o1 小于o2乎折。
可以將 Comparator 傳遞給 sort 方法可以使用匿名內(nèi)部類進行操作（如 Collections.sort 或 Arrays.sort），從而允許在排序順序上實現(xiàn)精確控制侵歇。
當(dāng)元素的類型實現(xiàn)java.lang.Comparable 接口笆檀，而你又使用了定制排序，那就按照定制排序設(shè)定的來排序
<u>代碼案例如下：</u>**
public class Goods implements Comparable {
private String name;
private double price;
//重寫compareTo方法
@Override
public int compareTo(Object o) {
if (o instanceof Goods) {
Goods goods = (Goods) o;
////按照價格從高到低排序
if (this.price > goods.price) {
return 1;
//按照價格從低到高排序
} else if (this.price < goods.price) {
return -1;
} else {
//按照產(chǎn)品名稱從高到低排序
return -this.name.compareTo(goods.name);
}
}
throw new RuntimeException("傳入的數(shù)據(jù)類型不一致盒至！");
}
}
public class CompareTest {
@Test
public void test4() {
Goods[] arr = new Goods[6];
arr[0] = new Goods("lenovoMouse", 34);
arr[1] = new Goods("dellMouse", 43);
arr[2] = new Goods("xiaomiMouse", 12);
arr[3] = new Goods("huaweiMouse", 65);
arr[4] = new Goods("huaweiMouse", 224);
arr[5] = new Goods("microsoftMouse", 43);
Arrays.sort(arr, new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof Goods && o2 instanceof Goods) {
Goods g1 = (Goods) o1;
Goods g2 = (Goods) o2;
if (g1.getName().equals(g2.getName())) {
//如果名字相同酗洒，就比較價格從大到小排序
return -Double.compare(g1.getPrice(), g2.getPrice());
} else {
//否則就比較名字
return g1.getName().compareTo(g2.getName());
}
}
throw new RuntimeException("輸入的數(shù)據(jù)類型不一致");
}
});
System.out.println(Arrays.toString(arr));
//打印結(jié)果：
//[Goods{name='dellMouse', price=43.0}, Goods{name='huaweiMouse', price=224.0}, Goods{name='huaweiMouse', price=65.0}, Goods{name='lenovoMouse', price=34.0}, Goods{name='microsoftMouse', price=43.0}, Goods{name='xiaomiMouse', price=12.0}]
}
@Test
public void test3() {
String[] arr = new String[]{"aa", "bb", "cc", "dd", "ee", "ff", "gg"};
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if (o1 instanceof String && o2 instanceof String) {
String s1 = (String) o1;
String s2 = (String) o2;
//從大到小進行排序
return -s1.compareTo(s2);
}
throw new RuntimeException("輸入的數(shù)據(jù)類型不一致");
}
});
System.out.println(Arrays.toString(arr));
//打印結(jié)果如下:[gg, ff, ee, dd, cc, bb, aa]
}
}
八、Map接口
8.1枷遂、Map接口
Map 中的 key 和 value 都可以是任何引用類型的數(shù)據(jù)
Map接口的常用實現(xiàn)類：HashMap樱衷、TreeMap、LinkedHashMap和Properties酒唉。其中矩桂，HashMap是 Map 接口使用頻率最高的實現(xiàn)類
key 和 value 之間存在單向一對一關(guān)系，即通過指定的 key 總能找到唯一的痪伦、確定的 value
Map 中的 key 用Set來存放侄榴， 不允許重復(fù)，即同一個 Map 對象所對應(yīng)的類网沾，<u>須重寫hashCode()和equals()方法</u>**
8.2癞蚕、Map存儲數(shù)據(jù)結(jié)構(gòu)圖
8.3、Map中常用的接口方法
<u>添加辉哥、刪除桦山、修改操作：</u>**
Object put(Object key,Object value)：將指定key-value添加到(或修改)當(dāng)前map對象中void putAll(Map m):將m中的所有key-value對存放到當(dāng)前map中Object remove(Object key)：移除指定key的key-value對，并返回當(dāng)前刪除的valuevoid clear()：清空當(dāng)前map中的所有數(shù)據(jù)醋旦，當(dāng)前size為零
<u>元素查詢的操作：</u>**
Object get(Object key)：獲取指定key對應(yīng)的valueboolean containsKey(Object key)：是否包含指定的keyboolean containsValue(Object value)：是否包含指定的valueint size()：返回map中key-value對的個數(shù)boolean isEmpty()：判斷當(dāng)前map是否為空boolean equals(Object obj)：判斷當(dāng)前map和參數(shù)對象obj是否相等
<u>元視圖操作的方法（相當(dāng)于遍歷Map集合）：</u>**
Set keySet()：返回所有key構(gòu)成的Set集合
Collection values()：返回所有value構(gòu)成的Collection集合
Set entrySet()：返回所有key-value對構(gòu)成的Set集合
對于遍歷的方法恒水，如下代碼所示：
public class MapTest {
@Test
public void test() {
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 1234);
map.put("BB", 56);
//遍歷所有的key集:KeySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
/**
* 打印結(jié)果如下：
* AA
* BB
* 45
*/
}
//遍歷Value集:values()
Collection values = map.values();
Iterator iterator1 = values.iterator();
while (iterator1.hasNext()) {
System.out.println(iterator1.next());
/**
* 打印結(jié)果如下:
* 123
* 56
* 1234
*/
}
//方式一、 遍歷所有的Key-value
Set entrySet = map.entrySet();
Iterator iterator2 = entrySet.iterator();
while (iterator2.hasNext()) {
Object obj = iterator2.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
/**
* 打印結(jié)果如下：
* AA---->123
* BB---->56
* 45---->1234
*/
}
//方式二饲齐、 遍歷所有的Key-value
Set set1 = map.keySet();
Iterator iterator3 = set1.iterator();
while (iterator3.hasNext()) {
Object key = iterator3.next();
Object value = map.get(key);
System.out.println(key + "---->" + value);
/**
* 打印結(jié)果如下：
* AA---->123
* BB---->56
* 45---->1234
*/
}
}
}
九钉凌、Map實現(xiàn)類之一：HashMap
9.1、HashMap實現(xiàn)類
HashMap是 Map 接口 使用頻率最高的實現(xiàn)類
-
HashMap底層：
JDK7之前：數(shù)組+鏈表
JDK8之后：數(shù)組+鏈表+紅黑樹
Map中的key:無序的捂人、不可重復(fù)的御雕，使用Set存儲所有的key -------> key所在的類要重寫equals()和hashCode()
Map中的value:無序的矢沿、可重復(fù)的，使用Collection存儲所有的value -----> value所在的類要重寫equals()
Map中的一個鍵值對：key-value 構(gòu)成了一個Entry對象饮笛。
Map中的鍵值對構(gòu)成的Entry對象：無序的咨察、不可重復(fù)的论熙，使用Set存儲所有的entry對象
HashMap：線程不安全的福青，效率高；可以存儲null的key和null的value
HashMap 判斷兩個 key 相等的標(biāo)準(zhǔn)是：兩個 key 通過 equals() 方法返回 true脓诡，hashCode 值也相等无午。
HashMap 判斷兩個 value 相等的標(biāo)準(zhǔn)是：兩個 value 通過 equals() 方法返回 true
9.2、HashMap的存儲結(jié)構(gòu)
JDK7之前：
JDK8之后：
9.3祝谚、HashMap源碼中的重要常量
DEFAULT_INITIAL_CAPACITY: HashMap的默認(rèn)容量16MAXIMUM_CAPACITY: HashMap的最大支持容量2^30DEFAULT_LOAD_FACTOR：HashMap的默認(rèn)加載因子0.75TREEIFY_THRESHOLD：Bucket中鏈表長度大于該默認(rèn)值8時宪迟，轉(zhuǎn)化為紅黑樹UNTREEIFY_THRESHOLD：Bucket中紅黑樹存儲的Node小于該默認(rèn)值，轉(zhuǎn)化為鏈表MIN_TREEIFY_CAPACITY：桶中的Node被樹化時最小的hash表容量交惯。（當(dāng)桶中Node的數(shù)量大到需要變紅黑樹時次泽，若hash表容量小于MIN_TREEIFY_CAPACITY時，此時應(yīng)執(zhí)行resize擴容操作這MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍席爽。）table：存儲元素的數(shù)組意荤，總是2的n次冪entrySet： ：存儲具體元素的集size：HashMap中存儲的鍵值對的數(shù)量modCount：HashMap擴容和結(jié)構(gòu)改變的次數(shù)。threshold：擴容的臨界值只锻，=容量*填充因子loadFactor：填充因子
9.4玖像、HashMap在JDK1.7之前存儲數(shù)據(jù)的過程
HashMap的內(nèi)部存儲結(jié)構(gòu)其實是 數(shù)組和鏈表的結(jié)合，當(dāng)實例化一個HashMap時齐饮，系統(tǒng)會創(chuàng)建一個長度為16的Entry數(shù)組捐寥，在這個數(shù)組中可以存放元素的位置我們稱之為“桶”(bucket)
每個bucket中存儲一個元素，即一個Entry對象祖驱，但每一個Entry對象可以帶一個引用變量握恳，用于指向下一個元素，因此捺僻，在一個桶中睡互，就有可能生成一個Entry鏈。而且新添加的元素作為鏈表的頭節(jié)點(head)陵像。
-
添加元素過程：
向HashMap中添加entry1(key就珠，value)，1醒颖、需要首先計算entry1中key的哈希值(根據(jù)key所在類hashCode()計算得到)妻怎，此哈希值經(jīng)過處理以后，得到在底層Entry[]數(shù)組中要存儲的位置i泞歉。2逼侦、如果位置i上沒有元素匿辩，則entry1直接添加成功。3榛丢、如果位置i上已經(jīng)存在entry2(或還有鏈表存在的entry3铲球，entry4)，則需要通過循環(huán)的方法晰赞，依次比較entry1中key和其他的entry稼病。4、如果彼此hash值不同掖鱼，則直接添加成功然走。5、如果hash值相同戏挡，繼續(xù)調(diào)用equals()方法比較芍瑞，如果返回值為true，則使用entry1的value去替換equals為true的entry的value褐墅。如果遍歷一遍以后拆檬，發(fā)現(xiàn)所有的equals返回都為false,則entry1仍可添加成功。entry1指向原有entry元素妥凳。
-
HashMap擴容：
當(dāng)HashMap中的元素越來越多的時候竟贯，hash沖突的幾率也就越來越高，因為數(shù)組的長度是固定的猾封。所以為了提高查詢的效率澄耍，就要對HashMap的數(shù)組進行擴容，而在HashMap數(shù)組擴容之后晌缘，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置齐莲，并放進去，這就是resize磷箕。
-
那么HashMap 什么時候進行擴容呢 选酗？
當(dāng)HashMap中的元素個數(shù)超過數(shù)組的
size*DEFAULT_LOAD_FACTOR時且在數(shù)組中要存放的位置非空)時就會進行數(shù)組擴容。DEFAULT_LOAD_FACTOR=0.75這是一個折中的取值岳枷。數(shù)組中大小默認(rèn)值為16芒填，當(dāng)HashMap中元素個數(shù)超過160.75=12（臨界值）就會將數(shù)組的大小擴大為2乘以16=32并將原有的數(shù)據(jù)復(fù)制過來，這是非常消耗性能的空繁，如果我們已經(jīng)預(yù)知HashMap中元素的個數(shù)殿衰，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高HashMap的性能。*
9.5盛泡、HashMap在JDK1.8之后存儲數(shù)據(jù)的過程
HashMap的內(nèi)部存儲結(jié)構(gòu)其實是 數(shù)組+ 鏈表+ 樹 的結(jié)合闷祥。當(dāng)實例化一個HashMap時，會初始initialCapacity和loadFactor傲诵，在put第一對映射關(guān)系時凯砍，系統(tǒng)會創(chuàng)建一個長度為16的Node數(shù)組箱硕，在這個數(shù)組中可以存放元素的位置我們稱之為“桶”(bucket)
每個bucket中存儲一個元素，即一個Node對象悟衩，但每一個Node對象可以帶一個引用變量next剧罩，用于指向下一個元素，因此座泳，在一個桶中惠昔，就有可能生成一個Node鏈。也可能是一個一個TreeNode對象钳榨，每一個TreeNode對象可以有兩個葉子結(jié)點left和right舰罚，因此纽门，在一個桶中薛耻，就有可能生成一個TreeNode樹。而新添加的元素作為鏈表的last赏陵，或樹的葉子結(jié)點饼齿。
-
那么HashMap 什么時候進行擴容和樹形化呢 ？
當(dāng)HashMap中的元素個數(shù)超過數(shù)組的
size*DEFAULT_LOAD_FACTOR時且在數(shù)組中要存放的位置非空)時就會進行數(shù)組擴容蝙搔。DEFAULT_LOAD_FACTOR=0.75這是一個折中的取值缕溉。數(shù)組中大小默認(rèn)值為16，當(dāng)HashMap中元素個數(shù)超過160.75=12（臨界值threshold）就會將數(shù)組的大小擴大為2乘以16=32并將原有的數(shù)據(jù)復(fù)制過來吃型，這是非常消耗性能的证鸥，如果我們已經(jīng)預(yù)知HashMap中元素的個數(shù)，那么預(yù)設(shè)元素的個數(shù)能夠有效的提HashMap的性能勤晚。*當(dāng)HashMap中的其中一個鏈的對象個數(shù)如果達(dá)到了8個枉层，此時如果capacity沒有達(dá)到64，那么HashMap會先擴容解決赐写，如果已經(jīng)達(dá)到了64鸟蜡，那么這個鏈會變成樹，結(jié)點類型由Node變成TreeNode類型挺邀。當(dāng)然揉忘，如果當(dāng)映射關(guān)系被移除后，下次resize方法時判斷樹的結(jié)點個數(shù)低于6個端铛，也會把樹再轉(zhuǎn)為鏈表
9.6泣矛、關(guān)于映射關(guān)系的key 是否可以修改（會修改hashcode的值） ？
- 答：最好不要禾蚕，映射關(guān)系存儲到HashMap中會存儲key的hash值您朽，這樣就不用在每次查找時重新計算每一個Entry或Node（TreeNode）的hash值了，因此如果已經(jīng)put到Map中的映射關(guān)系夕膀，再修改key的屬性虚倒，而這個屬性又參與hashcode值的計算美侦，那么會導(dǎo)致匹配不上
9.7、JDK8相對于JDK7的變化：
HashMap map = new HashMap();//默認(rèn)情況下魂奥，先不創(chuàng)建長度為16的數(shù)組菠剩，會加載加載因子
當(dāng)首次調(diào)用map.put()時，再創(chuàng)建長度為16的數(shù)組
JDK8中數(shù)組為Node類型耻煤，在jdk7中稱為Entry類型
形成鏈表結(jié)構(gòu)時具壮，新添加的key-value對在鏈表的尾部（七上八下）
當(dāng)數(shù)組指定索引位置的鏈表長度>8時，且map中的數(shù)組的長度> 64時哈蝇，此索引位置上的所有key-value對使用紅黑樹進行存儲
9.8棺妓、對于HashMap的面試題（負(fù)載對 因子值的大小，對HashMap 有什么影響炮赦？）
負(fù)載因子的大小決定了HashMap的數(shù)據(jù)密度
負(fù)載因子越大密度越大怜跑，發(fā)生碰撞的幾率越高，數(shù)組中的鏈表越容易長,造成查詢或插入時的比較次數(shù)增多吠勘，性能會下降
-
負(fù)載因子越小性芬，就越容易觸發(fā)擴容，數(shù)據(jù)密度也越小剧防，意味著發(fā)生碰撞的幾率越小植锉，數(shù)組中的鏈表也就越短，查詢和插入時比較的次數(shù)也越小峭拘，性能會更高俊庇。但是會浪費一定的內(nèi)容空間。而且經(jīng)常擴容也會影響性能鸡挠，建
議初始化預(yù)設(shè)大一點的空間辉饱。
會考慮將負(fù)載因子設(shè)置為0.7~0.75，此時平均檢索長度接近于常數(shù)
十宵凌、Map實現(xiàn)類之二：LinkedHashMap
在遍歷map元素時鞋囊，可以按照添加的順序?qū)崿F(xiàn)遍歷。
LinkedHashMap 是 HashMap 的子類
在HashMap存儲結(jié)構(gòu)的基礎(chǔ)上瞎惫，使用了一對雙向鏈表來記錄添加元素的順序
與LinkedHashSet類似溜腐，LinkedHashMap 可以維護 Map 的迭代順序：迭代順序與 Key-Value 對的插入順序一致
-
為什么會按照添加的順序?qū)崿F(xiàn)遍歷，請看源碼如下：
//LinkedHashMap內(nèi)部類： Entry static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } //HashMap內(nèi)部類：Node static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } }實現(xiàn)了雙向鏈表記錄添加元素的順序瓜喇，才會按照添加的順序?qū)崿F(xiàn)遍歷
十一挺益、Map實現(xiàn)類之三：TreeMap
TreeMap存儲 Key-Value 對時，需要根據(jù) key-value 對進行排序乘寒。TreeMap 可以保證所有的 Key-Value 對處于 有序狀態(tài)望众。
向TreeMap中添加key-value，要求key必須是由同一個類創(chuàng)建的對象
TreeMap底層使用 紅黑樹結(jié)構(gòu)存儲數(shù)據(jù)
-
TreeMap 的 Key 的排序：
- 自然排序：TreeMap 的所有的 Key 必須實現(xiàn) Comparable 接口，而且所有的 Key 應(yīng)該是同一個類的對象烂翰，否則將會拋出 ClasssCastException
- 定制排序：創(chuàng)建 TreeMap 時夯缺，傳入一個 Comparator 對象，該對象負(fù)責(zé)對TreeMap 中的所有 key 進行排序甘耿。此時不需要 Map 的 Key 實現(xiàn)Comparable 接口
treeMap判斷 兩個key 相等的標(biāo)準(zhǔn)：兩個key通過compareTo()方法或者compare()方法返回0踊兜。
案例如下：自然排序
public class User implements Comparable{
private String name;
private int age;
//按照姓名從大到小排列,年齡從小到大排列
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
//return -this.name.compareTo(user.name);
int compare = -this.name.compareTo(user.name);
if(compare != 0){
return compare;
}else{
return Integer.compare(this.age,user.age);
}
}else{
throw new RuntimeException("輸入的類型不匹配");
}
}
}
public class TreeMapTest {
@Test
public void test1(){
TreeMap map = new TreeMap();
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
}
定制排序：
public class TreeMapTest {
@Test
public void test2(){
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
return Integer.compare(u1.getAge(),u2.getAge());
}
throw new RuntimeException("輸入的類型不匹配！");
}
});
User u1 = new User("Tom",23);
User u2 = new User("Jerry",32);
User u3 = new User("Jack",20);
User u4 = new User("Rose",18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "---->" + entry.getValue());
}
}
}
十二佳恬、Map實現(xiàn)類之四：Hashtable
Hashtable是個古老的 Map 實現(xiàn)類捏境，JDK1.0就提供了
Hashtable是線程安全的
與HashMap不同，Hashtable 不允許使用 null 作為 key 和 null 作為value
Hashtable判斷兩個key相等毁葱、兩個value相等的標(biāo)準(zhǔn)垫言，與HashMap一致。
Hashtable實現(xiàn)原理和HashMap相同倾剿，底層都使用數(shù)組+紅黑樹+鏈表結(jié)構(gòu)
代碼案例如下：
public class MapTest {
@Test
public void test(){
//HashTable
Map map1 = new Hashtable();
map1.put(null, null);
System.out.println(map1);
/**
* 會報錯：不能添加為null的元素
* java.lang.NullPointerException
*/
//HashMap
Map map = new HashMap();
map.put(null, null);
System.out.println(map);
/**
* 打印結(jié)果如下：
* {null=null}
*/
}
}
十三筷频、Map實現(xiàn)類之五：Properties
Properties 類是 Hashtable 的子類，該對象用于處理屬性文件
由于屬性文件里的 key柱告、value 都是字符串類型截驮，所以 <u>Properties 里的 key和 value 都是字符串類型</u>**
存取數(shù)據(jù)時笑陈，建議使用
setProperty(String key,String value)方法和getProperty(String key)方法
案例如下：
public class PropertiesTest {
//Properties:常用來處理配置文件且key和value都是String類型
public static void main(String[] args) {
FileInputStream fis = null;
try {
Properties pros = new Properties();
fis = new FileInputStream("jdbc.properties");
pros.load(fis);//加載流對應(yīng)的文件
String name = pros.getProperty("name");
String password = pros.getProperty("password");
System.out.println("name = " + name + ", password = " + password);
} catch (IOException e) {
e.printStackTrace();
} finally {
if(fis != null){
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
}
十五际度、Collections工具類（操作集合）Arrays工具類（操作數(shù)組）
1、Collections工具類
Collections 是一個操作 Set涵妥、List 和 Map 等集合的工具類
Collections 中提供了一系列靜態(tài)的方法對集合元素進行排序乖菱、查詢和修改等操作，還提供了對集合對象設(shè)置不可變蓬网、對集合對象實現(xiàn)同步控制等方法
2窒所、Collections常用方法
排序操作：
reverse(List)：反轉(zhuǎn) List 中元素的順序shuffle(List)：對 List 集合元素進行隨機排序sort(List)：根據(jù)元素的自然順序?qū)χ付?List 集合元素按升序排序sort(List，Comparator)：根據(jù)指定的 Comparator 產(chǎn)生的順序?qū)?List 集合元素進行排序swap(List帆锋，int吵取， int)：將指定 list 集合中的 i 處元素和 j 處元素進行交換
查找、替換：
Object max(Collection)：根據(jù)元素的自然順序锯厢，返回給定集合中的最大元素Object max(Collection皮官，Comparator)：根據(jù) Comparator 指定的順序，返回給定集合中的最大元素Object min(Collection)：根據(jù)元素的自然順序实辑，返回給定集合中的最小元素Object min(Collection捺氢，Comparator)：根據(jù) Comparator 指定的順序，返回給定集合中的最小元素int frequency(Collection剪撬，Object)：返回指定集合中指定元素的出現(xiàn)次數(shù)void copy(List dest,List src)：將src中的內(nèi)容復(fù)制到dest中boolean replaceAll(List list摄乒，Object oldVal，Object newVal)：使用新值替換List 對象的所有舊值-
注意
void copy(List dest,List src)方法的使用,給個案例如下：public class Collections { @Test public void test(){ List list = new ArrayList(); list.add(123); list.add(43); list.add(765); list.add(-97); list.add(0); //錯誤寫法;報異常java.lang.IndexOutOfBoundsException: Source does not fit in dest List dest = new ArrayList(); java.util.Collections.copy(dest,list); System.out.println(dest); System.out.println(dest.size()); } } -
為啥會報異常錯誤，我們可以看下
void copy(List dest,List src)源碼：public static <T> void copy(List<? super T> dest, List<? extends T> src) { int srcSize = src.size(); if (srcSize > dest.size())//注意這里馍佑，dest.size() throw new IndexOutOfBoundsException("Source does not fit in dest"); if (srcSize < COPY_THRESHOLD || (src instanceof RandomAccess && dest instanceof RandomAccess)) { for (int i=0; i<srcSize; i++) dest.set(i, src.get(i)); } else { ListIterator<? super T> di=dest.listIterator(); ListIterator<? extends T> si=src.listIterator(); for (int i=0; i<srcSize; i++) { di.next(); di.set(si.next()); } } } -
解決方法：
public class Collections { @Test public void test(){ List list = new ArrayList(); list.add(123); list.add(43); list.add(765); list.add(-97); list.add(0); //解決方法 List<Object> dest = Arrays.asList(new Object[list.size()]); java.util.Collections.copy(dest,list); //[123, 43, 765, -97, 0] System.out.println(dest); //5 System.out.println(dest.size()); } }
同步控制：
- Collections 類中提供了多個 synchronizedXxx() 方法斋否，該方法可使將指定集合包裝成線程同步的集合，從而可以解決多線程并發(fā)訪問集合時的線程安全問題
創(chuàng)建只讀集合拭荤，不可更改：
- Collections類中提供了多個unmodifiableXxx()方法來創(chuàng)建一個只讀集合如叼，這樣改變集合的任何操作都會拋出 Java. lang. UnsupportedOperationException 異常
3、Collection和Collections的區(qū)別
Collection：存儲單列數(shù)據(jù)的一個接口穷劈，里面有繼承它的Set接口和List接口
Collections：是一個操作 Set笼恰、List 和 Map 等集合的工具類
<u>如果，此文章對你有所幫助歇终，請幫忙點個贊唄社证！ 謝謝！Ｆ滥追葡！</u>
