手寫(xiě) Java 動(dòng)態(tài)數(shù)組ArrayList從泛型原理到 1.5 倍擴(kuò)容機(jī)制的全量實(shí)現(xiàn)本文基于一次 Java 課程的核心內(nèi)容實(shí)現(xiàn)一個(gè)支持泛型、自動(dòng)擴(kuò)容、指定位置插入、去重添加與自定義排序的動(dòng)態(tài)數(shù)組ZArrayListE。我們將從集合框架的分類(lèi)講起了解泛型的類(lèi)型模板機(jī)制逐行實(shí)現(xiàn)核心功能并對(duì)擴(kuò)容策略與時(shí)間復(fù)雜度進(jìn)行嚴(yán)謹(jǐn)分析。一、前言為什么要手寫(xiě)動(dòng)態(tài)數(shù)組在日常開(kāi)發(fā)中ArrayList是使用頻率最高的集合類(lèi)之一。但會(huì)用和理解之間隔著一層窗戶(hù)紙它如何做到容量自動(dòng)增長(zhǎng)為什么 JDK 優(yōu)先選擇1.5倍擴(kuò)容而不是 2 倍泛型 在編譯期和運(yùn)行期分別做了什么很多成熟代碼中大量篇幅其實(shí)用于性能優(yōu)化、特殊場(chǎng)景兜底、安全與合規(guī)校驗(yàn)而核心邏輯往往只占一小部分。親手實(shí)現(xiàn)一個(gè)動(dòng)態(tài)數(shù)組是捅破這層窗戶(hù)紙最有效的方式。補(bǔ)充JDK 是什么AI生成在動(dòng)手實(shí)現(xiàn)之前先厘清一個(gè)貫穿全文的基礎(chǔ)概念——JDK。JDKJava Development KitJava 開(kāi)發(fā)工具包是 Oracle及 OpenJDK 社區(qū)提供的 Java 開(kāi)發(fā)環(huán)境集合是編寫(xiě)、編譯、調(diào)試、運(yùn)行 Java 程序所必需的一整套工具。它包含三個(gè)層次組成全稱(chēng)作用JVMJava Virtual MachineJava 虛擬機(jī)負(fù)責(zé)加載并執(zhí)行字節(jié)碼是一次編寫(xiě)、到處運(yùn)行的根基JREJava Runtime EnvironmentJava 運(yùn)行時(shí)環(huán)境 JVM 核心類(lèi)庫(kù)只能運(yùn)行 Java 程序不能編譯JDKJava Development KitJava 開(kāi)發(fā)工具包 JRE 編譯器javac、調(diào)試器jdb、打包工具jar、文檔工具javadoc等開(kāi)發(fā)工具三者的包含關(guān)系可以簡(jiǎn)單記為JDK ? JRE ? JVM。只運(yùn)行不開(kāi)發(fā)裝 JRE 即可要寫(xiě)代碼、編譯源碼就必須裝 JDK。JDK 中幾個(gè)最常用的命令javac HelloWorld.java# 編譯把 .java 源碼編譯成 .class 字節(jié)碼javaHelloWorld# 運(yùn)行由 JVM 加載并執(zhí)行字節(jié)碼javadoc-ddoc src/# 生成 API 文檔本文后面講到的文檔注釋就靠它javap-cZArrayList# 反編譯字節(jié)碼查看泛型擦除后的真實(shí)方法簽名版本說(shuō)明JDK 目前按半年一個(gè)特性版本迭代JDK 8、11、17、21……其中 8、11、17、21 為長(zhǎng)期支持版LTS。本文的示例代碼基于JDK 17ArrayList的源碼分析同樣以 JDK 17 為準(zhǔn)代碼本身只用到泛型、數(shù)組與Arrays.copyOf等基礎(chǔ) API在 JDK 8 及以上版本均可直接編譯運(yùn)行。順帶一提本文提到的JDK 源碼指的就是 JDK 安裝目錄下src.zip中附帶的 Java 標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)代碼解壓后即可在 IDE 中直接跳轉(zhuǎn)閱讀java.util.ArrayList的原始實(shí)現(xiàn)——這是學(xué)習(xí)集合框架最權(quán)威的一手資料。二、集合框架Java 集合框架Java Collections Framework按數(shù)據(jù)組織形式可以劃分為三大體系體系核心結(jié)構(gòu)典型實(shí)現(xiàn)數(shù)據(jù)特征線(xiàn)性表List數(shù)組、鏈表、隊(duì)列、棧ArrayList、LinkedList元素有序、可重復(fù)、可按索引訪問(wèn)集合Set基于數(shù)組/鏈表/哈希組織HashSet、TreeSet元素不重復(fù)鍵值對(duì)Map哈希表、紅黑樹(shù)HashMap、TreeMapKey-Value 映射存儲(chǔ)三、泛型類(lèi)型模板符號(hào)的機(jī)制剖析3.1 泛型的定義與規(guī)則泛型Generics是一種類(lèi)型模板符號(hào)。定義類(lèi)時(shí)在類(lèi)名右側(cè)寫(xiě)括號(hào)內(nèi)用一個(gè)字母如E、T、K、V也可以是一個(gè)單詞來(lái)代表一種未知的類(lèi)型。此后在類(lèi)的內(nèi)部所有需要類(lèi)型聲明的地方——參數(shù)類(lèi)型、返回值類(lèi)型、轉(zhuǎn)型類(lèi)型——都可以使用這個(gè)泛型名替代。使用泛型必須遵守四條核心規(guī)則1.泛型名只能做類(lèi)型占位符不能實(shí)例化對(duì)象。new E()是非法的因?yàn)榫幾g期無(wú)法確定 E 的實(shí)際類(lèi)型也無(wú)法調(diào)用其構(gòu)造方法2.創(chuàng)建對(duì)象時(shí)指定具體類(lèi)型。new ZArrayListString()會(huì)將類(lèi)中所有E替換為String3.替換是全方法的。使用該對(duì)象調(diào)用方法時(shí)方法的參數(shù)類(lèi)型與返回值類(lèi)型都會(huì)替換為具體類(lèi)型從而獲得編譯期類(lèi)型檢查免除強(qiáng)制轉(zhuǎn)換4.不指定泛型則默認(rèn)為 Object。如果創(chuàng)建對(duì)象時(shí)未指定類(lèi)型裸類(lèi)型/raw type所有泛型位置默認(rèn)按Object處理。3.2 為什么底層用 Object 數(shù)組Object是 Java 所有類(lèi)的隱式父類(lèi)未顯式extends時(shí)默認(rèn)繼承Object因此Object[]數(shù)組可以存儲(chǔ)任何引用類(lèi)型。JDK 的ArrayList同樣采用這一方案privateObject[]elementData;// Object 數(shù)組什么類(lèi)型都能存對(duì)外接口則通過(guò)泛型E約束.四、類(lèi)設(shè)計(jì)屬性與構(gòu)造方法4.1 核心屬性一個(gè)動(dòng)態(tài)數(shù)組最少需要兩個(gè)狀態(tài)量這是本類(lèi)設(shè)計(jì)的基石屬性類(lèi)型含義elementDataObject[]真正存儲(chǔ)元素的底層數(shù)組sizeint數(shù)組中實(shí)際元素個(gè)數(shù)同時(shí)是新元素待寫(xiě)入的下標(biāo)注意size邏輯長(zhǎng)度用戶(hù)視角數(shù)組里裝了多少個(gè)元素capacity物理容量?jī)?nèi)存視角底層數(shù)組一共能裝多少個(gè)元素。容量信息可以直接通過(guò)elementData.length獲取無(wú)需冗余字段教學(xué)版代碼中若單獨(dú)維護(hù)length字段必須保證其與elementData.length嚴(yán)格同步否則極易引發(fā)越界 BugJDK 源碼中也不單獨(dú)維護(hù)該字段。4.2 構(gòu)造方法與合法性校驗(yàn)初始化時(shí)必須對(duì)傳入的容量參數(shù)進(jìn)行合法性判斷這是防御式編程的基本要求publicclassZArrayListE{/** 默認(rèn)初始容量與 JDK ArrayList 保持一致 */privatestaticfinalintDEFAULT_CAPACITY10;/** 底層存儲(chǔ)數(shù)組使用 Object 類(lèi)型可容納任意引用類(lèi)型 */privateObject[]elementData;/** 數(shù)組中實(shí)際元素的個(gè)數(shù)同時(shí)也是新元素待寫(xiě)入的下標(biāo) */privateintsize;/** 無(wú)參構(gòu)造使用默認(rèn)容量 */publicZArrayList(){this(DEFAULT_CAPACITY);}/** * 指定初始容量構(gòu)造 * param initCapacity 初始容量 * throws IllegalArgumentException 容量小于等于 0 時(shí)拋出 */publicZArrayList(intinitCapacity){if(initCapacity0){thrownewIllegalArgumentException(初始容量必須為正數(shù): initCapacity);}this.elementDatanewObject[initCapacity];}/** * 查詢(xún)當(dāng)前元素個(gè)數(shù) * return 實(shí)際元素個(gè)數(shù) */publicintsize(){returnsize;}/** * 判斷集合是否為空 * return 為空返回 true */publicbooleanisEmpty(){returnsize0;}}設(shè)計(jì)要點(diǎn)容量常量使用static final修飾——它屬于類(lèi)級(jí)別的規(guī)則所有實(shí)例共享且不可修改下限校驗(yàn)直接拋出IllegalArgumentException而不是改為默認(rèn)值讓調(diào)用方在第一時(shí)間感知錯(cuò)誤。五、核心功能實(shí)現(xiàn)增、插、刪、查、改5.1 擴(kuò)容機(jī)制1.5 倍增長(zhǎng)策略先定義統(tǒng)一的擴(kuò)容方法它是所有添加類(lèi)操作的公共依賴(lài)/** * 擴(kuò)容至至少滿(mǎn)足 minCapacity 的容量需求 * 擴(kuò)容策略新容量 舊容量 * 1.5若仍不足則直接擴(kuò)至 minCapacity * param minCapacity 最小需要的容量 */privatevoidgrow(intminCapacity){intoldCapacityelementData.length;intnewCapacityoldCapacity(oldCapacity1);// 位運(yùn)算等價(jià)于 oldCapacity * 1.5if(newCapacityminCapacity){// 一次批量插入的元素過(guò)多1.5 倍仍不夠一次性擴(kuò)容到位避免多次遷移newCapacityminCapacity;}// Arrays.copyOf按新容量創(chuàng)建數(shù)組并復(fù)制舊元素等價(jià)于新建 for 循環(huán)搬運(yùn) 換引用三步elementDataArrays.copyOf(elementData,newCapacity);}為什么是 1.5 倍擴(kuò)容倍數(shù)過(guò)小如 1.1 倍→ 擴(kuò)容頻繁每次擴(kuò)容都要整體搬遷數(shù)組均攤成本高擴(kuò)容倍數(shù)過(guò)大如 2 倍以上→空閑空間浪費(fèi)嚴(yán)重內(nèi)存利用率低oldCapacity (oldCapacity 1)使用位運(yùn)算 1完成÷2比乘除法指令效率更高且當(dāng)容量超過(guò)Integer.MAX_VALUE / 2時(shí)不易溢出到負(fù)數(shù)。批量插入場(chǎng)景的優(yōu)化addAll一次追加 N 個(gè)元素時(shí)若按單元素邏輯逐次觸發(fā)擴(kuò)容可能發(fā)生多次數(shù)組搬遷。正確做法是先計(jì)算總需求、一次性擴(kuò)容到位/** * 末尾批量添加元素 * param es 待添加的元素?cái)?shù)組 */publicvoidaddAll(E[]es){if(esnull||es.length0){return;}intneedsizees.length;// 添加后的總需求容量if(needelementData.length){grow(need);// 一次性擴(kuò)容到位}for(inti0;ies.length;i){elementData[size]es[i];}}關(guān)于舊數(shù)組的內(nèi)存回收擴(kuò)容后舊數(shù)組不再被elementData引用會(huì)成為不可達(dá)對(duì)象JVM 的垃圾回收器會(huì)自動(dòng)回收其占用的內(nèi)存無(wú)需程序員干預(yù)。課程代碼中出現(xiàn)的System.gc()只是建議JVM 盡快執(zhí)行一次回收并不能強(qiáng)制立即回收生產(chǎn)代碼中不應(yīng)依賴(lài)它。5.2 添加元素末尾追加 O(1)/** * 末尾添加單個(gè)元素 * param e 待添加的元素 * return 添加成功返回 true */publicbooleanadd(Ee){if(sizeelementData.length){grow(size1);// 數(shù)組已滿(mǎn)先擴(kuò)容再存入}elementData[size]e;returntrue;}5.3 指定下標(biāo)插入整體后移 O(n)指定下標(biāo)插入需要先判斷擴(kuò)容再將[index, size-1]區(qū)間的所有元素整體向后挪動(dòng)一位騰出目標(biāo)位置后寫(xiě)入/** * 指定下標(biāo)插入單個(gè)元素 * param index 插入位置取值范圍 [0, size] * param e 待插入的元素 * throws IndexOutOfBoundsException 下標(biāo)越界時(shí)拋出 */publicvoidinsert(intindex,Ee){if(index0||indexsize){thrownewIndexOutOfBoundsException(下標(biāo)越界: index, 合法范圍: [0, size]);}if(sizeelementData.length){grow(size1);}for(intisize-1;iindex;i--){// 從最后一個(gè)元素開(kāi)始逐位后移elementData[i1]elementData[i];}elementData[index]e;size;}常見(jiàn)坑插入場(chǎng)景下index size是合法的等價(jià)于末尾追加因此越界判斷的上界是 size 而非 size - 1同時(shí)注意挪動(dòng)循環(huán)必須從后往前遍歷若從前往后挪會(huì)用前面的值覆蓋后面未搬移的元素。批量插入同理先擴(kuò)容、再挪動(dòng)size - index個(gè)元素、最后寫(xiě)入此處從略。5.4 去重添加去重添加的原則是先擴(kuò)容判斷 遍歷查重確認(rèn)不存在后再追加避免重復(fù)元素反復(fù)進(jìn)入數(shù)組。實(shí)現(xiàn)如下/** * 去重添加數(shù)組中已存在該元素時(shí)不再添加 * param e 待添加的元素 * return 實(shí)際添加成功返回 true元素已存在返回 false */publicbooleanaddUnique(Ee){if(contains(e)){returnfalse;}returnadd(e);}/** * 批量去重添加 * param es 待添加的元素?cái)?shù)組 */publicvoidaddAllUnique(E[]es){for(Ee:es){addUnique(e);}}注意查重依賴(lài)equals方法比較元素自定義類(lèi)如User若要正確去重需要重寫(xiě)equals()與hashCode()。5.5 刪除、查詢(xún)與修改/** * 刪除指定下標(biāo)的元素后續(xù)元素整體前移 * param index 待刪除下標(biāo) * return 被刪除的元素 */SuppressWarnings(unchecked)publicEremove(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(下標(biāo)越界: index);}EoldValue(E)elementData[index];intnumMovedsize-index-1;// 需要前移的元素個(gè)數(shù)if(numMoved0){System.arraycopy(elementData,index1,elementData,index,numMoved);}elementData[--size]null;// 置 null幫助 GC 盡快回收失效引用returnoldValue;}/** * 按內(nèi)容刪除第一個(gè)匹配的元素 * param e 目標(biāo)元素 * return 刪除成功返回 true */publicbooleanremove(Ee){intindexindexOf(e);if(index0){remove(index);returntrue;}returnfalse;}/** * 返回元素首次出現(xiàn)的下標(biāo) * param e 目標(biāo)元素 * return 存在返回下標(biāo)不存在返回 -1 */publicintindexOf(Ee){for(inti0;isize;i){if(enull?elementData[i]null:e.equals(elementData[i])){returni;}}return-1;}/** * 判斷元素是否存在 */publicbooleancontains(Ee){returnindexOf(e)0;}/** * 獲取指定下標(biāo)的元素 */SuppressWarnings(unchecked)publicEget(intindex){if(index0||indexsize){thrownewIndexOutOfBoundsException(下標(biāo)越界: index);}return(E)elementData[index];}/** * 替換指定下標(biāo)的元素返回舊值 */SuppressWarnings(unchecked)publicEset(intindex,Ee){if(index0||indexsize){thrownewIndexOutOfBoundsException(下標(biāo)越界: index);}EoldValue(E)elementData[index];elementData[index]e;returnoldValue;}兩個(gè)細(xì)節(jié)1.從Object[]取元素時(shí)必須強(qiáng)制轉(zhuǎn)型為 E并標(biāo)注SuppressWarnings(unchecked)抑制編譯器警告——由于泛型擦除轉(zhuǎn)型在運(yùn)行期是安全的2.remove 后將數(shù)組尾部槽位置nullelementData[--size] null及時(shí)切斷失效引用避免內(nèi)存泄漏這正是JDK ArrayList.remove的標(biāo)準(zhǔn)寫(xiě)法。5.6 遍歷打印/** * 打印數(shù)組中的實(shí)際元素 */publicvoidprintArr(){StringBuildersbnewStringBuilder(數(shù)組元素為【);for(inti0;isize;i){sb.append(elementData[i]);if(isize-1){sb.append( );}}sb.append(】 size ).append(size);System.out.println(sb);}六、排序Lambda 表達(dá)式與標(biāo)準(zhǔn)比較器對(duì)自定義類(lèi)型如按年齡排序的 User排序時(shí)有兩條技術(shù)路線(xiàn)二者本質(zhì)都是實(shí)現(xiàn)比較規(guī)則、返回正數(shù) / 負(fù)數(shù) / 0 來(lái)決定元素的左右位置是否交換返回正數(shù)則交換降序返回負(fù)數(shù)或 0 則保持升序。6.1 Lambda 表達(dá)式// 按年齡降序o2 排在前面時(shí)返回正數(shù)list.sort((o1,o2)-o2.age-o1.age);6.2 匿名內(nèi)部類(lèi)實(shí)現(xiàn) Comparator 接口結(jié)構(gòu)清晰// 按年齡升序o1 - o2 為負(fù)數(shù)或 0 時(shí)保持原順序list.sort(newComparatorUser(){Overridepublicintcompare(Usero1,Usero2){returno1.age-o2.age;}});提示o1.age - o2.age這種減法寫(xiě)法在年齡等小范圍數(shù)值上安全但若字段值可能接近Integer.MAX_VALUE減法會(huì)溢出標(biāo)準(zhǔn)寫(xiě)法應(yīng)使用Integer.compare(o1.age, o2.age).七、測(cè)試驗(yàn)證運(yùn)行輸出節(jié)選 text 復(fù)制 數(shù)組元素為【0123456100712345612312234123245123666】 size24indexOf(123)1519181716151413121110...降序輸出10111213141516171819...升序輸出八、復(fù)雜度分析與常見(jiàn)問(wèn)題8.1 時(shí)間復(fù)雜度一覽操作時(shí)間復(fù)雜度說(shuō)明末尾添加add均攤 O(1)偶發(fā)擴(kuò)容的搬遷成本被均攤指定下標(biāo)插入insertO(n)平均需移動(dòng) n/2 個(gè)元素刪除removeO(n)平均需前移 n/2 個(gè)元素按下標(biāo)查詢(xún)getO(1)數(shù)組隨機(jī)訪問(wèn)特性按內(nèi)容查詢(xún)indexOfO(n)線(xiàn)性?huà)呙钄U(kuò)容growO(n)整體搬遷一次8.2 常見(jiàn)易錯(cuò)點(diǎn)匯總size與capacity混用遍歷時(shí)必須以size為上界若誤用elementData.length會(huì)把未使用的槽位一并打印出來(lái)輸出一堆null插入不校驗(yàn)下標(biāo)index size或負(fù)數(shù)下標(biāo)會(huì)直接破壞數(shù)據(jù)或拋出越界異常應(yīng)在方法入口統(tǒng)一校驗(yàn)從前往后挪動(dòng)元素插入時(shí)的元素后移必須從尾部開(kāi)始否則前面的值會(huì)覆蓋尚未搬移的元素裸類(lèi)型使用集合new ZArrayList()不指定泛型會(huì)退化為Object喪失編譯期類(lèi)型檢查依賴(lài)System.gc()回收內(nèi)存擴(kuò)容后的舊數(shù)組由 GC 自動(dòng)回收手動(dòng)調(diào)用只是建議不應(yīng)作為內(nèi)存管理手段。九、總結(jié)本文完成了一個(gè)教學(xué)版動(dòng)態(tài)數(shù)組的全量實(shí)現(xiàn)核心收獲可以濃縮為四點(diǎn)泛型是類(lèi)型模板符號(hào)定義期占位、使用期替換、不能實(shí)例化缺省時(shí)退化為Object動(dòng)態(tài)數(shù)組的靈魂是size與elementData的分工size管邏輯邊界底層數(shù)組管物理容量1.5 倍擴(kuò)容 一次性到位是空間與時(shí)間的經(jīng)典折中單元素添加走 1.5 倍批量插入則按總需求直接擴(kuò)容排序的通用范式Lambda 或Comparator提供正數(shù)交換、負(fù)數(shù)保持的比較規(guī)則即可實(shí)現(xiàn)升序或降序。課后練習(xí)建議按由易到難排序補(bǔ)全removeRange(int fromIndex, int toIndex)區(qū)間刪除實(shí)現(xiàn)按條件查詢(xún)返回滿(mǎn)足條件的元素子集合用鏈表重新實(shí)現(xiàn)一遍線(xiàn)性表并與本文實(shí)現(xiàn)對(duì)比各操作的性能差異在此基礎(chǔ)上完成隊(duì)列Queue與棧Stack的封裝。