1. 首頁 > 生活百科 > >

Java集合精選常見面試題( 四 )

生活百科

minCapacity - elementData.length > 0成立，所以會進入 grow(minCapacity) 方法 。

  • 當 add 第 2 個元素時 ， minCapacity 為 2，此時 e lementData.length(容量)在添加第一個元素后擴容成 10 了 。此時，minCapacity - elementData.length > 0 不成立 ， 所以不會進入 （執行）grow(minCapacity) 方法 。
  • 添加第 3、4···到第 10 個元素時，依然不會執行 grow 方法，數組容量都為 10 。
    • 直到添加第 11 個元素 ， minCapacity(為 11)比 elementData.length（為 10）要大 。進入 grow 方法進行擴容 。
    grow()
    /*** 要分配的最大數組大小*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** ArrayList擴容的核心方法 。*/private void grow(int minCapacity) {// oldCapacity為舊容量，newCapacity為新容量int oldCapacity = elementData.length;//將oldCapacity 右移一位，其效果相當于oldCapacity /2，//我們知道位運算的速度遠遠快于整除運算 ， 整句運算式的結果就是將新容量更新為舊容量的1.5倍，int newCapacity = oldCapacity + (oldCapacity >> 1);//然后檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當作數組的新容量，if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量大于 MAX_ARRAY_SIZE，進入(執行) `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 = https://www.huyubaike.com/biancheng/Arrays.copyOf(elementData，newCapacity);}int newCapacity = oldCapacity + (oldCapacity >> 1)，所以 ArrayList 每次擴容之后容量都會變為原來的 1.5 倍左右（oldCapacity 為偶數就是 1.5 倍 ， 否則是 1.5 倍左右）！ 奇偶不同，比如 ：10+10/2 = 15，33+33/2=49 。如果是奇數的話會丟掉小數.
    >（移位運算符）：>>1 右移一位相當于除 2，右移 n 位相當于除以 2 的 n 次方 。這里 oldCapacity 明顯右移了 1 位所以相當于 oldCapacity /2 。對于大數據的 2 進制運算 ， 位移運算符比那些普通運算符的運算要快很多，因為程序僅僅移動一下而已，不去計算，這樣提高了效率，節省了資源
    我們再來通過例子探究一下grow() 方法 ：
    • 當 add 第 1 個元素時，oldCapacity 為 0 ， 經比較后第一個 if 判斷成立，newCapacity = minCapacity(為 10) 。但是第二個 if 判斷不會成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，則不會進入 hugeCapacity 方法 。數組容量為 10，add 方法中 return true，size 增為 1 。
    • 當 add 第 11 個元素進入 grow 方法時，newCapacity 為 15，比 minCapacity（為 11）大，第一個 if 判斷不成立 。新容量沒有大于數組最大 size ， 不會進入 hugeCapacity 方法 。數組容量擴為 15，add 方法中 return true，size 增為 11 。
    • 當第16個元素進入容器時再次擴容
    這里補充一點比較重要，但是容易被忽視掉的知識點：
    • java 中的 length屬性是針對數組說的，比如說你聲明了一個數組，想知道這個數組的長度則用到了 length 這個屬性.
    • java 中的 length() 方法是針對字符串說，如果想看這個字符串的長度則用到 length() 這個方法.
    • java 中的 size() 方法是針對泛型集合說的，如果想看這個泛型有多少個元素，就調用此方法來查看!
    hugeCapacity()
    從上面 grow() 方法源碼我們知道： 如果新容量大于 MAX_ARRAY_SIZE，進入(執行) hugeCapacity() 方法來比較 minCapacity 和 MAX_ARRAY_SIZE ， 如果 minCapacity 大于最大容量，則新容量則為Integer.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 Integer.MAX_VALUE - 8 。
    private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();//對minCapacity和MAX_ARRAY_SIZE進行比較//若minCapacity大，將Integer.MAX_VALUE作為新數組的大小//若MAX_ARRAY_SIZE大 ， 將MAX_ARRAY_SIZE作為新數組的大小//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}System.arraycopy() 和 Arrays.copyOf()
    閱讀源碼的話，我們就會發現 ArrayList 中大量調用了這兩個方法 。比如：我們上面講的擴容操作以及

    推薦閱讀