HashMap

簡單說下HashMap的實現(xiàn)原理：
首先有一個每個元素都是鏈表（可能表述不準確）的數(shù)組烘苹，當添加一個元素（key-value）時宴霸，就首先計算元素key的hash值拌倍，以此確定插入數(shù)組中的位置勋又，但是可能存在同一hash值的元素已經(jīng)被放在數(shù)組同一位置了裸删，這時就添加到同一hash值的元素的后面八拱，他們在數(shù)組的同一位置，但是形成了鏈表涯塔，同一各鏈表上的Hash值是相同的肌稻，所以說數(shù)組存放的是鏈表。而當鏈表長度太長時伤塌，鏈表就轉(zhuǎn)換為紅黑樹灯萍，這樣大大提高了查找的效率。
當鏈表數(shù)組的容量超過初始容量的0.75時每聪，再散列將鏈表數(shù)組擴大2倍旦棉，把原鏈表數(shù)組的搬移到新的數(shù)組中齿风。

//初始table長度16
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75F;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient HashMap.Node<K, V>[] table;
transient Set<Entry<K, V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

JDK1.8 的優(yōu)化

1. 紅黑樹

JDK1.8之前，HashMap采用位桶+鏈表實現(xiàn)绑洛，即使用鏈表處理沖突救斑，同一hash值的鏈表都存儲在一個鏈表里。但是當位于一個桶中的元素較多真屯，即hash值相等的元素較多時脸候，通過key值依次查找的效率較低。

JDK1.8中绑蔫，HashMap采用位桶+鏈表+紅黑樹實現(xiàn)运沦，超過閾值時，將鏈表轉(zhuǎn)換為紅黑樹配深，這樣大大減少了查找時間携添。
單向鏈表->紅黑樹：table長度>=64 且 bucket里鏈表長度>=8
紅黑樹->單向鏈表：bucket里鏈表長度<=6

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

2. 尾插法

根據(jù)對沖突的處理方式不同，哈希表有兩種實現(xiàn)方式篓叶，一種開放地址方式(Open addressing)烈掠，另一種是沖突鏈表方式(Separate chaining with linked lists)。
Java HashMap采用的是沖突鏈表方式/拉鏈法缸托。

• 1.8 之前用頭插法左敌，在沖突鏈表頭部插入新的entry。
• 1.8 開始用尾插法

hash值

1. hash值的計算

Object：本地方法俐镐，返回引用地址對應(yīng)的編碼

byte(8位)
int(16位) 值
short(32位) 值
long(64位) value^(value>>32) 高32位與低32位異或
float(32位) int floatToIntBits(value)
double(64位) value^(value>>32) 高32位與低32位異或
char,String 如jack：jn^3 + an^2 + cn^1 + kn^0, n = 31 ( 31*i+i = (i << 5) - i)

String 類型是如何重寫 hashCode 方法的呢矫限？

我們看看代碼：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

代碼非常簡單，就是使用 String 的 char 數(shù)組的數(shù)字每次乘以 31 再疊加最后返回京革，因此奇唤，每個不同的字符串，返回的 hashCode 肯定不一樣匹摇。上面提到Arrays.hashCode方法也是乘以 31 再疊加咬扇，那么為什么使用 31 呢？

在名著 《Effective Java》第 42 頁就有對 hashCode 為什么采用 31 做了說明：

之所以使用 31廊勃， 是因為他是一個奇素數(shù)懈贺。

• 奇數(shù)：如果乘數(shù)是偶數(shù)，并且乘法溢出的話坡垫，信息就會丟失梭灿，因為與2相乘等價于移位運算（低位補0）。
• 素數(shù)：使用素數(shù)的好處并不很明顯冰悠，但是習慣上使用素數(shù)來計算散列結(jié)果堡妒。
• 位運算：31 有個很好的性能，即用移位和減法來代替乘法溉卓，可以得到更好的性能： 31 * i == (i << 5）- i皮迟， 現(xiàn)代的 VM 可以自動完成這種優(yōu)化搬泥。

參考鏈接：hashCode 為什么乘以 31？深入理解 hashCode 和 hash 算法

2. hash值的進一步處理：擾動計算

高16位與低16位的異或運算：
hash = hash ^ (hash>>> 16)

因為hashcode的計算方法導致哈希值的差異主要在高位伏尼，而 (n - 1) & hash是忽略了容量以上的高位的忿檩，使用擾動函數(shù)就是為了增加隨機性，讓數(shù)據(jù)元素更加均衡的散列爆阶，減少碰撞燥透。

計算index（在數(shù)組哪個位置）

index = hash & (n - 1)
前提是table長度n是2的冪，因為當 n 為 2次冪時辨图，hash & (n - 1) == hash % n 班套，%是取余即取模運算。

擴容

負載因子(loadFactor) = key-value鍵值對entry的總數(shù)量（不是不同的hash值）/table.length
loadFactor > 0.75 : table擴容為原來2倍

我們自定義 HashMap 容量最好是多少故河？
那我們?nèi)绾巫远x呢孽尽？自從有了阿里的規(guī)約插件，每次樓主都要初始化容量忧勿，如果我們預(yù)計我們的散列表中有2個數(shù)據(jù)，那么我就初始化容量為2嗎瞻讽？
絕對不行鸳吸，如果大家看過源碼就會發(fā)現(xiàn)，如果Map中已有數(shù)據(jù)的容量達到了初始容量的 75%速勇，那么散列表就會擴容晌砾，而擴容將會重新將所有的數(shù)據(jù)重新散列，性能損失嚴重烦磁，所以养匈，我們可以必須要大于我們預(yù)計數(shù)據(jù)量的 1.34 倍，如果是2個數(shù)據(jù)的話都伪，就需要初始化 2.68 個容量呕乎。當然這是開玩笑的，2.68 不可以陨晶，3 可不可以呢猬仁？肯定也是不可以的，我前面說了先誉，如果不是2的冪次方湿刽，散列結(jié)果將會大大下降。導致出現(xiàn)大量鏈表褐耳。那么我可以將初始化容量設(shè)置為4诈闺。 當然了，如果你預(yù)計大概會插入 12 條數(shù)據(jù)的話铃芦，那么初始容量為16簡直是完美雅镊，一點不浪費襟雷，而且也不會擴容。

遷移

if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
}
else {
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

HashMap的數(shù)組長度一定保持2的次冪漓穿，比如16的二進制表示為 10000嗤军，那么length-1就是15，二進制為01111晃危，同理擴容后的數(shù)組長度為32叙赚，二進制表示為100000，length-1為31僚饭，二進制表示為011111震叮。從下圖可以我們也能看到這樣會保證低位全為1，而擴容后只有一位差異鳍鸵，也就是多出了最左位的1苇瓣，這樣在通過 h&(length-1)的時候，只要h對應(yīng)的最左邊的那一個差異位為0偿乖，就能保證得到的新的數(shù)組索引和老數(shù)組索引一致(大大減少了之前已經(jīng)散列良好的老數(shù)組的數(shù)據(jù)位置重新調(diào)換)击罪，這也是為啥數(shù)組長度必須是2的冪次原因之一。

image.png

參考鏈接：HashMap擴容時數(shù)據(jù)遷移實現(xiàn)的亮點（ConcurrentHashMap類似）

參考鏈接：

• https://blog.csdn.net/weixin_37356262/article/details/80543218
• http://www.reibang.com/p/5ddf1b664641

LinkedHashMap

LinkedHashMap是HashMap的直接子類贪薪。
區(qū)別：
LinkedHashMap在HashMap的基礎(chǔ)上媳禁，采用雙向鏈表(doubly-linked list)的形式將所有entry連接起來，順序為插入順序或者最近最少使用（LRU）順序画切。

注意竣稽，每個hash對應(yīng)的bucket里是單向鏈表。

除了可以保迭代歷順序霍弹，這種結(jié)構(gòu)還有一個好處 : 迭代LinkedHashMap時不需要像HashMap那樣遍歷整個table毫别，而只需要直接遍歷header指向的雙向鏈表即可，也就是說LinkedHashMap的迭代時間就只跟entry的個數(shù)相關(guān)典格，而跟table的大小無關(guān)岛宦。

HashMap，HashTable钝计，ConcurrentHashMap的區(qū)別恋博。

HashTable與HashMap、ConcurrentHashMap主要的區(qū)別在于HashMap不是同步的私恬、線程不安全的和不適合應(yīng)用于多線程并發(fā)環(huán)境下债沮，而ConcurrentHashMap是線程安全的集合容器，特別是在多線程和并發(fā)環(huán)境中本鸣，通常作為Map的主要實現(xiàn)疫衩。
HashMap 的迭代器是 fail-fast 迭代器。

連接：https://www.cnblogs.com/heyonggang/p/9112731.html

HashMap在高并發(fā)下如果沒有處理線程安全會有怎樣的安全隱患号杠，具體表現(xiàn)是什么

1. 并發(fā)下的Rehash 會造成元素之間會形成?個循環(huán)鏈表。不過丰歌，jdk 1.8 后解決了這個問題姨蟋，但是還是不建議在多線程下使? HashMap,因為多線程下使? HashMap 還是會存在其他問題?如數(shù)據(jù)丟失。并發(fā)環(huán)境下推薦使? ConcurrentHashMap 立帖。

2. 多線程put時可能導致元素丟失眼溶，原因：當多個線程同時執(zhí)行addEntry(hash,key ,value,i)時，如果產(chǎn)生哈希碰撞晓勇，導致兩個線程得到同樣的bucketIndex去存儲堂飞，就可能會發(fā)生元素覆蓋丟失的情況。

鏈接：

• https://juejin.cn/post/6844903606148136968
• 疫苗：JAVA HASHMAP的死循環(huán)

HashSet

HashSet 是基于 HashMap 實現(xiàn)的绑咱。
set里的元素對應(yīng)map的key绰筛，value是一個靜態(tài)常量Object對象。

HashSet 是 Set 接?的主要實現(xiàn)類 描融， HashSet 的底層是 HashMap 铝噩，線程不安全的，可以存儲 null 值窿克；
LinkedHashSet 是 HashSet 的?類骏庸，能夠按照添加的順序遍歷毛甲；
TreeSet 底層使?紅?樹，能夠按照添加元素的順序進?遍歷具被，排序的?式有?然排序和定制排序玻募。

java.util.Arrays.asList()

Arrays.asList() 方法返回的 ArrayList 不是 java.util.ArrayList ，而是 java.util.Arrays 的一個靜態(tài)內(nèi)部類ArrayList一姿。

在這個內(nèi)部類中有一個被聲明為 final 的數(shù)組 a 七咧，所有傳入的元素都會被保存在這個數(shù)組 a 中，因此用 Arrays.asList() 方法產(chǎn)生的 ArrayList 是不可修改大小的啸蜜，如果在該方法的返回對象上進行remove()或add()坑雅，會拋出了一個java.lang.UnsupportedOperationException 異常。

底層還是數(shù)組衬横，只是對一些常見方法做了適配裹粤。

private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, Serializable{
   ....
   private final E[] a;
   ...
}

創(chuàng)建一個真正的 ArrayList 的方法：
List<String> myList = new ArrayList<String>(Arrays.asList(myArray));

參考鏈接：http://www.reibang.com/p/2b113f487e5e

ArrayList

ArrayList的特點

1. ArrayList的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，所以查找遍歷快蜂林，增刪慢遥诉。
2. ArrayList可隨著元素的增長而自動擴容，正常擴容的話噪叙，每次擴容到原來的1.5倍矮锈。
3. ArrayList的線程是不安全的。

ArrayList的擴容

ArrayList的構(gòu)造函數(shù)總共有三個：
（1）ArrayList()
（2）ArrayList(Collection<? extends E> c)
（3）ArrayList(int initialCapacity)

擴容可分為兩種情況：

第一種情況睁蕾，當ArrayList的容量為0時苞笨，此時添加元素的話，需要擴容子眶，三種構(gòu)造方法創(chuàng)建的ArrayList在擴容時略有不同：

1. 無參構(gòu)造ArrayList()瀑凝，創(chuàng)建容量為0的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，添加第一個元素后臭杰，容量變?yōu)?0粤咪，此后若需要擴容，則正常擴容渴杆。

2. 傳容量構(gòu)造ArrayList(int initialCapacity)寥枝，當參數(shù)為0時，創(chuàng)建容量為0的EMPTY_ELEMENTDATA磁奖，添加第一個元素后囊拜，容量為1，此時ArrayList是滿的比搭，下次添加元素時需正常擴容艾疟。

3. 傳列表構(gòu)造ArrayList(Collection<? extends E> c)，當列表為空時，創(chuàng)建ArrayList后容量為0蔽莱，添加第一個元素后弟疆，容量為1，此時ArrayList是滿的盗冷，下次添加元素時需正常擴容怠苔。

第二種情況，當ArrayList的容量大于0仪糖，并且ArrayList是滿的時柑司，此時添加元素的話，進行正常擴容锅劝，每次擴容到原來的1.5倍攒驰。

鏈接：淺談 ArrayList 及其擴容機制
透過源碼角度一步一步帶你分析 ArrayList 擴容機制

一個ArrayList在循環(huán)過程中刪除，會不會出問題故爵，為什么

List<String> 相鄰的兩個一樣的字符串：
普通 for 循環(huán)-使用List 的 remove( Object) 正序刪除：會漏掉后面那個字符串玻粪；
普通 for 循環(huán)-使用List 的 remove( Object) 倒序刪除：可以正常刪除，且線程安全诬垂；
增強 forEach 循環(huán)：使用List 的 remove( Object) 刪除劲室，forEach 循環(huán)寫法是對實際的Iterator、hasNext结窘、next 方法的簡寫很洋，checkForComodification 方法會拋出并發(fā)修改異常 ConcurrentModificationException；
迭代器刪除 iterator.remove()：多線程環(huán)境下無法使用隧枫；

快速失敽泶拧（fail—fast）

在用迭代器遍歷一個集合對象時，如果遍歷過程中對集合對象的內(nèi)容進行了修改（增加官脓、刪除线定、修改），則會拋出Concurrent Modification Exception确买。
原理：迭代器在遍歷時直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個 modCount 變量纱皆。集合在被遍歷期間如果內(nèi)容發(fā)生變化湾趾，就會改變modCount的值。每當?shù)魇褂胔ashNext()/next()遍歷下一個元素之前派草，都會檢測modCount變量是否為expectedmodCount值搀缠，是的話就返回遍歷；否則拋出異常近迁，終止遍歷艺普。
注意：這里異常的拋出條件是檢測到 modCount！=expectedmodCount 這個條件。如果集合發(fā)生變化時修改modCount值剛好又設(shè)置為了expectedmodCount值歧譬，則異常不會拋出岸浑。因此，不能依賴于這個異常是否拋出而進行并發(fā)操作的編程瑰步，這個異常只建議用于檢測并發(fā)修改的bug矢洲。
場景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改（迭代過程中被修改）缩焦。

foreach 循環(huán)里為什么不能進行元素的 remove/add 操作读虏？

image

原因在于，foreach循環(huán)（也叫增強for循環(huán)袁滥，即for(Integer x : list）這樣的寫法盖桥，其實是Java本身給我們的一個語法糖，當你對編譯之后class文件進行反編譯之后题翻，你會發(fā)現(xiàn)揩徊，foreach循環(huán)其實是依賴了while循環(huán)和Iterator實現(xiàn)的。

Iterator iterator = list.iterator();
do
{
    if(!iterator.hasNext())
        break;
    Object obj = iterator.next();
    // 業(yè)務(wù)邏輯 瞎編的
    if(canExecute()) {
        list.remove(object)    
    }
} while(true);

foreach循環(huán)：集合遍歷是通過iterator進行的藐握，但是但是元素的add/remove卻是直接使用的集合對象自己的方法靴拱，集合對象自己的add/remove方法不會去更新迭代器自身的expectedModCount值。
Iterator：Iterator的add/remove方法猾普，除了調(diào)用對應(yīng)集合的對應(yīng)add/remove方法的同時袜炕，它還會去修改自身的expectedModCount值。

安全失敵跫摇（fail—safe）

采用安全失敗機制的集合容器偎窘，在遍歷時不是直接在集合內(nèi)容上訪問的，而是先復制原有集合內(nèi)容溜在，在拷貝的集合上進行遍歷陌知。
原理：由于迭代時是對原集合的拷貝進行遍歷，所以在遍歷過程中對原集合所作的修改并不能被迭代器檢測到掖肋，所以不會觸發(fā)Concurrent Modification Exception仆葡。
缺點：基于拷貝內(nèi)容的優(yōu)點是避免了Concurrent Modification Exception，但同樣地志笼，迭代器并不能訪問到修改后的內(nèi)容沿盅，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的纫溃。
場景：java.util.concurrent包下的容器都是安全失敗腰涧，可以在多線程下并發(fā)使用，并發(fā)修改紊浩。

copy-on-write 機制

Copy-on-write 是解決并發(fā)的的一種思路窖铡，也是指的是實行讀寫分離疗锐，如果執(zhí)行的是寫操作，則復制一個新集合费彼，在新集合內(nèi)添加或者刪除元素滑臊。待一切修改完成之后，再將原集合的引用指向新的集合敌买。

這樣的好處就是简珠，可以高并發(fā)地對COW進行讀和遍歷操作，而不需要加鎖虹钮。因為當前集合不會添加任何元素聋庵。

前面我們有提到過線程安全的集合Vector，但是Vector的加鎖粒度太大芙粱，性能差祭玉，所以在并發(fā)環(huán)境下，推薦JUC包下的的CopyOnWriteArrayList來代替春畔。CopyOnWriteArrayList就是COW家族中的一員脱货。

一般我們認為，CopyOnWriteArrayList 是 同步List 的替代品律姨，CopyOnWriteArraySet 是同步Set 的替代品振峻。

CopyOnWriteArrayList*

核心理念就是讀寫分離：

• 寫操作在一個復制的數(shù)組上進行；寫操作需要加鎖择份，防止并發(fā)寫入時導致數(shù)據(jù)丟失扣孟；寫操作結(jié)束之后需要把 原始數(shù)組 指向新的復制數(shù)組。
• 讀操作還是在原始操作上進行荣赶，讀寫分離凤价，互不影響。
• 遍歷：COWIterator拔创，COWIterator內(nèi)部維護了一個循環(huán)開始時的數(shù)組快照利诺。

鏈接：

• Java 容器 - 集合世界的fail-fast機制 和 CopyOnWriteArrayList 源碼詳解
• https://juejin.cn/post/6844903672481054733
• https://blog.csdn.net/L_kanglin/article/details/70148043

Vector

Vector 的實現(xiàn)與 ArrayList 類似，但是使用了 synchronized 進行同步剩燥。
Vector 的構(gòu)造函數(shù)可以傳入 capacityIncrement 參數(shù)慢逾，它的作用是在擴容時使容量 capacity 增長 capacityIncrement。如果這個參數(shù)的值小于等于 0灭红，擴容時每次都令 capacity 為原來的兩倍侣滩。

替代方案

可以使用 Collections.synchronizedList() 得到一個線程安全的 ArrayList。

List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);

也可以使用 concurrent 并發(fā)包下的 CopyOnWriteArrayList 類比伏。
CopyOnWriteArrayList 的特點：
讀寫分離
寫操作在一個復制的數(shù)組上進行，讀操作還是在原始數(shù)組中進行疆导，讀寫分離赁项，互不影響。
寫操作需要加鎖，防止并發(fā)寫入時導致寫入數(shù)據(jù)丟失悠菜。
寫操作結(jié)束之后需要把原始數(shù)組指向新的復制數(shù)組舰攒。

List<String> list = new CopyOnWriteArrayList<>();

參考鏈接：https://github.com/CyC2018/CS-Notes/blob/master/notes/Java%20%E5%AE%B9%E5%99%A8.md#vector

LinkedList

雙向鏈表；
每個鏈表存儲了 first 和 last 兩個指針悔醋。

ArrayDeque

ArrayDeque和LinkedList是Deque的兩個通用實現(xiàn)摩窃，官方更推薦使用AarryDeque用作棧和隊列。

從名字可以看出ArrayDeque底層通過數(shù)組實現(xiàn)芬骄，為了滿足可以同時在數(shù)組兩端插入或刪除元素的需求猾愿，該數(shù)組還必須是循環(huán)的，即循環(huán)數(shù)組(circular array)账阻，也就是說數(shù)組的任何一點都可能被看作起點或者終點蒂秘。ArrayDeque是非線程安全的(not thread-safe)，當多個線程同時使用的時候淘太，需要程序員手動同步姻僧；另外，該容器不允許放入null元素蒲牧。

參考鏈接：
https://www.pdai.tech/md/java/collection/java-collection-Queue&Stack.html