?手撕java集合源碼——List篇
閱讀list集合觀察它們底層是如何實(shí)現(xiàn)的，以及集合面試中提出的問題進(jìn)行實(shí)踐。
list集合中常用的類為Arraylist、LinkedLIst。
兩者的區(qū)別
| 區(qū)別 | Arraylist | LinkedList |
|---|---|---|
| 底層實(shí)現(xiàn) | 數(shù)組 | 雙向鏈表 |
| 適用場(chǎng)景 | 增刪操作較少，查找較多 | 增刪效率較高，查找效率較低 |
| 容量大小 | 數(shù)組大小不能超過Integer最大值 | 理論無限增加，實(shí)際size范圍為Integer最大值 |
| 線程安全 | 線程不安全 | 線程不安全 |
| NUll值處理 | 允許添加NUll值 | 允許添加NUll值 |
下面分別對(duì)著源碼來進(jìn)行逐條比較
底層實(shí)現(xiàn)
Arraylist
? ?
....
????private?static?final?long?serialVersionUID = 8683452581122892189L;
????private?static?final?int?DEFAULT_CAPACITY = 10;
????private?static?final?Object[] EMPTY_ELEMENTDATA = new?Object[0];
????private?static?final?Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new?Object[0];
????transient?Object[] elementData;
????private?int?size;
????private?static?final?int?MAX_ARRAY_SIZE = 2147483639;
...
????//構(gòu)造方法1
public?ArrayList(int?var1)?{
????if?(var1 > 0) {
????????this.elementData = new?Object[var1];
????} else?{
????????if?(var1 != 0) {
????????????throw?new?IllegalArgumentException("Illegal Capacity: "?+ var1);
????????}
????????this.elementData = EMPTY_ELEMENTDATA;
????}
}
??//構(gòu)造方法2
public?ArrayList()?{
????????this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
????}
??//構(gòu)造方法3
public?ArrayList(Collection var1)?{
????????this.elementData = var1.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;
????????}
????}ArrayList的三個(gè)構(gòu)造方法分別初始化了ElementData變量不同的值。若傳入?yún)?shù)<=0或者使用無參構(gòu)造函數(shù)會(huì)賦值數(shù)組element對(duì)象一個(gè)長(zhǎng)度為0的Object數(shù)組。
LinkedList
//linkedList集合元素
??transient?int?size = 0;
????transient?Node first;
????transient?Node last;
????
?????private?static?class?Node<E> {
????????E item;
????????Node next;
????????Node prev;
????????Node(Node prev, E element, Node next) {
????????????this.item = element;
????????????this.next = next;
????????????this.prev = prev;
????????}
????}
??//構(gòu)造方法1
???public?LinkedList()?{
????}
??//構(gòu)造方法2
??public?LinkedList(Collection c)?{
????????this();
????????addAll(c);
????} LinkedList內(nèi)部實(shí)現(xiàn)很簡(jiǎn)單只有一個(gè)頭節(jié)點(diǎn)，一個(gè)尾節(jié)點(diǎn)，以及一個(gè)size變量來記錄集合中的元素。Ctrl點(diǎn)入Node。發(fā)現(xiàn)這是一個(gè)泛型類，內(nèi)部保存兩個(gè)指針，指向前后兩個(gè)節(jié)點(diǎn)，E 類型的變量。如果鏈表數(shù)據(jù)為空的話，頭尾節(jié)點(diǎn)是同一個(gè)節(jié)點(diǎn)，本身是 null，指向前后節(jié)點(diǎn)的值也是 null。
總結(jié)
Arraylist和Linkedlist實(shí)現(xiàn)底層都跟數(shù)據(jù)結(jié)構(gòu)有關(guān)系，可以轉(zhuǎn)換為鏈表以及數(shù)組的優(yōu)缺點(diǎn)進(jìn)行兩者的回答，鏈表的擴(kuò)容更加方便，而數(shù)組的查找更加便捷。具體如何可以給面試官講你看到的細(xì)節(jié)。
適用場(chǎng)景
Arraylist
Arraylist底層是使用數(shù)組來進(jìn)行實(shí)現(xiàn)，對(duì)于數(shù)組的查找只要通過下標(biāo)便可以獲得，查找時(shí)間復(fù)雜度為O(1);數(shù)組的刪除操作為刪除該下標(biāo)節(jié)點(diǎn)，并將后續(xù)節(jié)點(diǎn)前移動(dòng)，具體實(shí)現(xiàn)為使用System.arraycopy()方法時(shí)間復(fù)雜度為O(n)。添加方法分為尾部添加以及指定位置添加，尾部添加時(shí)間復(fù)雜度為O(n),指定位置添加與刪除類似。
//查找操作
???public?E get(int?var1)?{
?????//查找范圍判斷 下標(biāo)是否越界
????????this.rangeCheck(var1);
????????return?this.elementData(var1);
????}
????//添加操作
????public?boolean?add(E var1)?{
??????//檢查數(shù)組是否需要擴(kuò)容
????????this.ensureCapacityInternal(this.size + 1);
????????this.elementData[this.size++] = var1;
????????return?true;
????}
????//指定位置添加元素
????public?void?add(int?var1, E var2)?{
??????//指定位置 越界判斷
????????this.rangeCheckForAdd(var1);
????????this.ensureCapacityInternal(this.size + 1);
????????//底層native方法
????????System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
????????this.elementData[var1] = var2;
????????++this.size;
????}
????//刪除方法
????public?E remove(int?var1)?{
????????this.rangeCheck(var1);
????????//modCount 記錄列表結(jié)構(gòu)修改次數(shù)
????????++this.modCount;
????????Object var2 = this.elementData(var1);
????????int?var3 = this.size - var1 - 1;
????????if?(var3 > 0) {
????????????System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
????????}
????????this.elementData[--this.size] = null;
????????return?var2;
????}Linkedlist
Linkedlist底層是使用雙向鏈表來進(jìn)行實(shí)現(xiàn)，所以對(duì)于元素的添加更加靈活，對(duì)于添加操作，有表首添加表尾添加，以及制定位置添加。對(duì)于鏈表的遍歷時(shí)間復(fù)雜度都為O(n),表首添加和表尾添加時(shí)間復(fù)雜度為O(1),查找操作時(shí)間復(fù)雜度為O(n)但是底層有利用二分思想進(jìn)行細(xì)微的優(yōu)化。刪除操作為O(n);
//表首添加 與表尾添加 方法類似 以addfirst為例
public?void?addFirst(E e)?{
????????linkFirst(e);
????}
private?void?linkFirst(E e)?{
????????final?Node f = first;
????????final?Node newNode = new?Node<>(null, e, f);
????????first = newNode;
????????if?(f == null)//表為空，設(shè)置表尾節(jié)點(diǎn)也是這個(gè)元素
????????????last = newNode;
????????else
????????????f.prev = newNode;
????????size++;
????????modCount++;
????}
//查找操作 node方法中使用一次二分判斷進(jìn)行優(yōu)化
public?E get(int?index)?{
????????checkElementIndex(index);
????????return?node(index).item;
????}
Node node(int?index)? {
????????if?(index < (size >> 1)) {
????????????Node x = first;
????????????for?(int?i = 0; i < index; i++)
????????????????x = x.next;
????????????return?x;
????????} else?{
????????????Node x = last;
????????????for?(int?i = size - 1; i > index; i--)
????????????????x = x.prev;
????????????return?x;
????????}
????}
//移除操作分為表首移除和表尾移除，以及指定元素刪除 以指定元素刪除為例
public?boolean?remove(Object o)?{
????//添加時(shí)未對(duì)空進(jìn)行判斷所以移動(dòng)時(shí)進(jìn)行判斷
????????if?(o == null) {
????????????for?(Node x = first; x != null; x = x.next) {
????????????????if?(x.item == null) {
????????????????????unlink(x);
????????????????????return?true;
????????????????}
????????????}
????????} else?{
????????????for?(Node x = first; x != null; x = x.next) {
????????????????if?(o.equals(x.item)) {
????????????????????unlink(x);
????????????????????return?true;
????????????????}
????????????}
????????}
????????return?false;
????} Arraylist 可以從size獲取到列表中當(dāng)元素的個(gè)數(shù)，所以通過Arraylist類中size的大小就可以判斷數(shù)組的大小，其次通過Arraylist的擴(kuò)容函數(shù)也可以發(fā)現(xiàn)這一點(diǎn)，之后會(huì)介紹。同時(shí)創(chuàng)建一個(gè)數(shù)組數(shù)組的容量大小也是跟虛擬機(jī)heap大小相互關(guān)聯(lián)。
public?int?size()?{
????return?this.size; //返回的元素為int型 所以數(shù)組大小被限制為最大2147483647
}//main代碼
public?static?void?main(String[] args) {
????ArrayList a=new?ArrayList<>(100000);
}
//結(jié)果
Error occurred during initialization of VM
GC triggered before VM initialization completed. Try increasing NewSize, current value?1536K. Linkedlist 底層是雙向鏈表，理論上可以無限大。但源碼中，LinkedList 實(shí)際大小用的是 int 類型，這也說明了 LinkedList 不能超過 Integer 的最大值，不然會(huì)溢出。
public?class?LinkedList<E>
????extends?AbstractSequentialList<E>
????implements?List<E>, Deque<E>, Cloneable, java.io.Serializable
{
????transient?int?size = 0;
????......
????......Arraylist和Linkedlist都不是線程安全的。當(dāng)鏈表對(duì)象作為一個(gè)共享變量，多個(gè)線程在任何時(shí)刻下都可以對(duì)鏈表進(jìn)行操作導(dǎo)致數(shù)值覆蓋等問題。只有當(dāng)鏈表對(duì)象作為局部變量的時(shí)候是沒有線程安全問題的。
若想創(chuàng)建一個(gè)線程安全的鏈表可以使用Collections.synchronizedList()方法，底層實(shí)現(xiàn)是將鏈表轉(zhuǎn)換為SynchronizedList類該類的所有方法都帶有Synchronized方法。
Collections.synchronizedList(a);
?//底層實(shí)現(xiàn)
?public?static? List synchronizedList(List list) {
????????return?(list?instanceof?RandomAccess ?
????????????????new?SynchronizedRandomAccessList<>(list) :
????????????????new?SynchronizedList<>(list));
????} Arraylist和Linkedlist類中對(duì)于添加NUll值時(shí)并沒有特殊判斷所以在刪除時(shí)要對(duì)null進(jìn)行判斷。
//Arraylist類 刪除方法
public?boolean remove(Object var1) {
????????int?var2;
????????if?(var1 == null) {
????????????for(var2 = 0; var2 < this.size; ++var2) {
????????????????if?(this.elementData[var2] == null) {
????????????????????this.fastRemove(var2);
????????????????????return?true;
????????????????}
????????????}
????????} else?{
????????????for(var2 = 0; var2 < this.size; ++var2) {
????????????????if?(var1.equals(this.elementData[var2])) {
????????????????????this.fastRemove(var2);
????????????????????return?true;
????????????????}
????????????}
????????}
????????return?false;
????}
//linkedlist類的null值remove方法在適用場(chǎng)景處已經(jīng)舉出，不在重復(fù)難點(diǎn) ：Arraylist擴(kuò)容操作
了解Arraylist擴(kuò)容的最好辦法就是一路debug下去了解擴(kuò)容機(jī)制整體流程。
public?static?void?main(String[] args) {
????????ArrayList a=new?ArrayList<>();
????????a.add(1);
????????a.add(2);
????} Debug分析可得首先進(jìn)行ensureCapacityInternal()方法進(jìn)行size判斷,若數(shù)組為第一次添加元素則初始化數(shù)組大小為10，若數(shù)組size+1后小于數(shù)組容量，就直接添加否則調(diào)用grow()擴(kuò)容函數(shù)。
st=>start: add()
e=>end: 結(jié)束
op=>operation: ensureCapacityInternal() 容量判斷
cond=>condition: Elements數(shù)組是否為空
io=>operation: minCapacity設(shè)置為10
three=>operation: ensureExplicitCapacity(minCapacity)
panduan=>condition: minCapacity>Elements.length
grow=>operation: grow()
st(right)->op(right)->cond
cond(yes)->io(right)->e
cond(no)->panduan
io->three->panduan
panduan(yes,right)->grow->e
panduan(no)->e//擴(kuò)容函數(shù)
private?void?grow(int?minCapacity)?{
????????// overflow-conscious code
????????int?oldCapacity = elementData.length;
????????int?newCapacity = oldCapacity + (oldCapacity >> 1);
????????if?(newCapacity - minCapacity < 0)
1???????????newCapacity = minCapacity;
????????if?(newCapacity - MAX_ARRAY_SIZE > 0)
2???????????newCapacity = hugeCapacity(minCapacity);
????????// minCapacity is usually close to size, so this is a win:
????????elementData = Arrays.copyOf(elementData, newCapacity);
????}擴(kuò)容內(nèi)部使用1.5倍擴(kuò)容來實(shí)現(xiàn) 其中使用右移運(yùn)算符來進(jìn)行0.5倍長(zhǎng)度計(jì)算，使用右移而不是除法，因?yàn)橛?jì)算機(jī)底層右移操作速度更快。如果擴(kuò)容后的數(shù)組大小仍小于要添加元素大小，會(huì)將大小設(shè)置為要添加元素大小.
舉例：先前我們已經(jīng)計(jì)算出來數(shù)組在加入一個(gè)值后，實(shí)際大小是 1，最大可用大小是 10 ，現(xiàn) 在需要一下子加入 15 個(gè)值，那我們期望數(shù)組的大小值就是 16，此時(shí)數(shù)組最大可用大小只有 10，明顯不夠，需要擴(kuò)容，擴(kuò)容后的大小是：10 + 10 ／2 = 15，這時(shí)候發(fā)現(xiàn)擴(kuò)容后的大小仍 然不到我們期望的值 16，這時(shí)候源碼使用上述策略如下：所以最終數(shù)組擴(kuò)容后的大小為 16。
如果遇到大數(shù)組的情況：最好一次性添加元素容量使用addAll(Collection c)方法，而不要使用for循環(huán)add，因?yàn)檠h(huán)add，會(huì)造成多次擴(kuò)容，性能降低。
源碼擴(kuò)容過程有什么值得借鑒的地方？
是擴(kuò)容的思想值得學(xué)習(xí)，通過自動(dòng)擴(kuò)容的方式，讓使用者不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)的變化，封 裝得很好，1.5 倍的擴(kuò)容速度，可以讓擴(kuò)容速度在前期緩慢上升，在后期增速較快，大部分 工作中要求數(shù)組的值并不是很大，所以前期增長(zhǎng)緩慢有利于節(jié)省資源，在后期增速較快時(shí)， 也可快速擴(kuò)容。
擴(kuò)容過程中，有數(shù)組大小溢出的意識(shí)，比如要求擴(kuò)容后的數(shù)組大小，不能小于 0，不能大于 Integer 的最大值。
難點(diǎn)：Arraylist remove方法
先看代碼 猜測(cè)結(jié)果是多少？
public?static?void?main(String[] args) {
????????ArrayList a=new?ArrayList<>();
????????a.add(1);
????????a.add(1);
????????a.add(1);
????????a.add(1);
????????for?(int?i = 0; i < a.size(); i++) {
????????????if(a.get(i)==1){
????????????????a.remove(i);
????????????}
????????}
????????System.out.println(a.size());
????} 輸出結(jié)果為2，而不是0，原因是底層在remove后調(diào)用System.copyOf()方法進(jìn)行復(fù)制，將刪除Element[0]后，放在Element[1]的值放在Element[0]處，使得原先Element[1]元素未被刪除。
如果使用foreach()方法結(jié)果如何？
for?(int?i:a) {
????????????if(i==1){
????????????????a.remove(i);
????????????}
????????}輸出結(jié)果為Exception in thread "main" java.util.ConcurrentModificationException
再次Debug進(jìn)去走一遍流程，哪里出了問題。
foreach的內(nèi)部實(shí)現(xiàn)是使用Iterator迭代器來實(shí)現(xiàn)。因?yàn)樵鰪?qiáng) for 循環(huán)過程其實(shí)調(diào)用的就是迭代器的 next () 方法，當(dāng)你調(diào)用list#remove () 方 法 進(jìn) 行 刪 除 時(shí) ， modCount 的 值 會(huì) +1 ， 而 這 時(shí) 候 迭 代 器 中 的expectedModCount 的 值 卻 沒 有 變 ， 導(dǎo) 致 在 迭 代 器 下 次 執(zhí) 行 next () 方 法 時(shí) ，expectedModCount != modCount 就會(huì)報(bào) ConcurrentModificationException 的錯(cuò)誤。
那如果使用Iterator.remove () 方法可以刪除么，為什么？
可以的，因?yàn)?Iterator.remove () 方法在執(zhí)行的過程中，會(huì)把最新的 modCount 賦值給expectedModCount，這樣在下次循環(huán)過程中，modCount和expectedModCount 兩者就會(huì)相等。
//Iterator內(nèi)部remove方法
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();
????????????}
????????}好了以上就是在閱讀Linkedlist和Arraylist中遇到的問題以及使用Debug觀察后的感受。
作者：Deciscive
鏈接：juejin.im/post/6844904079399845896