Arraylist底層是由數(shù)組實(shí)現(xiàn)的,因此ArrayList擁有很好的隨機(jī)訪問(wèn)能力(時(shí)間復(fù)雜度為O(1))硬毕,但是刪除和添加操作性能比較差時(shí)間復(fù)雜度為O(n).因?yàn)锳rrayList底層是數(shù)組實(shí)現(xiàn)的所以刪除和添加操作會(huì)造成數(shù)據(jù)擴(kuò)容或者收縮台妆;ArrayList允許null元素暂刘;
問(wèn)題一:ArrayList怎么初始化如贷?
1.無(wú)參的構(gòu)造方法,不初始化任何容器漾根,給一個(gè)空的數(shù)組
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.帶參數(shù)的構(gòu)造方法厚宰,如果入?yún)⑹且粋€(gè)空集合和無(wú)參構(gòu)造一樣腌巾;
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
3.帶容器大小的構(gòu)造函數(shù)
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);
}
}
問(wèn)題二:ArrayList如何擴(kuò)容?
1.計(jì)算最小的容器大小minCapacity铲觉,現(xiàn)在最小為10澈蝙;
2.新大小newCapacity是oldCapacity的1.5倍(擴(kuò)容邏輯和ArrayMap類似都是1.5倍);
3.新容量newCapacity不超過(guò)Int最大值撵幽;
4.拷貝原始數(shù)據(jù)到新數(shù)組中灯荧;
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);
}
問(wèn)題三:通過(guò)迭代器遍歷ArrayList時(shí)做了什么?
程序員在通過(guò)迭代器遍歷ArrayList的時(shí)候盐杂,主要使用了Iterator的next()和hasNext()方法,現(xiàn)在我們來(lái)看下這兩個(gè)方法逗载;
1.cursor記錄了該迭代器訪問(wèn)游標(biāo)的位置,每調(diào)用一次next方法链烈,cursor的值都會(huì)+1厉斟;
2.limit是返回迭代器中,對(duì)當(dāng)前ArrayList中數(shù)組數(shù)據(jù)量的一個(gè)快照强衡;
3.如果cursor<limit說(shuō)明迭代器中還有可以訪問(wèn)的數(shù)據(jù)
public boolean hasNext() {
return cursor < limit;
}
=====================================================
1.next方法里面實(shí)現(xiàn)了fail-fast機(jī)制,expectedModCount是迭代器返回時(shí)記錄的容器修改次數(shù)擦秽。如果ArrayList被多線程修改了modCount的值就不會(huì)等于之前的expectedModCount,這就說(shuō)明了其他線程修改了這個(gè)容器漩勤。
public E next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}