[Java复习02] 集合框架 Collection
Q1 Collection
java的集合以及集合之間的繼承關(guān)系?
數(shù)組和鏈表的區(qū)別?
固定長度，連續(xù)內(nèi)存，不能擴展，隨機訪問快，插入刪除慢。鏈表相反
?
List, Set, Map的區(qū)別?
List，Set繼承Collection接口
List可以放重復(fù)數(shù)據(jù)，Set不能，Map是k-v對
?
List和Map的實現(xiàn)方式以及存儲方式?
ArrayList: 底層動態(tài)數(shù)組。隨機訪問快，增刪慢，線程不安全。
擴容導(dǎo)致數(shù)組復(fù)制，批量刪除會導(dǎo)致找兩個集合交集，效率低。
LinkedList: 底層鏈表(雙向列表)。增刪快，查找慢，線程不安全。
遍歷: 1.普通for循環(huán),元素越多后面越慢 2.迭代器：每次訪問，用游標(biāo)記錄當(dāng)前位置
根據(jù)下標(biāo)獲取node，會根據(jù)index處于前半段還是后半段進行折半，提升效率。
HashMap: 散列表, 數(shù)組+鏈表+紅黑樹(JDK1.8) 默認(rèn)16， 擴容2的冪
?
Q2 List
ArrayList實現(xiàn)原理？
動態(tài)數(shù)組，默認(rèn)10，擴容grow(minCapacity)，增加到1.5倍
ArrayList和LinkedList的區(qū)別，以及應(yīng)用場景?
1.動態(tài)數(shù)組和雙向隊列鏈表。
2.ArrayList用for循環(huán)遍歷優(yōu)于迭代器，LinkedList則相反。
3.ArrayList在數(shù)組任意位置插入，或?qū)е略撐恢煤竺嬖刂匦屡帕?#xff0c;效率相對低。
LinkedList增刪只需移動指針，時間效率高。不需擴容，空間效率也高。但隨機訪問元素時間效率低。
?
鏈表翻轉(zhuǎn)? 手寫鏈表逆序代碼?
方法1：遞歸: 從最后一個Node開始，在彈棧的過程中將指針順序置換。
1 public class Node { 2 3 private String data; 4 5 private Node next; 6 7 // Getter() & Setter() 8 9 } 10 11 public Node reverse(Node head) { 12 13 if (head == null || head.getNext() == null) { 14 15 return head; 16 17 } 18 19 Node temp = head.getNext(); 20 21 Node newHead = reverse(head.getNext()); 22 23 temp.setNext(head); 24 25 head.setNext(null); 26 27 return newHead; 28 29 } View Code解析：遞歸本質(zhì)是系統(tǒng)壓棧，壓棧時保留現(xiàn)場。
例子：A->B->C->D
程序先壓棧，到達(dá)倒數(shù)第2個節(jié)點時(C)，C的next為D, reverse(D)返回D。
接著就是彈棧過程，執(zhí)行temp.setNext(head); 此時temp是D, head是C，temp的next設(shè)置為C, 就是D->C, 不過head是C，還有next是D，這句會形成環(huán)(D->C->D)。需要下一句head.setNext(null);把C的next指針斷開，形成D->C(C.next->null)的反轉(zhuǎn)最后2個節(jié)點。返回新鏈表的頭結(jié)點newHead，也就是D。后面進行相同操作，最終完成整個鏈表的反轉(zhuǎn)。
方法2：遍歷: 在鏈表遍歷的過程中將指針順序置換。
1 public Node traverseReverse(Node head) { 2 3 Node pre = null; 4 5 Node next; 6 7 while(head != null) { 8 9 next = head.getNext(); 10 11 head.setNext(pre); 12 13 pre = head; 14 15 head = next; 16 17 } 18 19 return pre; 20 21 } View Code解析：在head點遍歷, 第一次時為A節(jié)點，next為B節(jié)點，head(A)節(jié)點的next設(shè)置為前一個節(jié)點pre(當(dāng)前為null)，把head節(jié)點賦給pre，pre為A節(jié)點，再把next節(jié)點(B)賦給head。
進行下一次循環(huán)，head為B節(jié)點，pre為A節(jié)點，head(B)節(jié)點的next設(shè)置為前一個節(jié)點pre(A)，形成B->A，再復(fù)制給pre。Head移動到下一個節(jié)點。依次繼續(xù)循環(huán)。。。
?
判斷一個單鏈表是否有環(huán)？如果有環(huán)找出環(huán)的起點，以及環(huán)的長度？
方法一，窮舉遍歷。用新節(jié)點ID和此節(jié)點之前所有節(jié)點ID依次比較，如發(fā)現(xiàn)存在相同ID，則有環(huán)。時間復(fù)雜度O(N*N), 沒有額外空間，空間復(fù)雜度O(1)
方法二，哈希表HashSet緩存。如發(fā)現(xiàn)存在相同節(jié)點，則說明有環(huán)。時間復(fù)雜度O(N)，空間復(fù)雜度O(N)。
方法三，快慢指針。快指針移動2個節(jié)點，慢指針移動1個節(jié)點。然后比較2個指針節(jié)點是否相同。相同有環(huán)。
?
Q3 Map
HashMap數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)原理？put, get, resize等工作原理？
HashMap存儲key-value鍵值對。Key和value都允許為null。Key重復(fù)會被覆蓋，value可以重復(fù)。無序。非線程安全。
JDK1.7 數(shù)組+鏈表，JDK1.8 數(shù)組+鏈表+紅黑樹。
默認(rèn)集合容量16，默認(rèn)填充因子0.75，鏈表長度2的冪，鏈表長度>8，集合容量>64，鏈表轉(zhuǎn)紅黑樹，當(dāng)紅黑樹節(jié)點個數(shù)小于6，又會轉(zhuǎn)化為鏈表。新增紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)量較大且哈希碰撞較多時，提高索引效率。
HashMap實現(xiàn)原理：
底層table，是一個Node<K,V>的數(shù)組，當(dāng)添加一個元素時，先計算key的hash值，以此確定插入table的位置。如果同一個hash的元素已經(jīng)放入在table的同一位置，則添加到該元素的后面，形成鏈表。當(dāng)鏈表過長時，轉(zhuǎn)化為紅黑樹，提高查詢效率。
計算數(shù)組table索引的方法：(算hash是1,2步，第3步算table索引)
1. 取 hashCode 值： h = key.hashCode()
2. 高位參與運算：h ^ (h>>>16)
? ? ?好處：右位移16位，正好是32bit的一半，高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。
3. 取模運算：(table.length - 1) & hash
? ? 為什么用&，不用%? 因為lenth =?2n 時，X % length = X & (length - 1),?& 的效率比 % 高很多。
Put()方法工作原理：
① 判斷鍵值對數(shù)組 table 是否為空或為null，否則執(zhí)行resize()進行擴容；
② 根據(jù)鍵值key計算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點添加，轉(zhuǎn)向⑥，如果table[i]不為空，轉(zhuǎn)向③；
③ 判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals；
④ 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉(zhuǎn)向⑤；
⑤ 遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹(treeifyBin)，在紅黑樹中執(zhí)行插入操作，否則進行鏈表的插入操作；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
⑥ 插入成功后，判斷實際存在的鍵值對數(shù)量size是否超過了最大容量threshold，如果超過，進行擴容resize()。
⑦ 如果新插入的key不存在，則返回null，如果新插入的key存在，則返回原key對應(yīng)的value值（注意新插入的value會覆蓋原value值）
Resize擴容的工作原理：
1.計算新桶數(shù)組的容量 newCap
2.新閥值 newThr
3. 將原集合的元素重新映射到新集合中
3.1 既不是鏈表又不是紅黑樹，直接插入
3.2 紅黑樹，調(diào)用split方法重新分配
3.3.鏈表，不用像JDK1.7重新計算hash，只看原h(huán)ash值新增的bit是1還是0，是0則索引不變，是1則索引變?yōu)椤痹饕?#43;oldCap”
Get工作原理：
1. 通過key的hash計算table索引位置:hash & (length - 1)。
2. 檢查數(shù)組該位置節(jié)點是否剛好是要找的元素，如果是則返回，如果不是則第3步。
3. 判斷該元素時否TreeNode, 如果是則用紅黑樹TreeNode的方法find查找元素。如果不是則第4步。
4.遍歷鏈表，找到相等(==或equals)的key。
HashMap線程不安全實際會如何體現(xiàn)？
1. 多線程同時Put元素，假設(shè)key發(fā)生碰撞(hash相同)，這個兩個key會添加到數(shù)組同一個位置，其中一個線程的數(shù)據(jù)被覆蓋。
2. 多線程同時檢查到需要擴容，都在重新計算元素位置及復(fù)制數(shù)據(jù)，最終只有一個線程擴容后的數(shù)組會賦值給table，其他線程會丟失。
?
HashMap如何變成線程安全？
1. Collections.synchronizeMap();
2. ConcurrentHashMap(java.util.concurrent). JDK1.5+
?
為什么String, Integer這樣的wrapper類適合作為鍵？
String是不可變的，所以他創(chuàng)建的時候hashcode就被緩存了，不需要重新計算。還有字符串的處理速度要快過其他的鍵對象。
Integer的hashcode返回本身的值，也是不變的。
?
重新調(diào)整HashMap的大小存在什么問題？
JDK1.7多線程會產(chǎn)生競爭條件(race condition)。
兩個線程同時嘗試調(diào)整大小。調(diào)整過程，存儲鏈表中元素次序會反過來，放在頭部不是尾部，是為了避免尾部遍歷(tail traversing)。如果競爭條件發(fā)生，就產(chǎn)生死循環(huán)。
HashMap中如何解決碰撞問題？如何減少碰撞？
在調(diào)用Put和get方法時，首先通過key的hashcode方法計算哈希桶的位置在存儲對象。當(dāng)獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對。
HashMap使用鏈表來解決碰撞問題，當(dāng)碰撞發(fā)生了，對象將會存儲在鏈表的下一個節(jié)點。
減少碰撞：1. 使用不可變,聲明為final的對象，比如String 作為Key。
2.采用合適的equals()和hashCode()方法，將會減少碰撞發(fā)生，提高效率。String已經(jīng)重寫了equals和hashcode方法，很適合作為HashMap的Key。
?
LinkedHashMap和TreeMap是如何保證它的順序的？
LinkedHashMap繼承HashMap.Node的屬性，額外增加了before, after用于指向前一個Entry和后一個Entry，在哈希表繼承上構(gòu)成雙向鏈表。可以按照插入的順序排序的Map。
TreeMap是按照Key的自然順序或者Comparator的順序進行排序。
LinkedHashMap是雙向鏈表，TreeMap是紅黑樹。
它們兩個哪個的有序?qū)崿F(xiàn)比較好？
如果要按自然順序或自定義順序遍歷鍵，那么TreeMap實現(xiàn)更好。如果需要輸出的順序和輸入的相同,那么用LinkedHashMap實現(xiàn)更好。
?
附上Collection思維導(dǎo)圖
Collection思維導(dǎo)圖Github地址：
https://github.com/channingy/JavaSummary/
參考資料：
https://www.cnblogs.com/ysocean/p/8657850.html
https://www.cnblogs.com/ysocean/p/8711071.html
https://www.cnblogs.com/litexy/p/9744241.html
轉(zhuǎn)載于:https://www.cnblogs.com/fyql/p/11027148.html
總結(jié)
以上是生活随笔為你收集整理的[Java复习02] 集合框架 Collection的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
