第一次寫博客轧飞，有些知識點還是得記錄下衅鹿，不然過了段時間難免忘記曾經(jīng)發(fā)現(xiàn)的問題，和是否解決過和研究到多深入（還不懂的一律用９А４蟛场！表示）掸绞。我寫的內(nèi)容只記錄到我最后發(fā)現(xiàn)知識點的認知泵三，肯定是宏觀不全或者說有講解不到點上，但是沒關(guān)系，認知是循序漸進的烫幕。
說到Java集合俺抽，第一反應(yīng)是List，ArrayList较曼，如下代碼：
好磷斧，那就以這段代碼為切入點，ArrayList有三種構(gòu)造方法
看到這三種構(gòu)造器想起一個問題诗芜，為什么創(chuàng)建容器的時候要指定大型ァ？
第三種構(gòu)造方法不做對比伏恐，跟進代碼就知道這個方法相當于克隆或者是類型的互轉(zhuǎn)孩哑。
直接說結(jié)論，因為我覺得這個很基礎(chǔ)翠桦，沒必要大廢文章横蜒。指定大小創(chuàng)建容器時就初始化好數(shù)組的長度，不用后續(xù)add操作時對數(shù)組進行擴容销凑，提高了使用效率丛晌。
說到擴容，ArrayList是怎么擴容的斗幼？
直接跟進add方法：
minCapacity：當前add操作需要的最小容量大小
newCapacity：新的容量大小newCapacity =?oldCapacity +oldCapacity /2澎蛛，那就是擴容1.5倍
if (newCapacity - minCapacity <0) 這個if暫時認為是就只是判斷一下，因為我現(xiàn)在覺得這個判斷是不會成立的蜕窿。
Arrays.copyOf調(diào)用了兩個本地方法谋逻，一個是創(chuàng)建newCapacity 大小的數(shù)組，一個是復制數(shù)組桐经。
好毁兆，再來看下add的另一個重載方法
rangeCheckForAdd是校驗index的值是不是在0到size之間（都是閉區(qū)間），否則會報錯阴挣，這么做的目的只有一個气堕，前面的必須填滿，否則將增加維護邏輯畔咧。
System.arraycopy是將下標為index開始的區(qū)間值復制到從index+1開始茎芭，也就是下標為index到size的值右移一位。
問題點記錄：行丁Ｆ！arraycopy的本地方法是怎么實現(xiàn)的尚未可知蔽介，可以猜想是遍歷賦值摘投，但是是不是不知道煮寡。
好，有add就有remove犀呼，直接看remove怎么實現(xiàn)的幸撕。
一看很清晰，就是將下標為index+1開始的區(qū)間值的全部復制到index開始外臂，也就是左移一位坐儿，然后再將多余的最后一個設(shè)為null。另一個重載方法如下宋光，代碼邏輯很清晰
好貌矿，四種讀寫操作講完，那么問題來了罪佳，四種操作的時間復雜度是多少逛漫？答案我就不寫了，如果真的看懂了就能知道赘艳，死記是記不住的酌毡，get、set就不說了蕾管。
接著說LinkedList吧枷踏，記住下面幾個結(jié)論。（我發(fā)現(xiàn)寫博客很浪費時間掰曾，還不如直接點進源碼看看就什么都知道了）
1旭蠕、遍歷不要用for(int i = 0;i<length;i++)這種形式，LinkedList是用鏈表實現(xiàn)旷坦，所以index不能確定位置下梢，要用迭代器或者foreach。
2塞蹭、ArrayList的get、set快讶坯，直接數(shù)組定位番电。至于add不一定，ArrayList是數(shù)組尾部插入辆琅，除了要擴容沒什么損耗漱办，而LinkedList需要new Node，remove正常來說是LinkedList快婉烟。
接著說Map吧娩井，直接看put方法
hash方法的作用是將hashcode的高區(qū)間的16位和低區(qū)間的16位做異或運算，目的是為了降低hash沖突似袁。
好洞辣，看完圖咐刨，問題來了，嘿嘿嘿扬霜。定鸟。
1、為什么數(shù)組槽被占用后要用鏈表結(jié)構(gòu)著瓶，不繼續(xù)用數(shù)組結(jié)構(gòu)联予？
數(shù)組和鏈表都需要遍歷，時間復雜度都是O(n)材原，增刪數(shù)組需要擴容加復制沸久。
2、為什么鏈表長度大于8就要進行轉(zhuǎn)樹結(jié)構(gòu)處理余蟹？為什么是8卷胯？（圖片的7有誤，binCount是從0開始）
為什么是8客叉，好問題诵竭，我也不知道，找找注釋兼搏，嗯..大概意思是說和數(shù)據(jù)分布概率有關(guān)系卵慰，關(guān)鍵字，follows a Poisson distribution
這個是what佛呻？裳朋？？不管吓著，以后再說鲤嫡，這里記下！０筝骸暖眼！
3、這個modCount變量是干嘛用的纺裁？
迭代器使用的诫肠，有關(guān)于fail-fast概念。
好接著講resize()方法
resize方法是初始化和擴容方法欺缘，這部分看完可以得到這幾個信息
1栋豫、數(shù)組最大容量為MAXIMUM_CAPACITY =1 <<30，左移31位會超出int的大小谚殊。
2丧鸯、數(shù)組是兩倍擴容，newCap = oldCap <<1嫩絮。
3丛肢、初始數(shù)組容量為DEFAULT_INITIAL_CAPACITY =1 <<4围肥，初始閾值threshold為DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY，即0.75*16 = 12摔踱。
4虐先、threshold也是兩倍擴容，newThr = oldThr <<1; // double threshold派敷，可以得出threshold = 0.75*newCap依舊不變蛹批。
剩下的就是擴容之后結(jié)構(gòu)的重建了，為啥要重建篮愉？因為計算元素的下標 = hash &?(n-1) ,n是數(shù)組長度腐芍，長度發(fā)生變化，下標值肯定也是發(fā)生變化了试躏。
這部分有兩個難點猪勇，一個是樹結(jié)構(gòu)數(shù)據(jù)的轉(zhuǎn)移，這個暫時看不懂颠蕴，后續(xù)看下泣刹，先不管！Ｏ弧椅您！
另外一個是鏈表的元素轉(zhuǎn)移，那就講講鏈表的元素的轉(zhuǎn)移寡键。
do while是遍歷原來鏈表元素掀泳，假如讓我來實現(xiàn)，我會遍歷鏈表西轩，得到每一個元素的index = hash & （newCap -1)员舵，然后拿到newTab[index] 的值去做判斷，鏈表就插入尾部藕畔，樹就進行樹結(jié)構(gòu)的插入马僻。但是發(fā)現(xiàn)hashmap沒有這么處理，看懂之后才發(fā)現(xiàn)hashmap的處理更加簡潔注服，這就是值得借鑒的地方巫玻。
(e.hash & oldCap) ==0 這是什么意思呢？看下數(shù)據(jù)就很清晰了祠汇，假設(shè)由16擴容到32
我們計算下標是這么計算的，發(fā)現(xiàn)規(guī)律沒有熄诡，因為相同key的hash值是相同的可很，擴容前后和擴容后的下標定位差異是在倒數(shù)第5位，那么也就是說原數(shù)組長度的二進制數(shù)的最高位所對應(yīng)的hash值對應(yīng)的位置的值是0說明擴容后的數(shù)組下標不變（這句話有點繞凰浮，就看圖的hash的倒數(shù)第5位）我抠，如果是1說明擴容后的元素下標為原下標值+原數(shù)組長度（就是01011+10000）苇本。
好這里搞懂了，那再來看為啥是oldCap菜拓，很簡單瓣窄，oldCap = 16 = 10000就是拿到最高位判斷hash值對應(yīng)位置是0還是1，是0那就是說元素下標擴容前后不變纳鼎，為1就是newindex =?原下標值+原數(shù)組長度俺夕。
對比下我的思路和HashMap的解決思路，比我的思路少了一步拿到newTab[index] 的值然后判斷再去做插入贱鄙。
