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