面試官讓我聊聊 ArrayList 解決了數組的哪些問題
數組簡介
數組對于我們來說并不陌生,在內存中是一塊連續的內存空間,通過下標可以隨機訪問數組元素 如圖一所示,而在JDK中提供了功能更加強大的ArrayList其底層是基于數據實現的,為什么JDK已經提供了數據還要使用ArrayList呢?我們通過比較兩者之間的差異來聊聊ArrayList的優勢
java數組中如何獲取數組實際元素
在面試中經常會問在java中數組長度和ArrayList中的size的區別?
通過下面的代碼我們其實已經看出來數組獲取其長度的時候永遠是在聲明的時候定義的長度,即使數組中只有一個元素,通過下面的輸出有人會問arr[1]輸出的是0,這個是因為 int 類型在java中為基本類型所以在初始化數組時會默認用0填充
在ArrayList中的長度為list中實際元素的數量,這一點跟數組有著明顯的差別,具體如何實現后面會根據源碼分析
數組刪除元素和添加元素
在數組中刪除一個元素后需要移動元素保證數組的連續性,如果刪除的是數組最后一個元素則不需要移動,如果刪除了下標為3的元素后使數組連續則需要將3號元素后的元素依次向前移動
刪除元素后下標為7的元素不再含有有效元素,如果我們使用的數組刪除數據后這些移動的操作需要我們寫相關的代碼來完成,使用ArrayList刪除與數據移動都將自動完成不需要我們手動處理
在數組中添加元素如果插入元素后元素個數超過了數組的長度則會報數組越界的錯誤,這是因為數組的容量是固定的不能動態的增加
如下圖原數組容量為8如果想要成功添加第9個元素則需要將原來數組容量擴大為9然后移動指定位置的元素并將9插入,正因為這樣數組不具有動態性因此在使用數據時需要額外考慮很多數組本身的問題導致不能專注于核心代碼的編寫
ArrayList的出現正式解決了數組存在以下問題
- 動態擴容
- 有效數據長度
- 增加刪除元素后數據移動
- 數據遍歷
結合ArrayList一些面試問題來看下具體源代碼
- ArrayList的默認初始化容量
- 何時擴容
- 擴容容量大小
- 遍歷刪除fast fail原理
- 迭代器刪除為什么不越界
首先看下ArrayList的兩個重要的屬性
- elementData 存儲數據的數組
- size 數組中實際元素個數
- transient Object[] elementData; // non-private to simplify nested class access
- /**
- * The size of the ArrayList (the number of elements it contains).
- *
- * @serial
- */
- private int size;
ArrayList 的構造函數分為有參和無參兩種方式
- 無參構造函數為ArrayList()其初始化后并未分配內存空間而是在第一次add操作時分配
- 有參構造函數ArrayList(int initialCapacity)初始化即分配制定大小內存
- 有參構造函數ArrayList(Collection c) 初始化即分配內存
問題一: 無參初始化默認容量是多少,何時擴容,擴容大小為多少都在下面的注釋中可以找到
具體分析請看下面注釋
- // 默認初始化elementData為空數組
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- //接下來進行add操作
- public boolean add(E e) {
- // 檢查當前數據容量是否充足
- ensureCapacityInternal(size + 1); // Increments modCount!!
- // size 自增可以保證有效元素的個數
- elementData[size++] = e;
- return true;
- }
- //計算容量大小主要用于默認初始化第一次add操作
- private static int calculateCapacity(Object[] elementData, int minCapacity) {
- //默認初始化時elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- // 此處返回默認容量DEFAULT_CAPACITY,此值大小為10
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- return Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- return minCapacity;
- }
- private void ensureCapacityInternal(int minCapacity) {
- ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
- }
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- //檢查是否擴容,如果當前容量大于數組長度進行擴容
- // overflow-conscious code
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
- //根據原來數據長度進行擴容
- //oldCapacity >> 1 位運算相當于 oldCapacity=oldCapacity/2
- //新容量為 newCapacity = oldCapacity + (oldCapacity >> 1);即為原來的1.5倍
- //將老數組中的數據移動到新數組中
- //此處解釋下為何為1.5倍,這是一種折中是對擴容次數和空間大小的折中,如果擴容次數太多會降低效率如果空間太大會浪費空間
- 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);
- }
問題二:數據遍歷,fast-fail,迭代器刪除為什么不越界
在如下代碼注釋中將找到答案
- ArrayList 遍歷支持for,foreach,迭代器遍歷
- fail-fast 機制是java集合(Collection)中的一種錯誤機制。當多個線程對同一個集合的內容進行操作時,就可能會產生fail-fast事件。
例如:當某一個線程A通過iterator去遍歷某集合的過程中,若該集合的內容被其他線程所改變了;那么線程A訪問集合時,就會拋出ConcurrentModificationException異常,產生fail-fast事件。
- //ArrayList 迭代器是通過兩個游標數組的下標
- 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;
- Itr() {} // 如果游標不等于size 代表還有下一個元素 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;
- // 更新lastRet游標為當前數組下標
- 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(); } } }