Java中的ArrayList和contains函數(shù)和擴(kuò)容機(jī)制(源碼詳解)
起因
在Leetcode上做題寫了兩種暴力解法,但是執(zhí)行效率上不太一樣。
時間上差很遠(yuǎn),內(nèi)存雖然差不多但是前者擊敗30%,后者擊敗94%。這兩種解法區(qū)別是用一條ArrayList
還是兩條來存數(shù)據(jù),所以contains雖然執(zhí)行次數(shù)一樣但是檢測的長度上不一樣,而且ArrayList
的擴(kuò)容次數(shù)也不一樣,所以學(xué)習(xí)一下。
contains(Object o)
直接翻(JDK8)源碼:
null
和object
區(qū)分開來還是因為equals
有一方是null
的話都會導(dǎo)致異常. 合并一起寫的話可以用Objects.equals(obj1, obj2)
的寫法.
所以顯然暴力解法用到的contains
的原理就是樸實無華的一遍遍搜索所以時間特別長.
ArrayList擴(kuò)容機(jī)制
省流: 直接看最下面的grow
函數(shù).
如果是默認(rèn)的ArrayList
, 添加元素時會先計算數(shù)組長度, 如果元素個數(shù)+1大于當(dāng)前數(shù)組長度+1大于elementData.length
時進(jìn)行擴(kuò)容,擴(kuò)容后的數(shù)組大小是: oldCapacity + (oldCapacity >> 1)
可以理解成1.5倍擴(kuò)容。
涉及到的源碼:
// 向指定索引位置插入元素 public void add(int index, E element) { // 檢查索引范圍 rangeCheckForAdd(index); // 確保容量足夠 ensureCapacityInternal(size + 1); // 增加 modCount(用于支持并發(fā)修改的計數(shù)器) // 使用 System.arraycopy 將元素后移,為新元素騰出位置, 這是跟另一個add的區(qū)別????? System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; // 在指定位置插入新元素 size++; // 更新列表大小 } // 在列表末尾添加元素 public boolean add(E e) { // 確保容量足夠 ensureCapacityInternal(size + 1); // 增加 modCount elementData[size++] = e; // 在列表末尾添加新元素 return true; } // 內(nèi)部方法:確保容量足夠 private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } // 內(nèi)部方法:計算容量 private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果內(nèi)部數(shù)組為空,返回默認(rèn)容量或所需容量中的較大者 return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; // 否則返回所需容量 } // 內(nèi)部方法:確保容量足夠 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 增加并發(fā)修改計數(shù)器 // 檢查容量是否足夠,如果不夠則擴(kuò)展 if (minCapacity - elementData.length > 0) grow(minCapacity); } // 內(nèi)部方法:擴(kuò)展容量 private void grow(int minCapacity) { // 溢出安全的代碼 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量通常為舊容量的1.5倍 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; // 如果新容量小于所需容量,使用所需容量 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 處理可能的巨大容量情況 // 使用 Arrays.copyOf 擴(kuò)展數(shù)組容量 elementData = Arrays.copyOf(elementData, newCapacity); }
實際上Array.copyof
底層調(diào)用的還是System.arraycopy
.
到此這篇關(guān)于Java的ArrayList和contains函數(shù)和擴(kuò)容機(jī)制的文章就介紹到這了,更多相關(guān)Java ArrayList和contains函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java中&和&&以及|和||的區(qū)別、應(yīng)用場景和代碼示例
這篇文章主要介紹了Java中的邏輯運算符&、&&、|和||的區(qū)別,包括它們在布爾和整數(shù)類型上的應(yīng)用,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-03-03Java使用線程池批量處理數(shù)據(jù)操作具體流程
這篇文章主要給大家介紹了關(guān)于Java使用線程池批量處理數(shù)據(jù)操作的相關(guān)資料,Java多線程編程中線程池是一個非常重要的概念,線程池可以提高線程的復(fù)用率和任務(wù)調(diào)度的效率,尤其是當(dāng)需要查詢大批量數(shù)據(jù)時,需要的朋友可以參考下2023-06-06java獲取文件擴(kuò)展名的方法小結(jié)【正則與字符串截取】
這篇文章主要介紹了java獲取文件擴(kuò)展名的方法,結(jié)合實例形式分析了使用正則與字符串截取兩種獲取擴(kuò)展名的操作技巧,需要的朋友可以參考下2017-01-01為Java應(yīng)用創(chuàng)建Docker鏡像的3種方式總結(jié)
Docker的使用可以將應(yīng)用程序做成鏡像,這樣可以將鏡像發(fā)布到私有或者公有倉庫中,在其他主機(jī)上也可以pull鏡像,并且運行容器,運行程,下面這篇文章主要給大家總結(jié)介紹了關(guān)于為Java應(yīng)用創(chuàng)建Docker鏡像的3種方式,需要的朋友可以參考下2023-06-06Java中double和float類型的區(qū)別與使用方法
float和double都是用來表示浮點數(shù)的數(shù)據(jù)類型,但是它們之間有一些區(qū)別,這篇文章主要給大家介紹了關(guān)于Java中double和float類型的區(qū)別與使用方法的相關(guān)資料,需要的朋友可以參考下2024-07-07Java注解之Retention、Documented、Inherited介紹
這篇文章主要介紹了Java注解之Retention、Documented、Inherited注解介紹,本文內(nèi)容和相關(guān)文章是系列文章,需要的朋友可以參考下2014-09-09應(yīng)用Java泛型和反射導(dǎo)出CSV文件的方法
這篇文章主要介紹了應(yīng)用Java泛型和反射導(dǎo)出CSV文件的方法,通過一個自定義函數(shù)結(jié)合泛型與反射的應(yīng)用實現(xiàn)導(dǎo)出CSV文件的功能,具有一定的參考借鑒價值,需要的朋友可以參考下2014-12-12springboot 動態(tài)數(shù)據(jù)源的實現(xiàn)方法(Mybatis+Druid)
這篇文章主要介紹了springboot 動態(tài)數(shù)據(jù)源的實現(xiàn)方法(Mybatis+Druid),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2019-01-01