Java容器–2021面試題系列教程（附答案解析）–大白話解讀–JavaPub版本
Java容器–2021面試題系列教程（附答案解析）–大白話解讀–JavaPub版本
前言
序言
再高大上的框架，也需要紮實的基礎才能玩轉，高頻面試問題更是基礎中的高頻實戰要點。
適合閱讀人群
Java 學習者和愛好者，有一定工作經驗的技術人，准面試官等。
閱讀建議
本教程是系列教程，包含 Java 基礎，JVM，容器，多線程，反射，異常，網絡，對象拷貝，JavaWeb，設計模式，Spring-Spring MVC，Spring Boot / Spring Cloud，Mybatis / Hibernate，Kafka，RocketMQ，Zookeeper，MySQL，Redis，Elasticsearch，Lucene。訂閱不迷路，2021奧利給。
微信搜：JavaPub，閱讀全套系列面試題教程
- 前言
- 題目
- 前言
- 1.java 容器都有哪些？
- 2.Collection 和 Collections 有什麼區別？
- 3.List、Set、Map 之間的區別是什麼？
- 4.HashMap 和 Hashtable 有什麼區別？
- 5.如何決定使用 HashMap 還是 TreeMap？
- 6.說一下 HashMap 的實現原理？
- 7.說一下 HashSet 的實現原理？
- 8.ArrayList 和 LinkedList 的區別是什麼？
- 9.如何實現數組和 List 之間的轉換？
- 10.ArrayList 和 Vector 的區別是什麼？
- 11.Array 和 ArrayList 有何區別？
- 12.在 Queue 中 poll()和 remove()有什麼區別？
- 13.哪些集合類是線程安全的？
- 14.迭代器 Iterator 是什麼？
- 15.Iterator 怎麼使用？有什麼特點？
- 16.Iterator 和 ListIterator 有什麼區別？
- 17.怎麼確保一個集合不能被修改？
容器是開發中非常重要的一部分知識，本篇盡量以大白話描述各個知識點。HashMap 實現原理是非常重要的一個知識點，我們在日常設計代碼時也會涉及到這個思想，推薦第6題，會讓你使用起來更得心應手。
題目
前言
先對 Java 容器做一個簡單介紹
首先放一張官方的圖：
從上面的集合框架圖可以看到，Java 集合框架主要包括兩種類型的容器，一種是集合（Collection），存儲一個元素集合，另一種是圖（Map），存儲鍵/值對映射。Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最後是具體實現類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
接口：是代表集合的抽象數據類型。例如 Collection、List、Set、Map 等。之所以定義多個接口，是為了以不同的方式操作集合對象
實現（類）：是集合接口的具體實現。從本質上講，它們是可重複使用的數據結構，例如：ArrayList、LinkedList、HashSet、HashMap。
算法：是實現集合接口的對象里的方法執行的一些有用的計算，例如：搜索和排序。這些算法被稱為多態，那是因為相同的方法可以在相似的接口上有着不同的實現。
除了集合，該框架也定義了幾個 Map 接口和類。Map 里存儲的是鍵/值對。儘管 Map 不是集合，但是它們完全整合在集合中。
集合框架體系如圖所示：
Java 集合框架提供了一套性能優良，使用方便的接口和類，java集合框架位於java.util包中。
1.java 容器都有哪些？
常用容器圖錄：
從圖上可以看到，Java容器分為兩大陣營：Collection和Map
Collection：主要是單個元素的集合，由List、Queue、Set三個接口區分不同的集合特徵，然後由下面的具體的類來實現對應的功能。
Map：有一組鍵值對的存儲形式來保存，可以用鍵對象來查找值。
JavaPub參考巨人：//zhuanlan.zhihu.com/p/29421226
2.Collection 和 Collections 有什麼區別？
java.util.Collection是一個集合接口。它提供了對集合對象進行基本操作的通用接口方法。Collection 接口在 Java 類庫中有很多具體的實現。Collection 接口的意義是為各種具體的集合提供了最大化的統一操作方式。
List，Set，Queue接口都繼承Collection。
直接實現該接口的類只有AbstractCollection類，該類也只是一個抽象類，提供了對集合類操作的一些基本實現。List和Set的具體實現類基本上都直接或間接的繼承了該類。
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
java.util.Collections是一個包裝類。它包含有各種有關集合操作的靜態方法（對集合的搜索、排序、線程安全化等），大多數方法都是用來處理線性表的。此類不能實例化，就像一個工具類，服務於 Java 的 Collection 框架。
3.List、Set、Map 之間的區別是什麼？
-
List：有序集合，元素可重複
-
Set：不重複集合，LinkedHashSet 按照插入排序，SortedSet 可排序，HashSet 無序
-
Map：鍵值對集合，存儲鍵、值和之間的映射；Key 無序，唯一；value 不要求有序，允許重複
List 、Set、 Map都有哪些子類
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
|-HashSet
└TreeSet
Map
├Hashtable
├HashMap
└WeakHashMap
4.HashMap 和 Hashtable 有什麼區別？
HashMap 不是線程安全的
HashMap 是 map 接口的實現類，是將鍵映射到值的對象，其中鍵和值都是對象，並且不能包含重複鍵，但可以包含重複值。HashMap 允許 null key 和 null value，而 HashTable 不允許。
HashTable 是線程安全 Collection。
HashMap 是 HashTable 的輕量級實現，他們都完成了Map 接口，主要區別在於 HashMap 允許 null key 和 null value,由於非線程安全，效率上可能高於 Hashtable。
區別：
- Hashtable 繼承自 Dictionary 類，而 HashMap 繼承自 AbstractMap 類。但二者都實現了 Map 接口。
- HashMap 允許將 null 作為一個 entry 的 key 或者 value，而 Hashtable 不允許。
- HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因為 contains 方法容易讓人引起誤解。Hashtable 則保留了 contains，containsValue 和containsKey 三個方法，其中 contains 和 containsValue 功能相同。
- Hashtable 中的方法是 Synchronize 的，而 HashMap 中的方法在缺省情況下是非 Synchronize 的。在多線程並發的環境下，可以直接使用 Hashtable，不需要自己為它的方法實現同步，但使用 HashMap 時就必須要自己增加同步處理。（結構上的修改是指添加或刪除一個或多個映射關係的任何操作；僅改變與實例已經包含的鍵關聯的值不是結構上的修改。）這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedMap 方法來「包裝」該映射。最好在創建時完成這一操作，以防止對映射進行意外的非同步訪問，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...)); - hash值不同，哈希值的使用不同，HashTable直接使用對象的hashCode。而HashMap重新計算hash值。
hashCode是jdk根據對象的地址或者字符串或者數字算出來的int類型的數值。
Hashtable計算hash值，直接用key的hashCode()，而HashMap重新計算了key的hash值，Hashtable在求hash值對應的位置索引時，用取模運算，而HashMap在求位置索引時，則用與運算，且這裡一般先用hash&0x7FFFFFFF後，再對length取模，&0x7FFFFFFF的目的是為了將負的hash值轉化為正值，因為hash值有可能為負數，而&0x7FFFFFFF後，只有符號外改變，而後面的位都不變。
- 內部實現使用的數組初始化和擴容方式不同，
HashTable在不指定容量的情況下的默認容量為11，而HashMap為16，Hashtable不要求底層數組的容量一定要為2的整數次冪，而HashMap則要求一定為2的整數次冪。
Hashtable擴容時，將容量變為原來的2倍加1，而HashMap擴容時，將容量變為原來的2倍。
Hashtable和HashMap它們兩個內部實現方式的數組的初始大小和擴容的方式。HashTable中hash數組默認大小是11，增加的方式是 old*2+1。
源碼也是非常重要的一點，而且寫得非常棒，後面單獨寫一篇。
JavaPub參考巨人（包括一部分源碼）：//www.cnblogs.com/williamjie/p/9099141.html
5.如何決定使用 HashMap 還是 TreeMap？
TreeMap<K,V> 的 Key 值是要求實現 java.lang.Comparable，所以迭代的時候TreeMap 默認是按照 Key 值升序排序的；TreeMap 的實現是基於紅黑樹結構。適用於按自然順序或自定義順序遍歷鍵（key）。
HashMap<K,V> 的 Key 值實現散列 hashCode()，分佈是散列的、均勻的，不支持排序；數據結構主要是桶(數組)，鏈表或紅黑樹。適用於在 Map 中插入、刪除和定位元素。
結論：
如果你需要得到一個有序的結果時就應該使用 TreeMap（因為 HashMap 中元素的排列順序是不固定的）。除此之外，由於 HashMap 有更好的性能，所以大多不需要排序的時候我們會使用 HashMap。
JavaPub參考巨人：//javapub.blog.csdn.net/article/details/113482689
6.說一下 HashMap 的實現原理？
HashMap 的重要性就不說了。說到原理，就要說它的數據結構和實現原理。
官方文檔是這樣描述HashMap的：
Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
幾個關鍵的信息：基於 Map 接口實現、允許 null鍵/值、非同步、不保證有序(比如插入的順序)、也不保證序不隨時間變化。
兩個重要的參數
在HashMap中有兩個很重要的參數，容量(Capacity)和負載因子(Load factor)
Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.
Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
簡單的說，Capacity 就是 buckets 的數目，Load factor 就是 buckets 填滿程度的最大比例。如果對迭代性能要求很高的話不要把 capacit 設置過大，也不要把 load factor 設置過小。當 bucket 填充的數目（即hashmap中元素的個數）大於 capacity*load factor 時就需要調整 buckets 的數目為當前的2倍。
put函數的實現
jdk8的思路
put函數大致的思路為：
- 對key的hashCode()做hash，然後再計算index;
- 如果沒碰撞直接放到bucket里；
- 如果碰撞了，以鏈表的形式存在buckets後；
- 如果碰撞導致鏈表過長(大於等於TREEIFY_THRESHOLD)，就把鏈錶轉換成紅黑樹；
- 如果節點已經存在就替換old value(保證key的唯一性)
- 如果bucket滿了(超過load factor*current capacity)，就要resize。
具體代碼實現：
public V put(K key, V value) {
// 對key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
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為空則創建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算index，並對null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 節點存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 該鏈為樹
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 寫入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超過load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get函數的實現
在理解了put之後，get就很簡單了。大致思路如下：
- bucket里的第一個節點，直接命中；
- 如果有衝突，則通過key.equals(k)去查找對應的entry
若為樹，則在樹中通過key.equals(k)查找，O(logn)；
若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。
具體代碼的實現如下：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 在樹中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
hash函數的實現
在get和put的過程中，計算下標時，先對hashCode進行hash操作，然後再通過hash值進一步計算下標，如下圖所示：
在對hashCode()計算hash時具體實現是這樣的：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
可以看到這個函數大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或。其中代碼注釋是這樣寫的：
Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don』t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.
在設計hash函數時，因為目前的table長度n為2的冪，而計算下標的時候，是這樣實現的(使用 & 位操作，而非 % 求余)：
(n - 1) & hash
(n - 1) & hash
設計者認為這方法很容易發生碰撞。為什麼這麼說呢？不妨思考一下，在n – 1為15(0x1111)時，其實散列真正生效的只是低4bit的有效位，當然容易碰撞了。
因此，設計者想了一個顧全大局的方法(綜合考慮了速度、作用、質量)，就是把高16bit和低16bit異或了一下。設計者還解釋到因為現在大多數的hashCode的分佈已經很不錯了，就算是發生了碰撞也用O(logn)的tree去做了。僅僅異或一下，既減少了系統的開銷，也不會造成的因為高位沒有參與下標的計算(table長度比較小時)，從而引起的碰撞。
如果還是產生了頻繁的碰撞，會發生什麼問題呢？作者注釋說，他們使用樹來處理頻繁的碰撞(we use trees to handle large sets of collisions in bins)，在 JEP-180(//openjdk.java.net/jeps/180)中，描述了這個問題：
Improve the performance of java.util.HashMap under high hash-collision conditions by using balanced trees rather than linked lists to store map entries. Implement the same improvement in the LinkedHashMap class.
之前已經提過，在獲取HashMap的元素時，基本分兩步：
- 首先根據hashCode()做hash，然後確定bucket的index；
- 如果bucket的節點的key不是我們需要的，則通過keys.equals()在鏈中找。
在Java 8之前的實現中是用鏈表解決衝突的，在產生碰撞的情況下，進行get時，兩步的時間複雜度是O(1)+O(n)。因此，當碰撞很厲害的時候n很大，O(n)的速度顯然是影響速度的。
因此在Java 8中，利用紅黑樹替換鏈表，這樣複雜度就變成了O(1)+O(logn)了，這樣在n很大的時候，能夠比較理想的解決這個問題，在 ** Java 8：HashMap的性能提升**(//www.importnew.com/14417.html)一文中有性能測試的結果。
resize的實現（非常有趣又重要的一節）
當put時，如果發現目前的bucket佔用程度已經超過了Load Factor所希望的比例，那麼就會發生resize。在resize的過程，簡單的說就是把bucket擴充為2倍，之後重新計算index，把節點再放到新的bucket中。resize的注釋是這樣描述的：
Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
大致意思就是說，當超過限制的時候會resize，然而又因為我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。
怎麼理解呢？例如我們從16擴展為32時，具體的變化如下所示：
因此元素在重新計算 hash 之後，因為 n 變為 2 倍，那麼 n-1 的 mask 範圍在高位多 1bit(紅色)，因此新的 index 就會發生這樣的變化：
因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成「原索引+oldCap」。可以看看下圖為16擴充為32的resize示意圖：
這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由於新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的衝突的節點分散到新的bucket了。
下面是代碼的具體實現：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過最大值就不再擴充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過最大值，就擴充為原來的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
jdk7和jdk8中HashMap的大致變化？
這也是很重要的一點，因為JDK7、JDK8依然是市場上的主流版本。還是像開篇說的一樣，高頻面試題是Java中的重中之重，都是前輩技術人員總結出的工作經驗，必會基礎。
jdk1.7
在 jdk1.7 版本的時候採用的是 數組+鏈表 的形式，也就是採用了 拉鏈法。
Java 標準庫的 HashMap 基本上就是用 拉鏈法 實現的。 拉鏈法 的實現比較簡單，將鏈表和數組相結合。也就是說創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希衝突，則將衝突的值加到鏈表中即可。
將哈希衝突值加入到每個數組的鏈表中，他的插入採用的是頭插法的形式(這種方法最大的弊端就是會使插入值產生環，從而無限循環，後面我們將詳細講解這種方法的弊端操作)，在進行hash值計算的時候，jdk1.7則採用的是9次擾動(4次位運算+5次異或運算)的方式進行處理（因為本人目前暫時用的jdk1.8所以無法利用源碼進行講解，望見諒），除此之外在擴容上也有所不同，在jdk1.7中採用的全部按照原來的方式進行計算（即hashCode ->> 擾動函數 ->> (h&length-1)），而在jdk1.8 中則採用按照擴容後的規律計算（即擴容後的位置=原位置 or 原位置 + 舊容量）。
關於頭插法的拓展：
1. 頭插法（頭是靠近數組的一端）
2. JDK8以前是頭插法，JDK8後是尾插法
3. 為什麼要從頭插法改成尾插法？
A.因為頭插法會造成死鏈，
B.JDK7用頭插是考慮到了一個所謂的熱點數據的點(新插入的數據可能會更早用到)，但這其實是個偽命題,因為JDK7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置(就是因為頭插) 所以最後的結果 還是打亂了插入的順序 所以總的來看支撐JDK7使用頭插的這點原因也不足以支撐下去了 所以就乾脆換成尾插 一舉多得。
你可以面試這樣回答（JavaPub本人經供參考，更詳細閱讀下面的參考巨人）：hashmap用數組+鏈表。數組是固定長度，鏈表太長就需要擴充數組長度進行rehash減少鏈表長度。如果兩個線程同時觸發擴容，在移動節點時會導致一個鏈表中的2個節點相互引用，從而生成環鏈表。
JavaPub參考巨人：//blog.csdn.net/chenyiminnanjing/article/details/82706942
jdk1.8
jdk1.8 的版本則採用 數組+鏈表+紅黑樹 的方式，如下圖：
Java集合小抄是這樣描述的：
以Entry[]數組實現的哈希桶數組，用Key的哈希值取模桶數組的大小可得到數組下標。
插入元素時，如果兩條Key落在同一個桶（比如哈希值1和17取模16後都屬於第一個哈希桶），我們稱之為哈希衝突。
JDK的做法是鏈表法，Entry用一個next屬性實現多個Entry以單向鏈表存放。查找哈希值為17的key時，先定位到哈希桶，然後鏈表遍歷桶里所有元素，逐個比較其Hash值然後key值。
在JDK8里，新增默認為8的閾值，當一個桶里的Entry超過閥值，就不以單向鏈表而以紅黑樹來存放以加快Key的查找速度。
當然，最好還是桶里只有一個元素，不用去比較。所以默認當Entry數量達到桶數量的75%時，哈希衝突已比較嚴重，就會成倍擴容桶數組，並重新分配所有原來的Entry。擴容成本不低，所以也最好有個預估值。
取模用與操作（hash & （arrayLength-1））會比較快，所以數組的大小永遠是2的N次方， 你隨便給一個初始值比如17會轉為32。默認第一次放入元素時的初始值是16。
iterator（）時順着哈希桶數組來遍歷，看起來是個亂序
你知道HashMap工作原理嗎
通過 hash 的方法，通過 put 和 get 存儲和獲取對象。存儲對象時，我們將 K/V 傳給 put 方法時，它調用 hashCode 計算 hash 從而得到 bucket 位置，進一步存儲，HashMap會根據當前 bucket 的佔用情況自動調整容量(超過Load Facotr則resize為原來的2倍)。獲取對象時，我們將K傳給 get，它調用 hashCode 計算 hash 從而得到bucket位置，並進一步調用 equals() 方法確定鍵值對。如果發生碰撞的時候，Hashmap 通過鏈表將產生碰撞衝突的元素組織起來，在 Java 8 中，如果一個 bucket 中碰撞衝突的元素超過某個限制(默認是8)，則使用紅黑樹來替換鏈表，從而提高速度。
JavaPub在寫HashMap參考巨人：
//yikun.github.io/2015/04/01/Java-HashMap工作原理及實現/
//segmentfault.com/a/1190000023388339
7.說一下 HashSet 的實現原理？
- HashSet 類是按照哈希算法（離散函數）來存儲集合中的元素，他當中的元素是無序的，允許且最多一個元素為 null 。它是Set 的一個實現，所以沒有重複元素。
- 在 HashSet 類中實現了 Collection 接口中的所有方法
- HashSet 是基於 HashMap 實現的，默認構造函數是構建一個初始容量為16，負載因子為 0.75 的 HashMap。封裝了一個 HashMap 對象來存儲所有的集合元素，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態的 Oject 對象。
- HashSet的其他操作都是基於HashMap的。
8.ArrayList 和 LinkedList 的區別是什麼？
學過 Java 基礎的同學都能快速回答出，ArrayList 數組實現，所以查詢快；LinkedList 列表實現，所以增刪快。
為什麼快？
掌握這個問題，才能更好的理解這個知識點。
數組
列表
那麼為什麼數組查詢就快了呢?因為假設數組裏面保存的是一組對象,每個對象都有內存大小,例如對象中有一個字段是int類型佔用4個位元組(只考慮實際數據佔用的內存),數組在堆上的內存在數組被創建出來就被確定了是40個位元組.如果我們要查找第9個對象,可以通過(9-1)*4=32,從33到36位元組就是我們要找的對象.是不是很快呢?而鏈表卻不能做到這樣的效率.如上圖,我們要找到A4,必須先找到A3,再先找到A2,再先找到A1.這樣的查找效率會大大降低.
好了,說了查找,再說說插入,數組的插入也相當的浪費效率,如果要在數組內的某一個位置進行插入,需要先將插入位置的前面複製一份,然後在新的數組後面添加新的元素,最後將舊的數組後半部分添加的新的數組後面,而在鏈表中插入就變得相當簡單了,比如我要在A3和A4中插入B,只需定位到A3的指針和A4的數據即可,將A3的指針指向B的值,將B的指針指向A4的值,B就插入進了鏈表.
JavaPub 推薦關於 ArrayList 底層數組擴容方法：//javapub.blog.csdn.net/article/details/113686651
9.如何實現數組和 List 之間的轉換？
數組轉 List ，使用 JDK 中 java.util.Arrays 工具類的 asList 方法
public static void testArray2List() {
String[] strs = new String[] {"aaa", "bbb", "ccc"};
List<String> list = Arrays.asList(strs);
for (String s : list) {
System.out.println(s);
}
}
List 轉數組，使用 List 的 toArray 方法。無參 toArray 方法返回 Object 數組，傳入初始化長度的數組對象，返回該對象數組。
public static void testList2Array() {
List<String> list = Arrays.asList("aaa", "bbb", "ccc");
String[] array = list.toArray(new String[list.size()]);
for (String s : array) {
System.out.println(s);
}
}
10.ArrayList 和 Vector 的區別是什麼？
-
線程安全：Vector 使用了 Synchronized 來實現線程同步，是線程安全的，而 ArrayList 是非線程安全的。
-
性能：ArrayList 在性能方面要優於 Vector。
-
擴容：ArrayList 和 Vector 都會根據實際的需要動態的調整容量，都採用線性連續存儲空。
只不過在 Vector 擴容每次會增加 1 倍，而 ArrayList 只會增加 50%。
- Vector 可以設置 capacityIncrement ，而 ArrayList 不可以，從字面理解就是 capacity 容量，Increment 增加，容量增長的參數。
11.Array 和 ArrayList 有何區別？
Array：它是數組，申明數組的時候就要初始化並確定長度，長度不可變，而且它只能存儲同一類型的數據，比如申明為 String 類型的數組，那麼它只能存儲 String 類型數據
ArrayList：它是一個集合，需要先申明，然後再添加數據，長度是根據內容的多少而改變的， ArrayList 可以存放不同類型的數據，在存儲基本類型數據的時候要使用基本數據類型的包裝類
當能確定長度並且數據類型一致的時候就可以用數組，其他時候使用 ArrayList。
12.在 Queue 中 poll()和 remove()有什麼區別？
隊列（Queue） 是一種特殊的線性表，它只允許在表的前端進行刪除操作，而在表的後端進行插入操作。
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll poll} only in that it throws an exception if this
* queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E poll();
從源碼描述可以知道，remove() 如果隊列為空的時候，則會拋出異常，poll() 會返回 null。
13.哪些集合類是線程安全的？
- Vector，實現 List 接口，與 ArrayList 相比幾乎相同，但是是線程安全的。底層是數組。
- Stack，繼承 Vector 類，先進後出。
- HashTable，實現 Map 接口，與 HashMap 幾乎完全相同，但是是線程安全的。
- java.util.concurrent包下的所有集合類，例如：ConcurrentHashMap。（ConcurrentLinkedQueue、ConcurrentLinkedDueue 等）
拓展：java.util.concurrent包下的集合類如何保證線程安全
JavaPub參考巨人：//www.cnblogs.com/junjiang3/p/8686290.html
14.迭代器 Iterator 是什麼？
標準答案：
迭代器是一種設計模式，它是一個對象，它可以遍歷並選擇序列中的對象，而開發人員不需要了解該序列的底層結構。迭代器通常被稱為「輕量級」對象，因為創建它的代價小。迭代器設計模式案例演示、講解，wx訂閱：JavaPub
簡單來說，迭代器是用於順序訪問集合對象的元素，無需知道集合對象的底層實現。Iterator 是可以遍歷集合的對象，為各種容器提供了公共的操作接口，隔離對容器的遍歷操作和底層實現，從而解耦。
Java中的Iterator功能比較簡單，並且只能單向移動：
-
使用方法iterator()要求容器返回一個Iterator。第一次調用Iterator的next()方法時，它返回序列的第一個元素。注意：iterator()方法是java.lang.Iterable接口,被Collection繼承。
-
使用next()獲得序列中的下一個元素。
-
使用hasNext()檢查序列中是否還有元素。
-
使用remove()將迭代器新返回的元素刪除。
簡單栗子：
import java.util.*;
public class Muster {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
Iterator it = list.iterator();
while(it.hasNext()){
String str = (String) it.next();
System.out.println(str);
}
}
}
JavaPub參考巨人：//www.cnblogs.com/hasse/p/5024193.html
15.Iterator 怎麼使用？有什麼特點？
接口源碼：
//是否有下一個元素
boolean hasNext();
//下一個元素
E next();
//從迭代器指向的集合中刪除迭代器返回的最後一個元素
default void remove() {
throw new UnsupportedOperationException("remove");
}
/**
* Performs the given action for each remaining element until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.
*
* 簡單來說，就是對集合中剩餘的元素進行操作，直到元素完畢或者拋出異常。這裡重要的是剩餘元素，怎麼理解呢，下面就來用代碼解釋
*
* @since 1.8
*/
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
使用案例：
public class TestIterator {
static List<String> list = new ArrayList<String>();
static {
list.add("111");
list.add("222");
list.add("333");
}
public static void main(String[] args) {
testIteratorNext();
System.out.println();
testForEachRemaining();
System.out.println();
testIteratorRemove();
}
//使用 hasNext 和 next遍歷
public static void testIteratorNext() {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String str = iterator.next();
System.out.println(str);
}
}
//使用 Iterator 刪除元素
public static void testIteratorRemove() {
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String str = iterator.next();
if ("222".equals(str)) {
iterator.remove();
}
}
System.out.println(list);
}
//使用 forEachRemaining 遍歷
public static void testForEachRemaining() {
final Iterator<String> iterator = list.iterator();
iterator.forEachRemaining(new Consumer<String>() {
public void accept(String t) {
System.out.println(t);
}
});
}
}
打印結果：
111
222
333
111
222
333
111
333
注意事項：
-
在迭代過程中調用集合的 remove(Object o) 可能會報 java.util.ConcurrentModificationException 異常
-
forEachRemaining 方法中 調用Iterator 的 remove 方法會報 java.lang.IllegalStateException 異常
forEachRemaining() 用法：
import java.util.*;
public class Test{
public static void main(String[] args){
//創建一個元素類型為Integer的集合
Collection<Integer> collection = new HashSet<>();
for (int i=0;i<10 ;i++ ){
//向集合中添加元素
collection.add(i);
}
//獲取該集合的迭代器
Iterator<Integer> iterator= collection.iterator();
//調用forEachRemaining()方法遍歷集合元素
iterator.forEachRemaining(ele -> System.out.println(ele));
}
}
-----------------------------------------------------------------------
輸出為：
0
1
2
3
4
5
6
7
8
9
這是預料之中的結果。那繼續看下面代碼：
import java.util.*;
public class Test
{
public static void main(String[] args)
{
//創建一個元素類型為Integer的集合
Collection<Integer> collection = new HashSet<>();
for (int i=0;i<10 ;i++ )
{
//向集合中添加元素
collection.add(i);
}
//獲取該集合的迭代器
Iterator<Integer> iterator= collection.iterator();
//調用迭代器的經過集合實現的抽象方法遍歷集合元素
while(iterator.hasNext())
{
System.out.println(iterator.next());
}
System.out.println("--------------");
//調用forEachRemaining()方法遍歷集合元素
iterator.forEachRemaining(ele -> System.out.println(ele));
}
}
-----------------------------------------------------------------------
這時輸出為：
0
1
2
3
4
5
6
7
8
9
明明調用了迭代器兩個遍歷方法，怎麼會只遍歷一次呢？
問題就出在剩餘里，當第一次調用迭代器的經過集合實現的抽象方法遍歷集合元素時，迭代器就已經將元素遍歷完畢，也就是說迭代器中已經沒有剩餘元素了，因此這時調用forEachRemaining()方法，就什麼也不輸出了，為了驗證，再來看下面代碼：
//獲取該集合的迭代器
Iterator<Integer> iterator= collection.iterator();
//調用forEachRemaining()方法遍歷集合元素
int i=0;
while(iterator.hasNext())
{
System.out.println(iterator.next());
i++;
if (i==5)
{
break;
}
}
System.out.println("--------------");
//調用forEachRemaining()方法遍歷集合元素
iterator.forEachRemaining(ele -> System.out.println(ele));
}
}
-----------------------------------------------------------------------
這時輸出：
0
1
2
3
4
--------------
5
6
7
8
9
可以看到，當我們第一次用迭代器遍歷時，只讓它遍歷五次就跳出循環，那麼就還剩下五個元素，再調用 forEachRemaining() 方法，就可以看到輸出後五個元素了。
JavaPub參考巨人：
//www.cnblogs.com/it-deepinmind/p/13376544.html
16.Iterator 和 ListIterator 有什麼區別？
在使用Java集合的時候，都需要使用Iterator。但是java集合中還有一個迭代器ListIterator,在使用List、ArrayList、LinkedList和Vector的時候可以使用。這兩種迭代器有什麼區別呢？下面我們詳細分析。這裡有一點需要明確的時候，迭代器指向的位置是元素之前的位置。
-
ListIterator有add()方法，可以向List中添加對象，而Iterator不能
-
ListIterator和Iterator都有hasNext()和next()方法，可以實現順序向後遍歷，但是ListIterator有hasPrevious()和previous()方法，可以實現逆向（順序向前）遍歷。Iterator就不可以。
-
ListIterator可以定位當前的索引位置，nextIndex()和previousIndex()可以實現。Iterator沒有此功能。
-
都可實現刪除對象，但是ListIterator可以實現對象的修改，set()方法可以實現。Iierator僅能遍歷，不能修改。
JavPub參考巨人：//www.cnblogs.com/lijia0511/p/4960033.html
包含方法
Iterator迭代器包含的方法有：
hasNext()：如果迭代器指向位置後面還有元素，則返回 true，否則返回false
next()：返回集合中Iterator指向位置後面的元素
remove()：刪除集合中Iterator指向位置後面的元素
ListIterator迭代器包含的方法有：
add(E e): 將指定的元素插入列表，插入位置為迭代器當前位置之前
hasNext()：以正向遍歷列表時，如果列表迭代器後面還有元素，則返回 true，否則返回false
hasPrevious():如果以逆向遍歷列表，列表迭代器前面還有元素，則返回 true，否則返回false
next()：返回列表中ListIterator指向位置後面的元素
nextIndex():返回列表中ListIterator所需位置後面元素的索引
previous():返回列表中ListIterator指向位置前面的元素
previousIndex()：返回列表中ListIterator所需位置前面元素的索引
remove():從列表中刪除next()或previous()返回的最後一個元素（有點拗口，意思就是對迭代器使用hasNext()方法時，刪除ListIterator指向位置後面的元素；當對迭代器使用hasPrevious()方法時，刪除ListIterator指向位置前面的元素）
set(E e)：從列表中將next()或previous()返回的最後一個元素返回的最後一個元素更改為指定元素e
17.怎麼確保一個集合不能被修改？
1.Collections. unmodifiableCollection(Collection c) 方法
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Collection<Integer> readOnlyList = Collections.unmodifiableCollection(list);
readOnlyList.add(4); // 會報錯
2.使用Arrays.asList創建的集合
List<Integer> integers = Arrays.asList(11, 22, 33, 44);
integers.add(55);
參考地址有詳細的源碼debug解析步驟。
JavaPub參考巨人-包括源碼解讀（篇幅較長）：//javapub.blog.csdn.net/article/details/113768605
恭喜你看到了最後，這篇文章整理用了四天時間。再看和轉發是對我最大的鼓勵，我的pub哥，歡迎關注JavaPub。
