一、背景介紹

Java集合的使用相信大家都已經(jīng)非常得心應(yīng)手，但是我們怎么做到知其然，更知其所以然這種出神入化的境界呢？我們揭開集合框架底層神秘面紗來一探究竟

目錄

一、背景介紹

二、思路&方案

數(shù)據(jù)結(jié)構(gòu)是什么？

數(shù)據(jù)結(jié)構(gòu)可以分為線性和非線性兩種數(shù)據(jù)結(jié)構(gòu)

線性數(shù)據(jù)結(jié)構(gòu)：

非線性數(shù)據(jù)結(jié)構(gòu)：

Java集合分類

Collection接口：

Map接口：

三、過程

ArrayList和LinkedList的區(qū)別有哪些？

ArrayList是如何存儲數(shù)據(jù)的？

ArrayList擴容機制

①、如何進行擴容的？

②、增加元素

③、ArrayList給指定位置插入元素

④、刪除元素

按照下標位置刪除元素

按照內(nèi)容刪除元素

四、總結(jié)

二、思路&方案

在說集合之前我們要先了解數(shù)據(jù)結(jié)構(gòu)這一概念

數(shù)據(jù)結(jié)構(gòu)是什么？

數(shù)據(jù)結(jié)構(gòu)時對數(shù)據(jù)進行組織和存儲一種方式，數(shù)據(jù)使用不同的數(shù)據(jù)結(jié)構(gòu)組織和存儲時所帶來的時間和空間性能也是不同的。List、Set、Map集合背后使用了不同的數(shù)據(jù)結(jié)構(gòu)，我們理解為集合是一種數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)。例如：可以使用數(shù)組結(jié)構(gòu)來實現(xiàn)集合，當訪問數(shù)組元素的時候通過數(shù)組下標查找時更快。

程序=數(shù)據(jù)結(jié)構(gòu)+算法。數(shù)據(jù)結(jié)構(gòu)還提供了一些各種查找、排序算法，集合可以用來解決一堆數(shù)據(jù)的處理問題，如：查找、排序、去重等等

數(shù)據(jù)結(jié)構(gòu)可以分為線性和非線性兩種數(shù)據(jù)結(jié)構(gòu)

線性數(shù)據(jù)結(jié)構(gòu)：

特點：

一對一的關(guān)系并且邏輯上有序，數(shù)據(jù)元素之間存在一個前后關(guān)系，每個元素只有一個直接前驅(qū)和一個直接后去

組成：

• 數(shù)組（Array）：相同類型元素并且連續(xù)存儲
• 鏈表（LinkedList）：一系列node節(jié)點，每個節(jié)點包括數(shù)據(jù)、指向下一個節(jié)點的指針
• 棧（Stack）：先進后出(LIFO)，在棧頂進行刪除和插入操作
• 隊列（Queue）：先進先出（FIFO），在隊尾插入、對頭刪除元素

非線性數(shù)據(jù)結(jié)構(gòu)：

特點：

多對多關(guān)系，數(shù)據(jù)元素之間不存在直接的前后關(guān)系，元素和元素之間通過指針相連，

包括：

• 樹（Tree）：一組node節(jié)點組成，每個父節(jié)點下級可以有子節(jié)點，節(jié)點之間是上下層次關(guān)系
• 圖（Graph）：一組節(jié)點、邊之間的關(guān)系
• 堆（Heap）：實現(xiàn)優(yōu)先隊列
• 散列表（Hash Table）：根據(jù)關(guān)鍵字可以直接查詢數(shù)據(jù)，通過散列函數(shù)確認存儲位置

結(jié)合上面講到的數(shù)據(jù)結(jié)構(gòu)，我們來看下Java究竟是如何應(yīng)用的

Java集合分類

集合相關(guān)類和接口都在java.util中，從宏觀上我們把Java集合分為了以Collection為中心的實現(xiàn)類、以Map為中心的實現(xiàn)類，?Collection和Map兩個接口下面分別有不同的實現(xiàn)類，它們都是用來存儲和操作數(shù)據(jù)的集合

Collection接口：

特點：

一組對象的集合，通過索引或迭代器訪問元素，元素可以重復(fù)

包括：

• List：有序集合
• Set：無序集合
• Queue：先進先出集合

Map接口：

特點：

鍵值對映射的集合，通過key查找value，每個key是唯一的

包括：

• HashMap：通過哈希表實現(xiàn)，無序
• TreeMap：基于紅黑樹實現(xiàn)，有序
• LinkedHashMap：哈希表+雙向鏈表實現(xiàn)，順序插入

今天先重點來講講List集合中ArrayList增刪改查是如何實現(xiàn)的

三、過程

ArrayList和LinkedList的區(qū)別有哪些？

ArrayList是如何存儲數(shù)據(jù)的？

底層是數(shù)組，數(shù)組存儲的數(shù)據(jù)的特點是元素類型相同并且數(shù)組容量固定

數(shù)組存儲容量固定？那在實際業(yè)務(wù)場景中數(shù)據(jù)肯定是不固定的呀？如何解決？

ArrayList擴容機制

ArrayList提供了自動擴容機制，當插入數(shù)據(jù)時候底層會先判斷是否需要擴容，如果當前容量+1超過數(shù)組長度，就會進行擴容，反之。

①、如何進行擴容的？

ArrayList內(nèi)部封裝了一個動態(tài)再分配的對象數(shù)組，ArrayList的底層數(shù)據(jù)庫初始容量為10，擴容因子為1.5

?

②、增加元素

當我們第一次添加元素使用add（）方法添加元素的過程中，底層的流程是這樣的：

內(nèi)部會調(diào)用ensureExplicitCapacity（）方法判斷添加元素之后的數(shù)組長度是否大于數(shù)組容量，如果超出數(shù)組容量調(diào)用grow（）方法擴容，否則給數(shù)組長度+1

當?shù)谝淮螌?shù)組進行add添加元素的時候，才會把內(nèi)部的數(shù)組擴容為10，這也是數(shù)組的第一次擴容

?注意：

• 數(shù)組長度是指當前數(shù)組內(nèi)元素的個數(shù)
• 數(shù)組容量是指數(shù)組所能容納的長度

示意圖：

那如果要添加的元素不足數(shù)組容量呢？現(xiàn)在我們來看下具體是如何擴容的？

假設(shè)場景：數(shù)組中已經(jīng)有10個元素，需要添加第11個元素

calculateCapacity方法內(nèi)部首先會判斷elementData數(shù)組是否是默認的空數(shù)組（看是否往數(shù)組里面添加了元素），如果不是默認數(shù)組則返回添加元素之后數(shù)組所需要的長度

如果添加元素之后的數(shù)組長度超出了數(shù)組容量，則說明需要擴容，調(diào)用grow（）方法進行擴容

?grow（）方法內(nèi)部會調(diào)用一個交copyOf方法進行擴容，會創(chuàng)建一個1.5倍的新數(shù)組，將原來的數(shù)組元素挪到新數(shù)組中

此時ArrayList擴容為原來的大小+原來大小/2=10+5=15，數(shù)組擴容后容量為15

?擴容后的數(shù)組示意圖如下：

add(E e)添加元素的流程為：

第一步、判斷是否需要擴容：

? ? ? ? 需要擴容

? ? ? ? ? ? ? ? ①、計算新數(shù)組容量：newCapacity = oldCapacity + (oldCapacity >> 1)

? ? ? ? ? ? ??? ②、創(chuàng)建新數(shù)組：elementData = Arrays.copyOf(elementData, newCapacity)

第二步、追加元素到數(shù)組末尾 。 ?elementData[size++] =element;

第三步、添加成功

③、ArrayList給指定位置插入元素

示例：

添加指定位置流程如下：

第一步、檢查下標是否越界

? ? ? ? 越界：拋出IndexOutOfBoundsException異常

第二步、判斷是否需要擴容，如果需要擴容則擴容

第三步、后移元素.從指定要插入元素位置依次向后移動一個位置，此時指定要插入的位置為空

第四步、插入新元素。將要插入的元素放入指定位置

第五步、更新數(shù)組大小。size+1

? ? ? ??

注意： 其中rangeCheckForAdd(index)方法會檢查下標是否越界，如果要插入的元素位置超出了當前數(shù)組的容量，會拋出”IndexOutOfBoundsException“的異常

?示意圖：

④、刪除元素

按照下標位置刪除元素

按照內(nèi)容刪除元素

四、總結(jié)

通過分析源碼我們了解了ArrayList底層增刪改查操作具體的細節(jié)，再次總結(jié)

文章來源地址http://www.zghlxwxcb.cn/news/detail-684321.html

到了這里，關(guān)于探索Java集合框架—數(shù)據(jù)結(jié)構(gòu)、ArrayList集合的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！