一拦耐、基本原理
- 數(shù)組的長度是固定的弯蚜，java里面數(shù)組都是定長數(shù)組十籍，如果不停的往ArrayList里面塞入這個數(shù)據(jù)蛆封，此時元素?cái)?shù)量超過了初始大小，此時就會發(fā)生一個數(shù)組的擴(kuò)容勾栗，就會搞一個更大的數(shù)組惨篱，把以前的數(shù)組拷貝到新的數(shù)組里面去
- 缺點(diǎn)一、這個數(shù)組擴(kuò)容+元素拷貝的過程围俘，相對來說會慢一些. 所以砸讳，不要頻繁的往arralist里面去塞數(shù)據(jù)琢融，導(dǎo)致他頻繁的數(shù)組擴(kuò)容，避免擴(kuò)容的時候較差的性能影響了系統(tǒng)的運(yùn)行
- 缺點(diǎn)二簿寂、數(shù)組來實(shí)現(xiàn)漾抬，數(shù)組你要是往數(shù)組的中間加一個元素，是不是要把數(shù)組中那個新增元素后面的元素全部往后面挪動一位常遂，所以說纳令，如果你是往ArrayList中間插入一個元素，性能比較差克胳，會導(dǎo)致他后面的大量的元素挪動一個位置
- 優(yōu)點(diǎn)一平绩、基于數(shù)組來實(shí)現(xiàn)，非常適合隨機(jī)讀漠另，你可以隨機(jī)的去讀數(shù)組中的某個元素捏雌，list.get(10)，相當(dāng)于是在獲取第11個元素笆搓，這個隨機(jī)讀的性能是比較高的腹忽，隨機(jī)讀，list.get(2)砚作，list.get(20)窘奏，隨機(jī)讀list里任何一個元素
- 為什么基于數(shù)組的ArrayList隨機(jī)讀寫會很快，而插入性能較低葫录，因?yàn)閿?shù)組是基于內(nèi)存里連續(xù)的空間着裹，只要根據(jù)Index+offset就可以計(jì)算出我們想訪問的那個元素在內(nèi)存中的地址
源碼
代碼片段一、
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
// 代碼片段二米同、
list.add("zhangsan");
list.add("lisi");
list.add("wuwang");
System.out.println(list.toString());
System.out.println(list.toString());
// 代碼片段六骇扇、
list.get(2);
// 代碼片段七、這里其實(shí)是向集合中的index為1的地方面粮，插入一個新的元素
list.add(1,"zhaoliu");
}
代碼片段二少孝、
/**
* 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) {
// 這里是在計(jì)算當(dāng)前元素應(yīng)該放在list中的index索引，代碼片段三熬苍、
// 這里的size其實(shí)就是當(dāng)前集合的大小稍走，這里要和capacity區(qū)分開
ensureCapacityInternal(size + 1); // Increments modCount!!
// 將當(dāng)前元素放入到集合中，index=size++
elementData[size++] = e;
return true;
}
代碼片段三柴底、
private void ensureCapacityInternal(int minCapacity) {
// 代碼片段四婿脸、
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 通過代碼片段四，第一次進(jìn)來柄驻，minCapacity的值為10
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 如果minCapacity大于集合現(xiàn)在的大小的話狐树，就會走k擴(kuò)容邏輯
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
代碼片段四、
/**
* elementData:代表當(dāng)前集合的底層數(shù)組
* minCapacity：當(dāng)前數(shù)組的大小+1
* 所以第一次調(diào)用list的add()方法的時候鸿脓，elementData是空的抑钟，minCapacity為1
* 返回DEFAULT_CAPACITY涯曲，集合的初始化大小 10
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
代碼片段五、
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
// 集合現(xiàn)在的大小
int oldCapacity = elementData.length;
// 擴(kuò)容邏輯就是：oldCapacity(老的大小) + oldCapacity/ 2
// 比如原來大小10在塔，現(xiàn)在擴(kuò)容掀抹，就是10 + 10/2 = 15
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的倉位15大于minCapacity
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:
// 這里進(jìn)行數(shù)組拷貝，完成老數(shù)組到新數(shù)組的拷貝
elementData = Arrays.copyOf(elementData, newCapacity);
}
代碼片段六心俗、
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
// 如下面代碼，如果index超過了size蓉驹，就會報出來一個數(shù)組越界異常
rangeCheck(index);
// 返回index下的元素城榛，所以，集合的讀是很快的
return elementData(index);
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
代碼片段七态兴、
/**
* 在指定位置插入一個新的元素狠持，然后指定位置以后的元素進(jìn)行重新排序
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 檢查index是否越界，越界則拋出角標(biāo)越界異常
rangeCheckForAdd(index);
// 代碼片段四中的檢查是否需要擴(kuò)容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 這里的數(shù)組拷貝瞻润，然后index后面的元素向后移動
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 將新的元素放入到指定index中
elementData[index] = element;
size++;
}
/**
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
// 檢查index是否越界
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
三喘垂、總結(jié)
- 其實(shí)對于大部分Java的程序員來說，ArrayList的基本原理都沒啥問題绍撞，但是我們?yōu)槭裁催€要繼續(xù)分析ArrayList的源碼呢正勒，主要是，隨著我們工作年限的增加傻铣，在去面試的話章贞，基本上都是往死里問，所以對于基礎(chǔ)的集合非洲，我們還是很有必要來分析一下他的源碼
- 我們僅僅是研究一下核心源碼鸭限，如果對ArrzyList中1500行左右的源碼全部剖析的話，首先我們肯定記不住這么多两踏，其次還可能忽略核心功能败京，如果對于核心功能已經(jīng)了解的話，其他的API其實(shí)都不難的
