廢話不多說(shuō)，先看下集合結(jié)構(gòu)天揖。今天的三個(gè)主角都是繼承自AbstractList這個(gè)抽象類夺欲，所以他們有很多的相似性（增刪查操作），卻因?yàn)樘匦运杂迷诓煌膱?chǎng)景今膊。接下來(lái)先分別介紹下些阅，再比較說(shuō)明。
Vector :它是一個(gè)封裝好的線程安全的動(dòng)態(tài)數(shù)組斑唬。通過(guò)synchronized對(duì)方法加鎖市埋，以此保證線程安全。Vector集合平時(shí)基本用不到恕刘。如果不是不需要線程安全缤谎，就不要使用，所以這里就不重點(diǎn)說(shuō)了褐着。
ArrayList :平時(shí)Java開(kāi)發(fā)用的最多的就是ArrayList了坷澡，他與Vector相似，內(nèi)部都是通過(guò)數(shù)組來(lái)保存元素含蓉。但是它是線程不安全的所以效率要高于Vector洋访，但是每次超過(guò)了原來(lái)的大小就需要?jiǎng)討B(tài)擴(kuò)容，擴(kuò)展需要進(jìn)行copy谴餐，是一個(gè)耗時(shí)操作姻政。ArrayList擴(kuò)容增加之前的一半大小，而Vector是增加一倍大小岂嗓。
LinkedList：它的內(nèi)部并不是個(gè)動(dòng)態(tài)數(shù)組汁展，而是維護(hù)者一個(gè)雙向列表，數(shù)組在物理空間中是連續(xù)的，鏈表不需要連續(xù)存儲(chǔ)食绿，上個(gè)元素會(huì)保存下個(gè)元素的存儲(chǔ)地址侈咕。所以相對(duì)ArrayList的優(yōu)點(diǎn)就在于，LinkedList的插入刪除的效率很高器紧，如果訪問(wèn)的效率就很低耀销，需要遍歷才可以。所以選擇LinkedList還是ArrayList是需要根據(jù)業(yè)務(wù)來(lái)選擇的铲汪。
這三個(gè)集合都是同一個(gè)父類熊尉，具體用法簡(jiǎn)單相似不一一介紹。以ArrayList為例掌腰，帶著以下的問(wèn)題出發(fā)狰住。
- ArrayList動(dòng)態(tài)數(shù)組的擴(kuò)容流程？
- AbstractList中的Iterator設(shè)計(jì)模式場(chǎng)景齿梁？
- ArrayList的Sort排序算法催植？
一、ArrayList動(dòng)態(tài)數(shù)組的擴(kuò)容流程
先看下ArrayList的一個(gè)構(gòu)造方法勺择，一開(kāi)始就設(shè)置一個(gè)動(dòng)態(tài)數(shù)組大小创南，如果使用ArrayList之前就已經(jīng)知道大致的長(zhǎng)度是多少，就最好使用這個(gè)構(gòu)造方法創(chuàng)建省核，以減少擴(kuò)容的開(kāi)銷稿辙。
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
擴(kuò)容的觸發(fā)動(dòng)機(jī)只有在添加的時(shí)候，發(fā)現(xiàn)原來(lái)的數(shù)據(jù)容量不夠了芳撒，才開(kāi)始擴(kuò)容邓深。找個(gè)add方法作為入口查看未桥。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 核心笔刹，確保容量夠大，就執(zhí)行下一步添加數(shù)據(jù)
elementData[size++] = e;
return true;
}
// 核心方法 minCapacity為數(shù)組大小加一
private void ensureCapacityInternal(int minCapacity) {
// 如果數(shù)組為{}冬耿，也就是一開(kāi)始無(wú)參構(gòu)造方法中給動(dòng)態(tài)數(shù)組賦值{}舌菜，那么就給一個(gè)默認(rèn)的大小，我的源碼是10
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity); // 核心
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) // 所需要的最小的長(zhǎng)度亦镶，比現(xiàn)在的要大日月，那就需要擴(kuò)容
grow(minCapacity);
}
// 真正的擴(kuò)容方法
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新的長(zhǎng)度為之前的1.5倍
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:
// 之間完成copy工作，Arrays是一個(gè)處理數(shù)組的工具類
elementData = Arrays.copyOf(elementData, newCapacity);
}
到此缤骨，就基本知道如何實(shí)現(xiàn)擴(kuò)容的了爱咬，整體比較簡(jiǎn)單，就是判斷數(shù)組夠不夠用了绊起，不過(guò)再多給你一半長(zhǎng)度精拟，完成數(shù)組的copy
二、AbstractList中的設(shè)計(jì)模式之Iterator
個(gè)人理解，迭代器模式蜂绎，就是給數(shù)據(jù)源提供一個(gè)遍歷操作方法栅表，這里就是遍歷操作動(dòng)態(tài)數(shù)組
可以分為兩部分理解，一部分肯定提供一個(gè)Iterator模板师枣，比如next()怪瓶。另一部分是提供數(shù)據(jù)源，并創(chuàng)建一個(gè)具體的Iterator践美，沒(méi)有數(shù)據(jù)源Iterator操作什么了洗贰。
在ArrayList中將Iterator作為ArrayList的內(nèi)部類，這樣就可以持有外部動(dòng)態(tài)數(shù)組的引用了拨脉，就可以直接操作數(shù)據(jù)源了哆姻。
三、ArrayList的Sort排序算法
直接看源碼玫膀，Arrays.sort的內(nèi)部使用的是一種歸并和二分插入排序相結(jié)合的方法TimSort矛缨。
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c); // 給一個(gè)排序規(guī)則Comparator ，和ArrayList數(shù)據(jù)源
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
