前言：所有數(shù)據(jù)結(jié)構(gòu)以及源碼相關(guān)內(nèi)容基于jdk1.8版本。對常見的數(shù)據(jù)結(jié)構(gòu)進行解釋以及對常見方法進行源碼解讀年柠。
ArrayList
ArrayList底層數(shù)據(jù)結(jié)構(gòu)較為簡單
// 底層為數(shù)組結(jié)構(gòu) 所有數(shù)據(jù)均存儲在elementData數(shù)組中
transient Object[] elementData;
底層為數(shù)組結(jié)構(gòu)決定了該集合的優(yōu)缺點：
優(yōu)點：
有序，有索引顾复。
可以根據(jù)索引直接獲取對應的元素餐抢，同時數(shù)組結(jié)構(gòu)根據(jù)索引定位元素性能高，因此查詢快宗收。
缺點：
數(shù)組長度是固定的，導致每次add元素都需判斷長度是否滿足亚兄，如果不滿足需要擴容數(shù)組混稽，擴容的過程其實效率比較低(后面會通過源碼分析擴容過程)。
隨機插入或者刪除元素會導致數(shù)據(jù)內(nèi)容大范圍移動审胚，效率低匈勋。
這就是常說的ArrayList查詢快 增刪慢
源碼剖析
構(gòu)造函數(shù)剖析
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
首先，通過源碼注釋可以了解到膳叨，當使用無參構(gòu)造的時候會初始化一個長度為10的空數(shù)據(jù)洽洁，但是實際源碼發(fā)現(xiàn)剛初始化出來的數(shù)組其實長度是0。而真正初始化該數(shù)據(jù)的位置其實是在add方法中菲嘴。后面講到add方法的時候再做詳細說明饿自。
有參構(gòu)造
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
通過以上源碼我們可以發(fā)現(xiàn)，當傳入一個容量長度的時候龄坪，會初始化一個對應長度的數(shù)組昭雌，如果傳入的長度為0則相當于使用了無參構(gòu)造。如果傳入的為負數(shù)則會拋出非法參數(shù)異常悉默。
add(E e)源碼剖析
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 長度動態(tài)判斷以及擴容的方法城豁，是ArrayList的核心方法
ensureCapacityInternal(size + 1); // Increments modCount!!
// 長度滿足之后會直接將傳遞進來的數(shù)據(jù) 賦值給size對對應的索引位置。
// 同時讓當前集合的size+1 注意集合的長度是size抄课，并不是集合中數(shù)組的長度唱星，這里要特別注意
elementData[size++] = e;
return true;
}
以上代碼不難看出雳旅，ArrayList對數(shù)據(jù)的存儲就是把元素放到數(shù)組中。
接下來主要看這個核心擴容的方法代碼间聊。
這段代碼方法較多攒盈，為了方便閱讀，直接通過注釋來解析哎榴。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 最大數(shù)組長度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 數(shù)組默認容量長度
private static final int DEFAULT_CAPACITY = 10;
protected transient int modCount = 0;
// 核心確保數(shù)組容量的方法型豁，主要功能有計算當前所需的容量值，以及如果容量不夠完成擴容操作尚蝌。
private void ensureCapacityInternal(int minCapacity) {
// calculateCapacity方法用于計算當前所需容量
// ensureExplicitCapacity方法用于擴容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 首先結(jié)合之前看到的無參構(gòu)造的例子來講
// 無參構(gòu)造初始化的數(shù)組其實就是一個{}空數(shù)組其實就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 因此這里判斷成立迎变。而此時minCapacity = size + 1 默認數(shù)組長度為0，因此minCapacity值為1飘言。
// 到此 可以看到 如果使用無參構(gòu)造衣形，計算容量的方法返回的值為DEFAULT_CAPACITY = 10。
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 此時再看另外一種情況姿鸿，假設(shè)使用有參構(gòu)造初始化的一個長度為20的數(shù)組谆吴，
// 上面的判斷條件就不滿足，就會直接返回傳遞過來的minCapacity = size + 1 ,
return minCapacity;
}
// 當計算出來當前數(shù)組所需的長度之后執(zhí)行該方法完成數(shù)組的擴容操作
private void ensureExplicitCapacity(int minCapacity) {
// modCount該值沒有實際的業(yè)務含義苛预，只要的作用就是為了防止在使用迭代器遍歷的時候?qū)?shù)組做增刪操作句狼，會根據(jù)該值的變化拋出并發(fā)修改異常
modCount++;
// 當計算出來當前數(shù)組應有的容量比當前數(shù)組現(xiàn)有長度要大的時候來完成數(shù)組的擴容操作，否則不進行任何操作热某。
// 當使用無參構(gòu)造初始化數(shù)組的時候腻菇，默認數(shù)組長度為0，而計算出來的數(shù)組長度為默認的長度10苫拍，所以這里就會直接調(diào)用grow方法來完成數(shù)據(jù)的擴容操作
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 數(shù)組的擴容方法
private void grow(int minCapacity) {
// 記錄擴容之前數(shù)組的長度
int oldCapacity = elementData.length;
// 根據(jù)之前數(shù)組的長度芜繁，計算擴容之后的數(shù)組長度。這里用到了位運算绒极，如果對位運算有了解的應該不難看出，這個擴容系數(shù)大致就是0.5蔬捷。
// 假定當前老數(shù)組長度為10 10的二進制為 1010 右移一位之后變成0101 換算回來就是5 垄提， 10+5 = 15.
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判斷當前傳遞過來數(shù)組的最小應有長度和擴容之后的長度，取較大值周拐。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果當前算出來的擴容長度大于最大數(shù)組長度 Integer.MAX_VALUE - 8(一般不會有這么長的數(shù)組)铡俐，則會使用hugeCapacity方法來限定一個大小。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 最終調(diào)用Arrays工具類的復制方法來完成數(shù)組的擴容妥粟。這個方法會先初始化一個newCapacity長度的數(shù)組审丘，
// 再把elementData中的數(shù)據(jù)拷貝過去，這里就是比較耗時勾给，耗內(nèi)存的地方滩报。
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 該方法比較簡單自己閱讀锅知。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add(int indec,E e)源碼剖析
public void add(int index, E element) {
// 校驗傳入的index合法性方法，如果傳入的索引小于0或者大于當前數(shù)組的size則會拋出索引越界異常
rangeCheckForAdd(index);
// 和上面add方法擴容一樣脓钾。
ensureCapacityInternal(size + 1); // Increments modCount!!
// 調(diào)用系統(tǒng)的native方法完成數(shù)組的拷貝操作售睹。
// 從elementData數(shù)組索引為index的位置開始拷貝，講數(shù)據(jù)拷貝到index+1的位置可训，拷貝的長度為size-index
// 例如當前數(shù)組內(nèi)容為["a","b","c","d","e","","","","",""]昌妹，此時調(diào)用add(1,"f")方法。
// 則拷貝之后的內(nèi)容為["a","b","b","c","d","e","","","",""]
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 拷貝完成之后在給對應index位置元素值做一次覆蓋握截，覆蓋之后數(shù)組的值為 ["a","f","b","c","d","e","","","",""]
// 由此可以看出這種對應索引位置的插入會導致整個數(shù)組發(fā)生拷貝飞崖，大部分數(shù)據(jù)位置發(fā)生移動。
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
set(int index,E e)源碼剖析
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
以上代碼就比較簡單谨胞，就是直接的值覆蓋對應索引位置的值蚜厉，并返回舊值。
remove(int index)源碼剖析
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
和上面的代碼基本類似畜眨，同樣使用System.arraycopy來拷貝元素昼牛，相當于把要刪除的索引位置的元素用后面index+1開始的索引元素整體前移了一位。
remove(E e)源碼剖析
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
這里的移除和之前的一樣都是使用復制的方式來覆蓋內(nèi)容康聂。只不過移除的時候需要整體遍歷元素找到需要移除的值對應的索引贰健。
get方法源碼
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get方法的源碼非常簡單。直接就是去數(shù)組對應索引的元素恬汁。
到這里ArrayList相關(guān)常用的api源碼差不多就分析完了伶椿。看完源碼后應該更能體會ArrayList查詢快氓侧，增刪慢的原因了脊另。
接下來繼續(xù)來看LinkedList以及Map相關(guān)的一些api。
