摘要:表明該類具有序列化功能。關(guān)鍵屬性默認(rèn)初始容量大小指定該容量為時(shí),返回該空數(shù)組。構(gòu)造一個(gè)包含指定的元素的列表,這些元素是按照該的迭代器返回它們的順序排列的。對(duì)擴(kuò)容后的容量進(jìn)行判斷,如果大于允許的最大容量,則將容量再次調(diào)整為。
總覽
底層:ArrayList底層是一個(gè)數(shù)組,可以擴(kuò)容,正因?yàn)樗鼣U(kuò)容,所以它能夠?qū)崿F(xiàn)“動(dòng)態(tài)”增長(zhǎng)
允許null元素
時(shí)間復(fù)雜度:size、isEmpty、get、set、iterator和listIterator方法都以固定時(shí)間運(yùn)行,時(shí)間復(fù)雜度為O(1)。add和remove方法需要O(n)時(shí)間。與用于LinkedList實(shí)現(xiàn)的常數(shù)因子相比,此實(shí)現(xiàn)的常數(shù)因子較低。
容量:ArrayList的容量可以自動(dòng)增長(zhǎng)。
是否同步:ArrayList不同步的。
迭代器:ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的。
定義public class ArrayListextends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
ArrayList
extends AbstractList
implements
List
RandomAccess:RandomAccess 是一個(gè)標(biāo)志接口,表明實(shí)現(xiàn)這個(gè)這個(gè)接口的 List 集合是支持快速隨機(jī)訪問(wèn)的。在 ArrayList 中,我們即可以通過(guò)元素的序號(hào)快速獲取元素對(duì)象,這就是快速隨機(jī)訪問(wèn)。
Cloneable:表明其可以調(diào)用clone()方法來(lái)返回實(shí)例的field-for-field拷貝。
java.io.Serializable:表明該類具有序列化功能。
關(guān)鍵屬性/** * 默認(rèn)初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 指定該ArrayList容量為0時(shí),返回該空數(shù)組。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 當(dāng)調(diào)用無(wú)參構(gòu)造方法,返回的是該數(shù)組。剛創(chuàng)建一個(gè)ArrayList 時(shí),其內(nèi)數(shù)據(jù)量為0。 * 它與EMPTY_ELEMENTDATA的區(qū)別就是:該數(shù)組是默認(rèn)返回的,而后者是在用戶指定容量為0時(shí)返回。 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 保存ArrayList數(shù)據(jù)的數(shù)組 * 該值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA 時(shí),當(dāng)?shù)谝淮翁砑釉剡M(jìn)入ArrayList中時(shí),數(shù)組將擴(kuò)容值DEFAULT_CAPACITY。 */ transient Object[] elementData; /** * ArrayList 所包含的元素個(gè)數(shù) */ private int size;
問(wèn):elementData被標(biāo)記為transient,那么它的序列化和反序列化是如何實(shí)現(xiàn)的呢?
答:ArrayList自定義了它的序列化和反序列化方式。詳情請(qǐng)查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。
ArrayList提供了三種構(gòu)造方法。
ArrayList(int initialCapacity):構(gòu)造一個(gè)指定容量為capacity的空ArrayList。
ArrayList():構(gòu)造一個(gè)初始容量為 10 的空列表。
ArrayList(Collection extends E> c):構(gòu)造一個(gè)包含指定 collection 的元素的列表,這些元素是按照該 collection 的迭代器返回它們的順序排列的。
/** * 帶初始容量參數(shù)的構(gòu)造函數(shù)。(用戶自己指定容量) */ public ArrayList(int initialCapacity) { //初始容量大于0 if (initialCapacity > 0) { //創(chuàng)建initialCapacity大小的數(shù)組 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //創(chuàng)建空數(shù)組 this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 默認(rèn)構(gòu)造函數(shù),DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為0.初始化為10, * 也就是說(shuō)初始其實(shí)是空數(shù)組 當(dāng)添加第一個(gè)元素的時(shí)候數(shù)組容量才變成10 */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 構(gòu)造一個(gè)包含指定集合的元素的列表,按照它們由集合的迭代器返回的順序。 * 如果指定的集合為null,throws NullPointerException。 */ public ArrayList(Collection extends E> c) { elementData = c.toArray(); //如果指定集合元素個(gè)數(shù)不為0 if ((size = elementData.length) != 0) { // c.toArray 可能返回的不是Object類型的數(shù)組所以加上下面的語(yǔ)句用于判斷, if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); //【2】Arrays包含用來(lái)操作數(shù)組(比如排序和搜索)的各種方法。 //copyOf(U[] original, int newLength, Class extends T[]> newType) // 復(fù)制指定的數(shù)組,截取或用 null 填充(如有必要),以使副本具有指定的長(zhǎng)度。 } else { this.elementData = EMPTY_ELEMENTDATA; } }核心方法 get(int index)
步驟:
檢查角標(biāo)
返回元素
/** * 返回此列表中指定位置的元素。 * * @param index 需要返回的元素的索引 * @return list中索引為index的元素 * @throws IndexOutOfBoundsException 如果索引超出size */ public E get(int index) { //越界檢查 rangeCheck(index); return elementData(index); } /** * 檢查給定的索引是否在范圍內(nèi)。 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 返回IndexOutOfBoundsException細(xì)節(jié)信息 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } /** * 返回索引為index的元素 */ @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }add(E e)
步驟:
檢查是否需要擴(kuò)容
插入元素
整個(gè)擴(kuò)容過(guò)程:
首先去檢查一下數(shù)組的容量是否足夠
足夠:直接添加
不足夠:擴(kuò)容
擴(kuò)容到原來(lái)的1.5倍
第一次擴(kuò)容后,如果容量還是小于minCapacity,就將容量擴(kuò)充為minCapacity。
/** * 將指定的元素追加到此列表的末尾。 */ public boolean add(E e) { //確認(rèn)list容量,如果不夠,容量加1。注意:只加1,保證資源不被浪費(fèi) ensureCapacityInternal(size + 1); //這里看到ArrayList添加元素的實(shí)質(zhì)就相當(dāng)于為數(shù)組賦值 elementData[size++] = e; return true; }
擴(kuò)容
/** * ArrayList的擴(kuò)容機(jī)制 * ArrayList的擴(kuò)容機(jī)制提高了性能,如果每次只擴(kuò)充一個(gè), * 那么頻繁的插入會(huì)導(dǎo)致頻繁的拷貝,降低性能,而ArrayList的擴(kuò)容機(jī)制避免了這種情況。 * 如有必要,增加此ArrayList實(shí)例的容量,以確保它至少能容納元素的數(shù)量 * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { // 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA,最小擴(kuò)容量為DEFAULT_CAPACITY,否則為0 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } /** * 數(shù)組容量檢查,不夠時(shí)則進(jìn)行擴(kuò)容。 * * @param minCapacity 想要的最小容量 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA, // 則取minCapacity為DEFAULT_CAPACITY和參數(shù)minCapacity之間的最大值 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } //得到最小擴(kuò)容量 private void ensureCapacityInternal(int minCapacity) { // 獲取默認(rèn)的容量和傳入?yún)?shù)的較大值 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } //判斷是否需要擴(kuò)容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 確保指定的最小容量 > 數(shù)組緩沖區(qū)當(dāng)前的長(zhǎng)度 if (minCapacity - elementData.length > 0) //擴(kuò)容 grow(minCapacity); } /** * 要分配的最大數(shù)組大小 * 為什么要減去8呢? * 因?yàn)槟承¬M會(huì)在數(shù)組中保留一些頭字,嘗試分配這個(gè)最大存儲(chǔ)容量,可能會(huì)導(dǎo)致array容量大于VM的limit,最終導(dǎo)致OutOfMemoryError。 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList擴(kuò)容的核心方法 * * 第一次擴(kuò)容,邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎(chǔ)上增加一半。 * 第一次擴(kuò)容后,如果容量還是小于minCapacity,就將容量擴(kuò)充為minCapacity。 */ private void grow(int minCapacity) { // oldCapacity為舊容量,newCapacity為新容量 int oldCapacity = elementData.length; //將oldCapacity 右移一位,其效果相當(dāng)于oldCapacity /2, //我們知道位運(yùn)算的速度遠(yuǎn)遠(yuǎn)快于整除運(yùn)算,整句運(yùn)算式的結(jié)果就是將新容量更新為舊容量的1.5倍, int newCapacity = oldCapacity + (oldCapacity >> 1); //然后檢查新容量是否大于最小需要容量,若還是小于最小需要容量,那么就把最小需要容量當(dāng)作數(shù)組的新容量, if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //再檢查新容量是否超出了ArrayList所定義的最大容量, //若超出了,則調(diào)用hugeCapacity()來(lái)比較minCapacity和 MAX_ARRAY_SIZE, //如果minCapacity大于MAX_ARRAY_SIZE,則新容量則為Interger.MAX_VALUE,否則,新容量大小則為 MAX_ARRAY_SIZE。 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); } //比較minCapacity和 MAX_ARRAY_SIZE private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
看完了代碼,可以對(duì)擴(kuò)容方法總結(jié)如下:
進(jìn)行空間檢查,決定是否進(jìn)行擴(kuò)容,以及確定最少需要的容量
如果確定擴(kuò)容,就執(zhí)行g(shù)row(int minCapacity),minCapacity為最少需要的容量
第一次擴(kuò)容,邏輯為newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基礎(chǔ)上增加一半。
第一次擴(kuò)容后,如果容量還是小于minCapacity,就將容量擴(kuò)充為minCapacity。
對(duì)擴(kuò)容后的容量進(jìn)行判斷,如果大于允許的最大容量MAX_ARRAY_SIZE,則將容量再次調(diào)整為MAX_ARRAY_SIZE。至此擴(kuò)容操作結(jié)束。
add(int index, E element)步驟:
越界檢查
空間檢查,如果有需要進(jìn)行擴(kuò)容
插入元素
/** * 在此列表中的指定位置插入指定的元素。 * 先調(diào)用 rangeCheckForAdd 對(duì)index進(jìn)行界限檢查;然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大; * 再將從index開(kāi)始之后的所有成員后移一個(gè)位置;將element插入index位置;最后size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); //arraycopy()這個(gè)實(shí)現(xiàn)數(shù)組之間復(fù)制的方法一定要看一下,下面就用到了arraycopy()方法實(shí)現(xiàn)數(shù)組自己復(fù)制自己 //實(shí)現(xiàn)讓index開(kāi)始之后的所有元素后移一個(gè)位置: //elementData:源數(shù)組;index:源數(shù)組中的起始位置;elementData:目標(biāo)數(shù)組;index + 1:目標(biāo)數(shù)組中的起始位置; size - index:要復(fù)制的數(shù)組元素的數(shù)量; System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
add(int index, E e)需要先對(duì)元素進(jìn)行移動(dòng),然后完成插入操作,也就意味著該方法有著線性的時(shí)間復(fù)雜度,即O(n)
remove(int index)步驟:
檢查角標(biāo)
刪除元素
計(jì)算出需要移動(dòng)的個(gè)數(shù),將索引大于index的元素左移一位(左移后,該刪除的元素就被覆蓋了,相當(dāng)于被刪除了)
設(shè)置為null(size-1處),讓Gc回收
/** * 刪除該列表中指定位置的元素。 將任何后續(xù)元素移動(dòng)到左側(cè)(從其索引中減去一個(gè)元素)。 */ public E remove(int index) { //檢查索引是否越界 rangeCheck(index); //結(jié)構(gòu)性修改次數(shù)+1【1】 modCount++; E oldValue = elementData(index); // 刪除指定元素后,需要左移的元素個(gè)數(shù) int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // size減一,然后將索引為size-1處的元素置為null。為了讓GC起作用,必須顯式的為最后一個(gè)位置賦null值 elementData[--size] = null; //從列表中刪除的元素 return oldValue; }
注意:為了讓GC起作用,必須顯式的為最后一個(gè)位置賦null值。上面代碼中如果不手動(dòng)賦null值,除非對(duì)應(yīng)的位置被其他元素覆蓋,否則原來(lái)的對(duì)象就一直不會(huì)被回收。
set( int index, E element)步驟:
檢查角標(biāo)
替代元素
返回舊值
/** * 用指定的元素替換此列表中指定索引的元素。 */ public E set(int index, E element) { //對(duì)index進(jìn)行界限檢查 rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; //返回原來(lái)在這個(gè)位置的元素 return oldValue; }
細(xì)節(jié):
ArrayList是基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的,在增刪時(shí)候,需要數(shù)組的拷貝復(fù)制。
ArrayList的默認(rèn)初始化容量是10,每次擴(kuò)容時(shí)候增加原先容量的一半,也就是變?yōu)樵瓉?lái)的1.5倍
刪除元素時(shí)不會(huì)減少容量,若希望減少容量則調(diào)用trimToSize()
它能存放null值。
和 Vector 不同,ArrayList 中的操作不是線程安全的!所以,建議在單線程中才使用 ArrayList,而在多線程中可以選擇 Vector 或者 CopyOnWriteArrayList。
移位運(yùn)算符
簡(jiǎn)介:移位運(yùn)算符就是在二進(jìn)制的基礎(chǔ)上對(duì)數(shù)字進(jìn)行平移。按照平移的方向和填充數(shù)字的規(guī)則分為三種:<<(左移)、>>(帶符號(hào)右移)和>>>(無(wú)符號(hào)右移)。
作用:對(duì)于大數(shù)據(jù)的2進(jìn)制運(yùn)算,位移運(yùn)算符比那些普通運(yùn)算符的運(yùn)算要快很多,因?yàn)槌绦騼H僅移動(dòng)一下而已,不去計(jì)算,這樣提高了效率,節(jié)省了資源
比如這里:int newCapacity = oldCapacity + (oldCapacity >> 1); 右移一位相當(dāng)于除2,右移n位相當(dāng)于除以 2 的 n 次方。這里 oldCapacity 明顯右移了1位所以相當(dāng)于oldCapacity /2。
另外需要注意的是:
java 中的length 屬性是針對(duì)數(shù)組說(shuō)的,比如說(shuō)你聲明了一個(gè)數(shù)組,想知道這個(gè)數(shù)組的長(zhǎng)度則用到了 length 這個(gè)屬性.
java 中的length()方法是針對(duì)字符串String說(shuō)的,如果想看這個(gè)字符串的長(zhǎng)度則用到 length()這個(gè)方法.
java 中的size()方法是針對(duì)泛型集合說(shuō)的,如果想看這個(gè)泛型有多少個(gè)元素,就調(diào)用此方法來(lái)查看!
內(nèi)部類:
(1)private class Itr implements Iterator(2)private class ListItr extends Itr implements ListIterator (3)private class SubList extends AbstractList implements RandomAccess (4)static final class ArrayListSpliterator implements Spliterator
Itr是實(shí)現(xiàn)了Iterator接口,同時(shí)重寫(xiě)了里面的hasNext(),next(),remove()等方法;
ListItr繼承Itr,實(shí)現(xiàn)了ListIterator接口,同時(shí)重寫(xiě)了hasPrevious(),nextIndex(),previousIndex(),previous(),set(E e),add(E e)等方法,
所以這也可以看出了 Iterator和ListIterator的區(qū)別:ListIterator在Iterator的基礎(chǔ)上增加了添加對(duì)象,修改對(duì)象,逆向遍歷等方法,這些是Iterator不能實(shí)現(xiàn)的。
參考資料:
https://blog.csdn.net/panweiw...
https://segmentfault.com/a/11...
https://github.com/Snailclimb...
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/74475.html
摘要:需要注意的是,通過(guò)構(gòu)造函數(shù)定義初始量是動(dòng)態(tài)數(shù)組的實(shí)際大小。帶容量的構(gòu)造函數(shù)新建一個(gè)容量為的數(shù)組默認(rèn)構(gòu)造函數(shù),默認(rèn)為空構(gòu)造一個(gè)包含指定元素的第一個(gè)構(gòu)造方法使用提供的來(lái)初始化數(shù)組的大小。 前言 今天介紹經(jīng)常使用的一個(gè)Java集合類——ArrayList(基于JDK1.8.0_121)。ArrayList在工作和日常面試中經(jīng)常被使用或者提到。總的來(lái)說(shuō),工作中使用ArrayList主要是因?yàn)閯?dòng)...
摘要:源碼和多線程安全問(wèn)題分析在分析線程安全問(wèn)題之前,我們線對(duì)此類的源碼進(jìn)行分析,找出可能出現(xiàn)線程安全問(wèn)題的地方,然后代碼進(jìn)行驗(yàn)證和分析。即當(dāng)多線程調(diào)用方法的時(shí)候會(huì)出現(xiàn)元素覆蓋的問(wèn)題。 1.ArrayList源碼和多線程安全問(wèn)題分析 在分析ArrayList線程安全問(wèn)題之前,我們線對(duì)此類的源碼進(jìn)行分析,找出可能出現(xiàn)線程安全問(wèn)題的地方,然后代碼進(jìn)行驗(yàn)證和分析。 1.1 數(shù)據(jù)結(jié)構(gòu) ArrayLi...
摘要:部分源碼分析小記底層數(shù)據(jù)結(jié)構(gòu)底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,數(shù)組元素類型為類型,即可以存放所有類型數(shù)據(jù)。初始容量大于初始化元素?cái)?shù)組新建一個(gè)數(shù)組初始容量為為空對(duì)象數(shù)組初始容量小于,拋出異常無(wú)參構(gòu)造函數(shù)。 JDK1.8 ArrayList部分源碼分析小記 底層數(shù)據(jù)結(jié)構(gòu) 底層的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,數(shù)組元素類型為Object類型,即可以存放所有類型數(shù)據(jù)。我們對(duì)ArrayList類的實(shí)例的所有的操作底層都...
摘要:源碼分析類的實(shí)現(xiàn)接口及繼承父類和和都實(shí)現(xiàn)了接口。這個(gè)接口的作用是實(shí)現(xiàn)它能夠支持快速隨機(jī)訪問(wèn)。在取出值的時(shí)候利用范型轉(zhuǎn)為聲明的類型。如果等于則初始化為空如果小于則拋出異常。并且設(shè)置為傳入的大小。常用方法解析的元素?cái)?shù)方法很簡(jiǎn)單直接返回值的大小。 ArrayList源碼分析 類的實(shí)現(xiàn)接口及繼承父類 public class ArrayList extends AbstractList. i...
摘要:同步眾所周知,是同步的而不是,在一些必要的方法上都加了關(guān)鍵字,但是這也會(huì)加大系統(tǒng)開(kāi)銷。中有一個(gè)方法用來(lái)返回一個(gè),以匿名內(nèi)部類的方式實(shí)現(xiàn)的接口和類似,都用作于對(duì)集合進(jìn)行迭代,不過(guò)沒(méi)有刪除功能,已經(jīng)被取代。還有是的,但不是,這一點(diǎn)很重要。 在上篇文章ArrayList源碼淺析中分析了一下 ArrayList的源碼和一些重要方法,現(xiàn)在對(duì)比 ArrayList,總結(jié)一下 Vector和 Arr...
閱讀 2551·2023-04-26 00:57
閱讀 922·2021-11-25 09:43
閱讀 2228·2021-11-11 16:55
閱讀 2231·2019-08-30 15:53
閱讀 3600·2019-08-30 15:52
閱讀 1468·2019-08-30 14:10
閱讀 3386·2019-08-30 13:22
閱讀 1218·2019-08-29 11:18