? ? ? ? 在開始正文之前，先和大家聊點閑話：這是我關(guān)注簡書以來寫的第一篇筆記，當(dāng)然我堅信這只是一個開始侵蒙，以后會堅持寫更多的筆記。有寫筆記的想法是受周圍的一些優(yōu)秀伙伴們的影響傅蹂，他們有些是我學(xué)習(xí)后臺開發(fā)的啟蒙老師纷闺，有些是我從未謀面卻很敬佩的技術(shù)大神。他們都是這個行業(yè)里的佼佼者贬派，當(dāng)我看到如此優(yōu)秀的他們?nèi)匀幻刻煸诠ぷ髦喔录夹g(shù)博客急但，學(xué)習(xí)新技術(shù)澎媒，關(guān)注這個行業(yè)的飛速發(fā)展搞乏。我想作為一個剛?cè)腴T的小白，唯一的優(yōu)勢就是有著一顆年輕的心和敢于拼搏和探索的朝氣戒努。為所有在路上拼搏努力的朋友加油请敦，最有意義的事情總是需要我們通過自己的努力一步一步腳踏實地的去慢慢完成，堅持做成它储玫，近乎完美的實現(xiàn)它侍筛，你就是最棒的。
==========================================================================
目錄索引
? 1. java容器之間的關(guān)系簡介
? 2.ArrayList源碼中的一些細節(jié)總結(jié)
? 3.LinkendList源碼中的一些細節(jié)總結(jié)
? 4.最后聊聊寫時拷貝技術(shù)
1.1 java容器總框架圖
注：圖片來源? ? ? ? ? http://alexyyek.github.io/2015/04/06/Collection/
1.2 簡單總結(jié)一下各容器之間的聯(lián)系：
? ? ? ? ? ? java容器中包含了List列表撒穷、Set集合匣椰、Map、工具類（包含一些迭代器端礼、枚舉類禽笑、條件類等）；按元素是否成對出現(xiàn)容器可分為兩類：Colletion（獨立元素構(gòu)成的序列）和Map（以鍵值對組成的散列表）蛤奥，它們作為容器類的頂層接口分別實現(xiàn)了集合的基本操作：添加佳镜、刪除、清空凡桥、遍歷(讀取)蟀伸、是否為空、獲取大小缅刽、是否保護某元素和散列表的基本操作：添加啊掏、查找、刪除等等衰猛。
? ? ? ? Colletion集合又按照元素是否隨機存儲被分為List（元素可以重復(fù)迟蜜，按一定順序保存起來）、Set（元素不可以重復(fù)腕侄，無序的保存所有元素）小泉；我對這兩種集合的抽象理解是：List是一整條芦疏，一整條的存儲（不一定連續(xù)內(nèi)存存儲），而Set是被圈在一個“”大圓”中微姊。具體關(guān)聯(lián)可參考下面的圖片：
注：圖片來源? ? ? ? ? http://alexyyek.github.io/2015/04/06/Collection/
? 實現(xiàn)List接口的類有Arraylist酸茴、LinkedList、Vector兢交、Stack薪捍。下面主要說說ArrayList和? ? LinkedList在JDK中的具體實現(xiàn)。
2. 1.ArrayList定義
? ? ? ? ArrayList:是一個數(shù)組列表配喳，相比數(shù)組的優(yōu)勢是它可以動態(tài)擴容 酪穿，另外它是非線程安全的，當(dāng)多個線程同時操作一個ArrayList對象時不保證同步晴裹。
2.2 transient關(guān)鍵字
? ? ? ? 阻止一個可以被序列化的類中某些變量不被序列化 被济， 這樣使得該屬性在被反序列化時不會恢復(fù)以及持久化。例如涧团，當(dāng)反序列化對象——數(shù)據(jù)流（例如只磷，文件）可能不存在，原因是你的對象中存在類型為java.io.InputStream的變量時泌绣，序列化一個輸入流是毫無意義的钮追，因為在反序列化時大多數(shù)情況下，輸入流對象中都是不存在數(shù)據(jù)的阿迈。有些變量在使用該類的時候有作用 用完之后就沒有作用了元媚，持久化只能多占用點內(nèi)存空間
? ? ? ? ? transient Object[]elementData; // non-private to simplify nested class access
? 為什么不直接序列化elementData：
? ? ? ? 因為elementDate是一個緩存數(shù)組，大多數(shù)情況下 該數(shù)組? ? 中有很多空閑的位置苗沧，并沒有保存實際數(shù)據(jù)刊棕，序列化這些位置是沒有意義的，為了節(jié)省空間ArrayList采用WriteObject 和 ReadObject兩個方法進行序列化和反序列化崎页，這兩個方法會遍歷臨時數(shù)組中的每一個元素鞠绰，并且把他們序列化，這樣比直接序列化整個緩存空間要節(jié)省空間飒焦。
2.3 源碼分析
ArrayList包含了兩個重要的對象：elementData 和 size蜈膨。
transient Object[] elementData : ArrayList容器，保存添加到ArrayList中的元素牺荠。
private int size ：The size of the ArrayList（元素個數(shù)）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
解釋一下它的默認長度為什么是Integer.MAX_VALUE-8：有些虛擬機在數(shù)組中保留了一些頭信息翁巍。避免內(nèi)存溢出！
2.3.1休雌、在指定位置插入一個元素：
public void add(int index, E element) {
*? ? ? //判斷index是否合法
? ? ? ? rangeCheckForAdd(index);
*? ? ? //擴容灶壶，分為兩步：首先判斷添加元素后需要的數(shù)組空間是否超過數(shù)組本身長度
*? ? ? //如果超過則需要擴容調(diào)用grow()
*? ? ? ? ensureCapacityInternal(size + 1);? // Increments modCount!!
*? ? ? //從index開始后面的元素一次后移一位? 復(fù)制實現(xiàn)移動
*? ? ? ? System.arraycopy(elementData, index, elementData, index + 1,
*? ? ? ? ? ? ? ? ? ? ? ? ? size - index);
*? ? ? ? elementData[index] = element;
*? ? ? ? size++;
*? ? }
2.3.2、擴容
*? ? ? private void grow(int minCapacity) {
*? ? ? ? // overflow-conscious code
*? ? ? ? int oldCapacity = elementData.length;
*? ? ? ? //原數(shù)組長度加上原數(shù)組的長度的0.5倍? 1.8將除法改進為右移位運算
*? ? ? ? int newCapacity = oldCapacity + (oldCapacity >> 1);
*? ? ? ? if (newCapacity - minCapacity < 0)
*? ? ? ? ? ? newCapacity = minCapacity;
*? ? ? ? if (newCapacity - MAX_ARRAY_SIZE > 0)
*? ? ? ? ? ? newCapacity = hugeCapacity(minCapacity);
*? ? ? ? // minCapacity is usually close to size, so this is a win:
*? ? ? ? elementData = Arrays.copyOf(elementData, newCapacity);
*? ? }
2.3.3杈曲、 modCount的作用：修改次數(shù)計數(shù)器
? ? ? ? ? 在一個改變ArrayList的結(jié)構(gòu)的方法中需要對modCount進行自增驰凛，比如一些添加胸懈， 刪除的方法中。在ArrayList的迭代器中需要使用這個字段恰响，如果在迭代過程 中modCount發(fā)生了改變趣钱，（通常在多線程的環(huán)境下發(fā)生）在迭代的時候就會拋出ConcurrentModificationException異常。因為如果持續(xù)迭代讀取的數(shù)據(jù)可能不是 最新的數(shù)據(jù)胚宦，已經(jīng)過期 首有。
值的注意的一些細節(jié)：
*? ? 1.遍歷ArrayList時，使用隨機訪問(即通過索引序號訪問)效率最高枢劝，而使用迭代器的效率最低
*? ? ? 2.ListItr繼承自Itr井联，添加了向前遍歷的功能，當(dāng)獲取了iterator實例后您旁，list就不可改變烙常。當(dāng)ArrayList使用了ListIterator()方法產(chǎn)生自身對應(yīng)的Iterator后，只能使用Iterator自身的remove() 和add()方法來修改ArrayList的結(jié)構(gòu)被冒，因為這些方法對expectedModCount和modCount變量自動同步军掂。
*? 3.默認ArrayList的長度是10個，所以如果你要往list里添加20個元素肯定要擴充一次newCapacity 擴充 為原來的1.5倍昨悼，但和輸入的minCapacity相比發(fā)現(xiàn)小于minCapacity，于是 newCapacity = minCapacity跃洛，所以只擴容一次率触。
*? 4.Vector的實現(xiàn)基本上和ArrayList相同，不過ArrayList是線程不安全的 Vector是線程安全的
? 3.1 LinkedList定義
? ? ? ? ? ? LinkedList和ArrayList一樣都是實現(xiàn)了List接口汇竭，只是ArrayList是List接口的大小可變數(shù)組的實現(xiàn)葱蝗，LinkedList是List接口鏈表的實現(xiàn)∠噶牵基于鏈表實現(xiàn)的方式使得LinkedList在插入和刪除時更優(yōu)于ArrayList两曼，而隨機訪問則比ArrayList遜色些。 LinkedList繼承AbstractSequentialList（雙向鏈表抽象類） 可以被當(dāng)作堆棧玻驻、隊列或雙端隊列進行操作悼凑。
? 3.2 很細節(jié)的一個方法：返回標(biāo)記值為index的節(jié)點，從所有元素的最中間開始遍歷
? ? ? 如果index的值小于size的一半則從頭結(jié)點開始向中間查找 直到找到index為止
? ? ? ? 相反如果index的值大于size的一半則從尾節(jié)點開始向中間遍歷 直到找到index為止
*? Node node(int index) {?
? ? // assert isElementIndex(index);
? ? if (index < (size >> 1)) {
*? ? ? ? ? ? Node x = first;
*? ? ? ? ? ? for (int i = 0; i < index; i++)
*? ? ? ? ? ? ? ? x = x.next;
*? ? ? ? ? ? return x;
*? ? ? ? } else {
*? ? ? ? ? ? Node x = last;
*? ? ? ? ? ? for (int i = size - 1; i > index; i--)
*? ? ? ? ? ? ? ? x = x.prev;
*? ? ? ? ? ? return x;
*? ? ? ? }
*? ? }
? 3.3? 添加一整個集合
*? ? ? 基本思路是首先定義兩個臨時節(jié)點前驅(qū)節(jié)點和后續(xù)節(jié)點璧瞬，后繼指向要插入的位置? ? ?
*? ? ? 連接index后面的所有節(jié)點户辫，前驅(qū)節(jié)點一直指向index位置的前一個節(jié)點
*? ? ? ? 每次要插入一個新節(jié)點，如果前驅(qū)節(jié)點為空嗤锉，則將新插入的節(jié)點當(dāng)做頭結(jié)點
*? ? ? ? 如果不為空渔欢，前驅(qū)節(jié)點的后繼指向新節(jié)點，最后讓前驅(qū)節(jié)點指向新插入的節(jié)點
*? ? ? ? 直到遍歷完所有要插入的節(jié)點后瘟忱，在判斷后繼節(jié)點是否為空奥额，如果是空苫幢，則將
*? ? ? ? 最后一個節(jié)點指向前驅(qū)節(jié)點 如果不是空，直接將前驅(qū)節(jié)點和后繼節(jié)點相連
*? ? public boolean addAll(int index, Collectionc) {
*? ? ? ? //若插入的位置小于0或者大于鏈表長度垫挨，則拋出IndexOutOfBoundsException異常
*? ? ? ? checkPositionIndex(index);
*? ? ? ? //首先將集合變?yōu)閷ο髷?shù)組
*? ? ? ? Object[] a = c.toArray();
*? ? ? ? int numNew = a.length;//插入元素個數(shù)
*? ? ? ? if (numNew == 0)
*? ? ? ? ? ? return false;
*? ? ? ? Node pred, succ;? ? //定義臨時前驅(qū)和后繼
*? ? ? ? if (index == size) {? ? //如果在鏈表尾部插入
*? ? ? ? ? 1.1? succ = null;? ? //后繼置空
*? ? ? ? ? 1.2? pred = last;? ? //前驅(qū)指向隊尾元素last
*? ? ? ? } else {? ? ? ? ? ? //在指定位置插入
*? ? ? ? ? ? succ = node(index); //后繼指向該位置态坦，后繼一直連接當(dāng)前位置后面的所有節(jié)點
*? ? ? ? ? ? pred = succ.prev;? //前驅(qū)指向前一個元素 前驅(qū)一直連接當(dāng)前位置前面的所有節(jié)點
*? ? ? ? }
*? ? ? ? for (Object o : a) {
*? ? ? ? ? ? @SuppressWarnings("unchecked") E e = (E) o;
*? ? ? ? ? ? Node newNode = new Node<>(pred, e, null);//創(chuàng)建一個新節(jié)點，指定前驅(qū)棒拂，后繼置空
*? ? ? ? ? ? if (pred == null)//如果前驅(qū)不存在伞梯，說明當(dāng)前要插入的位置是頭
*? ? ? ? ? ? ? ? first = newNode;//表頭first指向此節(jié)點
*? ? ? ? ? ? else
*? ? ? ? ? pred.next = newNode;//前驅(qū)存在，則將其next指向新節(jié)點
*? ? ? ? ? pred = newNode;//前驅(qū)向后移動帚屉，繼續(xù)創(chuàng)建新節(jié)點
*? ? ? ? }
*? ? ? ? if (succ == null) {
*? ? ? ? ? ? last = pred;//如果后繼為空谜诫，說明當(dāng)前插入的節(jié)點應(yīng)該在鏈表尾部
*? ? ? ? } else {
*? ? ? ? ? //后繼不為空，那么前驅(qū)節(jié)點和后繼節(jié)點相連
*? ? ? ? ? ? pred.next = succ;
*? ? ? ? ? ? succ.prev = pred;
*? ? ? ? }
*? ? ? ? size += numNew;
*? ? ? ? modCount++;
*? ? ? ? return true;
*? ? }
3.4? 關(guān)于線程不安全的討論：從fil-fast到寫時拷貝
? ? ? ArrayList和LinkedList共同的特點是他們都是線程不安全的攻旦， 在多個線程同時操作一個集合對象時就會發(fā)生數(shù)據(jù)臟讀和數(shù)據(jù)覆蓋等問題喻旷，同時再調(diào)用它們的迭代器時，都會記錄當(dāng)前的修改版本modCount的值牢屋，如果在迭代的過程中該值發(fā)生了變化且预，迭代器立馬拋出一個ConcurrentModificationException異常。 像這種迭代時修改拋異常的情況被稱為fil-fast機制烙无；當(dāng)然在在日常開發(fā)中我們是不希望看到這種情況發(fā)生的锋谐，多線程并發(fā)在迭代器遍歷列表時只是簡單的讀取容器里面的數(shù)據(jù)而不做任何修改，憑什么不允許其他線程操作該列表對象截酷，CPU大哥的時間可是很寶貴的涮拗，我們應(yīng)該抓住CPU大哥的每一ms時間，讓它做更多有意義的事迂苛，而不是做大量的空閑等待三热。
4、寫時拷貝
? ? ? ? 基于上面的爭議我們引入寫時拷貝技術(shù)三幻，注意它是一項技術(shù)就漾，不歸屬于任何語言，也不歸屬于任何領(lǐng)域念搬，只不過大多數(shù)情況下被運用到計算機的相關(guān)領(lǐng)域抑堡，比如Linux操作系統(tǒng)fork的內(nèi)存分配，還有就是現(xiàn)在說的CopyOnWriteArrayList,該類在ArrayList的基礎(chǔ)上引用了寫時拷貝技術(shù)锁蠕。
? ? ? ? 具體引用過程如下：對于多個線程操作同一個列表時夷野，如果某個線程只是簡單讀取列表的值而不做任何修改，那么當(dāng)前線程將不需要獲得該對象的鎖荣倾，這樣就不會阻塞其他線程對該對象進行其他操作悯搔。當(dāng)某個線程想要修改一個列表對象的元素時，該線程將會獲得列表對象的鎖 并且從主存中拿到當(dāng)前數(shù)組對象的一份副本，所有的修改操作都是對副本而言的妒貌，對于主存中的實際數(shù)據(jù)并不會產(chǎn)生新的影響通危，在修改完成后將修改后的副本更新到主存 釋放對象鎖；則其他線程可以任意讀取數(shù)組對象中的數(shù)據(jù)灌曙，但是不能修改菊碟，因為該對象的鎖不能同時被兩個線程所擁有。
? ? ? ? ? 需要注意的是這里的沒有修改是片面的在刺，也就是說當(dāng)一個線程修改這個數(shù)組對象時 雖然操作的是一個副本逆害，但是真正想修改的還是主存中的真實數(shù)據(jù)，只不過暫時還沒有把修改的結(jié)果更新到主存中蚣驼，所以在其他線程無鎖讀取數(shù)組元素時魄幕，有可能會讀到已經(jīng)過期的數(shù)據(jù)，只不過這個過期數(shù)據(jù)在主存中體現(xiàn)出了一種沒有改變的假象 同樣的原理颖杏，在CopyOnWriteArrayList中的迭代器也做了一定的優(yōu)化纯陨，COWIterator是list迭代器的子類，它不支持獲得迭代器的線程對數(shù)組元素做任何的修改留储，在迭代過程中其他線程對該數(shù)組的更新也不會體現(xiàn)在迭代器中翼抠，也就是說迭代器中的數(shù)組相當(dāng)于是不可變的，獲得迭代器的線程如果想修改數(shù)組元素必須獲得對象的鎖获讳，而這又違背了多個線程同時迭代的初衷阴颖；換言之，COWIterator僅僅保證了在調(diào)用迭代器的同時其他線程在修改數(shù)據(jù)則不會拋出異常赔嚎，僅此而已膘盖。
至此就是今天關(guān)于java容器類的一些學(xué)習(xí)心得，文章中可能會出現(xiàn)很多的錯誤尤误，小白初犯還望各位大神諒解。下篇將會記錄一片HashMap相關(guān)的一些筆記结缚，敬請期待? !
