如有轉(zhuǎn)載請(qǐng)注明出處 http://www.reibang.com/p/7c0fbce086c6
緒論
ArrayList是線程不安全的酥宴，他的底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，ArrayList保存的數(shù)據(jù)是可以重復(fù)的。由于數(shù)組具有下表轧邪，所以他查詢起來(lái)比較快，主要操作方法有add羞海，remove忌愚，get。
add
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
1.在添加數(shù)據(jù)的時(shí)候首先要去擴(kuò)容却邓，如果之前數(shù)組中是空的那么就給他一個(gè)最小長(zhǎng)度10
2.數(shù)組目前不滿足添加數(shù)據(jù)的需要時(shí)硕糊，需要去擴(kuò)容
3.默認(rèn)數(shù)組擴(kuò)容1.5倍
- 大批量添加數(shù)據(jù)的時(shí)候，老數(shù)組擴(kuò)容1.5倍不滿足需求時(shí)腊徙，就把要添加的個(gè)數(shù)作為擴(kuò)容數(shù)組的個(gè)數(shù)
- 如果要添加的數(shù)據(jù)已經(jīng)大于數(shù)組的最大值简十，那么就讓她擴(kuò)容到Integer.MAX_VALUE
最后創(chuàng)建擴(kuò)容之后的數(shù)組，并且把原數(shù)組的值放入新數(shù)組中
remove
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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;
}
先將要溢出的數(shù)據(jù)拿出來(lái)撬腾，然后拿到移除數(shù)據(jù)前的index螟蝙，如果移除的不是最后面的數(shù)據(jù)需要將index+1的數(shù)據(jù)向左移動(dòng)，然后將最后一個(gè)數(shù)據(jù)設(shè)置為null
get
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
直接將數(shù)組中index位置的值拿出來(lái)
數(shù)組
由上面的操作可以看出來(lái)民傻，數(shù)組的查詢很快胰默，添加和刪除的時(shí)候都需要對(duì)數(shù)組進(jìn)行復(fù)制操作，所以效率比較低
數(shù)組查詢快是因?yàn)閿?shù)組的空間都是連續(xù)的漓踢，通過(guò)index直接獲取value
數(shù)組增刪比較慢是因?yàn)樵谠黾拥臅r(shí)候牵署，需要擴(kuò)容，并且將老的數(shù)組放到新數(shù)組中喧半，在刪除的時(shí)候需要將要?jiǎng)h除的位置之后的數(shù)據(jù)向左移動(dòng)奴迅，然后將最后一個(gè)數(shù)據(jù)這只為null。
