1. 為什么會出現(xiàn)集合
數(shù)組的長度是固定的，當(dāng)添加的元素超過了數(shù)組的長度時需要對數(shù)組重新定義，而集合能存儲任意對象，長度是可以改變的，隨著元素的增加而增加，隨元素的減少而減少。
2.數(shù)組和集合的區(qū)別
區(qū)別1 :
數(shù)組既可以存儲基本數(shù)據(jù)類型,又可以存儲引用數(shù)據(jù)類型,基本數(shù)據(jù)類型存儲的是值,引用數(shù)據(jù)類型存儲的是地址值。
集合能存儲引用數(shù)據(jù)類型(對象)集合中也可以存儲基本數(shù)據(jù)類型,但是在存儲的時候會自動裝箱變成對象。
區(qū)別2:
數(shù)組長度是固定的,不能自動增長。
集合的長度的是可變的,可以根據(jù)元素的增加而增長。
數(shù)組和集合什么時候用？
1.如果元素個數(shù)是固定的推薦用數(shù)組。
2.如果元素個數(shù)不是固定的推薦用集合
1. Collection 單列集合
Collection 作為單列集合的根接口，子接口List 和 Set 接口均繼承父類 Collection 接口。
2. List 集合接口下的子類
在List接口下，我們常用的子類有三個，分別是ArrayList、LinkedList 和 Vector，List 集合中元素是有序的，存和取的順序一致，有索引，可以存儲重復(fù)元素。
2.1 ArrayList（優(yōu)先考慮）
ArrayList基于數(shù)組實(shí)現(xiàn)，可以通過下標(biāo)索引直接查找到指定位置的元素，因此查找效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。
線程不安全，效率高。
2.2 Vector（JDK 1.0出現(xiàn)，線程安全）
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快，增刪慢。
線程安全，效率低。
Vector相對ArrayList查詢慢(線程安全的)。
Vector相對LinkedList增刪慢(數(shù)組結(jié)構(gòu))。
2.3 LinkedList
底層數(shù)據(jù)結(jié)構(gòu)是鏈表，查詢慢，增刪快。
線程不安全，效率高。
2.4 Vector和 ArrayList 的區(qū)別
Vector是線程安全的,效率低。
ArrayList是線程不安全的,效率高。
共同點(diǎn):都是數(shù)組實(shí)現(xiàn)的。
2.5 ArrayList和LinkedList的區(qū)別（常見面試題）
ArrayList底層是數(shù)組結(jié)構(gòu),查詢和修改快，時間復(fù)雜度為1。
LinkedList底層是鏈表結(jié)構(gòu)的,增和刪比較快,查詢和修改比較慢，時間復(fù)雜度為n。
共同點(diǎn):都是線程不安全的。
3. ArrayList集合的四種遍歷方法
ArrayList的遍歷方法可以總結(jié)為以下四種形式，分別是迭代器迭代實(shí)現(xiàn)、增強(qiáng)for循環(huán)實(shí)現(xiàn)、通過索引實(shí)現(xiàn)、通過集合轉(zhuǎn)換為數(shù)組進(jìn)行遍歷數(shù)組實(shí)現(xiàn)。顯然，我們在開發(fā)中優(yōu)先采用的是前兩種遍歷方式來實(shí)現(xiàn)。
public static void arrayList() {
ArrayList<String> list = new ArrayList<>();
list.add( "a" );
list.add( "b" );
list.add( "a" );
list.add( "d" );
list.add( "e" );
//迭代器迭代（推薦）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String values = it.next();
System.out.println( values );
}
System.out.println( "=====================" );
//增強(qiáng)for循環(huán)（推薦）
for (String string : list) {
System.out.println( string );
}
System.out.println( "=====================" );
//通過索引遍歷
for (int i = 0; i < list.size(); i++) {
System.out.println( list.get( i ) );
}
System.out.println( "=====================" );
//將集合轉(zhuǎn)換為數(shù)組進(jìn)行遍歷
Object[] strings = list.toArray();
for (Object string : strings) {
System.out.println( string );
}
}4. Set集合接口下的子類
Set 接口下的兩個常用子類是 HashSet（無序存儲，底層哈希算法實(shí)現(xiàn)）、 TreeSet（有序存儲，底層二叉樹算法實(shí)現(xiàn)）和 LInkedHashSet 集合。
Set 接口與 List 接口最大的區(qū)別就是 Set 接口的內(nèi)容不允許重復(fù)元素的存和取是無序的，及存和取的順序不一致，沒有索引的存在，也不可以存儲重復(fù)的元素。
4.1 HashSet 原理（如何保證元素的唯一性）
使用 Set 集合都是需要去掉重復(fù)元素的，如果在存儲的時候逐個 equals() 比較，效率肯定很低，哈希算法提高了去重的效率，進(jìn)而降低了使用 equals() 方法的次數(shù)。
當(dāng) HashSet 調(diào)用 add() 方法存儲對象的時候，先調(diào)用對象的 hashCode() 得到一個哈希值，然后在集合中查找是否有哈希值相同的對象：
如果沒有哈希值相同的對象就直接存入到集合當(dāng)中；
如果有哈希值相同的對象，就和哈希值相同的對象逐個進(jìn)行equals() 比較，比較結(jié)果為false就存入，true則不存。
對于LinkedHashSet 是HashSet 的子類，底層是鏈表實(shí)現(xiàn)，也可以保證元素的唯一性，和HashSet 原理一樣。
4.2 自定義類的對象存儲到 HashSet 去重復(fù)
類中必須重寫hashCode() 和equals() 方法。
當(dāng) hashcode 值相同時，才會調(diào)用 equals() 方法。
對于兩個對象相同而言，必須 hashCode() 和equals() 方法的返回值都相同才能判斷為相同，二者缺一不可。
4.3 TreeSet有序存儲
底層是二叉樹算法實(shí)現(xiàn)，一般在開發(fā)中不需要對存儲的元素進(jìn)行排序，所以在開發(fā)的時候大多用HashSet ，并且HashSet 的效率比較高，推薦使用。
TreeSet 是用來排序的，可以指定一個順序，對象存入之后會按照指定的順序排序。
使用方式：
<1>自然順序（Comparable）
TreeSet 類的add() 方法中會把存入的對象提升為Compara 類型；
調(diào)用對象的comparaTo() 方法和集合中的對象進(jìn)行比較；
根據(jù)comparaTo() 方法的返回的結(jié)果進(jìn)行存儲，返回0，集合中只有一個元素；返回正數(shù)，集合怎么存就怎么?。环祷刎?fù)數(shù)，集合倒序存儲。
<2>比較器順序(Comparator)
創(chuàng)建TreeSet 的時候可以制定一個Comparator；
如果傳入了Comparator 的子類對象，那么TreeSet 就會按照比較器中的順序排序；
add() 方法內(nèi)部會自動調(diào)用Comparator 接口中的compare() 方法排序。
<3>兩種方式的區(qū)別
TreeSet構(gòu)造函數(shù)什么都不傳，默認(rèn)按照類中Comparable 的順序（沒有就報錯ClassCastExcep）；
TreeSet 傳入Comparator ，就優(yōu)先按照Comparator 接口中的compare() 方法排序。
舉例：比較器比較代碼實(shí)現(xiàn)
public static void intSort() {
/*
* 程序啟動后可以從鍵盤輸入多個整數(shù)，直到輸入quit結(jié)束，把所有輸入的整數(shù)倒序打印出來
* */
//1.創(chuàng)建Scanner對象，鍵盤錄入
Scanner sc = new Scanner( System.in );
System.out.println( "請輸入整數(shù)：" );
//2.創(chuàng)建TreeSet集合對象，傳入比較器
TreeSet<Integer> treeSet = new TreeSet<>( new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
//int num = i2 - i1; //自動拆箱
int num = i2.compareTo( i1 );
return num == 0 ? 1 : num;
}
} );
//以字符串的形式無限循環(huán)接收整數(shù)，直到輸入quit退出
while (true) {
String line = sc.nextLine();
if ("quit".equals( line )) {
break;
}
//4.判斷是quit就退出，不是將其轉(zhuǎn)換為Integer，并添加到集合
Inreger i = Integer.parseInt( line );
treeSet.add( i );
}
//5.遍歷集合并打印
for (Integer integer : treeSet) {
System.out.println(integer);
}
}4.4 LinkedHashSet集合
對于 LinkedHashSet 而言，繼承于HashSet ，又基于 LinkedHashMap來實(shí)現(xiàn)的。底層使用 LinkedHashMap 來存儲所有的元素，并用雙向鏈表記錄插入順序，其所有的方法操作上與HashSet 相同，因此LinkedHashSet 的實(shí)現(xiàn)非常簡單，在此不多贅述。
5. HashSet 與 TreeSet 集合的兩種遍歷方法
HashSet 與 TreeSet 集合的兩種遍歷方式都是通過迭代器迭代遍歷和通過增強(qiáng)for 循環(huán)遍歷，兩種方式均推薦使用，TreeSet遍歷方式與之類似，在此不再展示。
//HashSet遍歷方法
public static void hashSet() {
HashSet<String> hashSet = new HashSet<>();
hashSet.add( "a" );
hashSet.add( "b" );
hashSet.add( "i" );
hashSet.add( "g" );
//通過迭代器迭代
Iterator<String> it = hashSet.iterator();
while (it.hasNext()) {
System.out.println( it.next() );
}
//通過增強(qiáng)for循環(huán)遍歷
for (String values : hashSet) {
System.out.println( values );
}
}6. Map雙列集合下的子類
Map接口下常用的子類有HashMap 、TreeMap 、Hashtable 和 ConcurrentHashMap 實(shí)現(xiàn)類，Map集合可以存儲一對對象，即會一次性保存兩個對象，存在key = value 結(jié)構(gòu)，其最大的特點(diǎn)還是可以通過key 找到對應(yīng)的value 值。
6.1 HashMap 原理（常用）
HashMap根據(jù)鍵的hashCode值存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值，因而具有很快的訪問速度，但遍歷順序卻是不確定的。
HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null。
HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致。如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。我們用下面這張圖來介紹 HashMap 的結(jié)構(gòu)。（圖片來源于網(wǎng)絡(luò)）
大方向上，HashMap 里面是一個數(shù)組，然后數(shù)組中每個元素是一個單向鏈表。上圖中，每個綠色的實(shí)體是嵌套類 Entry 的實(shí)例，Entry 包含四個屬性：key, value, hash 值和用于單向鏈表的 next。
capacity：當(dāng)前數(shù)組容量，始終保持 2^n，可以擴(kuò)容，擴(kuò)容后數(shù)組大小為當(dāng)前的 2 倍。
loadFactor：負(fù)載因子，默認(rèn)為 0.75。
threshold：擴(kuò)容的閾值，等于 capacity * loadFactor
Java8 對 HashMap 進(jìn)行了一些修改，最大的不同就是利用了紅黑樹，所以其由 數(shù)組+鏈表+紅黑樹 組成。 根據(jù) Java7 HashMap 的介紹，我們知道，查找的時候，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo)，但是之后的話，需要順著鏈表一個個比較下去才能找到我們需要的，時間復(fù)雜度取決于鏈表的長度，為 O(n)。 為了降低這部分的開銷，在 Java8 中，當(dāng)鏈表中的元素超過了 8 個以后，會將鏈表轉(zhuǎn)換為紅黑樹，在這些位置進(jìn)行查找的時候可以降低時間復(fù)雜度為 O(logN)。
6.2 TreeMap
TreeMap實(shí)現(xiàn)SortedMap接口，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器，當(dāng)用Iterator遍歷TreeMap時，得到的結(jié)果是排過序的。
如果使用排序的映射，建議使用TreeMap。
在使用TreeMap時，key必須實(shí)現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator，否則會在運(yùn)行時拋出java.lang.ClassCastException類型的異常。
6.3 Hashtable
Hashtable 在JDK 1.0出現(xiàn)，猶如Vector ,很多映射的常用功能與HashMap類似，不同的是它繼承自Dictionary類，并且是線程安全的，任一時間只有一個線程能寫Hashtable，并發(fā)性不如ConcurrentHashMap，因?yàn)镃oncurrentHashMap引入了分段鎖。
Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換，需要線程安全的場合可以用ConcurrentHashMap替換。
Hashtable 的鍵和值都不允許有null 值。
6.4ConcurrentHashMap
ConcurrentHashMap 和 HashMap 思路是差不多的，但是因?yàn)樗С植l(fā)操作，所以要復(fù)雜一些。簡單理解就是，ConcurrentHashMap 是一個 Segment 數(shù)組，它的內(nèi)部細(xì)分了若干個小的 HashMap ，我們稱之為段Segment，Segment 通過繼承 ReentrantLock 來進(jìn)行加鎖，所以每次需要加鎖的操作鎖住的是一個 Segment，這樣只要保證每個 Segment 是線程安全的，也就實(shí)現(xiàn)了全局的線程安全。
Segment 的大小也被稱為ConcurrentHashMap 的并發(fā)度，默認(rèn)情況下一個ConcurrentHashMap被進(jìn)一步細(xì)分為16個段，既就是鎖的并發(fā)度。
ConcurrentHashMap 的并發(fā)處理其實(shí)采用的技術(shù)是減少鎖粒度?？s小鎖定對象的范圍，從而減小鎖沖突的可能性，進(jìn)而提高系統(tǒng)的并發(fā)能力。
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment是一種可重入鎖ReentrantLock，在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵值對數(shù)據(jù)。一個ConcurrentHashMap里包含一個Segment數(shù)組，Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)， 一個Segment里包含一個HashEntry數(shù)組，每個HashEntry是一個鏈表結(jié)構(gòu)的元素， 每個Segment守護(hù)一個HashEntry數(shù)組里的元素,當(dāng)對HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時，必須首先獲得它對應(yīng)的Segment鎖。
6.5 LinkedHashMap
LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的，也可以在構(gòu)造時帶參數(shù)，按照訪問次序排序。
7. HashMap 集合的四種遍歷方法
Map集合子類的遍歷方法基本類似，這里就只展示HashMap 集合的遍歷方法，其他可參考以下代碼實(shí)現(xiàn)遍歷。
//HashMap遍歷方法
public static void hashMap() {
Map<Integer, String> map = new HashMap<>();
map.put( 0, "q" );
map.put( 1, "a" );
map.put( 2, "b" );
map.put( 5, "t" );
map.put( 3, "k" );
//根據(jù)鍵獲取值（第一種）
Set<Integer> keyset = map.keySet(); //獲取所有鍵的值
//獲取迭代器
Iterator<Integer> it = keyset.iterator();
while (it.hasNext()) {
Integer key = it.next(); //獲取每一個鍵
String value = map.get( key ); //根據(jù)鍵獲取值
System.out.println( key + " " + value );
}
//增強(qiáng)for循環(huán)遍歷（第二種）
for (Integer key : keyset) {
System.out.println( key + " " + map.get( key ) );
}
//根據(jù)鍵值對對象獲取鍵和值
//Map.Entry說明 Entry是 Map的內(nèi)部接口，將鍵和值封裝成了 Entry對象，并存儲到 Set集合中
Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
//迭代器遍歷（第三種）
Iterator<Map.Entry<Integer, String>> iterator = entrySet.iterator();
while (it.hasNext()) {
//獲取每一個Entry對象
Map.Entry<Integer, String> entry = iterator.next(); //父類引用指向子類對象
Integer key = entry.getKey(); //根據(jù)鍵值對對象獲取鍵
String values = entry.getValue(); //根據(jù)鍵值對對象獲取值
System.out.println( key + "" + values );
}
//增強(qiáng)for循環(huán)遍歷（第四種）
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println( entry.getKey() + " " + entry.getValue() );
}
}8. Map集合的常見面試題
8.1 HashMap 和 Hashtable 的區(qū)別是什么？
<1>HashMap 由JDK 1.2 版本出現(xiàn)，基于Dictionary 類，基本取代了JDK 1.0 版本出現(xiàn)的基于AbstractMap 類的Hashtable 。
<2>Hashtable 的方法是同步的，性能較低；HashMap未經(jīng)同步，性能高，所以在多線程下要手動同步HashMap，類似于Vector 和 ArrayList 一樣。
<3>HashMap 是線程不安全的，Hashtable 是線程安全的，底層源碼在對應(yīng)的方法上添加了synchronized 關(guān)鍵字進(jìn)行修飾，由于在執(zhí)行方法的時候需要獲得對象鎖，則執(zhí)行起來比較慢，為保證線程安全就選用ConcurrentHashMap。
<4>HashMap 允許key 和 value 存放null 值，Hashtable key 和 value 均不可存放null 值，否則出現(xiàn)NullPointerException。
<5>哈希值的使用不同。 Hashtable 直接使用對象的hashcode；而HashMap 重新計算hash值，而且用于代替求模。
<7>HashMap 中的hash數(shù)組的默認(rèn)大小是 16，而且一定是2 的指數(shù)；Hashtable 中的hash 數(shù)組默認(rèn)大小是 11，增加的方式是 old * 2 + 1。
8.2 HashMap 中的key 可以是任何對象或數(shù)據(jù)類型嗎？
<1>可以為null ，但不能是可變對象，如果是可變對象的話，對象中的屬性改變，則對象hashcode 也進(jìn)行相應(yīng)的改變，導(dǎo)致下次無法查找到已存在Map 中的數(shù)據(jù)。
<2>如果可變對象被用作鍵，那就要小心在改變對象狀態(tài)的時候，不要改變它的哈希值了。我們只需保證成員變量的改變能保證該對象的哈希值不變即可。
8.3 請解釋 HashMap 和 ConcurrentHashMap 的區(qū)別？
<1>HashMap 是非線程安全的， ConcurrentHashMap是線程安全的。
<2>ConcurrentHashMap 將整個Hash 桶進(jìn)行了分段 segment，也就是將這個大的數(shù)組分成了幾個小的片段segment，而且每個小的片段上都有鎖的存在，所以在插入元素的時候需要先找到應(yīng)該插入到哪一個片段，然后再向這個片段進(jìn)行插入，同時還要獲取到segment鎖才能進(jìn)行插入。
8.4 ConcurrentHashMap 是線程安全的嗎？如何保證線程安全？
<1>Hashtable 集合在競爭激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因是所有訪問Hashtable 的線程都必須競爭同一把鎖。假如容器中里有多把鎖，每把鎖用于鎖集合中的一部分?jǐn)?shù)據(jù)，當(dāng)多線程訪問集合中不同數(shù)據(jù)段的數(shù)據(jù)時，就不會出現(xiàn)鎖競爭，這樣就可以提高并訪問效率，這就是ConcurrentHashMap 所采用的鎖分段技術(shù)。首先將數(shù)據(jù)分成一段一段的存儲，然后在每段數(shù)據(jù)處都配一把鎖，當(dāng)一個線程占用鎖并訪問其中一段數(shù)據(jù)時，其他段的數(shù)據(jù)不受影響，可以被其他線程正常訪問到。
<2>put 方法首先定位到Segment，然后在Segment 里進(jìn)行插入。插入操作時先要判斷是否需要對Segment 里的HashEntry 數(shù)組進(jìn)行擴(kuò)容，其次定位添加元素的位置，然后放在HashEntry 數(shù)組里。
<3>如果需要在ConcurrentHashMap中添加一個新的表項(xiàng)，并不是將整個HashMap加鎖，而是首先根據(jù)hashcode得到該表項(xiàng)應(yīng)該存放在哪個段中，然后對該段加鎖，并完成put操作。在多線程環(huán)境中，如果多個線程同時進(jìn)行put操作，只要被加入的表項(xiàng)不存放在同一個段中，則線程間可以做到真正的并行。
————————————————
版權(quán)聲明：本文為CSDN博主「SolarL」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/SolarL/article/details/88081301
