ArrayList就是傳說中的動态數組,就是Array的複雜版本,它提供了如下一些好處:動态的增加和減少元素、靈活的設定數組的大小......
認真閱讀本文,我相信一定會對你有幫助。比如為什麼ArrayList裡面提供了一個受保護的removeRange方法?提供了其他沒有被調用過的私有方法?
首先看到對ArrayList的定義:
[java] view plain copy
- public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
從ArrayList<E>可以看出它是支援泛型的,它繼承自AbstractList,實作了List、RandomAccess、Cloneable、java.io.Serializable接口。
AbstractList提供了List接口的預設實作(個别方法為抽象方法)。
List接口定義了清單必須實作的方法。
RandomAccess是一個标記接口,接口内沒有定義任何内容。
實作了Cloneable接口(标記接口,接口内沒有定義任何内容)的類,可以調用Object.clone方法傳回該對象的淺拷貝。
通過實作 java.io.Serializable 接口以啟用其序列化功能。未實作此接口的類将無法使其任何狀态序列化或反序列化。序列化接口沒有方法或字段,僅用于辨別可序列化的語義。
ArrayList的屬性
ArrayList定義隻定義類兩個私有屬性:
[java] view plain copy
- private transient Object[] elementData;
- private int size;
[java] view plain copy
- 很容易了解,elementData存儲ArrayList内的元素,size表示它包含的元素的數量。
- 有個關鍵字需要解釋:transient。
- Java的serialization提供了一種持久化對象執行個體的機制。當持久化對象時,可能有一個特殊的對象資料成員,我們不想用serialization機制來儲存它。為了在一個特定對象的一個域上關閉serialization,可以在這個域前加上關鍵字transient。
- ansient是Java語言的關鍵字,用來表示一個域不是該對象串行化的一部分。當一個對象被串行化的時候,transient型變量的值不包括在串行化的表示中,然而非transient型的變量是被包括進去的。
- 有點抽象,看個例子應該能明白。
[java] view plain copy
- public class UserInfo implements Serializable {
- private static final long serialVersionUID = 996890129747019948L;
- private String name;
- private transient String psw;
- public UserInfo(String name, String psw) {
- this.name = name;
- this.psw = psw;
- }
- public String toString() {
- return "name=" + name + ", psw=" + psw;
- }
- }
- public class TestTransient {
- public static void main(String[] args) {
- UserInfo userInfo = new UserInfo("張三", "123456");
- System.out.println(userInfo);
- try {
- // 序列化,被設定為transient的屬性沒有被序列化
- ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
- "UserInfo.out"));
- o.writeObject(userInfo);
- o.close();
- } catch (Exception e) {
- // TODO: handle exception
- e.printStackTrace();
- }
- try {
- // 重新讀取内容
- ObjectInputStream in = new ObjectInputStream(new FileInputStream(
- "UserInfo.out"));
- UserInfo readUserInfo = (UserInfo) in.readObject();
- //讀取後psw的内容為null
- System.out.println(readUserInfo.toString());
- } catch (Exception e) {
- // TODO: handle exception
- e.printStackTrace();
- }
- }
- }
name=張三, psw=123456
name=張三, psw=null
被标記為transient的屬性在對象被序列化的時候不會被儲存。
接着回到ArrayList的分析中......
ArrayList的構造方法
看完屬性看構造方法。ArrayList提供了三個構造方法:
[java] view plain copy
- public ArrayList(int initialCapacity) {
- super();
- if (initialCapacity < 0)
- throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
- this.elementData = new Object[initialCapacity];
- }
- public ArrayList() {
- this(10);
- }
- public ArrayList(Collection<? extends E> c) {
- elementData = c.toArray();
- size = elementData.length;
- // c.toArray might (incorrectly) not return Object[] (see 6260652)
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- }
elementData = Arrays.copyOf(elementData, size, Object[].class)
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)
- 複制指定的數組,截取或用 null 填充(如有必要),以使副本具有指定的長度。對于在原數組和副本中都有效的所有索引,這兩個數組将包含相同的值。對于在副本中有效而在原數組無效的所有索引,副本将包含 null。當且僅當指定長度大于原數組的長度時,這些索引存在。所得數組屬于 newType 類。
-
- 參數:
-
- 要複制的數組original
-
- 要傳回的副本的長度newLength
-
- 要傳回的副本的類newType
傳回: - 原數組的副本,截取或用 null 填充以獲得指定的長度
-
第一個構造方法使用提供的initialCapacity來初始化elementData數組的大小。
第二個構造方法調用第一個構造方法并傳入參數10,即預設elementData數組的大小為10。
第三個構造方法則将提供的集合轉成數組傳回給elementData(傳回若不是Object[]将調用Arrays.copyOf方法将其轉為Object[])。
ArrayList的其他方法
add(E e)
add(E e)都知道是在尾部添加一個元素,如何實作的呢?
[java] view plain copy
- public boolean add(E e) {
- ensureCapacity(size + 1); // Increments modCount!!
- elementData[size++] = e;
- return true;
- }
書上都說ArrayList是基于數組實作的,屬性中也看到了數組,具體是怎麼實作的呢?
比如就這個添加元素的方法,如果數組大,則在将某個位置的值設定為指定元素即可,如果數組容量不夠了呢?
看到add(E e)中先調用了ensureCapacity(size+1)方法,之後将元素的索引賦給elementData[size],而後size自增。
例如初次添加時,size為0,add将elementData[0]指派為e,然後size設定為1(類似執行以下兩條語句elementData[0]=e;size=1)。
将元素的索引賦給elementData[size]不是會出現數組越界的情況嗎?這裡關鍵就在ensureCapacity(size+1)中了。
根據ensureCapacity的方法名可以知道是確定容量用的。
ensureCapacity(size+1)後面的注釋可以明白是增加modCount的值(加了倆感歎号,應該蠻重要的,來看看)。
[java] view plain copy
- public void ensureCapacity(int minCapacity) {
- modCount++;
- int oldCapacity = elementData.length;
- if (minCapacity > oldCapacity) {
- Object oldData[] = elementData;
- int newCapacity = (oldCapacity * 3)/2 + 1;
- if (newCapacity < minCapacity)
- newCapacity = minCapacity;
- // minCapacity is usually close to size, so this is a win:
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
- }
The number of times this list has been structurally modified.
這是對modCount的解釋,意為記錄list結構被改變的次數(觀察源碼可以發現每次調用ensureCapacoty方法,modCount的值都将增加,但未必數組 結構會改變,是以感覺對modCount的解釋不是很到位)。
增加modCount之後,判斷minCapacity(即size+1)是否大于oldCapacity(即elementData.length),若大于,則調整容量為 max((oldCapacity*3)/2+1 , minCapacity ),調整elementData容量為新的容量,即将傳回一個内容為原數組元素,大小為新容量的 新數組 賦給elementData;否則不做操作。
是以調用ensureCapacity至少将elementData的容量增加的1,是以elementData[size]不會出現越界的情況。
容量的拓展将導緻數組元素的複制,多次拓展容量将執行多次整個數組内容的複制。若提前能大緻判斷list的長度,調用ensureCapacity調整容量,将有效的提高運作速度。
可以了解提前配置設定好空間可以提高運作速度,但是測試發現提高的并不是很大,而且若list原本資料量就不會很大效果将更不明顯。
add(int index, E element)
add(int index,E element)在指定位置插入元素。
[java] view plain copy
- public void add(int index, E element) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size);
- ensureCapacity(size+1); // Increments modCount!!
- System.arraycopy(elementData, index, elementData, index + 1, size - index);
- elementData[index] = element;
- size++;
- }
System.arraycopy
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
src
- 源數組。 srcPos
- 源數組中的起始位置。 dest
- 目标數組。 destPos
- 目标資料中的起始位置。 length
- 要複制的數組元素的數量。 首先判斷指定位置index是否超出elementData的界限,之後調用ensureCapacity調整容量(若容量足夠則不會拓展),調用System.arraycopy将elementData從index開始的size-index個元素複制到index+1至size+1的位置(即index開始的元素都向後移動一個位置),然後将index位置的值指向element。
addAll(Collection<? extends E> c)
[java] view plain copy
- public boolean addAll(Collection<? extends E> c) {
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacity(size + numNew); // Increments modCount
- System.arraycopy(a, 0, elementData, size, numNew);
- size += numNew;
- return numNew != 0;
- }
先将集合c轉換成數組,根據轉換後數組的程度和ArrayList的size拓展容量,之後調用System.arraycopy方法複制元素到elementData的尾部,調整size。根據傳回的内容分析,隻要集合c的大小不為空,即轉換後的數組長度不為0則傳回true。
addAll(int index,Collection<? extends E> c)
[java] view plain copy
- public boolean addAll(int index, Collection<? extends E> c) {
- if (index > size || index < 0)
- throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
- Object[] a = c.toArray();
- int numNew = a.length;
- ensureCapacity(size + numNew); // Increments modCount
- int numMoved = size - index;
- if (numMoved > 0)
- System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
- System.arraycopy(a, 0, elementData, index, numNew);
- size += numNew;
- return numNew != 0;
- }
先判斷index是否越界。其他内容與addAll(Collection<? extends E> c)基本一緻,隻是複制的時候先将index開始的元素向後移動X
(c轉為數組後的長度)個位置(也是一個複制的過程),之後将數組内容複制到elementData的index位置至index+X。
clear()
[java] view plain copy
- public void clear() {
- modCount++;
- // Let gc do its work
- for (int i = 0; i < size; i++)
- elementData[i] = null;
- size = 0;
- }
clear的時候并沒有修改elementData的長度(好不容易申請、拓展來的,憑什麼釋放,留着搞不好還有用呢。這使得确定不再修改list内容之後最好調用trimToSize來釋放掉一些空間),隻是将所有元素置為null,size設定為0。
clone()
傳回此 ArrayList 執行個體的淺表副本。(不複制這些元素本身。)
[java] view plain copy
- public Object clone() {
- try {
- ArrayList<E> v = (ArrayList<E>) super.clone();
- v.elementData = Arrays.copyOf(elementData, size);
- v.modCount = 0;
- return v;
- } catch (CloneNotSupportedException e) {
- // this shouldn't happen, since we are Cloneable
- throw new InternalError();
- }
- }
調用父類的clone方法傳回一個對象的副本,将傳回對象的elementData數組的内容指派為原對象elementData數組的内容,将副本的modCount設定為0。
contains(Object)
[html] view plain copy
- public boolean contains(Object o) {
- return indexOf(o) >= 0;
- }
indexOf方法傳回值與0比較來判斷對象是否在list中。接着看indexOf。
indexOf(Object)
[java] view plain copy
- public int indexOf(Object o) {
- if (o == null) {
- for (int i = 0; i < size; i++)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = 0; i < size; i++)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
- }
通過周遊elementData數組來判斷對象是否在list中,若存在,傳回index([0,size-1]),若不存在則傳回-1。是以contains方法可以通過indexOf(Object)方法的傳回值來判斷對象是否被包含在list中。
既然看了indexOf(Object)方法,接着就看lastIndexOf,光看名字應該就明白了傳回的是傳入對象在elementData數組中最後出現的index值。
[java] view plain copy
- public int lastIndexOf(Object o) {
- if (o == null) {
- for (int i = size-1; i >= 0; i--)
- if (elementData[i]==null)
- return i;
- } else {
- for (int i = size-1; i >= 0; i--)
- if (o.equals(elementData[i]))
- return i;
- }
- return -1;
- }
采用了從後向前周遊element數組,若遇到Object則傳回index值,若沒有遇到,傳回-1。
get(int index)
這個方法看着很簡單,應該是傳回elementData[index]就完了。
[java] view plain copy
- public E get(int index) {
- RangeCheck(index);
- return (E) elementData[index];
- }
但看代碼的時候看到調用了RangeCheck方法,而且還是大寫的方法,看看究竟有什麼内容吧。
[java] view plain copy
- private void RangeCheck(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size);
- }
就是檢查一下是不是超出數組界限了,超出了就抛出IndexOutBoundsException異常。為什麼要大寫呢???
isEmpty()
public boolean isEmpty() { return size == 0; }
直接傳回size是否等于0。
remove(int index)
[java] view plain copy
- public E remove(int index) {
- RangeCheck(index);
- modCount++;
- E oldValue = (E) elementData[index];
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index, numMoved);
- elementData[--size] = null; // Let gc do its work
- return oldValue;
- }
首先是檢查範圍,修改modCount,保留将要被移除的元素,将移除位置之後的元素向前挪動一個位置,将list末尾元素置空(null),傳回被移除的元素。
remove(Object o)
[java] view plain copy
- public boolean remove(Object o) {
- if (o == null) {
- for (int index = 0; index < size; index++)
- if (elementData[index] == null) {
- fastRemove(index);
- return true;
- }
- } else {
- for (int index = 0; index < size; index++)
- if (o.equals(elementData[index])) {
- fastRemove(index);
- return true;
- }
- }
- return false;
- }
首先通過代碼可以看到,當移除成功後傳回true,否則傳回false。 remove(Object o)中通過周遊element尋找是否存在傳入對象,一旦找到就調用fastRemove移除對象。
為什麼找到了元素就知道了index,不通過remove(index)來移除元素呢?因為fastRemove跳過了判斷邊界的處理,因為找到元素就相當于确定了index不會超過邊界,而且fastRemove并不傳回被移除的元素。
下面是fastRemove的代碼,基本和remove(index)一緻。
[java] view plain copy
- private void fastRemove(int index) {
- modCount++;
- int numMoved = size - index - 1;
- if (numMoved > 0)
- System.arraycopy(elementData, index+1, elementData, index,
- numMoved);
- elementData[--size] = null; // Let gc do its work
- }
removeRange(int fromIndex,int toIndex) 從清單中移除索引在
fromIndex
(包括)和
toIndex
(不包括)之間的所有元素。
[java] view plain copy
- protected void removeRange(int fromIndex, int toIndex) {
- modCount++;
- int numMoved = size - toIndex;
- System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
- // Let gc do its work
- int newSize = size - (toIndex-fromIndex);
- while (size != newSize)
- elementData[--size] = null;
- }
執行過程是将elementData從toIndex位置開始的元素向前移動到fromIndex,然後将toIndex位置之後的元素全部置空順便修改size。
這個方法是protected,及受保護的方法,為什麼這個方法被定義為protected呢?
這是一個解釋,但是可能不容易看明白。http://stackoverflow.com/questions/2289183/why-is-javas-abstractlists-removerange-method-protected
先看下面這個例子
[java] view plain copy
- ArrayList<Integer> ints = new ArrayList<Integer>(Arrays.asList(0, 1, 2, 3, 4, 5, 6));
- // fromIndex low endpoint (inclusive) of the subList
- // toIndex high endpoint (exclusive) of the subList
- ints.subList(2, 4).clear();
- System.out.println(ints);
輸出結果是[0, 1, 4, 5, 6],結果是不是像調用了removeRange(int fromIndex,int toIndex)!哈哈哈,就是這樣的。
但是為什麼效果相同呢?是不是調用了removeRange(int fromIndex,int toIndex)呢?
(參考文章: 使用java.util.List.subList時最好小心點http://www.cnblogs.com/gaojing/archive/2012/06/17/java-list-sublist-caution.html)
java.util.List中有一個subList方法,用來傳回一個list的一部分的視圖。
List<E> subList(int fromIndex, int toIndex);
它傳回原來list的從[fromIndex, toIndex)之間這一部分的視圖,之是以說是視圖,是因為實際上,傳回的list是靠原來的list支援的。
是以,你對原來的list和傳回的list做的“非結構性修改”(non-structural changes),都會影響到彼此對方。
所謂的“非結構性修改”,是指不涉及到list的大小改變的修改。相反,結構性修改,指改變了list大小的修改。
那麼,如果涉及到結構性修改會怎麼樣呢?
如果發生結構性修改的是傳回的子list,那麼原來的list的大小也會發生變化;
而如果發生結構性修改的是原來的list(不包括由于傳回的子list導緻的改變),那麼傳回的子list語義上将會是undefined。
在AbstractList(ArrayList的父類)中,undefined的具體表現形式是抛出一個ConcurrentModificationException。
是以,如果你在調用了sublist傳回了子list之後,如果修改了原list的大小,那麼之前産生的子list将會失效,變得不可使用。
tips: 如何删除一個list的某個區段,比如删除list的第2-5個元素?
方法是: 可以利用sublist的幕後還是原來的list的這個特性,比如
list.subList(from, to).clear(); 這樣就可以了。
示例代碼:
public static void main(String[] args) {
for(int i = 0; i < 5; i++){
parentList.add(String.valueOf(i)); // 0 ,1 ,2, 3 ,4
}
List<String> subList = parentList.subList(1, 3);
for(String s : subList){
System.out.println(s);// 1 , 2
}
//non-structural modification by sublist, reflect parentList
subList.set(0, "new 1"); //new 1 , 2
for(String s : parentList){
System.out.println(s);//0, new 1, 2, 3, 4
}
//structural modification by sublist, reflect parentList
subList.add(String.valueOf(2.5)); //new 1 , 2 , 2.5
for(String s : parentList){
System.out.println(s);// 0, new 1, 2, 2.5, 3, 4
}
//non-structural modification by parentList, reflect sublist
parentList.set(2, "new 2");// 0, new 1, new 2, 2.5, 3, 4
for(String s : subList){
System.out.println(s);// new 1, new 2
}
//structural modification by parentList, sublist becomes undefined(throw exception)
parentList.add("undefine");
for(String s : subList){
System.out.println(s);
}
subList.get(0); //java.util.ConcurrentModificationException
set(int index,E element)
[java] view plain copy
- public E set(int index, E element) {
- RangeCheck(index);
- E oldValue = (E) elementData[index];
- elementData[index] = element;
- return oldValue;
- }
首先檢查範圍,用新元素替換舊元素并傳回舊元素。
size()
size()方法直接傳回size。
toArray() 傳回包含此清單中所有元素的數組。
[java] view plain copy
- public Object[] toArray() {
- return Arrays.copyOf(elementData, size);
- }
調用Arrays.copyOf将傳回一個數組,數組内容是size個elementData的元素,即拷貝elementData從0至size-1位置的元素到新數組并傳回。
toArray(T[] a)
[java] view plain copy
- public <T> T[] toArray(T[] a) {
- if (a.length < size)
- // Make a new array of a's runtime type, but my contents:
- return (T[]) Arrays.copyOf(elementData, size, a.getClass());
- System.arraycopy(elementData, 0, a, 0, size);
- if (a.length > size)
- a[size] = null;
- return a;
- }
如果傳入數組的長度小于size,傳回一個新的數組,大小為size,類型與傳入數組相同。
所傳入數組長度與size相等,則将elementData複制到傳入數組中并傳回傳入的數組。
若傳入數組長度大于size,除了複制elementData外,還将把傳回數組的第size個元素置為空。
trimToSize()
[java] view plain copy
- public void trimToSize() {
- modCount++;
- int oldCapacity = elementData.length;
- if (size < oldCapacity) {
- elementData = Arrays.copyOf(elementData, size);
- }
- }
由于elementData的長度會被拓展,size标記的是其中包含的元素的個數。
是以會出現size很小但elementData.length很大的情況,将出現空間的浪費。
trimToSize将傳回一個新的數組給elementData,元素内容保持不變,length與size相同,節省空間。
學習Java最好的方式還必須是讀源碼。讀完源碼你才會發現這東西為什麼是這麼玩的,有哪些限制,關鍵點在哪裡等等。而且這些源碼都是大牛們寫的,你能從中學習到很多。