1.List

1.1 Arraylist 與 LinkedList 區(qū)別

是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是 Object 數(shù)組；LinkedList 底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)
插入和刪除是否受元素位置的影響： ① ArrayList 采用數(shù)組存儲，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響。比如：執(zhí)行add(E e)方法的時候， ArrayList 會默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時間復(fù)雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間復(fù)雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作。 ② LinkedList 采用鏈表存儲，所以插入，刪除元素時間復(fù)雜度不受元素位置的影響，都是近似O（1）而數(shù)組為近似O（n）。
是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)。
內(nèi)存空間占用： ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾會預(yù)留一定的容量空間，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）。
注意:
ArrayList遍歷時使用普通for循環(huán)較快.
LinkedList遍歷時使用迭代器較快.

1.2 List中的迭代器

for(Object obj : list){
 list.remove(obj) 
}

注意:
一般list中迭代器不能使用此種方法移除元素,會觸發(fā) ConcurrentModifyException,如果要刪除可以使用Iterator.remove()
此處如果切換成CopyOnWriteArrayList則可以正常刪除

1.3 ArrayList的擴容機制

詳見:

https://github.com/Snailclimb/JAVAGuide/blob/master/docs/java/collection/ArrayList-Grow.md

Map

2.1 Java1.8底層實現(xiàn)

底層=數(shù)組+鏈表(大小超過8,轉(zhuǎn)換為紅黑樹)

HashMap 通過 key 的 hashCode 經(jīng)過擾動函數(shù)處理過后得到 hash 值，然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長度），如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鏈法解決沖突。

所謂擾動函數(shù)指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動函數(shù)是為了防止一些實現(xiàn)比較差的 hashCode() 方法,換句話說使用擾動函數(shù)之后可以減少碰撞。

 //hash方法
 static final int hash(Object key) {
 int h;
 // key.hashCode()：返回散列值也就是hashcode
 // ^ ：按位異或
 // >>>:無符號右移，忽略符號位，空位都以0補齊
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //擾動函數(shù)進行處理
 }

2.2 HashMap長度為什么是2的冪次方

一般用hash對map的長度取模使用,當(dāng)且僅當(dāng)length是2的冪次方時,hash%length==hash&(length-1)成立,這樣的話位與比取模%運算要更快

2.3 HashMap線程不安全問題

HashMap不是線程安全的類,兩個線程同時去put可能引起數(shù)據(jù)不一致,在1.7以前還存在閉鏈問題,1.8以后解決了這個問題,并發(fā)環(huán)境下建議使用ConcurrentHashMap;

詳情參見：

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

2.4 HashMap的其他資料

更詳細(xì)的資料, 請參見:

https://zhuanlan.zhihu.com/p/21673805

2.5 ConcurrentHashMap的基本結(jié)構(gòu)

1.底層數(shù)據(jù)結(jié)構(gòu):

JDK1.7的 ConcurrentHashMap 底層采用分段的數(shù)組+鏈表實現(xiàn)，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8的結(jié)構(gòu)一樣，數(shù)組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用數(shù)組+鏈表的形式，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的；

2.實現(xiàn)線程安全的方式:

① 在JDK1.7的時候，ConcurrentHashMap（分段鎖）對整個桶數(shù)組進行了分割分段(Segment)，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會存在鎖競爭，提高并發(fā)訪問率。到了 JDK1.8 的時候已經(jīng)摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，并發(fā)控制使用 synchronized 和 CAS 來操作。（JDK1.6以后對 synchronized鎖做了很多優(yōu)化）整個看起來就像是優(yōu)化過且線程安全的 HashMap，雖然在JDK1.8中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡化了屬性，只是為了兼容舊版本；synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點，這樣只要hash不沖突，就不會產(chǎn)生并發(fā)，效率又提升N倍。

Set

當(dāng)你把對象加入HashSet時，HashSet會先計算對象的hashcode值來判斷對象加入的位置，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode，HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)。但是如果發(fā)現(xiàn)有相同hashcode值的對象，這時會調(diào)用equals（）方法來檢查hashcode相等的對象是否真的相同。如果兩者相同，HashSet就不會讓加入操作成功。

最后，感謝你讀到了這里。

我最近又整合更新了一些資料，在這里分享給大家！