## 集合容器概述 ### 什么是集合 * 集合就是一個放數據的容器，準確的說是放數據對象引用的容器 * 集合類存放的都是對象的引用，而不是對象的本身 * 集合類型主要有3種：set(集）、list(列表）和map(映射)。 ### 集合的特點 * 集合的特點主要有如下兩點： * 集合用于存儲對象的容器，對象是用來封裝數據，對象多了也需要存儲集中式管理。 * 和數組對比對象的大小不確定。因為集合是可變長度的。數組需要提前定義大小 ### 集合和數組的區別 * 數組是固定長度的；集合可變長度的。 * 數組可以存儲基本數據類型，也可以存儲引用數據類型；集合只能存儲引用數據類型。 * 數組存儲的元素必須是同一個數據類型；集合存儲的對象可以是不同數據類型。 ### 使用集合框架的好處 1. 容量自增長； 2. 提供了高性能的數據結構和算法，使編碼更輕松，提高了程序速度和質量； 3. 可以方便地擴展或改寫集合，提高代碼復用性和可操作性。 4. 通過使用JDK自帶的集合類，可以降低代碼維護和學習新API成本。 ### 常用的集合類有哪些？ * Map接口和Collection接口是所有集合框架的父接口： 1. Collection接口的子接口包括：Set接口和List接口 2. Map接口的實現類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等 3. Set接口的實現類主要有：HashSet、TreeSet、LinkedHashSet等 4. List接口的實現類主要有：ArrayList、LinkedList、Stack以及Vector等 ### List，Set，Map三者的區別？  * Java 容器分為 Collection 和 Map 兩大類，Collection集合的子接口有Set、List、Queue三種子接口。我們比較常用的是Set、List，Map接口不是collection的子接口。 * Collection集合主要有List和Set兩大接口 * List：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。 * Set：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復元素，只允許存入一個null元素，必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。 * Map是一個鍵值對集合，存儲鍵、值和之間的映射。 Key無序，唯一；value 不要求有序，允許重復。Map沒有繼承于Collection接口，從Map集合中檢索元素時，只要給出鍵對象，就會返回對應的值對象。 * Map 的常用實現類：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap ### 集合框架底層數據結構 * Collection 1. List * Arraylist： Object數組 * Vector： Object數組 * LinkedList： 雙向循環鏈表 2. Set * HashSet（無序，唯一）：基于 HashMap 實現的，底層采用 HashMap 來保存元素 * LinkedHashSet： LinkedHashSet 繼承與 HashSet，并且其內部是通過 LinkedHashMap 來實現的。有點類似于我們之前說的LinkedHashMap 其內部是基于 Hashmap 實現一樣，不過還是有一點點區別的。 * TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。) * Map * HashMap： JDK1.8之前HashMap由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間 * LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈式散列結構即由數組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結構的基礎上，增加了一條雙向鏈表，使得上面的結構可以保持鍵值對的插入順序。同時通過對鏈表進行相應的操作，實現了訪問順序相關邏輯。 * HashTable： 數組+鏈表組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的 * TreeMap： 紅黑樹（自平衡的排序二叉樹） ### 哪些集合類是線程安全的？ * Vector：就比Arraylist多了個 synchronized （線程安全），因為效率較低，現在已經不太建議使用。 * hashTable：就比hashMap多了個synchronized (線程安全)，不建議使用。 * ConcurrentHashMap：是Java5中支持高并發、高吞吐量的線程安全HashMap實現。它由Segment數組結構和HashEntry數組結構組成。Segment數組在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵-值對數據。一個ConcurrentHashMap里包含一個Segment數組，Segment的結構和HashMap類似，是一種數組和鏈表結構；一個Segment里包含一個HashEntry數組，每個HashEntry是一個鏈表結構的元素；每個Segment守護著一個HashEntry數組里的元素，當對HashEntry數組的數據進行修改時，必須首先獲得它對應的Segment鎖。（推薦使用） * ... ### Java集合的快速失敗機制 “fail-fast”？ * 是java集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變的操作時，有可能會產生 fail-fast 機制。 * 例如：假設存在兩個線程（線程1、線程2），線程1通過Iterator在遍歷集合A中的元素，在某個時候線程2修改了集合A的結構（是結構上面的修改，而不是簡單的修改集合元素的內容），那么這個時候程序就會拋出 ConcurrentModificationException 異常，從而產生fail-fast機制。 * 原因：迭代器在遍歷時直接訪問集合中的內容，并且在遍歷過程中使用一個 modCount 變量。集合在被遍歷期間如果內容發生變化，就會改變modCount的值。每當迭代器使用hashNext()/next()遍歷下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就返回遍歷；否則拋出異常，終止遍歷。 * 解決辦法： 1. 在遍歷過程中，所有涉及到改變modCount值得地方全部加上synchronized。 2. 使用CopyOnWriteArrayList來替換ArrayList ### 怎么確保一個集合不能被修改？ * 可以使用 Collections. unmodifiableCollection(Collection c) 方法來創建一個只讀集合，這樣改變集合的任何操作都會拋出 Java. lang. UnsupportedOperationException 異常。 * 示例代碼如下： ~~~ List<String> list = new ArrayList<>(); list. add("x"); Collection<String> clist = Collections. unmodifiableCollection(list); clist. add("y"); // 運行時此行報錯 System. out. println(list. size()); 復制代碼 ~~~ ## Collection接口 ### List接口 #### 迭代器 Iterator 是什么？ * Iterator 接口提供遍歷任何 Collection 的接口。我們可以從一個 Collection 中使用迭代器方法來獲取迭代器實例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允許調用者在迭代過程中移除元素。 * 因為所有Collection接繼承了Iterator迭代器  #### Iterator 怎么使用？有什么特點？ * Iterator 使用代碼如下： ~~~ List<String> list = new ArrayList<>(); Iterator<String> it = list. iterator(); while(it. hasNext()){ String obj = it. next(); System. out. println(obj); } 復制代碼 ~~~ * Iterator 的特點是只能單向遍歷，但是更加安全，因為它可以確保，在當前遍歷的集合元素被更改的時候，就會拋出 ConcurrentModificationException 異常。 #### 如何邊遍歷邊移除 Collection 中的元素？ * 邊遍歷邊修改 Collection 的唯一正確方式是使用 Iterator.remove() 方法，如下： ~~~ Iterator<Integer> it = list.iterator(); while(it.hasNext()){ *// do something* it.remove(); } 復制代碼 ~~~ 一種最常見的**錯誤**代碼如下： ~~~ for(Integer i : list){ list.remove(i) } 復制代碼 ~~~ * 運行以上錯誤代碼會報 **ConcurrentModificationException 異常**。這是因為當使用 foreach(for(Integer i : list)) 語句時，會自動生成一個iterator 來遍歷該 list，但同時該 list 正在被 Iterator.remove() 修改。Java 一般不允許一個線程在遍歷 Collection 時另一個線程修改它。 #### Iterator 和 ListIterator 有什么區別？ * Iterator 可以遍歷 Set 和 List 集合，而 ListIterator 只能遍歷 List。 * Iterator 只能單向遍歷，而 ListIterator 可以雙向遍歷（向前/后遍歷）。 * ListIterator 實現 Iterator 接口，然后添加了一些額外的功能，比如添加一個元素、替換一個元素、獲取前面或后面元素的索引位置。 #### 遍歷一個 List 有哪些不同的方式？每種方法的實現原理是什么？Java 中 List 遍歷的最佳實踐是什么？ * 遍歷方式有以下幾種： 1. for 循環遍歷，基于計數器。在集合外部維護一個計數器，然后依次讀取每一個位置的元素，當讀取到最后一個元素后停止。 2. 迭代器遍歷，Iterator。Iterator 是面向對象的一個設計模式，目的是屏蔽不同數據集合的特點，統一遍歷集合的接口。Java 在 Collections 中支持了 Iterator 模式。 3. foreach 循環遍歷。foreach 內部也是采用了 Iterator 的方式實現，使用時不需要顯式聲明 Iterator 或計數器。優點是代碼簡潔，不易出錯；缺點是只能做簡單的遍歷，不能在遍歷過程中操作數據集合，例如刪除、替換。 * 最佳實踐：Java Collections 框架中提供了一個 RandomAccess 接口，用來標記 List 實現是否支持 Random Access。 * 如果一個數據集合實現了該接口，就意味著它支持 Random Access，按位置讀取元素的平均時間復雜度為 O(1)，如ArrayList。 * 如果沒有實現該接口，表示不支持 Random Access，如LinkedList。 * 推薦的做法就是，支持 Random Access 的列表可用 for 循環遍歷，否則建議用 Iterator 或 foreach 遍歷。 #### 說一下 ArrayList 的優缺點 * ArrayList的優點如下： * ArrayList 底層以數組實現，是一種隨機訪問模式。ArrayList 實現了 RandomAccess 接口，因此查找的時候非常快。 * ArrayList 在順序添加一個元素的時候非常方便。 * ArrayList 的缺點如下： * 刪除元素的時候，需要做一次元素復制操作。如果要復制的元素很多，那么就會比較耗費性能。 * 插入元素的時候，也需要做一次元素復制操作，缺點同上。 * ArrayList 比較適合順序添加、隨機訪問的場景。 #### 如何實現數組和 List 之間的轉換？ * 數組轉 List：使用 Arrays. asList(array) 進行轉換。 * List 轉數組：使用 List 自帶的 toArray() 方法。 * 代碼示例： ~~~ // list to array List<String> list = new ArrayList<String>(); list.add("123"); list.add("456"); list.toArray(); // array to list String[] array = new String[]{"123","456"}; Arrays.asList(array); 復制代碼 ~~~ #### ArrayList 和 LinkedList 的區別是什么？ * 數據結構實現：ArrayList 是動態數組的數據結構實現，而 LinkedList 是雙向鏈表的數據結構實現。 * 隨機訪問效率：ArrayList 比 LinkedList 在隨機訪問的時候效率要高，因為 LinkedList 是線性的數據存儲方式，所以需要移動指針從前往后依次查找。 * 增加和刪除效率：在非首尾的增加和刪除操作，LinkedList 要比 ArrayList 效率要高，因為 ArrayList 增刪操作要影響數組內的其他數據的下標。 * 內存空間占用：LinkedList 比 ArrayList 更占內存，因為 LinkedList 的節點除了存儲數據，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。 * 線程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全； * 綜合來說，在需要頻繁讀取集合中的元素時，更推薦使用 ArrayList，而在插入和刪除操作較多時，更推薦使用 LinkedList。 * LinkedList 的雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。 #### ArrayList 和 Vector 的區別是什么？ * 這兩個類都實現了 List 接口（List 接口繼承了 Collection 接口），他們都是有序集合 * 線程安全：Vector 使用了 Synchronized 來實現線程同步，是線程安全的，而 ArrayList 是非線程安全的。 * 性能：ArrayList 在性能方面要優于 Vector。 * 擴容：ArrayList 和 Vector 都會根據實際的需要動態的調整容量，只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%。 * Vector類的所有方法都是同步的。可以由兩個線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間。 * Arraylist不是同步的，所以在不需要保證線程安全時時建議使用Arraylist。 #### 插入數據時，ArrayList、LinkedList、Vector誰速度較快？闡述 ArrayList、Vector、LinkedList 的存儲性能和特性？ * ArrayList和Vector 底層的實現都是使用數組方式存儲數據。數組元素數大于實際存儲的數據以便增加和插入元素，它們都允許直接按序號索引元素，但是插入元素要涉及數組元素移動等內存操作，所以索引數據快而插入數據慢。 * Vector 中的方法由于加了 synchronized 修飾，因此 **Vector** **是線程安全容器，但性能上較ArrayList差**。 * LinkedList 使用雙向鏈表實現存儲，按序號索引數據需要進行前向或后向遍歷，但插入數據時只需要記錄當前項的前后項即可，所以 **LinkedList** **插入速度較快**。 #### 多線程場景下如何使用 ArrayList？ * ArrayList 不是線程安全的，如果遇到多線程場景，可以通過 Collections 的 synchronizedList 方法將其轉換成線程安全的容器后再使用。例如像下面這樣： ~~~ List<String> synchronizedList = Collections.synchronizedList(list); synchronizedList.add("aaa"); synchronizedList.add("bbb"); for (int i = 0; i < synchronizedList.size(); i++) { System.out.println(synchronizedList.get(i)); } 復制代碼 ~~~ #### 為什么 ArrayList 的 elementData 加上 transient 修飾？ * ArrayList 中的數組定義如下： private transient Object\[\] elementData; * 再看一下 ArrayList 的定義： ~~~ public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable 復制代碼 ~~~ * 可以看到 ArrayList 實現了 Serializable 接口，這意味著 ArrayList 支持序列化。transient 的作用是說不希望 elementData 數組被序列化，重寫了 writeObject 實現： ~~~ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{ *// Write out element count, and any hidden stuff* int expectedModCount = modCount; s.defaultWriteObject(); *// Write out array length* s.writeInt(elementData.length); *// Write out all elements in the proper order.* for (int i=0; i<size; i++) s.writeObject(elementData[i]); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } 復制代碼 ~~~ * 每次序列化時，先調用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍歷 elementData，只序列化已存入的元素，這樣既加快了序列化的速度，又減小了序列化之后的文件大小。 #### List 和 Set 的區別 * List , Set 都是繼承自Collection 接口 * List 特點：一個有序（元素存入集合的順序和取出的順序一致）容器，元素可以重復，可以插入多個null元素，元素都有索引。常用的實現類有 ArrayList、LinkedList 和 Vector。 * Set 特點：一個無序（存入和取出順序有可能不一致）容器，不可以存儲重復元素，只允許存入一個null元素，必須保證元素唯一性。Set 接口常用實現類是 HashSet、LinkedHashSet 以及 TreeSet。 * 另外 List 支持for循環，也就是通過下標來遍歷，也可以用迭代器，但是set只能用迭代，因為他無序，無法用下標來取得想要的值。 * Set和List對比 * Set：檢索元素效率低下，刪除和插入效率高，插入和刪除不會引起元素位置改變。 * List：和數組類似，List可以動態增長，查找元素效率高，插入刪除元素效率低，因為會引起其他元素位置改變 ### Set接口 #### 說一下 HashSet 的實現原理？ * HashSet 是基于 HashMap 實現的，HashSet的值存放于HashMap的key上，HashMap的value統一為present，因此 HashSet 的實現比較簡單，相關 HashSet 的操作，基本上都是直接調用底層 HashMap 的相關方法來完成，HashSet 不允許重復的值。 #### HashSet如何檢查重復？HashSet是如何保證數據不可重復的？ * 向HashSet 中add ()元素時，判斷元素是否存在的依據，不僅要比較hash值，同時還要結合equles 方法比較。 * HashSet 中的add ()方法會使用HashMap 的put()方法。 * HashMap 的 key 是唯一的，由源碼可以看出 HashSet 添加進去的值就是作為HashMap 的key，并且在HashMap中如果K/V相同時，會用新的V覆蓋掉舊的V，然后返回舊的V。所以不會重復（ HashMap 比較key是否相等是先比較hashcode 再比較equals ）。 * 以下是HashSet 部分源碼： ~~~ private static final Object PRESENT = new Object(); private transient HashMap<E,Object> map; public HashSet() { map = new HashMap<>(); } public boolean add(E e) { // 調用HashMap的put方法,PRESENT是一個至始至終都相同的虛值 return map.put(e, PRESENT)==null; } 復制代碼 ~~~ **hashCode（）與equals（）的相關規定**： 1. 如果兩個對象相等，則hashcode一定也是相同的 * hashCode是jdk根據對象的地址或者字符串或者數字算出來的int類型的數值 2. 兩個對象相等,對兩個equals方法返回true 3. 兩個對象有相同的hashcode值，它們也不一定是相等的 4. 綜上，equals方法被覆蓋過，則hashCode方法也必須被覆蓋 5. hashCode()的默認行為是對堆上的對象產生獨特值。如果沒有重寫hashCode()，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數據）。 **\==與equals的區別** 1. \==是判斷兩個變量或實例是不是指向同一個內存空間 equals是判斷兩個變量或實例所指向的內存空間的值是不是相同 2. \==是指對內存地址進行比較 equals()是對字符串的內容進行比較 #### HashSet與HashMap的區別 > | HashMap | HashSet | > | --- | --- | > | 實現了Map接口 | 實現Set接口 | > | 存儲鍵值對 | 僅存儲對象 | > | 調用put（）向map中添加元素 | 調用add（）方法向Set中添加元素 | > | HashMap使用鍵（Key）計算Hashcode | HashSet使用成員對象來計算hashcode值，對于兩個對象來說hashcode可能相同，所以equals()方法用來判斷對象的相等性，如果兩個對象不同的話，那么返回false | > | HashMap相對于HashSet較快，因為它是使用唯一的鍵獲取對象 | HashSet較HashMap來說比較慢 | ## Map接口 ### 什么是Hash算法 * 哈希算法是指把任意長度的二進制映射為固定長度的較小的二進制值，這個較小的二進制值叫做哈希值。 ### 什么是鏈表 * 鏈表是可以將物理地址上不連續的數據連接起來，通過指針來對物理地址進行操作，實現增刪改查等功能。 * 鏈表大致分為單鏈表和雙向鏈表 1. 單鏈表:每個節點包含兩部分,一部分存放數據變量的data,另一部分是指向下一節點的next指針  2. 雙向鏈表:除了包含單鏈表的部分,還增加的pre前一個節點的指針  * 鏈表的優點 * 插入刪除速度快（因為有next指針指向其下一個節點，通過改變指針的指向可以方便的增加刪除元素） * 內存利用率高，不會浪費內存（可以使用內存中細小的不連續空間（大于node節點的大小），并且在需要空間的時候才創建空間） * 大小沒有固定，拓展很靈活。 * 鏈表的缺點 * 不能隨機查找，必須從第一個開始遍歷，查找效率低 ### 說一下HashMap的實現原理？ * HashMap概述： HashMap是基于哈希表的Map接口的非同步實現。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。 * HashMap的數據結構： 在Java編程語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。 * HashMap 基于 Hash 算法實現的 1. 當我們往HashMap中put元素時，利用key的hashCode重新hash計算出當前對象的元素在數組中的下標 2. 存儲時，如果出現hash值相同的key，此時有兩種情況。 ? (1)如果key相同，則覆蓋原始值； ? (2)如果key不同（出現沖突），則將當前的key-value放入鏈表中 3. 獲取時，直接找到hash值對應的下標，在進一步判斷key是否相同，從而找到對應值。 4. 理解了以上過程就不難明白HashMap是如何解決hash沖突的問題，核心就是使用了數組的存儲方式，然后將沖突的key的對象放入鏈表中，一旦發現沖突就在鏈表中做進一步的對比。 * 需要注意Jdk 1.8中對HashMap的實現做了優化，當鏈表中的節點數據超過八個之后，該鏈表會轉為紅黑樹來提高查詢效率，從原來的O(n)到O(logn) ### HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底層實現 * 在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。**數組的特點是：尋址容易，插入和刪除困難；鏈表的特點是：尋址困難，但插入和刪除容易；**所以我們將數組和鏈表結合在一起，發揮兩者各自的優勢，使用一種叫做**拉鏈法**的方式可以解決哈希沖突。 #### HashMap JDK1.8之前 * JDK1.8之前采用的是拉鏈法。**拉鏈法**：將鏈表和數組相結合。也就是說創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。  #### HashMap JDK1.8之后 * 相比于之前的版本，jdk1.8在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。  #### JDK1.7 VS JDK1.8 比較 * JDK1.8主要解決或優化了一下問題： 1. resize 擴容優化 2. 引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹算法請參考 3. 解決了多線程死循環問題，但仍是非線程安全的，多線程時可能會造成數據丟失問題。 > | 不同 | JDK 1.7 | JDK 1.8 | > | --- | --- | --- | > | 存儲結構 | 數組 + 鏈表 | 數組 + 鏈表 + 紅黑樹 | > | 初始化方式 | 單獨函數：`inflateTable()` | 直接集成到了擴容函數`resize()`中 | > | hash值計算方式 | 擾動處理 = 9次擾動 = 4次位運算 + 5次異或運算 | 擾動處理 = 2次擾動 = 1次位運算 + 1次異或運算 | > | 存放數據的規則 | 無沖突時，存放數組；沖突時，存放鏈表 | 無沖突時，存放數組；沖突 & 鏈表長度 8：樹化并存放紅黑樹 | > | 插入數據方式 | 頭插法（先講原位置的數據移到后1位，再插入數據到該位置） | 尾插法（直接插入到鏈表尾部/紅黑樹） | > | 擴容后存儲位置的計算方式 | 全部按照原來方法進行計算（即hashCode ->> 擾動函數 ->> (h&length-1)） | 按照擴容后的規律計算（即擴容后的位置=原位置 or 原位置 + 舊容量） | ### 什么是紅黑樹 #### 說道紅黑樹先講什么是二叉樹 * 二叉樹簡單來說就是 每一個節上可以關聯倆個子節點 * ~~~ 大概就是這樣子： a / \ b c / \ / \ d e f g / \ / \ / \ / \ h i j k l m n o 復制代碼 ~~~ #### 紅黑樹 * 紅黑樹是一種特殊的二叉查找樹。紅黑樹的每個結點上都有存儲位表示結點的顏色，可以是紅(Red)或黑(Black)。  * 紅黑樹的每個結點是黑色或者紅色。當是不管怎么樣他的根結點是黑色。每個葉子結點（葉子結點代表終結、結尾的節點）也是黑色 \[注意：這里葉子結點，是指為空(NIL或NULL)的葉子結點！\]。 * 如果一個結點是紅色的，則它的子結點必須是黑色的。 * 每個結點到葉子結點NIL所經過的黑色結點的個數一樣的。\[確保沒有一條路徑會比其他路徑長出倆倍，所以紅黑樹是相對接近平衡的二叉樹的！\] * 紅黑樹的基本操作是**添加、刪除**。在對紅黑樹進行添加或刪除之后，都會用到旋轉方法。為什么呢？道理很簡單，添加或刪除紅黑樹中的結點之后，紅黑樹的結構就發生了變化，可能不滿足上面三條性質，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過旋轉和變色，可以使這顆樹重新成為紅黑樹。簡單點說，旋轉和變色的目的是讓樹保持紅黑樹的特性。 ### HashMap的put方法的具體流程？ * 當我們put的時候，首先計算 `key`的`hash`值，這里調用了 `hash`方法，`hash`方法實際是讓`key.hashCode()`與`key.hashCode()>>>16`進行異或操作，高16bit補0，一個數和0異或不變，所以 hash 函數大概的作用就是：**高16bit不變，低16bit和高16bit做了一個異或，目的是減少碰撞**。按照函數注釋，因為bucket數組大小是2的冪，計算下標`index = (table.length - 1) & hash`，如果不做 hash 處理，相當于散列生效的只有幾個低 bit 位，為了減少散列的碰撞，設計者綜合考慮了速度、作用、質量之后，使用高16bit和低16bit異或來簡單處理減少碰撞，而且JDK8中用了復雜度 O（logn）的樹結構來提升碰撞下的性能。 * putVal方法執行流程圖  ~~~ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //實現Map.put和相關方法 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 步驟①：tab為空則創建 // table未初始化或者長度為0，進行擴容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 步驟②：計算index，并對null做處理 // (n - 1) & hash 確定元素存放在哪個桶中，桶為空，新生成結點放入桶中(此時，這個結點是放在數組中) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 桶中已經存在元素 else { Node<K,V> e; K k; // 步驟③：節點key存在，直接覆蓋value // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 將第一個元素賦值給e，用e來記錄 e = p; // 步驟④：判斷該鏈為紅黑樹 // hash值不相等，即key不相等；為紅黑樹結點 // 如果當前元素類型為TreeNode，表示為紅黑樹，putTreeVal返回待存放的node, e可能為null else if (p instanceof TreeNode) // 放入樹中 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 步驟⑤：該鏈為鏈表 // 為鏈表結點 else { // 在鏈表最末插入結點 for (int binCount = 0; ; ++binCount) { // 到達鏈表的尾部 //判斷該鏈表尾部指針是不是空的 if ((e = p.next) == null) { // 在尾部插入新結點 p.next = newNode(hash, key, value, null); //判斷鏈表的長度是否達到轉化紅黑樹的臨界值，臨界值為8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //鏈表結構轉樹形結構 treeifyBin(tab, hash); // 跳出循環 break; } // 判斷鏈表中結點的key值與插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 相等，跳出循環 break; // 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表 p = e; } } //判斷當前的key已經存在的情況下，再來一個相同的hash值、key值時，返回新來的value這個值 if (e != null) { // 記錄e的value V oldValue = e.value; // onlyIfAbsent為false或者舊值為null if (!onlyIfAbsent || oldValue == null) //用新值替換舊值 e.value = value; // 訪問后回調 afterNodeAccess(e); // 返回舊值 return oldValue; } } // 結構性修改 ++modCount; // 步驟⑥：超過最大容量就擴容 // 實際大小大于閾值則擴容 if (++size > threshold) resize(); // 插入后回調 afterNodeInsertion(evict); return null; } 復制代碼 ~~~ 1. 判斷鍵值對數組table\[i\]是否為空或為null，否則執行resize()進行擴容； 2. 根據鍵值key計算hash值得到插入的數組索引i，如果table\[i\]==null，直接新建節點添加，轉向⑥，如果table\[i\]不為空，轉向③； 3. 判斷table\[i\]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉向④，這里的相同指的是hashCode以及equals； 4. 判斷table\[i\] 是否為treeNode，即table\[i\] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉向5； 5. 遍歷table\[i\]，判斷鏈表長度是否大于8，大于8的話把鏈表轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行鏈表的插入操作；遍歷過程中若發現key已經存在直接覆蓋value即可； 6. 插入成功后，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。 ### HashMap的擴容操作是怎么實現的？ 1. 在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調用resize方法進行擴容； 2. 每次擴展的時候，都是擴展2倍； 3. 擴展后Node對象的位置要么在原位置，要么移動到原偏移量兩倍的位置。 * 在putVal()中，我們看到在這個函數里面使用到了2次resize()方法，resize()方法表示的在進行第一次初始化時會對其進行擴容，或者當該數組的實際大小大于其臨界值值(第一次為12),這個時候在擴容的同時也會伴隨的桶上面的元素進行重新分發，這也是JDK1.8版本的一個優化的地方，在1.7中，擴容之后需要重新去計算其Hash值，根據Hash值對其進行分發，但在1.8版本中，則是根據在同一個桶的位置中進行判斷(e.hash & oldCap)是否為0，重新進行hash分配后，該元素的位置要么停留在原始位置，要么移動到原始位置+增加的數組大小這個位置上 ~~~ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//oldTab指向hash桶數組 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) {//如果oldCap不為空的話，就是hash桶數組不為空 if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就賦值為整數最大的閥值 threshold = Integer.MAX_VALUE; return oldTab;//返回 }//如果當前hash桶數組的長度在擴容后仍然小于最大容量 并且oldCap大于默認值16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold 雙倍擴容閥值threshold } // 舊的容量為0，但threshold大于零，代表有參構造有cap傳入，threshold已經被初始化成最小2的n次冪 // 直接將該值賦給新的容量 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 無參構造創建的map，給出默認容量和threshold 16, 16*0.75 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 新的threshold = 新的cap * 0.75 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // 計算出新的數組長度后賦給當前成員變量table @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶數組 table = newTab;//將新數組的值復制給舊的hash桶數組 // 如果原先的數組沒有初始化，那么resize的初始化工作到此結束，否則進入擴容元素重排邏輯，使其均勻的分散 if (oldTab != null) { // 遍歷新數組的所有桶下標 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { // 舊數組的桶下標賦給臨時變量e，并且解除舊數組中的引用，否則就數組無法被GC回收 oldTab[j] = null; // 如果e.next==null，代表桶中就一個元素，不存在鏈表或者紅黑樹 if (e.next == null) // 用同樣的hash映射算法把該元素加入新的數組 newTab[e.hash & (newCap - 1)] = e; // 如果e是TreeNode并且e.next!=null，那么處理樹中元素的重排 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // e是鏈表的頭并且e.next!=null，那么處理鏈表中元素重排 else { // preserve order // loHead,loTail 代表擴容后不用變換下標，見注1 Node<K,V> loHead = null, loTail = null; // hiHead,hiTail 代表擴容后變換下標，見注1 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 遍歷鏈表 do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) // 初始化head指向鏈表當前元素e，e不一定是鏈表的第一個元素，初始化后loHead // 代表下標保持不變的鏈表的頭元素 loHead = e; else // loTail.next指向當前e loTail.next = e; // loTail指向當前的元素e // 初始化后，loTail和loHead指向相同的內存，所以當loTail.next指向下一個元素時， // 底層數組中的元素的next引用也相應發生變化，造成lowHead.next.next..... // 跟隨loTail同步，使得lowHead可以鏈接到所有屬于該鏈表的元素。 loTail = e; } else { if (hiTail == null) // 初始化head指向鏈表當前元素e, 初始化后hiHead代表下標更改的鏈表頭元素 hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 遍歷結束, 將tail指向null，并把鏈表頭放入新數組的相應下標，形成新的映射。 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 復制代碼 ~~~ ### HashMap是怎么解決哈希沖突的？ * 答：在解決這個問題之前，我們首先需要知道**什么是哈希沖突**，而在了解哈希沖突之前我們還要知道**什么是哈希**才行； #### 什么是哈希？ * Hash，一般翻譯為“散列”，也有直接音譯為“哈希”的， Hash就是指使用哈希算法是指把任意長度的二進制映射為固定長度的較小的二進制值，這個較小的二進制值叫做哈希值。 #### 什么是哈希沖突？ * **當兩個不同的輸入值，根據同一散列函數計算出相同的散列值的現象，我們就把它叫做碰撞（哈希碰撞）**。 #### HashMap的數據結構 * 在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。 * 數組的特點是：尋址容易，插入和刪除困難； * 鏈表的特點是：尋址困難，但插入和刪除容易； * 所以我們將數組和鏈表結合在一起，發揮兩者各自的優勢，就可以使用倆種方式：鏈地址法和開放地址法可以解決哈希沖突：  * 鏈表法就是將相同hash值的對象組織成一個鏈表放在hash值對應的槽位； * 開放地址法是通過一個探測算法，當某個槽位已經被占據的情況下繼續查找下一個可以使用的槽位。 * **但相比于hashCode返回的int類型，我們HashMap初始的容量大小`DEFAULT_INITIAL_CAPACITY = 1 << 4`（即2的四次方16）要遠小于int類型的范圍，所以我們如果只是單純的用hashCode取余來獲取對應的bucket這將會大大增加哈希碰撞的概率，并且最壞情況下還會將HashMap變成一個單鏈表**，所以我們還需要對hashCode作一定的優化 #### hash()函數 * 上面提到的問題，主要是因為如果使用hashCode取余，那么相當于**參與運算的只有hashCode的低位**，高位是沒有起到任何作用的，所以我們的思路就是讓hashCode取值出的高位也參與運算，進一步降低hash碰撞的概率，使得數據分布更平均，我們把這樣的操作稱為**擾動**，在**JDK 1.8**中的hash()函數如下： ~~~ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 與自己右移16位進行異或運算（高低位異或） } 復制代碼 ~~~ * 這比在**JDK 1.7**中，更為簡潔，**相比在1.7中的4次位運算，5次異或運算（9次擾動），在1.8中，只進行了1次位運算和1次異或運算（2次擾動）**； #### 總結 * 簡單總結一下HashMap是使用了哪些方法來有效解決哈希沖突的： * 鏈表法就是將相同hash值的對象組織成一個鏈表放在hash值對應的槽位； * 開放地址法是通過一個探測算法，當某個槽位已經被占據的情況下繼續查找下一個可以使用的槽位。 ### 能否使用任何類作為 Map 的 key？ 可以使用任何類作為 Map 的 key，然而在使用之前，需要考慮以下幾點： * 如果類重寫了 equals() 方法，也應該重寫 hashCode() 方法。 * 類的所有實例需要遵循與 equals() 和 hashCode() 相關的規則。 * 如果一個類沒有使用 equals()，不應該在 hashCode() 中使用它。 * 用戶自定義 Key 類最佳實踐是使之為不可變的，這樣 hashCode() 值可以被緩存起來，擁有更好的性能。不可變的類也可以確保 hashCode() 和 equals() 在未來不會改變，這樣就會解決與可變相關的問題了。 ### 為什么HashMap中String、Integer這樣的包裝類適合作為K？ * 答：String、Integer等包裝類的特性能夠保證Hash值的不可更改性和計算準確性，能夠有效的減少Hash碰撞的幾率 * 都是final類型，即不可變性，保證key的不可更改性，不會存在獲取hash值不同的情況 * 內部已重寫了`equals()`、`hashCode()`等方法，遵守了HashMap內部的規范（不清楚可以去上面看看putValue的過程），不容易出現Hash值計算錯誤的情況； ### 如果使用Object作為HashMap的Key，應該怎么辦呢？ * 答：重寫`hashCode()`和`equals()`方法 1. **重寫`hashCode()`是因為需要計算存儲數據的存儲位置**，需要注意不要試圖從散列碼計算中排除掉一個對象的關鍵部分來提高性能，這樣雖然能更快但可能會導致更多的Hash碰撞； 2. **重寫`equals()`方法**，需要遵守自反性、對稱性、傳遞性、一致性以及對于任何非null的引用值x，x.equals(null)必須返回false的這幾個特性，**目的是為了保證key在哈希表中的唯一性**； ### HashMap為什么不直接使用hashCode()處理后的哈希值直接作為table的下標？ * 答：`hashCode()`方法返回的是int整數類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空間，而HashMap的容量范圍是在16（初始化默認值）~2 ^ 30，HashMap通常情況下是取不到最大值的，并且設備上也難以提供這么多的存儲空間，從而導致通過`hashCode()`計算出的哈希值可能不在數組大小范圍內，進而無法匹配存儲位置； * **那怎么解決呢？** 1. HashMap自己實現了自己的`hash()`方法，通過兩次擾動使得它自己的哈希值高低位自行進行異或運算，降低哈希碰撞概率也使得數據分布更平均； 2. 在保證數組長度為2的冪次方的時候，使用`hash()`運算之后的值與運算（&）（數組長度 - 1）來獲取數組下標的方式進行存儲，這樣一來是比取余操作更加有效率，二來也是因為只有當數組長度為2的冪次方時，h&(length-1)才等價于h%length，三來解決了“哈希值與數組大小范圍不匹配”的問題； ### HashMap 的長度為什么是2的冪次方 * 為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數據分配均勻，每個鏈表/紅黑樹長度大致相同。這個實現就是把數據存到哪個鏈表/紅黑樹中的算法。 * **這個算法應該如何設計呢？** * 我們首先可能會想到采用%取余的操作來實現。但是，重點來了：“取余(%)操作中如果除數是2的冪次則等價于與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二進制位操作 &，相對于%能夠提高運算效率，這就解釋了 HashMap 的長度為什么是2的冪次方。 * **那為什么是兩次擾動呢？** * 答：這樣就是加大哈希值低位的隨機性，使得分布更均勻，從而提高對應數組存儲下標位置的隨機性&均勻性，最終減少Hash沖突，兩次就夠了，已經達到了高位低位同時參與運算的目的； ### HashMap 與 HashTable 有什么區別？ 1. **線程安全**： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內部的方法基本都經過 `synchronized` 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap ）； 2. **效率**： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；（如果你要保證線程安全的話就使用 ConcurrentHashMap ）； 3. **對Null key 和Null value的支持**： HashMap 中，null 可以作為鍵，這樣的鍵只有一個，可以有一個或多個鍵所對應的值為 null。但是在 HashTable 中 put 進的鍵值只要有一個 null，直接拋NullPointerException。 4. **初始容量大小和每次擴充容量大小的不同** ： 1. 創建時如果不指定容量初始值，Hashtable 默認的初始大小為11，之后每次擴充，容量變為原來的2n+1。HashMap 默認的初始化大小為16。之后每次擴充，容量變為原來的2倍。 2. 創建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小。也就是說 HashMap 總是使用2的冪作為哈希表的大小，后面會介紹到為什么是2的冪次方。 5. **底層數據結構**： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。Hashtable 沒有這樣的機制。 6. 推薦使用：在 Hashtable 的類注釋可以看到，Hashtable 是保留類不建議使用，推薦在單線程環境下使用 HashMap 替代，如果需要多線程使用則用 ConcurrentHashMap 替代。 ### 什么是TreeMap 簡介 * TreeMap 是一個**有序的key-value集合**，它是通過紅黑樹實現的。 * TreeMap基于**紅黑樹（Red-Black tree）實現**。該映射根據**其鍵的自然順序進行排序**，或者根據**創建映射時提供的 Comparator 進行排序**，具體取決于使用的構造方法。 * TreeMap是線程**非同步**的。 ### 如何決定使用 HashMap 還是 TreeMap？ * 對于在Map中插入、刪除和定位元素這類操作，HashMap是最好的選擇。然而，假如你需要對一個有序的key集合進行遍歷，TreeMap是更好的選擇。基于你的collection的大小，也許向HashMap中添加元素會更快，將map換為TreeMap進行有序key的遍歷。 ### HashMap 和 ConcurrentHashMap 的區別 1. ConcurrentHashMap對整個桶數組進行了分割分段(Segment)，然后在每一個分段上都用lock鎖進行保護，相對于HashTable的synchronized鎖的粒度更精細了一些，并發性能更好，而HashMap沒有鎖機制，不是線程安全的。（JDK1.8之后ConcurrentHashMap啟用了一種全新的方式實現,利用CAS算法。） 2. HashMap的鍵值對允許有null，但是ConCurrentHashMap都不允許。 ### ConcurrentHashMap 和 Hashtable 的區別？ * ConcurrentHashMap 和 Hashtable 的區別主要體現在實現線程安全的方式上不同。 * **底層數據結構**： JDK1.7的 ConcurrentHashMap 底層采用 **分段的數組+鏈表** 實現，JDK1.8 采用的數據結構跟HashMap1.8的結構一樣，數組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數據結構類似都是采用 **數組+鏈表** 的形式，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的； * **實現線程安全的方式**： 1. **在JDK1.7的時候，ConcurrentHashMap（分段鎖）** 對整個桶數組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分數據，多線程訪問容器里不同數據段的數據，就不會存在鎖競爭，提高并發訪問率。（默認分配16個Segment，比Hashtable效率提高16倍。） **到了 JDK1.8 的時候已經摒棄了Segment的概念，而是直接用 Node 數組+鏈表+紅黑樹的數據結構來實現，并發控制使用 synchronized 和 CAS 來操作。（JDK1.6以后 對 synchronized鎖做了很多優化）** 整個看起來就像是優化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數據結構，但是已經簡化了屬性，只是為了兼容舊版本； 2. ② **Hashtable(同一把鎖)** :使用 synchronized 來保證線程安全，效率非常低下。當一個線程訪問同步方法時，其他線程也訪問同步方法，可能會進入阻塞或輪詢狀態，如使用 put 添加元素，另一個線程不能使用 put 添加元素，也不能使用 get，競爭會越來越激烈效率越低。 * **兩者的對比圖**： ##### 1、HashTable:  ##### 2、 JDK1.7的ConcurrentHashMap：  ##### 3、JDK1.8的ConcurrentHashMap（TreeBin: 紅黑二叉樹節點 Node: 鏈表節點）：  * 答：ConcurrentHashMap 結合了 HashMap 和 HashTable 二者的優勢。HashMap 沒有考慮同步，HashTable 考慮了同步的問題使用了synchronized 關鍵字，所以 HashTable 在每次同步執行時都要鎖住整個結構。 ConcurrentHashMap 鎖的方式是稍微細粒度的。 ### ConcurrentHashMap 底層具體實現知道嗎？實現原理是什么？ #### JDK1.7 * 首先將數據分為一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據時，其他段的數據也能被其他線程訪問。 * 在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進行實現，結構如下： * 一個 ConcurrentHashMap 里包含一個 Segment 數組。Segment 的結構和HashMap類似，是一種數組和鏈表結構，一個 Segment 包含一個 HashEntry 數組，每個 HashEntry 是一個鏈表結構的元素，每個 Segment 守護著一個HashEntry數組里的元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment的鎖。  1. 該類包含兩個靜態內部類 HashEntry 和 Segment ；前者用來封裝映射表的鍵值對，后者用來充當鎖的角色； 2. Segment 是一種可重入的鎖 ReentrantLock，每個 Segment 守護一個HashEntry 數組里得元素，當對 HashEntry 數組的數據進行修改時，必須首先獲得對應的 Segment 鎖。 #### JDK1.8 * 在**JDK1.8中，放棄了Segment臃腫的設計，取而代之的是采用Node + CAS + Synchronized來保證并發安全進行實現**，synchronized只鎖定當前鏈表或紅黑二叉樹的首節點，這樣只要hash不沖突，就不會產生并發，效率又提升N倍。 * 結構如下：  * **附加源碼，有需要的可以看看** * 插入元素過程（建議去看看源碼）： * 如果相應位置的Node還沒有初始化，則調用CAS插入相應的數據； ~~~ else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } 復制代碼 ~~~ * 如果相應位置的Node不為空，且當前該節點不處于移動狀態，則對該節點加synchronized鎖，如果該節點的hash不小于0，則遍歷鏈表更新節點或插入新節點； ~~~ if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } 復制代碼 ~~~ 1. 如果該節點是TreeBin類型的節點，說明是紅黑樹結構，則通過putTreeVal方法往紅黑樹中插入節點；如果binCount不為0，說明put操作對數據產生了影響，如果當前鏈表的個數達到8個，則通過treeifyBin方法轉化為紅黑樹，如果oldVal不為空，說明是一次更新操作，沒有對元素個數產生影響，則直接返回舊值； 2. 如果插入的是一個新節點，則執行addCount()方法嘗試更新元素個數baseCount； ## 輔助工具類 ### Array 和 ArrayList 有何區別？ * Array 可以存儲基本數據類型和對象，ArrayList 只能存儲對象。 * Array 是指定固定大小的，而 ArrayList 大小是自動擴展的。 * Array 內置方法沒有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 `對于基本類型數據，集合使用自動裝箱來減少編碼工作量。但是，當處理固定大小的基本數據類型的時候，這種方式相對比較慢。` ### 如何實現 Array 和 List 之間的轉換？ * Array 轉 List： Arrays. asList(array) ； * List 轉 Array：List 的 toArray() 方法。 ### comparable 和 comparator的區別？ * comparable接口實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序 * comparator接口實際上是出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序 * 一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo方法或compare方法，當我們需要對某一個集合實現兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個Comparator來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的Collections.sort(). ### Collection 和 Collections 有什么區別？ * java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現。Collection接口的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承接口有List與Set。 * Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。 ### TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？ * TreeSet 要求存放的對象所屬的類必須實現 Comparable 接口，該接口提供了比較元素的 compareTo()方法，當插入元素時會回調該方法比較元素的大小。TreeMap 要求存放的鍵值對映射的鍵必須實現 Comparable 接口從而根據鍵對元素進 行排 序。 * Collections 工具類的 sort 方法有兩種重載的形式， * 第一種要求傳入的待排序容器中存放的對象比較實現 Comparable 接口以實現元素的比較； ？ * comparable接口實際上是出自java.lang包，它有一個 compareTo(Object obj)方法用來排序 * comparator接口實際上是出自 java.util 包，它有一個compare(Object obj1, Object obj2)方法用來排序 * 一般我們需要對一個集合使用自定義排序時，我們就要重寫compareTo方法或compare方法，當我們需要對某一個集合實現兩種排序方式，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話，我們可以重寫compareTo方法和使用自制的Comparator方法或者以兩個Comparator來實現歌名排序和歌星名排序，第二種代表我們只能使用兩個參數版的Collections.sort(). ### Collection 和 Collections 有什么區別？ * java.util.Collection 是一個集合接口（集合類的一個頂級接口）。它提供了對集合對象進行基本操作的通用接口方法。Collection接口在Java 類庫中有很多具體的實現。Collection接口的意義是為各種具體的集合提供了最大化的統一操作方式，其直接繼承接口有List與Set。 * Collections則是集合類的一個工具類/幫助類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。 ### TreeMap 和 TreeSet 在排序時如何比較元素？Collections 工具類中的 sort()方法如何比較元素？ * TreeSet 要求存放的對象所屬的類必須實現 Comparable 接口，該接口提供了比較元素的 compareTo()方法，當插入元素時會回調該方法比較元素的大小。TreeMap 要求存放的鍵值對映射的鍵必須實現 Comparable 接口從而根據鍵對元素進 行排 序。 * Collections 工具類的 sort 方法有兩種重載的形式， * 第一種要求傳入的待排序容器中存放的對象比較實現 Comparable 接口以實現元素的比較； * 第二種不強制性的要求容器中的元素必須可比較，但是要求傳入第二個參數，參數是Comparator 接口的子類型（需要重寫 compare 方法實現元素的比較），相當于一個臨時定義的排序規則，其實就是通過接口注入比較元素大小的算法，也是對回調模式的應用（Java 中對函數式編程的支持）。