Java集合擴(kuò)容策略詳解

Java集合框架中的集合類（如ArrayList、LinkedList、HashSet等）會根據(jù)需要自動調(diào)整其大小，這種調(diào)整過程稱為擴(kuò)容。當(dāng)集合中的元素?cái)?shù)量超過當(dāng)前容量時，集合會進(jìn)行擴(kuò)容操作。不同的集合類有不同的擴(kuò)容策略，但它們的基本原理是相似的。下面詳細(xì)介紹Java集合的擴(kuò)容策略。

1. ArrayList擴(kuò)容策略：

   • ArrayList是基于數(shù)組實(shí)現(xiàn)的動態(tài)數(shù)組，其默認(rèn)初始容量為16。
   • 當(dāng)向ArrayList中添加元素時，如果其當(dāng)前容量不足以容納新元素，ArrayList會進(jìn)行擴(kuò)容操作。
   • ArrayList的擴(kuò)容策略是將其容量增加到原來的1.5倍加2。即，新的容量 newCapacity = oldCapacity + (oldCapacity >> 1) + 2。這里的 >> 是右移操作符，相當(dāng)于除以2。
   • 擴(kuò)容后，ArrayList會創(chuàng)建一個新的數(shù)組，并將原數(shù)組中的元素復(fù)制到新數(shù)組中。

2. LinkedList擴(kuò)容策略：

   • LinkedList是基于雙向鏈表實(shí)現(xiàn)的，其內(nèi)部使用一個雙向鏈表來存儲元素，因此不存在擴(kuò)容問題。
   • 當(dāng)需要添加元素時，LinkedList會在鏈表的末尾添加新節(jié)點(diǎn)。如果鏈表長度超過特定閾值（默認(rèn)為8），LinkedList會創(chuàng)建一個新的鏈表，并將原鏈表中的所有節(jié)點(diǎn)復(fù)制到新鏈表中。這個閾值是LinkedList內(nèi)部的一個優(yōu)化策略，用于減少鏈表節(jié)點(diǎn)的復(fù)制操作。

3. HashSet擴(kuò)容策略：

   • HashSet是基于哈希表實(shí)現(xiàn)的，其默認(rèn)初始容量為16。
   • 當(dāng)向HashSet中添加元素時，如果其當(dāng)前容量不足以容納新元素（即哈希沖突導(dǎo)致新元素需要被存儲在一個已有的桶中），HashSet會進(jìn)行擴(kuò)容操作。
   • HashSet的擴(kuò)容策略與ArrayList類似，也是將其容量增加到原來的1.5倍加2。即，新的容量 newCapacity = oldCapacity + (oldCapacity >> 1) + 2。
   • 擴(kuò)容后，HashSet會創(chuàng)建一個新的哈希表，并將原哈希表中的所有元素重新哈希到新哈希表中。

需要注意的是，雖然上述集合類在擴(kuò)容時會增加其容量，但在實(shí)際應(yīng)用中，我們很少需要直接關(guān)心集合的容量大小。集合類提供了方便的方法（如 ArrayList.ensureExplicitCapacity(int minCapacity)、HashSet.ensureCapacity(int minCapacity)）來設(shè)置集合的最小容量，從而在一定程度上控制擴(kuò)容行為。然而，在大多數(shù)情況下，讓集合自動管理其容量是最佳實(shí)踐。