ArrayList

前言

這個分類中，将會寫寫java中的集合。集合是java中非常重要而且基礎的内容，因為任何資料必不可少的就是該資料是如何存儲的，集合的作用就是以一定的方式組織、存儲資料。這裡寫的集合，一部分是比較常見的、一部分是不常用但是我個人平時見到過的，一些比較相似的集合（比如hashmap和hashtable）就隻講一個，突出它們之間的差別即可。

最後，要指出一點，對于集合，我認為關注的點主要有四點：

1、是否允許空

2、是否允許重複資料

3、是否有序，有序的意思是讀取資料的順序和存放資料的順序是否一緻

4、是否線程安全

arraylist

arraylist是最常見以及每個java開發者最熟悉的集合類了，顧名思義，arraylist就是一個以數組形式實作的集合，以一張表格來看一下arraylist裡面有哪些基本的元素：

元 素 作 用

private transient object[] elementdata; arraylist是基于數組的一個實作，elementdata就是底層的數組

private int size; arraylist裡面元素的個數，這裡要注意一下，size是按照調用add、remove方法的次數進行自增或者自減的，是以add了一個null進入arraylist，size也會加1

四個關注點在arraylist上的答案

以後每篇文章在講解代碼前，都會先對于一個集合關注的四個點以表格形式做一個解答：

關 注 點 結 論

arraylist是否允許空 允許

arraylist是否允許重複資料 允許

arraylist是否有序 有序

arraylist是否線程安全 非線程安全

添加元素

有這麼一段代碼：

public static void main(string[] args)

{

}

看下底層會做什麼，進入add方法的源碼來看一下：

1 public boolean add(e e) {

2 ensurecapacity(size + 1); // increments modcount!!

3 elementdata[size++] = e;

4 return true;

5 }

先不去管第2行的ensurecapacity方法，這個方法是擴容用的，底層實際上在調用add方法的時候隻是給elementdata的某個位置添加了一個資料而已，用一張圖表示的話是這樣的：

多說一句，我這麼畫圖有一定的誤導性。elementdata中存儲的應該是堆記憶體中元素的引用，而不是實際的元素，這麼畫給人一種感覺就是說elementdata數組裡面存放的就是實際的元素，這是不太嚴謹的。不過這麼畫主要是為了友善起見，隻要知道這個問題就好了。

擴容

我們看一下，構造arraylist的時候，預設的底層數組大小是10：

public arraylist() {

this(10);

那麼有一個問題來了，底層數組的大小不夠了怎麼辦？答案就是擴容，這也就是為什麼一直說arraylist的底層是基于動态數組實作的原因，動态數組的意思就是指底層的數組大小并不是固定的，而是根據添加的元素大小進行一個判斷，不夠的話就動态擴容，擴容的代碼就在ensurecapacity裡面：

複制代碼

public void ensurecapacity(int mincapacity) {

modcount++;

int oldcapacity = elementdata.length;

if (mincapacity > oldcapacity) {

看到擴容的時候把元素組大小先乘以3，再除以2，最後加1。可能有些人要問為什麼？我們可以想：

1、如果一次性擴容擴得太大，必然造成記憶體空間的浪費

2、如果一次性擴容擴得不夠，那麼下一次擴容的操作必然比較快地會到來，這會降低程式運作效率，要知道擴容還是比價耗費性能的一個操作

是以擴容擴多少，是jdk開發人員在時間、空間上做的一個權衡，提供出來的一個比較合理的數值。最後調用到的是arrays的copyof方法，将元素組裡面的内容複制到新的數組裡面去：

public static t[] copyof(u[] original, int newlength, class<? extends t[]> newtype) {

用一張圖來表示就是這樣的：

删除元素

接着我們看一下删除的操作。arraylist支援兩種删除方式：

1、按照下标删除

2、按照元素删除，這會删除arraylist中與指定要删除的元素比對的第一個元素

對于arraylist來說，這兩種删除的方法差不多，都是調用的下面一段代碼：

int nummoved = size - index - 1;

if (nummoved > 0)

elementdata[--size] = null; // let gc do its work

其實做的事情就是兩件:

1、把指定元素後面位置的所有元素，利用system.arraycopy方法整體向前移動一個位置

2、最後一個位置的元素指定為null，這樣讓gc可以去回收它

比方說有這麼一段代碼：

用圖表示是這樣的：

插入元素

看一下arraylist的插入操作，插入操作調用的也是add方法，比如：

1 public static void main(string[] args)

2 {

3 list list = new arraylist();

4 list.add("111");

5 list.add("222");

6 list.add("333");

7 list.add("444");

8 list.add("555");

9 list.add("666");

10 list.add("777");

11 list.add("888");

12 list.add(2, "000");

13 system.out.println(list);

14 }

有一個地方不要搞錯了，第12行的add方法的意思是，往第幾個元素後面插入一個元素，像第12行就是往第二個元素後面插入一個000。看一下運作結果也證明了這一點：

[111, 222, 000, 333, 444, 555, 666, 777, 888]

還是看一下插入的時候做了什麼：

1 public void add(int index, e element) {

2 if (index > size || index < 0)

3 throw new indexoutofboundsexception(

4 "index: "+index+", size: "+size);

5 ensurecapacity(size+1); // increments modcount!!

6 system.arraycopy(elementdata, index, elementdata, index + 1,

7 size - index);

8 elementdata[index] = element;

9 size++;

10 }

看到插入的時候，按照指定位置，把從指定位置開始的所有元素利用system,arraycopy方法做一個整體的複制，向後移動一個位置（當然先要用ensurecapacity方法進行判斷，加了一個元素之後數組會不會不夠大），然後指定位置的元素設定為需要插入的元素，完成了一次插入的操作。用圖表示這個過程是這樣的：

arraylist的優缺點

從上面的幾個過程總結一下arraylist的優缺點。arraylist的優點如下：

1、arraylist底層以數組實作，是一種随機通路模式，再加上它實作了randomaccess接口，是以查找也就是get的時候非常快

2、arraylist在順序添加一個元素的時候非常友善，隻是往數組裡面添加了一個元素而已

不過arraylist的缺點也十分明顯：

1、删除元素的時候，涉及到一次元素複制，如果要複制的元素很多，那麼就會比較耗費性能

2、插入元素的時候，涉及到一次元素複制，如果要複制的元素很多，那麼就會比較耗費性能

是以，arraylist比較适合順序添加、随機通路的場景。

arraylist和vector的差別

arraylist是線程非安全的，這很明顯，因為arraylist中所有的方法都不是同步的，在并發下一定會出現線程安全問題。那麼我們想要使用arraylist并且讓它線程安全怎麼辦？一個方法是用collections.synchronizedlist方法把你的arraylist變成一個線程安全的list，比如：

list synchronizedlist = collections.synchronizedlist(list);

synchronizedlist.add("aaa");

synchronizedlist.add("bbb");

for (int i = 0; i < synchronizedlist.size(); i++)

另一個方法就是vector，它是arraylist的線程安全版本，其實作90%和arraylist都完全一樣，差別在于：

1、vector是線程安全的，arraylist是線程非安全的

2、vector可以指定增長因子，如果該增長因子指定了，那麼擴容的時候會每次新的數組大小會在原數組的大小基礎上加上增長因子；如果不指定增長因子，那麼就給原數組大小*2，源代碼是這樣的：

int newcapacity = oldcapacity + ((capacityincrement > 0) ?

為什麼arraylist的elementdata是用transient修飾的？

最後一個問題，我們看一下arraylist中的數組，是這麼定義的：

private transient object[] elementdata;

不知道大家有沒有想過，為什麼elementdata是使用transient修飾的呢？關于這個問題，說說我的看法。我們看一下arraylist的定義：

public class arraylist extends abstractlist

看到arraylist實作了serializable接口，這意味着arraylist是可以被序列化的，用transient修飾elementdata意味着我不希望elementdata數組被序列化。這是為什麼？因為序列化arraylist的時候，arraylist裡面的elementdata未必是滿的，比方說elementdata有10的大小，但是我隻用了其中的3個，那麼是否有必要序列化整個elementdata呢？顯然沒有這個必要，是以arraylist中重寫了writeobject方法：

private void writeobject(java.io.objectoutputstream s)

// write out element count, and any hidden stuff

int expectedmodcount = modcount;

s.defaultwriteobject();

for (int i=0; i

每次序列化的時候調用這個方法，先調用defaultwriteobject()方法序列化arraylist中的非transient元素，elementdata不去序列化它，然後周遊elementdata，隻序列化那些有的元素，這樣：

1、加快了序列化的速度

2、減小了序列化之後的檔案大小

不失為一種聰明的做法，如果以後開發過程中有遇到這種情況，也是值得學習、借鑒的一種思路。

====================================================================================================================================

我喜歡程式員，因為他們單純、固執、容易體會到成就感；面對壓力，能夠挑燈夜戰不眠不休；面對困難，能夠迎難而上挑戰自我。他們也會感到困惑與傍徨，但每個程式員的心中都有一個比爾蓋茨或是喬布斯的夢想

“用智慧開創屬于自己的事業”。我想說的是，其實我是一個程式員。。。