1.List

1.1 Arraylist 與 LinkedList 區(qū)別

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

1.2 List中的迭代器

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

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

1.3 ArrayList的擴(kuò)容機(jī)制

詳見:

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

Map

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

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

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

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

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

2.2 HashMap長(zhǎng)度為什么是2的冪次方

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

2.3 HashMap線程不安全問題

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

詳情參見：

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

2.4 HashMap的其他資料

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

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

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

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

JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實(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.實(shí)現(xiàn)線程安全的方式:

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

Set

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

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

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

需要請(qǐng)關(guān)注和轉(zhuǎn)發(fā)我的文章

然后私信我獲取哦！

記得回復(fù)“學(xué)習(xí)”！！！！

我是小架，我們

下篇見！！！