基礎(chǔ)知識(shí)
數(shù)組是具有相同類型的數(shù)據(jù)的集合，也就是說數(shù)組的所有元素的類型都是相同的衬以，在所有的數(shù)據(jù)結(jié)構(gòu)中缓艳，數(shù)組算是最常見也是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，我們最常見的也就是一維數(shù)組看峻，當(dāng)然還有二維阶淘，三維……，數(shù)組需要先聲明才能使用互妓，數(shù)組的大小一旦確定就不可以在變了溪窒。比如我們聲明一個(gè)長度為10的數(shù)組
int[] array = new int[10];
數(shù)組的下標(biāo)是從0開始的，比如上面數(shù)組的第一個(gè)元素是array[0]冯勉，最后一個(gè)元素是array[9]澈蚌。
我們還可以在聲明的時(shí)候直接對(duì)他進(jìn)行初始化，比如
int[] array = new int[]{1, 2, 3};
上面我們聲明了一個(gè)長度為3的數(shù)組灼狰。
源碼分析
操作數(shù)組的類我們常見的估計(jì)也就是ArrayList了宛瞄，他對(duì)數(shù)組的操作非常簡單，所有的數(shù)據(jù)都會(huì)存放到這個(gè)數(shù)組中
transient Object[] elementData;
我們來看一下他常見的幾個(gè)方法伏嗜，首先是get方法
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
首先判斷是否越界坛悉，如果越界直接拋異常，否則就根據(jù)他的下標(biāo)從數(shù)組中直接返回承绸，在看一下他的set方法
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
和get方法一樣裸影，也是先判斷是否越界，然后再操作军熏，代碼比較簡單轩猩，我們再來看一個(gè)add方法
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
這里也是先判斷是否越界，然后再判斷是否需要擴(kuò)容荡澎，最后在操作均践，接著我們來看一下ensureCapacityInternal方法
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);
}
他的默認(rèn)初始化大小是10
private static final int DEFAULT_CAPACITY = 10;
上面代碼第13行，如果我們需要的空間大于數(shù)組長度的時(shí)候摩幔，說明數(shù)組不夠用了彤委，要進(jìn)行擴(kuò)容，就會(huì)執(zhí)行下面的grow方法或衡，我們來看一下grow方法的代碼
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);
}
代碼也比較簡單焦影，擴(kuò)容的時(shí)候在第4行還會(huì)增加一半的大小车遂，比如原來數(shù)組大小是10，第一次擴(kuò)容后會(huì)是15斯辰。在ArrayList中無論使用add還是remove都會(huì)使用這樣一個(gè)方法
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
這說明對(duì)數(shù)組的查找是比較方便的舶担，但對(duì)數(shù)組的增刪就沒那么方便了，因?yàn)閿?shù)組是一塊連續(xù)的內(nèi)存空間彬呻，如果在前面增加和刪除衣陶，都會(huì)導(dǎo)致后面元素位置的變動(dòng)。
ArraList是線程不安全闸氮，如果使用線程安全的可以用Vector剪况，還有一個(gè)線程安全的類
CopyOnWriteArrayList，他只在add和remove的時(shí)候湖苞，也就是修改數(shù)據(jù)的時(shí)候會(huì)先synchronized拯欧，在get的時(shí)候沒有，我們來看一下代碼
private E get(Object[] a, int index) {
return (E) a[index];
}
我們再來看一下他的add方法
public boolean add(E e) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}
}
他不像ArrayList每次擴(kuò)容的時(shí)候财骨，size都會(huì)增加一半，他是每次add一個(gè)元素的時(shí)候size只會(huì)加1藏姐，同理remove的時(shí)候size只會(huì)減1隆箩。
