目錄
- 兩者相似的地方
- 兩者的差別
- 1. 默認容量大小及其他引數的區別
- 2. 擴容時的區別
- 3. 存入資料時的區別
- 4. 重點匯總
HashMap和ArrayList這兩個類由于在日常開發中會經常使用，所以是比較常見的面試考查點，面試官也會通過詢問該部分內容了解對這部分的熟悉程度，
兩者相似的地方
兩者是有一定的相似性的，例如：
-
都有默認初始容量及最大值
-
都會進行擴容操作
-
底層實作都是陣列（HashMap為鏈表陣列，JDK8之后為鏈表-紅黑樹陣列，本質上依然是陣列結構）
但是兩者又是有很大差別，最大的差別就是HashMap會進行Hash運算，ArrayList則不會，具體容量默認值和負載因子，以及擴容策略也是有很大區別，下面就進行一個對比，以便于更清晰地展示這兩個資料集合的特點和差別，
*說明: 以下均基于JDK1.8原始碼
兩者的差別
1. 默認容量大小及其他引數的區別
首先，HashMap和ArrayList中均設定了默認的容量值，如下：
//HashMap的默認容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//ArrayList的默認容量
private static final int DEFAULT_CAPACITY = 10;
可以看到，兩者從代碼風格上就有一定差異，HashMap沒有使用訪問修飾符，ArrayList使用了，很明顯是兩個不同風格的開發人員進行的開發，至于HashMap為什么使用16，建議看這篇文章https://www.iteye.com/topic/539465，ArrayList為什么默認為10呢？看網上說的，認為這是一個比較折中的方式，設定為1的話太小，設定為100的話又會太多，所以就設定為10，其實從日常生活經驗也可以感覺到，10就是日常事務中的一個分界線，10以內是少，10以上就算多了，我想這就是設定默認10的原因，
除了默認容量之外，HashMap和ArrayList在進行資料擴容的時候，都設定了一些標準，具體來說就是三個方面：
- 達到什么條件時擴容
- 擴容多少
- 最大值是多少
看原始碼，在HashMap中：
//HashMap的負載因子，默認值0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap容量的最大值，默認值2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
在ArrayList中：
//ArrayList默認最大陣列值，默認值2的31次方-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
可以看到HashMap和ArrayList中都規定了默認最大容量值，且不一致，HashMap最大容量值為2的30次方，即Integer.MAX_VALUE的一半，ArrayList則是接近Integer.MAX_VALUE，為Integer.MAX_VALUE - 8;
同時，HashMap包含DEFAULT_LOAD_FACTOR，而ArrayList則沒有，該值為負載因子，用于決定HashMap中元素資料達到多少時進行擴容，默認為0.75，則達到現有容量的0.75即會對容量進行擴容，
到這里，依然還有兩個問題：
-
HashMap是達到0.75時擴容，ArrayList達到多少呢？
-
HashMap和ArrayList擴容是分別擴容多少呢？
來看擴容的原始碼：
2. 擴容時的區別
先看HashMap擴容的原始碼：
/**
* Initializes or doubles table size. If null, allocates in accord with initial
* capacity target held in field threshold. Otherwise, because we are using
* power-of-two expansion, the elements from each bin must either stay at same
* index, or move with a power of two offset in the new table.
* 初始化或加倍表大小，如果為空，則根據欄位threshold中的initialcapacity目標進行分配，否則，因為 * 我們使用的是二次冪展開，所以每個bin中的元素要么保持在相同的下標，要么在新表中以二次冪偏移量移動，
* @return the table
*/
final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;//原table
int oldCap = (oldTab == null) ? 0 : oldTab.length;//原容量
int oldThr = threshold;//原閾值
int newCap, newThr = 0;//新容量、新閾值
if (oldCap > 0) {//原容量大于0
if (oldCap >= MAXIMUM_CAPACITY) {//原容量大于等于最大容量
threshold = Integer.MAX_VALUE;//Integer.MAX_VALUE作為閾值
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//原容量的2倍小于最大容量，且原容量大于默認初始化容量
newThr = oldThr << 1; //新閾值為原閾值的2倍（即原容量擴容，閾值也跟著擴容）
} else if (oldThr > 0) // 原閾值大于0
newCap = oldThr;//將原閾值作為新容量
else { // 初始化容量為0，使用默認容量和默認閾值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//新閾值為0
float ft = (float) newCap * loadFactor;//新容量乘以負載因子獲得臨時變數ft
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);//新容量小于最大容量并且臨時變數ft也小于最大容量，將ft作為新閾值，否則將Integer.MAX_VALUE作為新閾值
}
threshold = newThr;//新閾值作為閾值
@SuppressWarnings({ "rawtypes", "unchecked" })
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];//根據新容量創建新陣列
table = newTab;//新陣列作為HashMap的陣列
if (oldTab != null) {//以下為將原陣列中的資料進行重新分配
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
可以看到注釋就已經很明確的說明了，該方法"初始化或加倍表大小"，代碼中table即HashMap中用于存放key的hash值的陣列，所以，HashMap是進行2倍擴容，至于為什么是2倍擴容，這就和之前說的HashMap默認值為16一樣，都是為了減少Hash的沖突，使陣列各項能夠比較均勻地分配資料，
再看ArrayList的擴容原始碼：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*增加容量，以確保它至少可以容納由最小容量引數指定的元素數，
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//相當于oldCapacity*1.5
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);
}
ArrayList的注釋就和HashMap不一樣了，ArrayList說的是“增加容量，以確保它至少可以容納由最小容量引數指定的元素數”，雖然到這我們還并不能了解擴容的條件，但是我們卻可以知道擴容的策略是如何的，
-
根據
int newCapacity = oldCapacity + (oldCapacity >> 1);可知，是將原容量的1.5倍作為新容量的值newCapacity -
若新分配的容量依然小于minCapacity，則將minCapacity作為新的容量值
-
若新分配的容量值大于ArrayList的最大容量值MAX_ARRAY_SIZE，呼叫hugeCapacity()方法，該方法原始碼如下：
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // 超過Integer.MAX_VALUE，min會為負數 throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }原始碼中，minCapacity < 0的情況即是minCapacity 超出Integer.MAX_VALUE的情況，該情況下拋出記憶體溢位錯誤；否則會將最大容量設定為為Integer.MAX_VALUE，
-
呼叫Arrays.copyOf()方法對把陣列元素進行轉移，并將陣列大小設定為newCapacity
總結一下這兩者的差別：
- HashMap普通情況下是以2倍的容量進行擴容的，ArrayList則是以1.5倍進行擴容的；
- ArrayList擴容1.5倍后的容量依然小于傳入的minCapacity時，將minCapacity作為擴容的容量
- HashMap和ArrayList最大可設定的容量值都是Integer.MAX_VALUE,容量超過時ArrayList會拋出記憶體溢位錯誤，HashMap則是判斷原閾值是否大于0，閾值大于0則將原閾值作為新容量，否則重新將HashMap的容量和閾值設定為默認值；
- HashMap設定閾值為0時，會自動轉換為容量與負載因子的乘積（newCap * loadFactor）；
綜上，已經解答了如何擴容的問題，但是ArrayList什么情況下擴容還是個問題；另外，如果將另一個ArrayList的元素存入或者另一個HashMap的元素存入，和單個元素存放有什么不同，這些依然是個問題，
3. 存入資料時的區別
接著分析原始碼，可以看到ArrayList中呼叫grow(minCapacity) 的代碼如下
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 當minCapacity大于當前陣列容量長度（elementData.length）時，呼叫擴容方法grow(minCapacity);
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
繼續
private void ensureCapacityInternal(int minCapacity) {
//傳入當前HashMap的陣列和minCapacity作為引數
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
再向上查看
/**
* 添加單個資料元素
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 此處為呼叫ensureCapacityInternal(int minCapacity)方法，minCapacity為size+1
elementData[size++] = e;
return true;
}
/**
* 將一個集合內的資料元素都添加到ArrayList中
*/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 此處為呼叫ensureCapacityInternal(int minCapacity)方法，minCapacity為size+numNew
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
可以看到以上兩個方法都呼叫了ensureCapacityInternal，不難理解，由于add()方法每次都只添加一個元素所以minCapacity為size + 1；addAll()方法每次需要添加多個元素，所以minCapacity為size+numNew，而并不是回圈呼叫add()進行添加，此時，也就可以解答一個問題，”ArrayList什么時候進行擴容“，答案就是根據傳入的minCapacity的大小判斷是否需要擴容，minCapacity小于當前容量則不需要擴容，大于當前容量才會開始擴容，擴容后的容量大于minCapacity則擴容為原來的1.5倍，否則擴容到minCapacity，
舉個例子：當當前容量為10并呼叫add()方法存入1個元素時，容量會擴容到10+10*0.5=15;
當當前容量為10并呼叫addAll()方法存入6個元素時，由于10+6是大于15的，所以容量會直接擴容至16，
此時，再對比HashMap的存入資料的原始碼
/**
* 存入一個資料元素
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//當++size大于threshold時候，進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
*
* 將另一個Map中的元素存入
*
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float) s / loadFactor) + 1.0F;
int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold)
//當s大于threshold時候，進行擴容
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
可以看到呼叫putVal()方法存入一個資料元素時，if (++size > threshold) resize(); ，存入多個資料元素時候，if (s > threshold) resize();
這里可以看到和ArrayList一樣，存放單個資料元素和多個資料元素時，擴容的判斷都不是一個個添加的，但具體實作上又是完全不同的：
- HashMap是與閾值對比，而非ArrayList的與當前陣列容量進行對比
- HashMap存入單個資料元素時，將當前已存資料量 size 與閾值 TREEIFY_THRESHOLD 進行對比，存入多個資料元素時并沒有像ArrayList一樣使用（size+存入的map的size）與閾值進行對比，而是直接將存入的map的size只 s 與閾值進行對比
- HashMap存入多個是呼叫了putVal()方法，而ArrayList并不是
從以上這些可以看到，HashMap和ArrayList雖然都是一個會自動擴容的結構，但無論從設計思想和具體代碼實作上都有著不小的差別，對兩者進行對比可以比較清晰的看到兩者的差異，從而更方便地進行區別記憶，
另外需要注意的一點是，HashMap中是鏈表轉換為紅黑樹的標準是鏈表中的元素個數為8，紅黑樹退化為鏈表標準則為元素個數為6，并不不一致！
4. 重點匯總
包括以下幾點：
- 默認容量大小，ArrayList是10，HashMap是16
- 進行擴容時，ArrayList是和當前容量進行對比，HashMap是和當前容量*負載因子（默認為0.75）得到的閾值進行對比
- 進行擴容時，ArrayList擴容到原來的1.5倍，HashMap擴容到原來的2倍
- 進行擴容時，擴容的數值大于最大容量時候，判斷是否大于Integer.MAX_VALUE，ArrayList大于的話直接拋出記憶體溢位錯誤；HashMap判斷原閾值是否大于Integer.MAX_VALUE，原閾值不大于則將新容量設定為原閾值，新閾值設定為新容量的0.75；原閾值大于則將HashMap新容量和新閾值重新設定為默認值，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255567.html
標籤：java
上一篇：執行緒安全（三）Atomic是什么？ Atomic如何保證原子性？ Atomic比較案例 圖文解釋整個CAS程序 Atomic適用場景 Atomic缺點
下一篇：圖書管理系統