Java容器--2021面試題系列教程（附答案解析）--大白話解讀--JavaPub版本
Java容器--2021面試題系列教程（附答案解析）--大白話解讀--JavaPub版本
前言
序言
再高大上的框架，也需要扎實的基礎(chǔ)才能玩轉(zhuǎn)，高頻面試問題更是基礎(chǔ)中的高頻實戰(zhàn)要點。
適合閱讀人群
Java 學(xué)習(xí)者和愛好者，有一定工作經(jīng)驗的技術(shù)人，準(zhǔn)面試官等。
閱讀建議
本教程是系列教程，包含 Java 基礎(chǔ)，JVM，容器，多線程，反射，異常，網(wǎng)絡(luò)，對象拷貝，JavaWeb，設(shè)計模式，Spring-Spring MVC，Spring Boot / Spring Cloud，Mybatis / Hibernate，Kafka，RocketMQ，Zookeeper，MySQL，Redis，Elasticsearch，Lucene。訂閱不迷路，2021奧利給。
JavaPub知識清單
微信搜：JavaPub，閱讀全套系列面試題教程
前言
序言
適合閱讀人群
閱讀建議
題目
前言
1.java 容器都有哪些？
2.Collection 和 Collections 有什么區(qū)別？
3.List、Set、Map 之間的區(qū)別是什么？
4.HashMap 和 Hashtable 有什么區(qū)別？
5.如何決定使用 HashMap 還是 TreeMap？
6.說一下 HashMap 的實現(xiàn)原理？
7.說一下 HashSet 的實現(xiàn)原理？
8.ArrayList 和 LinkedList 的區(qū)別是什么？
9.如何實現(xiàn)數(shù)組和 List 之間的轉(zhuǎn)換？
10.ArrayList 和 Vector 的區(qū)別是什么？
11.Array 和 ArrayList 有何區(qū)別？
12.在 Queue 中 poll()和 remove()有什么區(qū)別？
13.哪些集合類是線程安全的？
14.迭代器 Iterator 是什么？
15.Iterator 怎么使用？有什么特點？
16.Iterator 和 ListIterator 有什么區(qū)別？
17.怎么確保一個集合不能被修改？
容器是開發(fā)中非常重要的一部分知識，本篇盡量以大白話描述各個知識點。HashMap 實現(xiàn)原理是非常重要的一個知識點，我們在日常設(shè)計代碼時也會涉及到這個思想，推薦第6題，會讓你使用起來更得心應(yīng)手。
題目
前言
先對 Java 容器做一個簡單介紹
首先放一張官方的圖：
從上面的集合框架圖可以看到，Java 集合框架主要包括兩種類型的容器，一種是集合（Collection），存儲一個元素集合，另一種是圖（Map），存儲鍵/值對映射。Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最后是具體實現(xiàn)類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
接口：是代表集合的抽象數(shù)據(jù)類型。例如 Collection、List、Set、Map 等。之所以定義多個接口，是為了以不同的方式操作集合對象
實現(xiàn)（類）：是集合接口的具體實現(xiàn)。從本質(zhì)上講，它們是可重復(fù)使用的數(shù)據(jù)結(jié)構(gòu)，例如：ArrayList、LinkedList、HashSet、HashMap。
算法：是實現(xiàn)集合接口的對象里的方法執(zhí)行的一些有用的計算，例如：搜索和排序。這些算法被稱為多態(tài)，那是因為相同的方法可以在相似的接口上有著不同的實現(xiàn)。
除了集合，該框架也定義了幾個 Map 接口和類。Map 里存儲的是鍵/值對。盡管 Map 不是集合，但是它們完全整合在集合中。
集合框架體系如圖所示：
Java 集合框架提供了一套性能優(yōu)良，使用方便的接口和類，java集合框架位于java.util包中。
1.java 容器都有哪些？
常用容器圖錄：
從圖上可以看到，Java容器分為兩大陣營：Collection和Map
Collection：主要是單個元素的集合，由List、Queue、Set三個接口區(qū)分不同的集合特征，然后由下面的具體的類來實現(xiàn)對應(yīng)的功能。
Map：有一組鍵值對的存儲形式來保存，可以用鍵對象來查找值。
JavaPub參考巨人：https://zhuanlan.zhihu.com/p/29421226
2.Collection 和 Collections 有什么區(qū)別？
java.util.Collection是一個集合接口。它提供了對集合對象進(jìn)行基本操作的通用接口方法。Collection 接口在 Java 類庫中有很多具體的實現(xiàn)。Collection 接口的意義是為各種具體的集合提供了最大化的統(tǒng)一操作方式。
List，Set，Queue接口都繼承Collection。 直接實現(xiàn)該接口的類只有AbstractCollection類，該類也只是一個抽象類，提供了對集合類操作的一些基本實現(xiàn)。List和Set的具體實現(xiàn)類基本上都直接或間接的繼承了該類。
?Collection??
├List??
│├LinkedList??
│├ArrayList??
│└Vector??
│?└Stack??
└Set?
java.util.Collections是一個包裝類。它包含有各種有關(guān)集合操作的靜態(tài)方法（對集合的搜索、排序、線程安全化等），大多數(shù)方法都是用來處理線性表的。此類不能實例化，就像一個工具類，服務(wù)于 Java 的 Collection 框架。
3.List、Set、Map 之間的區(qū)別是什么？
List：有序集合，元素可重復(fù)
Set：不重復(fù)集合，LinkedHashSet 按照插入排序，SortedSet 可排序，HashSet 無序
Map：鍵值對集合，存儲鍵、值和之間的映射；Key 無序，唯一；value 不要求有序，允許重復(fù)
List 、Set、 Map都有哪些子類
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│?└Stack
└Set
?|-HashSet
?└TreeSet????????
Map
├Hashtable
├HashMap
└WeakHashMap
4.HashMap 和 Hashtable 有什么區(qū)別？
HashMap 不是線程安全的HashMap 是 map 接口的實現(xiàn)類，是將鍵映射到值的對象，其中鍵和值都是對象，并且不能包含重復(fù)鍵，但可以包含重復(fù)值。HashMap 允許 null key 和 null value，而 HashTable 不允許。
HashTable 是線程安全 Collection。HashMap 是 HashTable 的輕量級實現(xiàn)，他們都完成了Map 接口，主要區(qū)別在于 HashMap 允許 null key 和 null value,由于非線程安全，效率上可能高于 Hashtable。
區(qū)別：
Hashtable 繼承自 Dictionary 類，而 HashMap 繼承自 AbstractMap 類。但二者都實現(xiàn)了 Map 接口。
HashMap 允許將 null 作為一個 entry 的 key 或者 value，而 Hashtable 不允許。
HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因為 contains 方法容易讓人引起誤解。Hashtable 則保留了 contains，containsValue 和containsKey 三個方法，其中 contains 和 containsValue 功能相同。
Hashtable 中的方法是 Synchronize 的，而 HashMap 中的方法在缺省情況下是非 Synchronize 的。在多線程并發(fā)的環(huán)境下，可以直接使用 Hashtable，不需要自己為它的方法實現(xiàn)同步，但使用 HashMap 時就必須要自己增加同步處理。（結(jié)構(gòu)上的修改是指添加或刪除一個或多個映射關(guān)系的任何操作；僅改變與實例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改。）這一般通過對自然封裝該映射的對象進(jìn)行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創(chuàng)建時完成這一操作，以防止對映射進(jìn)行意外的非同步訪問，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...));hash值不同，哈希值的使用不同，HashTable直接使用對象的hashCode。而HashMap重新計算hash值。
hashCode是jdk根據(jù)對象的地址或者字符串或者數(shù)字算出來的int類型的數(shù)值。 Hashtable計算hash值，直接用key的hashCode()，而HashMap重新計算了key的hash值，Hashtable在求hash值對應(yīng)的位置索引時，用取模運算，而HashMap在求位置索引時，則用與運算，且這里一般先用hash&0x7FFFFFFF后，再對length取模，&0x7FFFFFFF的目的是為了將負(fù)的hash值轉(zhuǎn)化為正值，因為hash值有可能為負(fù)數(shù)，而&0x7FFFFFFF后，只有符號外改變，而后面的位都不變。
內(nèi)部實現(xiàn)使用的數(shù)組初始化和擴(kuò)容方式不同，
HashTable在不指定容量的情況下的默認(rèn)容量為11，而HashMap為16，Hashtable不要求底層數(shù)組的容量一定要為2的整數(shù)次冪，而HashMap則要求一定為2的整數(shù)次冪。 Hashtable擴(kuò)容時，將容量變?yōu)樵瓉淼?倍加1，而HashMap擴(kuò)容時，將容量變?yōu)樵瓉淼?倍。 Hashtable和HashMap它們兩個內(nèi)部實現(xiàn)方式的數(shù)組的初始大小和擴(kuò)容的方式。HashTable中hash數(shù)組默認(rèn)大小是11，增加的方式是 old*2+1。
源碼也是非常重要的一點，而且寫得非常棒，后面單獨寫一篇。
JavaPub參考巨人（包括一部分源碼）：https://www.cnblogs.com/williamjie/p/9099141.html
5.如何決定使用 HashMap 還是 TreeMap？
TreeMap<K,V> 的 Key 值是要求實現(xiàn) java.lang.Comparable，所以迭代的時候TreeMap 默認(rèn)是按照 Key 值升序排序的；TreeMap 的實現(xiàn)是基于紅黑樹結(jié)構(gòu)。適用于按自然順序或自定義順序遍歷鍵（key）。
HashMap<K,V> 的 Key 值實現(xiàn)散列 hashCode()，分布是散列的、均勻的，不支持排序；數(shù)據(jù)結(jié)構(gòu)主要是桶(數(shù)組)，鏈表或紅黑樹。適用于在 Map 中插入、刪除和定位元素。
結(jié)論：
如果你需要得到一個有序的結(jié)果時就應(yīng)該使用 TreeMap（因為 HashMap 中元素的排列順序是不固定的）。除此之外，由于 HashMap 有更好的性能，所以大多不需要排序的時候我們會使用 HashMap。
JavaPub參考巨人：https://javapub.blog.csdn.net/article/details/113482689
6.說一下 HashMap 的實現(xiàn)原理？
HashMap 的重要性就不說了。說到原理，就要說它的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)原理。
官方文檔是這樣描述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.
幾個關(guān)鍵的信息：基于 Map 接口實現(xiàn)、允許 null鍵/值、非同步、不保證有序(比如插入的順序)、也不保證序不隨時間變化。
兩個重要的參數(shù)
在HashMap中有兩個很重要的參數(shù)，容量(Capacity)和負(fù)載因子(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 的數(shù)目，Load factor 就是 buckets 填滿程度的最大比例。如果對迭代性能要求很高的話不要把 capacit 設(shè)置過大，也不要把 load factor 設(shè)置過小。當(dāng) bucket 填充的數(shù)目（即hashmap中元素的個數(shù)）大于 capacity*load factor 時就需要調(diào)整 buckets 的數(shù)目為當(dāng)前的2倍。
put函數(shù)的實現(xiàn)
jdk8的思路
put函數(shù)大致的思路為：
對key的hashCode()做hash，然后再計算index;
如果沒碰撞直接放到bucket里；
如果碰撞了，以鏈表的形式存在buckets后；
如果碰撞導(dǎo)致鏈表過長(大于等于TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹；
如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)
如果bucket滿了(超過load factor*current capacity)，就要resize。 具體代碼實現(xiàn)：
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為空則創(chuàng)建
????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;
????????//?節(jié)點存在
????????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函數(shù)的實現(xiàn)
在理解了put之后，get就很簡單了。大致思路如下：
bucket里的第一個節(jié)點，直接命中；
如果有沖突，則通過key.equals(k)去查找對應(yīng)的entry 若為樹，則在樹中通過key.equals(k)查找，O(logn)； 若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。
具體代碼的實現(xià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)?{
????????????//?在樹中g(shù)et
????????????if?(first?instanceof?TreeNode)
????????????????return?((TreeNode<K,V>)first).getTreeNode(hash,?key);
????????????//?在鏈表中g(shù)et
????????????do?{
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????}
????return?null;
}
hash函數(shù)的實現(xiàn)
在get和put的過程中，計算下標(biāo)時，先對hashCode進(jìn)行hash操作，然后再通過hash值進(jìn)一步計算下標(biāo)，如下圖所示：
在對hashCode()計算hash時具體實現(xiàn)是這樣的：
static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}
可以看到這個函數(shù)大概的作用就是：高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.
在設(shè)計hash函數(shù)時，因為目前的table長度n為2的冪，而計算下標(biāo)的時候，是這樣實現(xiàn)的(使用 & 位操作，而非 % 求余)：
(n?-?1)?&?hash
(n?-?1)?&?hash
設(shè)計者認(rèn)為這方法很容易發(fā)生碰撞。為什么這么說呢？不妨思考一下，在n - 1為15(0x1111)時，其實散列真正生效的只是低4bit的有效位，當(dāng)然容易碰撞了。
因此，設(shè)計者想了一個顧全大局的方法(綜合考慮了速度、作用、質(zhì)量)，就是把高16bit和低16bit異或了一下。設(shè)計者還解釋到因為現(xiàn)在大多數(shù)的hashCode的分布已經(jīng)很不錯了，就算是發(fā)生了碰撞也用O(logn)的tree去做了。僅僅異或一下，既減少了系統(tǒng)的開銷，也不會造成的因為高位沒有參與下標(biāo)的計算(table長度比較小時)，從而引起的碰撞。
如果還是產(chǎn)生了頻繁的碰撞，會發(fā)生什么問題呢？作者注釋說，他們使用樹來處理頻繁的碰撞(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.
之前已經(jīng)提過，在獲取HashMap的元素時，基本分兩步：
首先根據(jù)hashCode()做hash，然后確定bucket的index；
如果bucket的節(jié)點的key不是我們需要的，則通過keys.equals()在鏈中找。 在Java 8之前的實現(xiàn)中是用鏈表解決沖突的，在產(chǎn)生碰撞的情況下，進(jìn)行g(shù)et時，兩步的時間復(fù)雜度是O(1)+O(n)。因此，當(dāng)碰撞很厲害的時候n很大，O(n)的速度顯然是影響速度的。
因此在Java 8中，利用紅黑樹替換鏈表，這樣復(fù)雜度就變成了O(1)+O(logn)了，這樣在n很大的時候，能夠比較理想的解決這個問題，在 ** Java 8：HashMap的性能提升**(http://www.importnew.com/14417.html)一文中有性能測試的結(jié)果。
resize的實現(xiàn)（非常有趣又重要的一節(jié)）
當(dāng)put時，如果發(fā)現(xiàn)目前的bucket占用程度已經(jīng)超過了Load Factor所希望的比例，那么就會發(fā)生resize。在resize的過程，簡單的說就是把bucket擴(kuò)充為2倍，之后重新計算index，把節(jié)點再放到新的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.
大致意思就是說，當(dāng)超過限制的時候會resize，然而又因為我們使用的是2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置。
怎么理解呢？例如我們從16擴(kuò)展為32時，具體的變化如下所示：
因此元素在重新計算 hash 之后，因為 n 變?yōu)?2 倍，那么 n-1 的 mask 范圍在高位多 1bit(紅色)，因此新的 index 就會發(fā)生這樣的變化：
因此，我們在擴(kuò)充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”?？梢钥纯聪聢D為16擴(kuò)充為32的resize示意圖：
這個設(shè)計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過程，均勻的把之前的沖突的節(jié)點分散到新的bucket了。
下面是代碼的具體實現(xiàn)：
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)?{
????????//?超過最大值就不再擴(kuò)充了，就只好隨你碰撞去吧
????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????threshold?=?Integer.MAX_VALUE;
????????????return?oldTab;
????????}
????????//?沒超過最大值，就擴(kuò)充為原來的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;
????({"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中的重中之重，都是前輩技術(shù)人員總結(jié)出的工作經(jīng)驗，必會基礎(chǔ)。
jdk1.7
在 jdk1.7 版本的時候采用的是 數(shù)組+鏈表 的形式，也就是采用了 拉鏈法。
Java 標(biāo)準(zhǔn)庫的 HashMap 基本上就是用 拉鏈法 實現(xiàn)的。 拉鏈法 的實現(xiàn)比較簡單，將鏈表和數(shù)組相結(jié)合。也就是說創(chuàng)建一個鏈表數(shù)組，數(shù)組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。
將哈希沖突值加入到每個數(shù)組的鏈表中，他的插入采用的是頭插法的形式(這種方法最大的弊端就是會使插入值產(chǎn)生環(huán)，從而無限循環(huán)，后面我們將詳細(xì)講解這種方法的弊端操作)，在進(jìn)行hash值計算的時候，jdk1.7則采用的是9次擾動(4次位運算+5次異或運算)的方式進(jìn)行處理（因為本人目前暫時用的jdk1.8所以無法利用源碼進(jìn)行講解，望見諒），除此之外在擴(kuò)容上也有所不同，在jdk1.7中采用的全部按照原來的方式進(jìn)行計算（即hashCode ->> 擾動函數(shù) ->> (h&length-1)），而在jdk1.8 中則采用按照擴(kuò)容后的規(guī)律計算（即擴(kuò)容后的位置=原位置 or 原位置 + 舊容量）。
關(guān)于頭插法的拓展：
1.?頭插法（頭是靠近數(shù)組的一端）
2.?JDK8以前是頭插法，JDK8后是尾插法
3.?為什么要從頭插法改成尾插法？
?A.因為頭插法會造成死鏈，
?B.JDK7用頭插是考慮到了一個所謂的熱點數(shù)據(jù)的點(新插入的數(shù)據(jù)可能會更早用到)，但這其實是個偽命題,因為JDK7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數(shù)組索引位置相同，則鏈表元素會倒置(就是因為頭插)?所以最后的結(jié)果?還是打亂了插入的順序?所以總的來看支撐JDK7使用頭插的這點原因也不足以支撐下去了?所以就干脆換成尾插?一舉多得。
你可以面試這樣回答（JavaPub本人經(jīng)供參考，更詳細(xì)閱讀下面的參考巨人）：hashmap用數(shù)組+鏈表。數(shù)組是固定長度，鏈表太長就需要擴(kuò)充數(shù)組長度進(jìn)行rehash減少鏈表長度。如果兩個線程同時觸發(fā)擴(kuò)容，在移動節(jié)點時會導(dǎo)致一個鏈表中的2個節(jié)點相互引用，從而生成環(huán)鏈表。
JavaPub參考巨人：https://blog.csdn.net/chenyiminnanjing/article/details/82706942
jdk1.8
jdk1.8 的版本則采用 數(shù)組+鏈表+紅黑樹 的方式，如下圖：
Java集合小抄是這樣描述的：
以Entry[]數(shù)組實現(xiàn)的哈希桶數(shù)組，用Key的哈希值取模桶數(shù)組的大小可得到數(shù)組下標(biāo)。
插入元素時，如果兩條Key落在同一個桶（比如哈希值1和17取模16后都屬于第一個哈希桶），我們稱之為哈希沖突。
JDK的做法是鏈表法，Entry用一個next屬性實現(xiàn)多個Entry以單向鏈表存放。查找哈希值為17的key時，先定位到哈希桶，然后鏈表遍歷桶里所有元素，逐個比較其Hash值然后key值。
在JDK8里，新增默認(rèn)為8的閾值，當(dāng)一個桶里的Entry超過閥值，就不以單向鏈表而以紅黑樹來存放以加快Key的查找速度。
當(dāng)然，最好還是桶里只有一個元素，不用去比較。所以默認(rèn)當(dāng)Entry數(shù)量達(dá)到桶數(shù)量的75%時，哈希沖突已比較嚴(yán)重，就會成倍擴(kuò)容桶數(shù)組，并重新分配所有原來的Entry。擴(kuò)容成本不低，所以也最好有個預(yù)估值。
取模用與操作（hash & （arrayLength-1））會比較快，所以數(shù)組的大小永遠(yuǎn)是2的N次方， 你隨便給一個初始值比如17會轉(zhuǎn)為32。默認(rèn)第一次放入元素時的初始值是16。
iterator（）時順著哈希桶數(shù)組來遍歷，看起來是個亂序
你知道HashMap工作原理嗎
通過 hash 的方法，通過 put 和 get 存儲和獲取對象。存儲對象時，我們將 K/V 傳給 put 方法時，它調(diào)用 hashCode 計算 hash 從而得到 bucket 位置，進(jìn)一步存儲，HashMap會根據(jù)當(dāng)前 bucket 的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)。獲取對象時，我們將K傳給 get，它調(diào)用 hashCode 計算 hash 從而得到bucket位置，并進(jìn)一步調(diào)用 equals() 方法確定鍵值對。如果發(fā)生碰撞的時候，Hashmap 通過鏈表將產(chǎn)生碰撞沖突的元素組織起來，在 Java 8 中，如果一個 bucket 中碰撞沖突的元素超過某個限制(默認(rèn)是8)，則使用紅黑樹來替換鏈表，從而提高速度。
JavaPub在寫HashMap參考巨人： https://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/ https://segmentfault.com/a/1190000023388339
7.說一下 HashSet 的實現(xiàn)原理？
HashSet 類是按照哈希算法（離散函數(shù)）來存儲集合中的元素，他當(dāng)中的元素是無序的，允許且最多一個元素為 null 。它是Set 的一個實現(xiàn)，所以沒有重復(fù)元素。
在 HashSet 類中實現(xiàn)了 Collection 接口中的所有方法
HashSet 是基于 HashMap 實現(xiàn)的，默認(rèn)構(gòu)造函數(shù)是構(gòu)建一個初始容量為16，負(fù)載因子為 0.75 的 HashMap。封裝了一個 HashMap 對象來存儲所有的集合元素，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態(tài)的 Oject 對象。
HashSet的其他操作都是基于HashMap的。
8.ArrayList 和 LinkedList 的區(qū)別是什么？
學(xué)過 Java 基礎(chǔ)的同學(xué)都能快速回答出，ArrayList 數(shù)組實現(xiàn)，所以查詢快；LinkedList 列表實現(xiàn)，所以增刪快。
為什么快？
掌握這個問題，才能更好的理解這個知識點。
數(shù)組
列表
那么為什么數(shù)組查詢就快了呢?因為假設(shè)數(shù)組里面保存的是一組對象,每個對象都有內(nèi)存大小,例如對象中有一個字段是int類型占用4個字節(jié)(只考慮實際數(shù)據(jù)占用的內(nèi)存),數(shù)組在堆上的內(nèi)存在數(shù)組被創(chuàng)建出來就被確定了是40個字節(jié).如果我們要查找第9個對象,可以通過(9-1)*4=32,從33到36字節(jié)就是我們要找的對象.是不是很快呢?而鏈表卻不能做到這樣的效率.如上圖,我們要找到A4,必須先找到A3,再先找到A2,再先找到A1.這樣的查找效率會大大降低.
好了,說了查找,再說說插入,數(shù)組的插入也相當(dāng)?shù)睦速M效率,如果要在數(shù)組內(nèi)的某一個位置進(jìn)行插入,需要先將插入位置的前面復(fù)制一份,然后在新的數(shù)組后面添加新的元素,最后將舊的數(shù)組后半部分添加的新的數(shù)組后面,而在鏈表中插入就變得相當(dāng)簡單了,比如我要在A3和A4中插入B,只需定位到A3的指針和A4的數(shù)據(jù)即可,將A3的指針指向B的值,將B的指針指向A4的值,B就插入進(jìn)了鏈表.
JavaPub 推薦關(guān)于 ArrayList 底層數(shù)組擴(kuò)容方法：https://javapub.blog.csdn.net/article/details/113686651
9.如何實現(xiàn)數(shù)組和 List 之間的轉(zhuǎn)換？
數(shù)組轉(zhuǎn) 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 轉(zhuǎn)數(shù)組，使用 List 的 toArray 方法。無參 toArray 方法返回 Object 數(shù)組，傳入初始化長度的數(shù)組對象，返回該對象數(shù)組。
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 的區(qū)別是什么？
線程安全：Vector 使用了 Synchronized 來實現(xiàn)線程同步，是線程安全的，而 ArrayList 是非線程安全的。
性能：ArrayList 在性能方面要優(yōu)于 Vector。
擴(kuò)容：ArrayList 和 Vector 都會根據(jù)實際的需要動態(tài)的調(diào)整容量，都采用線性連續(xù)存儲空。
只不過在 Vector 擴(kuò)容每次會增加 1 倍，而 ArrayList 只會增加 50%。
Vector 可以設(shè)置 capacityIncrement ，而 ArrayList 不可以，從字面理解就是 capacity 容量，Increment 增加，容量增長的參數(shù)。
11.Array 和 ArrayList 有何區(qū)別？
Array：它是數(shù)組，申明數(shù)組的時候就要初始化并確定長度，長度不可變，而且它只能存儲同一類型的數(shù)據(jù)，比如申明為 String 類型的數(shù)組，那么它只能存儲 String 類型數(shù)據(jù)
ArrayList：它是一個集合，需要先申明，然后再添加數(shù)據(jù)，長度是根據(jù)內(nèi)容的多少而改變的， ArrayList 可以存放不同類型的數(shù)據(jù)，在存儲基本類型數(shù)據(jù)的時候要使用基本數(shù)據(jù)類型的包裝類
當(dāng)能確定長度并且數(shù)據(jù)類型一致的時候就可以用數(shù)組，其他時候使用 ArrayList。
12.在 Queue 中 poll()和 remove()有什么區(qū)別？
隊列（Queue） 是一種特殊的線性表，它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作。
????/**
?????*?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，實現(xiàn) List 接口，與 ArrayList 相比幾乎相同，但是是線程安全的。底層是數(shù)組。
Stack，繼承 Vector 類，先進(jìn)后出。
HashTable，實現(xiàn) Map 接口，與 HashMap 幾乎完全相同，但是是線程安全的。
java.util.concurrent包下的所有集合類，例如：ConcurrentHashMap。（ConcurrentLinkedQueue、ConcurrentLinkedDueue 等）
拓展：java.util.concurrent包下的集合類如何保證線程安全
JavaPub參考巨人：https://www.cnblogs.com/junjiang3/p/8686290.html
14.迭代器 Iterator 是什么？
標(biāo)準(zhǔn)答案：
迭代器是一種設(shè)計模式，它是一個對象，它可以遍歷并選擇序列中的對象，而開發(fā)人員不需要了解該序列的底層結(jié)構(gòu)。迭代器通常被稱為“輕量級”對象，因為創(chuàng)建它的代價小。迭代器設(shè)計模式案例演示、講解，wx訂閱：JavaPub
簡單來說，迭代器是用于順序訪問集合對象的元素，無需知道集合對象的底層實現(xiàn)。Iterator 是可以遍歷集合的對象，為各種容器提供了公共的操作接口，隔離對容器的遍歷操作和底層實現(xiàn)，從而解耦。
Java中的Iterator功能比較簡單，并且只能單向移動：
使用方法iterator()要求容器返回一個Iterator。第一次調(diào)用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
恭喜你看到了最后，這篇文章整理用了四天時間。再看和轉(zhuǎn)發(fā)是對我最大的鼓勵，我的pub哥，歡迎關(guān)注JavaPub。
