您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“java數(shù)據(jù)結(jié)構(gòu)ArrayList是什么”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學(xué)習(xí)“java數(shù)據(jù)結(jié)構(gòu)ArrayList是什么”吧!
ArrayList 是 java 集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自 AbstractList,實現(xiàn)了 List 接口。底層基于數(shù)組實現(xiàn)容量大小動態(tài)變化。允許 null 的存在。同時還實現(xiàn)了 RandomAccess、Cloneable、Serializable 接口,所以ArrayList 是支持快速訪問、復(fù)制、序列化的。
ArrayList 底層是基于數(shù)組來實現(xiàn)容量大小動態(tài)變化的。
/** * The size of the ArrayList (the number of elements it contains). */ private int size; // 實際元素個數(shù) transient Object[] elementData;
注意:上面的 size 是指 elementData 中實際有多少個元素,而 elementData.length 為集合容量,表示最多可以容納多少個元素。
默認(rèn)初始容量大小為 10;
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
這個變量是定義在 AbstractList 中的。記錄對 List 操作的次數(shù)。主要使用是在 Iterator,是防止在迭代的過程中集合被修改。
protected transient int modCount = 0;
下面兩個變量是用在構(gòu)造函數(shù)里面的
/** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
兩個空的數(shù)組有什么區(qū)別呢? We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. 簡單來講就是第一次添加元素時知道該 elementData 從空的構(gòu)造函數(shù)還是有參構(gòu)造函數(shù)被初始化的。以便確認(rèn)如何擴容。
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
注意:注釋是說構(gòu)造一個容量大小為 10 的空的 list 集合,但構(gòu)造函數(shù)了只是給 elementData 賦值了一個空的數(shù)組,其實是在第一次添加元素時容量擴大至 10 的。
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); } }
由以上源碼可見: 當(dāng)使用無參構(gòu)造函數(shù)時是把 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 賦值給 elementData。 當(dāng) initialCapacity 為零時則是把 EMPTY_ELEMENTDATA 賦值給 elementData。 當(dāng) initialCapacity 大于零時初始化一個大小為 initialCapacity 的 object 數(shù)組并賦值給 elementData。
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; } }
將 Collection 轉(zhuǎn)化為數(shù)組并賦值給 elementData,把 elementData 中元素的個數(shù)賦值給 size。 如果 size 不為零,則判斷 elementData 的 class 類型是否為 Object[],不是的話則做一次轉(zhuǎn)換。 如果 size 為零,則把 EMPTY_ELEMENTDATA 賦值給 elementData,相當(dāng)于new ArrayList(0)。
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
由此可見:每次添加元素到集合中時都會先確認(rèn)下集合容量大小。然后將 size 自增 1。ensureCapacityInternal 函數(shù)中判斷如果 elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10。這就是 EMPTY_ELEMENTDATA 與DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的區(qū)別所在。同時也驗證了上面的說法:使用無慘構(gòu)造函數(shù)時是在第一次添加元素時初始化容量為 10 的。ensureExplicitCapacity 中對 modCount 自增 1,記錄操作次數(shù),然后如果 minCapacity 大于 elementData 的長度,則對集合進(jìn)行擴容。顯然第一次添加元素時 elementData 的長度為零。那我們來看看 grow 函數(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); }
很簡單明了的一個函數(shù),默認(rèn)將擴容至原來容量的 1.5 倍。但是擴容之后也不一定適用,有可能太小,有可能太大。所以才會有下面兩個 if 判斷。如果1.5倍太小的話,則將我們所需的容量大小賦值給newCapacity,如果1.5倍太大或者我們需要的容量太大,那就直接拿 newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE
來擴容。然后將原數(shù)組中的數(shù)據(jù)復(fù)制到大小為 newCapacity 的新數(shù)組中,并將新數(shù)組賦值給 elementData。
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(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; }
有以上源碼可知,add(int index, E element),addAll(Collection<? extends E> c),addAll(int index, Collection<? extends E> c) 操作是都是先對集合容量檢查 ,以確保不會數(shù)組越界。然后通過 System.arraycopy() 方法將舊數(shù)組元素拷貝至一個新的數(shù)組中去。
public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } 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; } 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; // clear to let GC do its work }
當(dāng)我們調(diào)用 remove(int index) 時,首先會檢查 index 是否合法,然后再判斷要刪除的元素是否位于數(shù)組的最后一個位置。如果 index 不是最后一個,就再次調(diào)用 System.arraycopy() 方法拷貝數(shù)組。說白了就是將從 index + 1 開始向后所有的元素都向前挪一個位置。然后將數(shù)組的最后一個位置空,size - 1。如果 index 是最后一個元素那么就直接將數(shù)組的最后一個位置空,size - 1即可。 當(dāng)我們調(diào)用 remove(Object o) 時,會把 o 分為是否為空來分別處理。然后對數(shù)組做遍歷,找到第一個與 o 對應(yīng)的下標(biāo) index,然后調(diào)用 fastRemove 方法,刪除下標(biāo)為 index 的元素。其實仔細(xì)觀察 fastRemove(int index) 方法和 remove(int index) 方法基本全部相同。
public E get(int index) { rangeCheck(index); return elementData(index); }
由于 ArrayList 底層是基于數(shù)組實現(xiàn)的,所以獲取元素就相當(dāng)簡單了,直接調(diào)用數(shù)組隨機訪問即可。
有使用過集合的都知道,在用 for 遍歷集合的時候是不可以對集合進(jìn)行 remove操作的,因為 remove 操作會改變集合的大小。從而容易造成結(jié)果不準(zhǔn)確甚至數(shù)組下標(biāo)越界,更嚴(yán)重者還會拋出 ConcurrentModificationException。
foreach 遍歷等同于 iterator。為了搞清楚異常原因,我們還必須過一遍源碼。
public Iterator<E> iterator() { return new Itr(); }
原來是直接返回一個 Itr 對象。
private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
從源碼可以看出,ArrayList 定義了一個內(nèi)部類 Itr 實現(xiàn)了 Iterator 接口。在 Itr 內(nèi)部有三個成員變量。 cursor:代表下一個要訪問的元素下標(biāo)。 lastRet:代表上一個要訪問的元素下標(biāo)。 expectedModCount:代表對 ArrayList 修改次數(shù)的期望值,初始值為 modCount。
下面看看 Itr 的三個主要函數(shù)。
hasNext 實現(xiàn)比較簡單,如果下一個元素的下標(biāo)等于集合的大小 ,就證明到最后了。
next 方法也不復(fù)雜,但很關(guān)鍵。首先判斷 expectedModCount 和 modCount 是否相等。然后對 cursor 進(jìn)行判斷,看是否超過集合大小和數(shù)組長度。然后將 cursor 賦值給 lastRet ,并返回下標(biāo)為 lastRet 的元素。最后將 cursor 自增 1。開始時,cursor = 0,lastRet = -1;每調(diào)用一次 next 方法, cursor 和 lastRet 都會自增 1。
remove 方法首先會判斷 lastRet 的值是否小于 0,然后在檢查 expectedModCount 和 modCount 是否相等。接下來是關(guān)鍵,直接調(diào)用 ArrayList 的 remove 方法刪除下標(biāo)為 lastRet 的元素。然后將 lastRet 賦值給 cursor ,將 lastRet 重新賦值為 -1,并將 modCount 重新賦值給 expectedModCount。
下面我們一步一步來分析 Itr 的操作。如圖一所示,開始時 cursor 指向下標(biāo)為 0 的元素,lastRet 指向下標(biāo)為 -1 的元素,也就是 null。每調(diào)用一次 next,cursor 和lastRet 就分別會自增 1。當(dāng) next 返回 “C” 時,cursor 和 lastRet 分別為 3 和 2 [圖二]。
此時調(diào)用 remove,注意是 ArrayList 的 remove,而不是 Itr 的 remove。會將 D E 兩個元素直接往前移動一位,最后一位置空,并且 modCount 會自增 1。從 remove 方法可以看出。[圖三]。
此時 cursor = 3,size = 4,沒有到數(shù)組末尾,所以循環(huán)繼續(xù)。來到 next 方法,因為上一步的 remove 方法對 modCount 做了修改 ,致使 expectedModCount 與 modCount 不相等,這就是 ConcurrentModificationException 異常的原因所在。從例子.png中也可以看出異常出自 ArrayList 中的內(nèi)部類 Itr 中的 checkForComodification 方法。
異常的解決:
直接調(diào)用 iterator.remove() 即可。因為在該方法中增加了 expectedModCount = modCount 操作。但是這個 remove 方法也有弊端。
1、只能進(jìn)行remove操作,add、clear 等 Itr 中沒有。
2、調(diào)用 remove 之前必須先調(diào)用 next。因為 remove 開始就對 lastRet 做了校驗。而 lastRet 初始化時為 -1。
3、next 之后只可以調(diào)用一次 remove。因為 remove 會將 lastRet 重新初始化為 -1
到此,相信大家對“java數(shù)據(jù)結(jié)構(gòu)ArrayList是什么”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。