您好,登錄后才能下訂單哦!
這篇文章主要介紹“怎么用add方法理解ArrayList的擴(kuò)容機(jī)制”,在日常操作中,相信很多人在怎么用add方法理解ArrayList的擴(kuò)容機(jī)制問題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”怎么用add方法理解ArrayList的擴(kuò)容機(jī)制”的疑惑有所幫助!接下來,請(qǐng)跟著小編一起來學(xué)習(xí)吧!
可快速過
一些基本成員變量:
// 默認(rèn)初始大小 private static final int DEFAULT_CAPACITY = 10; // 空數(shù)組 用于空實(shí)例 private static final Object[] EMPTY_ELEMENTDATA = new Object[0]; // 用于默認(rèn)大小空實(shí)例的共享空數(shù)組實(shí)例。 // 我們把它從EMPTY_ELEMENTDATA數(shù)組中區(qū)分出來,以知道在添加第一個(gè)元素時(shí)容量需要增加多少。 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0]; // 保存ArrayList數(shù)據(jù)的數(shù)組 transient Object[] elementData; // 大小 private int size; // 數(shù)組的最大長(zhǎng)度 private static final int MAX_ARRAY_SIZE = 2147483639;
構(gòu)造方法:
/** * 默認(rèn)初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** *默認(rèn)構(gòu)造函數(shù),使用初始容量10構(gòu)造一個(gè)空列表(無(wú)參數(shù)構(gòu)造) */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 帶初始容量參數(shù)的構(gòu)造函數(shù)。(用戶自己指定容量) */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//初始容量大于0 //創(chuàng)建initialCapacity大小的數(shù)組 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//初始容量等于0 //創(chuàng)建空數(shù)組 this.elementData = EMPTY_ELEMENTDATA; } else {//初始容量小于0,拋出異常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** *構(gòu)造包含指定collection元素的列表,這些元素利用該集合的迭代器按順序返回 *如果指定的集合為null,throws NullPointerException。 */ 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; } }
/** * 將指定的元素追加到此列表的末尾。 */ public boolean add(E e) { // 添加元素之前,先試探,容量夠不夠 // Increments modCount!! 這里有個(gè)failfast機(jī)制 // 簡(jiǎn)而言之就是并發(fā)場(chǎng)景下通過modcount的值判斷當(dāng)前的操作是否是最新的modcount的數(shù)據(jù) ensureCapacityInternal(size + 1); //這里看到ArrayList添加元素的實(shí)質(zhì)就相當(dāng)于為數(shù)組賦值 elementData[size++] = e; return true; }
我們接下來看看這個(gè)“試探容量的方法”ensureCapacityInternal()
怎么實(shí)現(xiàn)的
我們約定一個(gè)值,也就是傳參進(jìn)來的size+1,叫minCapacity
(最小需要容量)
//得到最小擴(kuò)容量 就是你至少要擴(kuò)容至這么多,才能容納下我的數(shù)據(jù) private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 獲取默認(rèn)的容量和傳入?yún)?shù)的較大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }
當(dāng)要add進(jìn)第1個(gè)元素時(shí),minCapacity為1,在Math.max()方法比較后,minCapacity為10。
然后是ensureExplicitCapacity()
:
//判斷是否需要擴(kuò)容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) //調(diào)用grow方法進(jìn)行擴(kuò)容,調(diào)用此方法代表已經(jīng)開始擴(kuò)容了 grow(minCapacity); }
我們來梳理一下:
當(dāng)我們要 add 進(jìn)第 1 個(gè)元素到 ArrayList 時(shí),elementData.length
為0 (因?yàn)檫€是一個(gè)空的 list),因?yàn)閳?zhí)行了 ensureCapacityInternal()
方法 ,所以minCapacity
此時(shí)為 10。此時(shí),minCapacity - elementData.length > 0
成立,所以會(huì)進(jìn)入 grow(minCapacity)
方法,此時(shí)數(shù)組容量變?yōu)?0
當(dāng) add 第 2 個(gè)元素時(shí),minCapacity 為 2,此時(shí) elementData.length(容量)在添加第一個(gè)元素后擴(kuò)容成 10 了。此時(shí),minCapacity - elementData.length > 0
不成立,所以不會(huì)進(jìn)入 (執(zhí)行)grow(minCapacity)
方法。
添加第 3、4···到第10個(gè)元素時(shí),依然不會(huì)執(zhí)行 grow()方法,數(shù)組容量都為10。
直到添加第 11 個(gè)元素,minCapacity(為 11)比 elementData.length(為 10)要大。進(jìn)入 grow 方法進(jìn)行擴(kuò)容。
按照elementData.length
(newCapacity)擴(kuò)容1.5倍,然后看看夠不夠minCapacity
。
不夠的話,newCapacity
就=minCapacity
hugeCapacity()
比較一下newCapacity
是否超過MAX_ARRAY_SIZE
,超過就賦為Integer.MAX_VALUE
然后就進(jìn)行擴(kuò)容,Arrays.copyof
方法
/** * 要分配的最大數(shù)組大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * ArrayList擴(kuò)容的核心方法。 */ 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; // 如果新容量大于 MAX_ARRAY_SIZE,進(jìn)入(執(zhí)行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE, //如果minCapacity大于最大容量 //則新容量則為`Integer.MAX_VALUE`,否則,新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`。 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); }
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴(kuò)容之后容量都會(huì)變?yōu)樵瓉淼?1.5 倍左右(oldCapacity 為偶數(shù)就是 1.5 倍,否則是 1.5 倍左右)! 奇偶不同,比如 :10+10/2 = 15, 33+33/2=49。如果是奇數(shù)的話會(huì)丟掉小數(shù)
tips:
java 中的 length
屬性是針對(duì)數(shù)組說的,比如說你聲明了一個(gè)數(shù)組,想知道這個(gè)數(shù)組的長(zhǎng)度則用到了 length 這個(gè)屬性.
java 中的 length()
方法是針對(duì)字符串說的,如果想看這個(gè)字符串的長(zhǎng)度則用到 length()
這個(gè)方法.
java 中的 size()
方法是針對(duì)泛型集合說的,如果想看這個(gè)泛型有多少個(gè)元素,就調(diào)用此方法來查看!
到此,關(guān)于“怎么用add方法理解ArrayList的擴(kuò)容機(jī)制”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。