1.List

1.1 Arraylist 與 LinkedList 區別

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

1.2 List中的迭代器

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

注意:
一般list中迭代器不能使用此種方法移除元素,會觸發 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底層實現

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

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

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

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

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

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

2.3 HashMap線程不安全問題

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

詳情參見：

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

2.4 HashMap的其他資料

更詳細的資料, 請參見:

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

2.5 ConcurrentHashMap的基本結構

1.底層數據結構:

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

2.實現線程安全的方式:

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

Set

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

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

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