更新時間:2022-11-16 來源:黑馬程序員 瀏覽量:
一、前言:
我們都知道ArrayList集合底層是數(shù)組結(jié)構(gòu),因為數(shù)組中每個元素是有索引存在,所以查詢效率高,增刪效率低。那為什么數(shù)組結(jié)構(gòu)有索引查詢效率就會高呢?而且ArrayList集合長度是可變的,數(shù)組一旦創(chuàng)建長度就不可變,那ArrayList集合底層是數(shù)組結(jié)構(gòu),它的底層原理又是如何執(zhí)行的?
下面我們就帶著這兩個問題,通過分析ArrayList源碼,了解其中的原理。
二、ArrayList集合增刪慢:
1、我們先來看一下ArrayList的底層源碼
2、自動擴容原理
(1)ArrayList集合底層是數(shù)組結(jié)構(gòu),新增元素時先創(chuàng)建長度為0的Object數(shù)組。
(2)添加元素時,判斷如果原數(shù)組中沒有元素,則再創(chuàng)建長度為10的新數(shù)組。
(3)添加元素時,判斷如果原數(shù)組中元素存滿時,則再創(chuàng)建長度為原數(shù)組長度*1.5倍的新數(shù)組。即oldCapacity + (oldCapacity >> 1);最后再將老數(shù)組元素拷貝到新數(shù)組中。
3、結(jié)論
ArrayList在添加元素時有可能會導(dǎo)致集合自動擴容,ArrayList底層是數(shù)組結(jié)構(gòu),但數(shù)組長度是不可變的不支持動態(tài)擴容,此時ArrayList集合底層會創(chuàng)建出一個新的數(shù)組,長度為老數(shù)組的1.5倍,并將老數(shù)組的元素復(fù)制到新數(shù)組中。
ArrayList在刪除元素時底層是將刪除索引位置起到最后索引位置結(jié)束中所有的元素,一一向前復(fù)制一個索引位置,再將最后索引位置元素設(shè)置為null。
所以ArrayList在進行增刪操作時,效率會很慢。
三、ArrayList集合查詢快:
1、我們先來看一下ArrayList的底層源碼
2、結(jié)論
ArrayList在查詢元素時底層是通過訪問數(shù)組元素方式進行查詢。
而數(shù)組只能存儲同一類型的元素。并且聲明一個數(shù)組時,會在內(nèi)存中申請一塊連續(xù)相鄰的內(nèi)存空間。當要通過索引訪問數(shù)組元素時,可通過數(shù)組地址值和偏移量,直接計算出要查找元素的內(nèi)存地址,所以數(shù)組支持通過索引直接訪問元素,效率非常高。
舉例分析:
四、總結(jié):
通過上述分析,我們發(fā)現(xiàn)ArrayList集合底層是Object[]數(shù)組,所以ArrayList具有數(shù)組的查詢速度快的優(yōu)點以及增刪速度慢的缺點。