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知識清單
微信搜：JavaPub，閱讀全套系列面試題教程
- 前言
- 序言
- 適合閱讀人群
- 閱讀建議
- 題目
- 前言
- 1.java 容器都有哪些？
- 2.Collection 和 Collections 有什么區別？
- 3.List、Set、Map 之間的區別是什么？
- List 、Set、 Map都有哪些子類
- 4.HashMap 和 Hashtable 有什么區別？
- 區別：
- 5.如何決定使用 HashMap 還是 TreeMap？
- 6.說一下 HashMap 的實作原理？
- 兩個重要的引數
- put函式的實作
- get函式的實作
- hash函式的實作
- resize的實作（非常有趣又重要的一節）
- jdk7和jdk8中HashMap的大致變化？
- 你知道HashMap作業原理嗎
- 7.說一下 HashSet 的實作原理？
- 8.ArrayList 和 LinkedList 的區別是什么？
- 為什么快？
- 9.如何實作陣列和 List 之間的轉換？
- 10.ArrayList 和 Vector 的區別是什么？
- 11.Array 和 ArrayList 有何區別？
- 12.在 Queue 中 poll()和 remove()有什么區別？
- 13.哪些集合類是執行緒安全的？
- 拓展：java.util.concurrent包下的集合類如何保證執行緒安全
- 14.迭代器 Iterator 是什么？
- 15.Iterator 怎么使用？有什么特點？
- forEachRemaining() 用法：
- 16.Iterator 和 ListIterator 有什么區別？
- 包含方法
- 17.怎么確保一個集合不能被修改？
- 1.Collections. unmodifiableCollection(Collection c) 方法
- 2.使用Arrays.asList創建的集合
容器是開發中非常重要的一部分知識，本篇盡量以大白話描述各個知識點，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參考巨人：https://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參考巨人（包括一部分原始碼）：https://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參考巨人：https://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 = https://www.cnblogs.com/JavaPub/archive/2021/02/09/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(http://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的性能提升**(http://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參考巨人：https://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參考巨人：
https://yikun.github.io/2015/04/01/Java-HashMap作業原理及實作/
https://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 底層陣列擴容方法：https://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參考巨人：https://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參考巨人：https://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參考巨人：
https://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參考巨人：https://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參考巨人-包括原始碼解讀（篇幅較長）：https://javapub.blog.csdn.net/article/details/113768605
恭喜你看到了最后，這篇文章整理用了四天時間，再看和轉發是對我最大的鼓勵，我的pub哥，歡迎關注JavaPub，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/258318.html
標籤：其他