摘要:線程不安全底層數據結構是鏈表。的默認初始化容量是,每次擴容時候增加原先容量的一半,也就是變為原來的倍刪除元素時不會減少容量,若希望減少容量則調用它不是線程安全的。
前言
聲明,本文用得是jdk1.8
前一篇已經講了Collection的總覽:Collection總覽,介紹了一些基礎知識。
現在這篇主要講List集合的三個子類:
ArrayList
底層數據結構是數組。線程不安全
LinkedList
底層數據結構是鏈表。線程不安全
Vector
底層數據結構是數組。線程安全
這篇主要來看看它們比較重要的方法是如何實現的,需要注意些什么,最后比較一下哪個時候用哪個~
看這篇文章之前最好是有點數據結構的基礎:Java實現單向鏈表,棧和隊列就是這么簡單,二叉樹就這么簡單
當然了,如果講得有錯的地方還請大家多多包涵并不吝在評論去指正~
一、ArrayList解析首先,我們來講解的是ArrayList集合,它是我們用得非常非常多的一個集合~
首先,我們來看一下ArrayList的屬性:
根據上面我們可以清晰的發現:ArrayList底層其實就是一個數組,ArrayList中有擴容這么一個概念,正因為它擴容,所以它能夠實現“動態”增長
1.2構造方法我們來看看構造方法來印證我們上面說得對不對:
1.3Add方法add方法可以說是ArrayList比較重要的方法了,我們來總覽一下:
1.3.1add(E e)步驟:
檢查是否需要擴容
插入元素
首先,我們來看看這個方法:
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
該方法很短,我們可以根據方法名就猜到他是干了什么:
確認list容量,嘗試容量加1,看看有無必要
添加元素
接下來我們來看看這個小容量(+1)是否滿足我們的需求:
隨后調用ensureExplicitCapacity()來確定明確的容量,我們也來看看這個方法是怎么實現的:
所以,接下來看看grow()是怎么實現的~
進去看copyOf()方法:
到目前為止,我們就可以知道add(E e)的基本實現了:
首先去檢查一下數組的容量是否足夠
足夠:直接添加
不足夠:擴容
擴容到原來的1.5倍
第一次擴容后,如果容量還是小于minCapacity,就將容量擴充為minCapacity。
1.3.2add(int index, E element)步驟:
檢查角標
空間檢查,如果有需要進行擴容
插入元素
我們來看看插入的實現:
我們發現,與擴容相關ArrayList的add方法底層其實都是arraycopy()來實現的
看到arraycopy(),我們可以發現:該方法是由C/C++來編寫的,并不是由Java實現:
總的來說:arraycopy()還是比較可靠高效的一個方法。
參考R大回答:https://www.zhihu.com/question/53749473
1.4 get方法檢查角標
返回元素
// 檢查角標 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } // 返回元素 E elementData(int index) { return (E) elementData[index]; }1.5 set方法
步驟:
檢查角標
替代元素
返回舊值
1.6remove方法步驟:
檢查角標
刪除元素
計算出需要移動的個數,并移動
設置為null,讓Gc回收
1.7細節再說明ArrayList是基于動態數組實現的,在增刪時候,需要數組的拷貝復制。
ArrayList的默認初始化容量是10,每次擴容時候增加原先容量的一半,也就是變為原來的1.5倍
刪除元素時不會減少容量,若希望減少容量則調用trimToSize()
它不是線程安全的。它能存放null值。
參考資料:
https://blog.csdn.net/panweiwei1994/article/details/76760238
https://zhuanlan.zhihu.com/p/27878015
二、Vector與ArrayList區別Vector是jdk1.2的類了,比較老舊的一個集合類。
Vector底層也是數組,與ArrayList最大的區別就是:同步(線程安全)
Vector是同步的,我們可以從方法上就可以看得出來~
在要求非同步的情況下,我們一般都是使用ArrayList來替代Vector的了~
如果想要ArrayList實現同步,可以使用Collections的方法:List list = Collections.synchronizedList(new ArrayList(...));,就可以實現同步了~
還有另一個區別:
ArrayList在底層數組不夠用時在原來的基礎上擴展0.5倍,Vector是擴展1倍。、
Vector源碼的解析可參考:
https://blog.csdn.net/panweiwei1994/article/details/76972890
https://zhuanlan.zhihu.com/p/28241176
三、LinkedList解析LinkedList底層是雙向鏈表~如果對于鏈表不熟悉的同學可先看看我的單向鏈表(雙向鏈表的練習我還沒做)【Java實現單向鏈表】
理解了單向鏈表,雙向鏈表也就不難了。
從結構上,我們還看到了LinkedList實現了Deque接口,因此,我們可以操作LinkedList像操作隊列和棧一樣~
LinkedList變量就這么幾個,因為我們操作單向鏈表的時候也發現了:有了頭結點,其他的數據我們都可以獲取得到了。(雙向鏈表也同理)
3.1構造方法LinkedList的構造方法有兩個:
3.2add方法如果做過鏈表的練習,對于下面的代碼并不陌生的~
add方法實際上就是往鏈表最后添加元素
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node3.3remove方法l = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
實際上就是下面那個圖的操作:
3.4get方法可以看到get方法實現就兩段代碼:
public E get(int index) { checkElementIndex(index); return node(index).item; }
我們進去看一下具體的實現是怎么樣的:
3.5set方法set方法和get方法其實差不多,根據下標來判斷是從頭遍歷還是從尾遍歷
public E set(int index, E element) { checkElementIndex(index); Nodex = node(index); E oldVal = x.item; x.item = element; return oldVal; }
......LinkedList的方法比ArrayList的方法多太多了,這里我就不一一說明了。具體可參考:
https://blog.csdn.net/panweiwei1994/article/details/77110354
https://zhuanlan.zhihu.com/p/24730576
https://zhuanlan.zhihu.com/p/28373321
四、總結其實集合的源碼看起來并不是很困難,遇到問題可以翻一翻,應該是能夠看懂的~
ArrayList、LinkedList、Vector算是在面試題中比較常見的的知識點了。下面我就來做一個簡單的總結:
ArrayList:
底層實現是數組
ArrayList的默認初始化容量是10,每次擴容時候增加原先容量的一半,也就是變為原來的1.5倍
在增刪時候,需要數組的拷貝復制(navite 方法由C/C++實現)
LinkedList:
底層實現是雙向鏈表[雙向鏈表方便實現往前遍歷]
Vector:
底層是數組,現在已少用,被ArrayList替代,原因有兩個:
Vector所有方法都是同步,有性能損失。
Vector初始length是10 超過length時 以100%比率增長,相比于ArrayList更多消耗內存。
參考資料:https://www.zhihu.com/question/31948523/answer/113357347
總的來說:查詢多用ArrayList,增刪多用LinkedList。
ArrayList增刪慢不是絕對的(在數量大的情況下,已測試):
如果增加元素一直是使用add()(增加到末尾)的話,那是ArrayList要快
一直刪除末尾的元素也是ArrayList要快【不用復制移動位置】
至于如果刪除的是中間的位置的話,還是ArrayList要快!
但一般來說:增刪多還是用LinkedList,因為上面的情況是極端的~
參考資料:
https://blog.csdn.net/panweiwei1994/article/details/76555359
https://zhuanlan.zhihu.com/p/28216267
《Core Java》
文章的目錄導航:https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li
如果文章有錯的地方歡迎指正,大家互相交流。習慣在微信看技術文章,想要獲取更多的Java資源的同學,可以關注微信公眾號:Java3y。為了大家方便,剛新建了一下qq群:742919422,大家也可以去交流交流。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68979.html
摘要:下面總結一下集合常用的三個子類吧無序,允許為,底層是散列表紅黑樹,非線程同步有序,不允許為,底層是紅黑樹非線程同步迭代有序,允許為,底層是雙向鏈表,非線程同步從結論而言我們就可以根據自己的實際情況來使用了。 前言 聲明,本文用的是jdk1.8 前面章節回顧: Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼...
摘要:而在集合中,值僅僅是一個對象罷了該對象對本身而言是無用的。將這篇文章作為集合的總結篇,但覺得沒什么好寫就回答一些面試題去了,找了一會面試題又覺得不夠系統。 前言 聲明,本文用的是jdk1.8 花了一個星期,把Java容器核心的知識過了一遍,感覺集合已經無所畏懼了!!(哈哈哈....),現在來總結一下吧~~ 回顧目錄: Collection總覽 List集合就這么簡單【源碼剖析】 Ma...
前言 聲明,本文用得是jdk1.8 前面已經講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹的基礎了: Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 本篇主要講解HashMap,以及涉及到一些與hashtable的比較~ 看這篇文章之前最好是有點數據結構的基礎: Java實現單向鏈表 棧和隊列就是這么簡單 二叉樹就...
摘要:在這種情況下,是以其為根的樹的最后一個結點。來源二總結底層是紅黑樹,能夠實現該集合有序如果在構造方法中傳遞了對象,那么就會以對象的方法進行比較。 前言 聲明,本文用得是jdk1.8 前面章節回顧: Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼剖析】 LinkedHashMap就這么簡單【源碼剖析】 本...
摘要:習慣在微信看技術文章,想要獲取更多的資源的同學,可以關注微信公眾號。為了大家方便,剛新建了一下群,大家也可以去交流交流。謝謝支持了希望能多介紹給其他有需要的朋友 前言 聲明,本文用得是jdk1.8 前面已經講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹還有HashMap基礎了: Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、...
閱讀 2731·2021-11-24 09:39
閱讀 1647·2021-09-28 09:35
閱讀 1119·2021-09-06 15:02
閱讀 1307·2021-07-25 21:37
閱讀 2726·2019-08-30 15:53
閱讀 3643·2019-08-30 14:07
閱讀 714·2019-08-30 11:07
閱讀 3512·2019-08-29 18:36