前言
本文主要給大家介紹了關于java中arraylist動態擴容的相關內容，分享出來供大家參考學習，下面話不多說了，來一起看看詳細的介紹吧。
arraylist 概述
arraylist是基于數組實現的，是一個動態數組，其容量能自動增長。arraylist不是線程安全的，只能用在單線程環境下。實現了serializable接口，因此它支持序列化，能夠通過序列化傳輸；實現了randomaccess接口，支持快速隨機訪問，實際上就是通過下標序號進行快速訪問；實現了cloneable接口，能被克隆。
動態擴容
一 初始化
首先有三種方式來初始化：
|
1
|
public arraylist(); |
默認的構造器，將會以默認的大小來初始化內部的數組
|
1
|
public arraylist(collection<? extends e> c) |
用一個icollection對象來構造，并將該集合的元素添加到arraylist
|
1
|
public arraylist(int initialcapacity) |
用指定的大小來初始化內部的數組
后兩種方式都可以理解，通過創造對象，或指定大小來初始化內部數據即可。
那我們來重點關注一下無參數構造器的實現過程：
|
1
2
3
4
5
6
7
8
9
|
/** * constructs an empty list with an initial capacity of ten. */ public arraylist() { // defaultcapacity_empty_elementdata是空數組 this.elementdata = defaultcapacity_empty_elementdata; } private static final object[] defaultcapacity_empty_elementdata = {}; |
可以看出它的默認數組為長度為0。而在之前jdk1,6中，無參數構造器代碼是初始長度為10。
jdk6代碼這樣的：
|
1
2
3
4
5
6
7
8
9
10
|
public arraylist() { this(10); } public arraylist(int initialcapacity) { super(); if (initialcapacity < 0) throw new illegalargumentexception("illegal capacity: "+ initialcapacity); this.elementdata = new object[initialcapacity]; } |
接下來，要擴容的話，肯定是在arraylist.add 方法中。我們來看一下具體實現。
二 確保內部容量
我們以無參數構造為例， 初始化時，數組長度為0. 那我現在要添加數據了，數組的長度是怎么變化的？
|
1
2
3
4
5
6
|
public boolean add(e e) { //確保內部容量(通過判斷，如果夠則不進行操作；容量不夠就擴容來確保內部容量) ensurecapacityinternal(size + 1); // ①increments modcount!! elementdata[size++] = e;//② return true;} |
① ensurecapacityinternal方法名的英文大致是“確保內部容量”，size表示的是執行添加之前的元素個數，并非arraylist的容量，容量應該是數組elementdata的長度。ensurecapacityinternal該方法通過將現有的元素個數數組的容量比較。看如果需要擴容，則擴容。
②是將要添加的元素放置到相應的數組中。
下面具體看 ensurecapacityinternal(size + 1);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// ① 是如何判斷和擴容的。private void ensurecapacityinternal(int mincapacity) { //如果實際存儲數組 是空數組，則最小需要容量就是默認容量 if (elementdata == defaultcapacity_empty_elementdata) { mincapacity = math.max(default_capacity, mincapacity); } ensureexplicitcapacity(mincapacity); } private void ensureexplicitcapacity(int mincapacity) { modcount++; //如果數組（elementdata)的長度小于最小需要的容量（mincapacity）就擴容 if (mincapacity - elementdata.length > 0) grow(mincapacity); } /** * default initial capacity. */ private static final int default_capacity = 10; |
以上，elementdata是用來存儲實際內容的數組。minexpand 是最小擴充容量。defaultcapacity_empty_elementdata共享的空數組實例用于默認大小的空實例。根據傳入的最小需要容量mincapacity來和數組的容量長度對比，若mincapactity大于或等于數組容量，則需要進行擴容。
三 擴容
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/* *增加容量，以確保它至少能容納 *由最小容量參數指定的元素數。 * @param mincapacity所需的最小容量 */ private void grow(int mincapacity) { // overflow-conscious code int oldcapacity = elementdata.length; //>>位運算，右移動一位。 整體相當于newcapacity =oldcapacity + 0.5 * oldcapacity // jdk1.7采用位運算比以前的計算方式更快 int newcapacity = oldcapacity + (oldcapacity >> 1); if (newcapacity - mincapacity < 0) newcapacity = mincapacity; //jdk1.7這里增加了對元素個數的最大個數判斷,jdk1.7以前是沒有最大值判斷的，max_array_size 為int最大值減去8（不清楚為什么用這個值做比較） if (newcapacity - max_array_size > 0) newcapacity = hugecapacity(mincapacity); // 最重要的復制元素方法 elementdata = arrays.copyof(elementdata, newcapacity); } |
綜上所述，arraylist相當于在沒指定initialcapacity時就是會使用延遲分配對象數組空間，當第一次插入元素時才分配10（默認）個對象空間。假如有20個數據需要添加，那么會分別在第一次的時候，將arraylist的容量變為10 (如下圖一)；之后擴容會按照1.5倍增長。也就是當添加第11個數據的時候，arraylist繼續擴容變為10*1.5=15(如下圖二)；當添加第16個數據時，繼續擴容變為15 * 1.5 =22個(如下圖四)。：
向數組中添加第一個元素時，數組容量為10.
向數組中添加到第10個元素時，數組容量仍為10.
向數組中添加到第11個元素時，數組容量擴為15.
向數組中添加到第16個元素時，數組容量擴為22.
每次擴容都是通過arrays.copyof(elementdata, newcapacity) 這樣的方式實現的。
對比和總結：
本文介紹了 arraylist動態擴容的全過程。如果通過無參構造的話，初始數組容量為0，當真正對數組進行添加時，才真正分配容量。每次按照1.5倍（位運算）的比率通過copeof的方式擴容。 在jkd1.6中實現是，如果通過無參構造的話，初始數組容量為10，每次通過copeof的方式擴容后容量為原來的1.5倍，以上就是動態擴容的原理。
好了，以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
參考資料：http://blog.csdn.net/u010176014/article/details/52073339
原文鏈接：http://www.cnblogs.com/kuoAT/p/6771653.html
