【不失業計劃】 Java常見集合擴容機制

Java集合擴容機制

- - - 1、ArrayList
    - 2、Vector
    - 3、Stack
    - 4、HashMap

為什麼需要擴容？即目前集合能容納的資料量達到一個飽和狀态(飽和狀态和加載因子有關)之後，集合需要申請新的存儲空間，即擴容。

常見的需要擴容的集合一般是底層基于數組實作的，連結清單不涉及擴容問題，是以LinkedList等無擴容，常見的有ArrayList、Vector、Stack、HashMap。

加載因子：集合中元素填滿的程度，例如ArrayList加載因子為1，初始容量為10，則當目前元素>=10*1需要進行擴容；HashMap加載因子為0.75，初始容量為16，當目前元素>=16 * 0.75=12時進行擴容。

1、ArrayList

檢視ArrayList源碼可以看到，在ArrayList初始化時，内部表示為一個object類型的數組，預設初始容量為10，加載因子為1；

private static final int DEFAULT_CAPACITY = 10;	//預設大小為10
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;	//ArrayList 在内部的表示即為一個Object類型的數組

初始化ArrayList時，會涉及到兩個構造器：

無參構造器：構造一個初始容量為 10 的空清單。

public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有參構造器：構造一個具有指定初始容量的空清單。

//當傳入的值大于0時，數組的大小即為傳入的值大小，為0時，則為EMPTY_ELEMENTDATA(即0)，小于0則抛出異常。
//initialCapacity不是ArrayList的size()，initialCapacity表示初始容量，size則是實際存放對象的數量。
public ArrayList(int initialCapacity) 
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else {
        if (initialCapacity != 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

此外在源碼中還有另一個構造器，該構造器一般用于構造一個包含指定 collection 的元素的清單，元素按照該 collection 的疊代器傳回它們的順序排列。

public ArrayList(Collection<? extends E> c) {
    this.elementData = c.toArray();
    if ((this.size = this.elementData.length) != 0) {
        if (this.elementData.getClass() != Object[].class) {
            this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
        }
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

擴容時，先進行目前容量長度和元素數量比較，需要擴容即調用grow()方法進行擴容。

public void ensureCapacity(int minCapacity) {
    if (minCapacity > this.elementData.length && (this.elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA || minCapacity > 10)) {		//判斷目前的長度大于了elementData長度，即需要進行擴容。
        ++this.modCount;
        this.grow(minCapacity);	//調用grow方法進行擴容，傳入參數為目前需要長度
    }
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));//調用newCapacity()， 将目前數組中的内容傳給新的數組
}
private Object[] grow() {
    return this.grow(this.size + 1);
}

//擴容核心方法
private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    //對目前數組長度進行擴容：擴容後長度 = 目前長度 + 目前長度二進制進位1(即目前長的1/2)；
    //是以初始化預設長度為10時，後面的每一次擴容後容量為 10、15、22、33、49...
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity - minCapacity <= 0) {
        if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(10, minCapacity);
        } else if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

2、Vector

Vector與ArrayList一樣，是存儲在數組結構中，加載因子為1，初始容量為10。

public Vector(int initialCapacity, int capacityIncrement) {
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    } else {
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
}
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//初始容量10
public Vector() {
    this(10);
}

擴容時，有兩種不同的方式

//判斷進行擴容
public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        ++this.modCount;
        if (minCapacity > this.elementData.length) {
            this.grow(minCapacity);	
        }
    }
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));//将目前的數組複制給擴容後數組
}

private Object[] grow() {
    return this.grow(this.elementCount + 1);
}

擴容時會先對capacityIncrement參數進行判斷

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    //判斷capacityIncrement是否大于0：大于0則擴容為目前長度加capacityIncrement的大小，否則擴容為目前長度的2倍
    int newCapacity = oldCapacity + (this.capacityIncrement > 0 ? this.capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity <= 0) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}
//例如 Vector<String> v = new Vector<String>(); 擴容大小則為10、20、40、80....
//例如 Vector<String> v = new Vector<String>(8,4); 擴容大小則為8、12、16、20、24....

3、Stack

stack繼承自Vector，是以Stack的擴容機制等同于Vector的預設情況，也就是2倍速度擴容，加載因子也為1。

public class Stack<E> extends Vector<E> {
    private static final long serialVersionUID = 1224463164541339165L;

    public Stack() {
    }
    //......
    
}

4、HashMap

HashMap的底層實作根據jdk版本的不同有兩種不同的實作方式，但是共同點是都有數組+連結清單的形式，HashMap預設初始容量為16，加載因子為0.75.

static final int DEFAULT_INITIAL_CAPACITY = 16;	//初始容量
static final float DEFAULT_LOAD_FACTOR = 0.75F; //加載因子

哈希表的擴容方法主要在put新值的時候進行判斷并執行，是以在他的put方法中，由于本地JDK版本為1.8，在1.8中擴容中，初始化後首次插入，先擴容再插入，後面容量達到容量*加載因子時，先插入，再擴容；但是在1.7之前，擴容方式是先判斷進行擴容，再插入資料。

public V put(K key, V value) {
    return this.putVal(hash(key), key, value, false, true);//運用到putVal方法
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    HashMap.Node[] tab;
    int n;
    if ((tab = this.table) == null || (n = tab.length) == 0) {
        n = (tab = this.resize()).length;
    }

    Object p;
    int i;
    //插入資料
    if ((p = tab[i = n - 1 & hash]) == null) {
        tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);
    } else {
       //.....
    }
	//判斷擴容
    ++this.modCount;
    if (++this.size > this.threshold) {
        //size空間不足時，進行resize擴容
        this.resize();
    }

    this.afterNodeInsertion(evict);
    return null;
}

擴容核心在于resize()方法

//resize()是進行擴容的核心函數
final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = this.table;
    int oldCap = oldTab == null ? 0 : oldTab.length;
    int oldThr = this.threshold;
    int newThr = 0;
    int newCap;
    if (oldCap > 0) {
        if (oldCap >= 1073741824) {
            this.threshold = 2147483647;
            return oldTab;
        }
		//擴容大小為原來的兩倍，二進制左移一位，原容量的2倍
        if ((newCap = oldCap << 1) < 1073741824 && oldCap >= 16) {
            newThr = oldThr << 1;
        }
    } else if (oldThr > 0) {
        newCap = oldThr;
    } else {
        newCap = 16;
        newThr = 12;
    }
	//擴容時機
    if (newThr == 0) {
        float ft = (float)newCap * this.loadFactor;
        newThr = newCap < 1073741824 && ft < 1.07374182E9F ? (int)ft : 2147483647;
    }

    this.threshold = newThr;
    HashMap.Node<K, V>[] newTab = new HashMap.Node[newCap];
    this.table = newTab;
    if (oldTab != null) {
        //這部分代碼目前還沒搞懂，個人覺得是擴容後兩個容器之間資料的拷貝，1.8這部分涉及到紅黑樹，目前紅黑樹還是懵逼狀态
    }
    return newTab;
}

【不失業計劃】 Java常見集合擴容機制

Java集合擴容機制

1、ArrayList

2、Vector

3、Stack

4、HashMap

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method