Java集合類面試題

一. 概述

1. Java集合概覽

Java集合類面試題總結Java集合類面試題

Collection

Set

TreeSet：基于紅黑樹實作，支援有序性操作.

HashSet：基于哈希表實作，支援快速查找，但不支援有序性操作。

LinkedHashSet：具有 HashSet 的查找效率，且内部使用雙向連結清單維護元素的插入順序。

List

ArrayList：基于動态數組實作，支援随機通路。

Vector：和 ArrayList 類似，但它是線程安全的。

LinkedList：基于雙向連結清單實作，隻能順序通路，但是可以快速地在連結清單中間插入和删除元素。不僅如此，LinkedList 還可以用作棧、隊列和雙向隊列。

Queue

LinkedList：可以用它來實作雙向隊列。

PriorityQueue：基于堆結構實作，可以用它來實作優先隊列。

Map

TreeMap：基于紅黑樹實作。

HashMap：基于哈希表實作。

HashTable：和 HashMap 類似，但它是線程安全的，這意味着同一時刻多個線程可以同時寫入 HashTable 并且不會導緻資料不一緻。它是遺留類，不應該去使用它。

LinkedHashMap：使用雙向連結清單來維護元素的順序，順序為插入順序或者最近最少使用（LRU）順序。

2. List,Set,Map 三者的差別？

List：存儲的元素是有序的、可重複的。
Set(注重獨一無二的性質): 存儲的元素是無序的、不可重複的。
Map: 使用鍵值對（kye-value）存儲，Key 是無序的、不可重複的，value 是無序的、可重複的，每個鍵最多映射到一個值。

3. 數組與集合的對比

數組的一旦聲明之後，長度就不可變了；同時，聲明數組時的資料類型也決定了該數組存儲的資料的類型；而且，數組存儲的資料是有序的、可重複的，特點單一。
集合提高了資料存儲的靈活性，Java 集合不僅可以用來存儲不同類型不同數量的對象，還可以儲存具有映射關系的資料。

4. RandomAccess 接口的作用

RandomAccess接口是一個标記接口，它并未定義方法。其目的是用于訓示實作類具有随機通路特性，在周遊時使用下标通路較疊代器更快。

如在 binarySearch（) 方法中，它要判斷傳入的 list 是否 RamdomAccess 的執行個體，如果是，調用indexedBinarySearch()方法，如果不是，那麼調用iteratorBinarySearch()方法

5. 哪些集合類提供對元素的随機通路？

ArrayList、HashMap、TreeMap和HashTable類提供對元素的随機通路。

6.什麼是Iterator？

标準化各類容器的周遊過程，使得周遊容器不依賴于容器的内部結構而采用同一種邏輯。Iterator的具體實作由各容器根據其資料結構特點自行實作。

7. Iterator與ListIterator有什麼差別？

Iterator：隻能正向周遊集合，适用于擷取移除元素。ListIerator：繼承Iterator，可以雙向清單的周遊，同樣支援元素的修改。
Iterator可以周遊Set和List集合，而ListIterator隻能周遊List
ListIterator從Iterator接口繼承，然後添加了一些額外的功能，比如添加一個元素、替換一個元素、擷取前面或後面元素的索引位置。

8. fail-fast（快速失敗）

“快速失敗”也就是fail-fast，它是Java集合的一種錯誤檢測機制。當多個線程對集合進行結構上的改變的操作時，有可能會産生fail-fast機制。記住是有可能，而不是一定。例如：假設存在兩個線程（線程1、線程2），線程1通過Iterator在周遊集合A中的元素，在某個時候線程2修改了集合A的結構（是結構上面的修改，而不是簡單的修改集合元素的内容），那麼這個時候程式就會抛出 ConcurrentModificationException 異常，進而産生fail-fast機制。
産生原因：疊代器在調用next()、remove()方法時都會檢測modCount == expectedModCount，如果不相同則抛出ConcurrentModificationException 異常。expectedModCount是在擷取疊代器時擷取的，而ArrayList中無論add、remove、clear方法隻要是涉及了改變ArrayList元素的個數的方法都會導緻modCount的改變。

9. fail-fast解決方案

方案一：在周遊過程中所有涉及到改變modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，這樣就可以解決。但是不推薦，因為增删造成的同步鎖可能會阻塞周遊操作。
方案二：使用CopyOnWriteArrayList來替換ArrayList。推薦使用該方案。

10. fail-fast 與 fail-safe 有什麼差別？

Iterator 的 fail-fast 屬性與目前的集合共同起作用，是以它不會受到集合中任何改動的影響。Java.util 包中的所有集合類都被設計為 fail-fast 的，而 java.util.concurrent 中的集合類都為 fail-safe 的。當檢測到正在周遊的集合的結構被改變時，fail-fast 疊代器抛出ConcurrentModificationException，而 fail-safe 疊代器從不抛出 ConcurrentModificationException。

11.為什麼 Collection 不能繼承 Cloneable 和 Serializable？

Collection表示一個集合，包含了一組對象。如何存儲和維護這些對象是由具體實作來決定的。因為集合的具體形式多種多樣，例如list允許重複，set則不允許。而克隆（clone）和序列化（serializable）隻對于具體的實體，對象有意義，你不能說去把一個接口，抽象類克隆，序列化甚至反序列化。是以具體的collection實作類是否可以克隆，是否可以序列化應該由其自身決定，而不能由其超類強行賦予。
如果collection繼承了clone和serializable，那麼所有的集合實作都會實作這兩個接口，而如果某個實作它不需要被克隆，甚至不允許它序列化（序列化有風險），那麼就與collection沖突了。

12. Arrays.sort()的原理

對于很小的數組（長度小于47），使用插入排序。
至于大過47且小于286的，用一種快速排序（多軸快排）的方法：
1. 從數列中挑出五個元素，稱為 “基準”（pivot）；
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
至于大于286的，它會進入歸并排序（Merge Sort）

二. List

¥1. ArrayList 和 LinkedList 的差別？

底層資料結構： Arraylist 底層使用的是Object數組；LinkedList 底層使用的是雙向連結清單資料結構；
插入和删除是否受元素位置的影響： ① ArrayList 采用數組存儲，插入和删除元素的時間複雜度受元素位置的影響，近似為 O（n）。 ② LinkedList 采用連結清單存儲，插入，删除元素時間複雜度不受元素位置的影響，近似 O（1）。
是否支援快速随機通路： LinkedList 不支援高效的随機元素通路，而ArrayList 實作了RandmoAccess 接口，是以有随機通路功能。快速随機通路就是通過元素的序号快速擷取元素對象(對應于get(int index)方法)。
記憶體空間占用： ArrayList的空間浪費主要展現在在list清單的結尾會預留一定的容量空間，而LinkedList的空間花費則展現在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接後繼和直接前驅以及資料）。

2. ArrayList 的增删是否一定比 LinkedList 要慢？

如果增删都是在末尾來操作，此時 ArrayList 就不需要移動和複制數組來進行操作，速度是比 LinkedList 要快的。
如果删除操作的位置是在中間。由于 LinkedList 的消耗主要是在周遊上，ArrayList 的消耗主要是在移動和複制上（底層調用的是 arrayCopy() 方法，是 native 方法）。LinkedList 的周遊速度是要慢于 ArrayList 的複制移動速度的，如果資料量有百萬級的時，還是 ArrayList 要快。

¥3. ArrayList 的擴容機制？

如果數組為空，則建立一個容量為10的初始數組（當真正對數組進行添加元素操作時，才真正配置設定容量）
添加元素時首先調用 ensureCapacityInternal 方法，傳入 size+1 進去，檢查是否需要擴充 elementData 數組的大小；
如果需要擴容，newCapacity = 擴充數組為原來的 1.5 倍(不能自定義)
如果擴容後數組大小超過了MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，就使用所需的最少容量 minCapacity ，如果minCapacity大于Integer的最大值，則報異常；否則判斷 minCapacity 是否大于 MAX_ARRAY_SIZE，如果大于，就取 Integer.MAX_VALUE，否則擴容到MAX_ARRAY_SIZE；
使用 System.arraycopy 方法，将 original 數組的所有資料複制到 copy 數組中，這是一個本地方法。

4. System.arraycopy() 和 Arrays.copyOf()方法的差別

copyOf()内部實際調用了 System.arraycopy() 方法
arraycopy() 需要目标數組，将原數組拷貝到你自己定義的數組裡或者原數組，而且可以選擇拷貝的起點和長度以及放入新數組中的位置 copyOf() 是系統自動在内部建立一個數組，并傳回該數組。

5. Arraylist 和 Vector 的差別?

ArrayList 線程不安全；Vector 是 List 的古老實作類，線程安全。
ArrayList的擴容因子是1.5，Vector 預設擴容因子是2，可指定
ArrayList在第一次添加元素時才建立數組，Vector在初始化時就建立好容量為10的數組

6. 為什麼Vector類認為是廢棄的或者是非官方地不推薦使用？

Vector同步了每個方法，導緻效率很低。
而通常有想要同步的是整個操作序列。同步單個的操作也不安全.而且效率更慢。
如果需要保證線程安全，可以使用Collections.sychronizedList來裝飾一個集合。

7.在 Queue 中 poll()和 remove()有什麼差別？

相同點：都是傳回第一個元素，并在隊列中删除傳回的對象。

不同點：如果沒有元素 poll()會傳回 null，而 remove()會直接抛出 NoSuchElementException 異常。

三. Set

1. HashSet 的實作原理？

HashSet 的實作是依賴于 HashMap 的。HashSet 的值是作為 HashMap 的 key 存儲在 HashMap 中的，HashMap 的 value 則是 PRESENT 變量（new Object())，這個變量隻作為放入 map 時的一個占位符而存在，是以沒什麼實際用處。
由于HashMap的Key不允許重複，是以HashSet的元素不會重複

四. Map

1. HashMap 和 Hashtable 的差別

線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的,因為 HashTable 内部的方法基本都經過synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）；
效率：因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在代碼中使用它；
對 Null key 和 Null value 的支援： HashMap 可以存儲 null 的 key 和 value，但 null 作為鍵隻能有一個，null 作為值可以有多個；HashTable 不允許有 null 鍵和 null 值，否則會抛出 NullPointerException。
初始容量大小和每次擴充容量大小的不同： ① 建立時如果不指定容量初始值，Hashtable 預設的初始大小為 11，之後每次擴充，容量變為原來的 2n+1。HashMap 預設的初始化大小為 16。之後每次擴充，容量變為原來的 2 倍。② 建立時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而 HashMap 會将其擴充為 2 的幂次方大小
底層資料結構： JDK1.8 以後的 HashMap 在解決哈希沖突時有了較大的變化，當連結清單長度大于門檻值（預設為 8）（将連結清單轉換成紅黑樹前會判斷，如果目前數組的長度小于 64，那麼會選擇先進行數組擴容，而不是轉換為紅黑樹）時，将連結清單轉化為紅黑樹，以減少搜尋時間。Hashtable 沒有這樣的機制。

2.HashMap 的實作原理/底層資料結構？JDK1.7 和 JDK1.8

JDK1.7：Entry數組 + 連結清單

JDK1.8：Node 數組 + 連結清單+紅黑樹，當連結清單上的元素個數超過 8 個并且數組長度 >= 64 時自動轉化成紅黑樹，節點變成樹節點，以提高搜尋效率和插入效率到 O(logN)。Entry 和 Node 都包含 key、value、hash、next 屬性。

2.5 HashMap的紅黑樹節點存儲的是什麼

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 紅黑樹父節點
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 删除後需要取消連結
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }　　　　 //省略後續代碼

TreeNode繼承自LinkedHashMap中的内部類——LinkedHashMap.Entry，而這個内部類又繼承自Node，是以算是Node的孫子輩了。
屬性：parent指向父節點，left指向左孩子，right指向右孩子，prev則指向前一個節點（原連結清單中的前一個節點），red表示顔色

3.HashMap 的 put 方法的執行過程？

首先會計算 key 的 hash 值，然後根據 hash 值确認在 table 中存儲的位置。
若該位置沒有元素，則直接插入。
否則疊代該處元素連結清單并依次比較其 key 的 hash 值。如果兩個 hash 值相等且 key 值相等(e.hash == hash && ((k = e.key) == key || key.equals(k)))，則用新的value 覆寫原來節點的 value。
如果兩個 hash 值相等但 key 值不等，若為樹結構則按樹的方式插入，若為連結清單結構則在連結清單尾部插入新節點
插入後若達到紅黑樹門檻值（連結清單上的元素個數超過 8 個并且數組長度 >= 64 ）則轉化為紅黑樹
更新size，達到擴容門檻值則開始擴容

3.5 轉換為紅黑樹的門檻值為什麼是8

首先和hashcode碰撞次數的泊松分布有關，主要是為了尋找一種時間和空間的平衡。在負載因子0.75（HashMap預設）的情況下，單個hash槽内元素個數為8的機率小于百萬分之一，将7作為一個分水嶺，等于7時不做轉換，大于等于8才轉紅黑樹，小于等于6才轉連結清單。連結清單中元素個數為8時的機率已經非常小，再多的就更少了，是以原作者在選擇連結清單元素個數時選擇了8，是根據機率統計而選擇的。

紅黑樹中的TreeNode是連結清單中的Node所占空間的2倍，雖然紅黑樹的查找效率為o(logN)，要優于連結清單的o(N)，但是當連結清單長度比較小的時候，即使全部周遊，時間複雜度也不會太高。是以，要尋找一種時間和空間的平衡，即在連結清單長度達到一個門檻值之後再轉換為紅黑樹。

4. HashMap 的 get 方法的執行過程？

通過 key 的 hash 值找到在 table 數組中的位置，在該位置用疊代查找有沒有相等的key，有則傳回該key對應的value，沒有則傳回null

判斷相等：先判斷hash是否相等，再判斷==，再判斷equals

if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))

4.5 為什麼先判斷hash再判斷equals

因為隻要hash不等equals一定不等，無需再去調用equals方法，提前傳回

5.HashMap 的 resize 方法的執行過程？

有兩種情況會調用 resize 方法：

第一次調用 HashMap 的 put 方法時，會調用 resize 方法對 table 數組進行初始化，如果不傳入指定值，預設大小為 16。
擴容時會調用 resize，即 size > threshold 時，建立一個原容量兩倍大小的新數組，再将原數組的元素按照put的規則逐個轉移至新數組。

如果轉移時發現該位置處拉着一條連結清單，則先講連結清單拆分：

連結清單中的 node 要麼在 newtab 的 i 位置（不變），要麼在 newtab 的 i + n 位置。
是以可以把 table[i] 這個桶中的 node 拆分為兩個連結清單 l1 和 l2：如果 hash & oldCap == 0，那麼目前這個 node 被連接配接到 l1 連結清單；否則連接配接到 l2 連結清單。
當周遊完 table[i] 處的所有 node 的時候，我們得到兩個連結清單 l1 和 l2，這時我們令 newtab[i] = l1，newtab[i + n] = l2，這就完成了 table[i] 位置所有 node 的遷移（rehash），這也是 HashMap 中容量一定的是 2 的整數次幂帶來的友善之處。

6.HashMap 的 size 為什麼必須是 2 的整數次方？

提升計算數組位置效率：size 為 2 的 n 次方時，hash& (size- 1) 等價于對 size 取模，且速度比直接取模快得多。
若size為奇數， (size- 1)最後一位為0，hash& (size- 1) 最後一位必為0，浪費了一半空間
擴容轉移時便于連結清單的拆分（根據hash & oldCap == 0拆分）

7. JDK1.7和 JDK1.8 HashMap實作原理的差別

底層資料結構：1.7為數組+連結清單，1.8為數組+連結清單+紅黑樹
hash的計算方式：1.7算法包含4次位運算+5次異或；1.8算法為 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 1次位運算+1次異或，比起1.7更加簡潔
連結清單資料插入方式：1.7采用頭插法，在多線程環境下會引發死循環；1.8采用尾插法，避免了這一問題
擴容機制：1.7轉移連結清單時逐個計算新位置，且采用頭插法；1.8轉移連結清單前統一計算，拆分為兩個連結清單後插入新位置

7.5. 為什麼HashMap為什麼不用跳表替換紅黑樹?

8. HashMap 多線程死循環問題？

主要原因在于并發下的 Rehash 會造成元素之間會形成一個循環連結清單，進而使得後面 get 的時候，會死循環。

jdk 1.8 後解決了這個問題，但是還是不建議在多線程下使用 HashMap,因為多線程下使用 HashMap 還是會存在其他問題比如資料丢失。并發環境下推薦使用 ConcurrentHashMap 。

https://coolshell.cn/articles/9606.html

9. HashMap 的 get 方法能否判斷某個元素是否在 map 中？

HashMap 的 get 函數的傳回值不能判斷一個 key 是否包含在 map 中，因為 get 傳回 null 有可能是不包含該 key，也有可能該 key 對應的 value 為 null。因為 HashMap 中允許 key 為 null，也允許 value 為 null。

10. 為什麼String, Interger這樣的wrapper類适合作為鍵？

因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。

不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和擷取時傳回不同的hashcode的話，那麼就不能從HashMap中找到你想要的對象。

因為擷取對象的時候要用到equals()和hashCode()方法，那麼鍵對象正确的重寫這兩個方法是非常重要的。如果兩個不相等的對象傳回不同的hashcode的話，那麼碰撞的幾率就會小些，這樣就能提高HashMap的性能。

11.能否使用任何類作為 Map 的 key？

可以使用任何類作為 Map 的 key，然而在使用之前，需要考慮以下幾點：

如果類重寫了 equals() 方法，也應該重寫 hashCode() 方法。

類的所有執行個體需要遵循與 equals() 和 hashCode() 相關的規則。

如果一個類沒有使用 equals()，不應該在 hashCode() 中使用它。

使用者自定義 Key 類最佳實踐是使之為不可變的，這樣 hashCode() 值可以被緩存起來，擁有更好的性能。不可變的類也可以確定 hashCode() 和 equals() 在未來不會改變，這樣就會解決與可變相關的問題了。

12. HashMap 的 7 種周遊方式與性能

使用疊代器（Iterator）EntrySet 的方式進行周遊；
使用疊代器（Iterator）KeySet 的方式進行周遊；
使用 For Each EntrySet 的方式進行周遊；
使用 For Each KeySet 的方式進行周遊；
使用 Lambda 表達式的方式進行周遊；
使用 Streams API 單線程的方式進行周遊；
使用 Streams API 多線程的方式進行周遊。

除了并行循環的 parallelStream 性能比極高之外（多線程方式性能肯定比較高），其他方式的周遊方法在性能方面幾乎沒有任何差别。

13.LinkedHashMap 的實作原理?

LinkedHashMap 也是基于 HashMap 實作的，不同的是它定義了一個 Entry header，這個 header 不是放在 Table 裡，它是額外獨立出來的。LinkedHashMap 通過繼承 hashMap 中的 Entry，并添加兩個屬性 Entry before，after 和 header 結合起來組成一個雙向連結清單，來實作按插入順序或通路順序排序。

LinkedHashMap 定義了排序模式 accessOrder，該屬性為 boolean 型變量，對于通路順序，為 true；對于插入順序，則為 false。一般情況下，不必指定排序模式，其疊代順序即為預設為插入順序。

13.5 HashMap為什麼不是線程安全的

如線程A發現某桶位置沒有元素後挂起，然後線程B在該位置處插入元素；之後又切換到A，A會把B插入的元素給覆寫了

if ((p = tab[i = (n - 1) & hash]) == null) // 如果沒有hash碰撞則直接插入元素
            tab[i] = newNode(hash, key, value, null);

size++操作也是非線程安全的

14. HashMap 與 ConcurrentHashMap 的差別是什麼?

HashMap 不是線程安全的，而 ConcurrentHashMap 是線程安全的。

ConcurrentHashMap 采用鎖分段技術，将整個Hash桶進行了分段segment，也就是将這個大的數組分成了幾個小的片段 segment，而且每個小的片段 segment 上面都有鎖存在，那麼在插入元素的時候就需要先找到應該插入到哪一個片段 segment，然後再在這個片段上面進行插入，而且這裡還需要擷取 segment 鎖，這樣做明顯減小了鎖的粒度。

16.ConcurrentHashMap 的實作原理是什麼？

JDK 7：中 ConcurrentHashMap 采用了數組 + Segment + 分段鎖的方式實作。
JDK 8：中 ConcurrentHashMap 參考了 JDK 8 HashMap 的實作，采用了數組 + 連結清單 + 紅黑樹的實作方式來設計，内部大量采用 CAS 操作。

ConcurrentHashMap 采用了非常精妙的"分段鎖"政策，ConcurrentHashMap 的主幹是個 Segment 數組。

final Segment<K,V>[] segments;

Segment 繼承了 ReentrantLock，是以它就是一種可重入鎖（ReentrantLock)。在 ConcurrentHashMap，一個 Segment 就是一個子哈希表，Segment 裡維護了一個 HashEntry 數組，并發環境下，對于不同 Segment 的資料進行操作是不用考慮鎖競争的。就按預設的 ConcurrentLevel 為 16 來講，理論上就允許 16 個線程并發執行。

是以，對于同一個 Segment 的操作才需考慮線程同步，不同的 Segment 則無需考慮。Segment 類似于 HashMap，一個 Segment 維護着一個HashEntry 數組：

transient volatile HashEntry<K,V>[] table;

HashEntry 是目前我們提到的最小的邏輯處理單元了。一個 ConcurrentHashMap 維護一個 Segment 數組，一個 Segment 維護一個 HashEntry 數組。是以，ConcurrentHashMap 定位一個元素的過程需要進行兩次 Hash 操作。第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的連結清單的頭部。

17. 有哪些計算Hash值的方法

直接尋址法：取keyword或keyword的某個線性函數值為散列位址。即H(key)=key或H(key) = a•key + b，當中a和b為常數（這樣的散列函數叫做自身函數）
數字分析法：分析一組資料，比方一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體同樣，這種話，出現沖突的幾率就會非常大，可是我們發現年月日的後幾位表示月份和詳細日期的數字差別非常大，假設用後面的數字來構成散列位址，則沖突的幾率會明顯減少。是以數字分析法就是找出數字的規律，盡可能利用這些資料來構造沖突幾率較低的散列位址。
平方取中法：取keyword平方後的中間幾位作為散列位址。
折疊法：将keyword切割成位數同樣的幾部分，最後一部分位數能夠不同，然後取這幾部分的疊加和（去除進位）作為散列位址。
随機數法：選擇一随機函數，取keyword的随機值作為散列位址，通經常使用于keyword長度不同的場合。
除留餘數法：取keyword被某個不大于散清單表長m的數p除後所得的餘數為散列位址。即 H(key) = key MOD p, p<=m。不僅能夠對keyword直接取模，也可在折疊、平方取中等運算之後取模。對p的選擇非常重要，一般取素數或m，若p選的不好，easy産生同義詞。

18. 常見的Hash算法

MD4。MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它适用在32位字長的處理器上用快速軟體實作–它是基于 32 位操作數的位操作來實作的。
MD5。MD5(RFC 1321)是 Rivest 于1991年對MD4的改進版本号。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 同樣。MD5比MD4來得複雜，而且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好

MD5算法的原理可簡要的叙述為：MD5碼以512位分組來處理輸入的資訊，且每一分組又被劃分為16個32位子分組，經過了一系列的處理後，算法的輸出由四個32位分組組成，将這四個32位分組級聯後将生成一個128位散列值。

步驟：每次的運算都由前一輪的128位結果值和目前的512bit值進行運算

SHA-1 及其它。SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小于264的輸入，産生長度為160bit的散列值，是以抗窮舉(brute-force)性更好。SHA-1 設計時基于和MD4同樣原理,而且模仿了該算法。

19. 紅黑樹節點的插入

先看父節點：

父黑直接插入
父紅看叔叔：
- 叔紅父叔塗黑爺爺塗紅
- 叔黑:
  - 父左我左以父R
  - 父左我右以我LR
  - 父右我左以我RL
  - 父右我右以父L

20. HashMap有哪些内部類

有以下内部類

Java集合類面試題總結Java集合類面試題

常用的有Node,TreeNode,EntrySet,KeySet,KeyIterator

Java集合類面試題總結Java集合類面試題

Java集合類面試題

一. 概述

1. Java集合概覽

Collection

Set

List

Queue

Map

2. List,Set,Map 三者的差別？

3. 數組與集合的對比

4. RandomAccess 接口的作用

5. 哪些集合類提供對元素的随機通路？

6.什麼是Iterator？

7. Iterator與ListIterator有什麼差別？

8. fail-fast（快速失敗）

9. fail-fast解決方案

10. fail-fast 與 fail-safe 有什麼差別？

11.為什麼 Collection 不能繼承 Cloneable 和 Serializable？

12. Arrays.sort()的原理

二. List

¥1. ArrayList 和 LinkedList 的差別？

2. ArrayList 的增删是否一定比 LinkedList 要慢？

¥3. ArrayList 的擴容機制？

4. System.arraycopy() 和 Arrays.copyOf()方法的差別

5. Arraylist 和 Vector 的差別?

6. 為什麼Vector類認為是廢棄的或者是非官方地不推薦使用？

7.在 Queue 中 poll()和 remove()有什麼差別？

三. Set

1. HashSet 的實作原理？

四. Map

1. HashMap 和 Hashtable 的差別

2.HashMap 的實作原理/底層資料結構？JDK1.7 和 JDK1.8

2.5 HashMap的紅黑樹節點存儲的是什麼

3.HashMap 的 put 方法的執行過程？

3.5 轉換為紅黑樹的門檻值為什麼是8

4. HashMap 的 get 方法的執行過程？

4.5 為什麼先判斷hash再判斷equals

5.HashMap 的 resize 方法的執行過程？

6.HashMap 的 size 為什麼必須是 2 的整數次方？

7. JDK1.7和 JDK1.8 HashMap實作原理的差別

7.5. 為什麼HashMap為什麼不用跳表替換紅黑樹?

8. HashMap 多線程死循環問題？

9. HashMap 的 get 方法能否判斷某個元素是否在 map 中？

10. 為什麼String, Interger這樣的wrapper類适合作為鍵？

11.能否使用任何類作為 Map 的 key？

12. HashMap 的 7 種周遊方式與性能

13.LinkedHashMap 的實作原理?

13.5 HashMap為什麼不是線程安全的

14. HashMap 與 ConcurrentHashMap 的差別是什麼?

16.ConcurrentHashMap 的實作原理是什麼？

17. 有哪些計算Hash值的方法

18. 常見的Hash算法

19. 紅黑樹節點的插入

20. HashMap有哪些内部類

繼續閱讀