化：SparseArray與ArrayMap替代HashMap的深度解析)
1. 從一個真實的性能問題說起做Android開發(fā)有些年頭的人大概率都經(jīng)歷過這樣一種場景某個列表頁在低端機上滑動起來就是不夠跟手幀率時不時掉到40以下明明邏輯不復(fù)雜Adapter里也沒做什么耗時操作但Profiler一掛上去GC日志刷得跟流水賬一樣。順著內(nèi)存分配一路追下去最后發(fā)現(xiàn)罪魁禍首既不是圖片加載也不是網(wǎng)絡(luò)請求而是某個用HashMapInteger, Object存了幾百條映射關(guān)系的緩存結(jié)構(gòu)。這個結(jié)論第一次看到的時候確實有點反直覺。HashMap在Java世界里幾乎是萬能容器的代名詞怎么到了Android上就成了性能瓶頸原因其實不復(fù)雜HashMap每個鍵值對都要額外創(chuàng)建一個Entry對象而Integer作為key在自動裝箱時又會產(chǎn)生臨時對象。一個幾百條數(shù)據(jù)的Map在頻繁讀寫場景下短時間內(nèi)就能制造出成千上萬個小對象GC壓力自然就上來了。Android的Dalvik和ART雖然一直在優(yōu)化GC但內(nèi)存分配這件事本身的開銷是躲不掉的。SparseArray和ArrayMap就是在這個背景下進入視野的。它們不是Android獨創(chuàng)的什么黑科技本質(zhì)上是用時間換空間的經(jīng)典思路放棄HashMap的哈希桶結(jié)構(gòu)改用有序數(shù)組加二分查找來存儲鍵值對。查找從O(1)退化到O(log n)但省掉了Entry對象和裝箱開銷在小數(shù)據(jù)量場景下綜合表現(xiàn)反而更好。這個取舍值不值得取決于你的數(shù)據(jù)規(guī)模和讀寫比例不能一概而論。這篇文章會把這兩個容器從設(shè)計動機、內(nèi)部結(jié)構(gòu)、核心方法實現(xiàn)、性能邊界到實際選型完整地拆一遍。適合已經(jīng)寫過一段時間Android、對Java集合有一定了解、但還沒系統(tǒng)研究過這兩個類的開發(fā)者?？赐曛竽銘?yīng)該能判斷什么場景該用SparseArray什么場景該用ArrayMap什么場景老老實實回去用HashMap。2. 為什么Android要另起爐灶2.1 HashMap在移動端的三個隱性成本要理解SparseArray和ArrayMap的價值得先把HashMap在Android上的成本算清楚。很多人只知道“HashMap快”但快是有代價的這個代價在服務(wù)端可能無所謂在移動端就會被放大。第一個成本是Entry對象的額外內(nèi)存。HashMap內(nèi)部維護一個Node數(shù)組Java 8之后是Node之前是Entry每個鍵值對都要包裝成一個Node對象里面存hash、key、value和next指針。一個Node對象在32位JVM上大約占32字節(jié)64位開啟指針壓縮后大約40字節(jié)左右。如果你存1000條數(shù)據(jù)光Node對象就是40KB這還沒算數(shù)組本身的容量。第二個成本是自動裝箱。HashMapInteger, Object里的key是Integer類型當你寫map.put(1, obj)的時候字面量1會被自動裝箱成Integer.valueOf(1)。雖然Integer有-128到127的緩存池但超過這個范圍的整數(shù)每次都會new一個新對象。在循環(huán)里頻繁put/get裝箱產(chǎn)生的臨時對象數(shù)量相當可觀。第三個成本是擴容時的rehash。HashMap默認容量16負載因子0.75超過閾值就擴容翻倍。擴容時所有元素都要重新計算hash并重新分配位置這個操作在數(shù)據(jù)量大時會造成明顯的卡頓。雖然可以通過預(yù)設(shè)初始容量來緩解但很多開發(fā)者并不會這么做。注意這里說的成本是相對的。如果你的Map只有幾十條數(shù)據(jù)或者讀寫頻率很低HashMap的這些開銷完全可以忽略。不要為了優(yōu)化而優(yōu)化先測量再動手。2.2 SparseArray的設(shè)計取舍SparseArray的全稱是android.util.SparseArray它的key被限定為int類型value是泛型Object。這個限定不是限制而是它的核心設(shè)計前提。因為key是int就不需要裝箱也不需要計算hashCode。SparseArray內(nèi)部維護兩個平行數(shù)組一個int[] mKeys存放鍵一個Object[] mValues存放值。所有鍵按升序排列查找時用二分查找定位。這個設(shè)計帶來的直接好處是沒有Entry對象沒有裝箱內(nèi)存占用大幅降低。代價是查找從O(1)變成O(log n)插入和刪除因為要移動數(shù)組元素最壞情況是O(n)。SparseArray還有一個變體叫SparseIntArray、SparseLongArray、SparseBooleanArray分別對應(yīng)value是基本類型的場景。這些變體連value的裝箱都省了在統(tǒng)計計數(shù)、狀態(tài)標記這類場景下非常實用。2.3 ArrayMap的通用化嘗試SparseArray的key只能是int這個限制在很多場景下不夠用。比如你想用String做keySparseArray就無能為力了。ArrayMap就是為了解決這個問題而出現(xiàn)的。ArrayMap同樣使用兩個平行數(shù)組但key是Object類型可以是String、Integer或任何對象。它內(nèi)部維護一個int[] mHashes數(shù)組存放key的hashCode以及Object[] mArray數(shù)組交替存放key和value。查找時先對mHashes做二分查找找到后再比較key的equals。ArrayMap在Android 5.0之后被加入androidx.collection包也可以在非Android項目中使用。它的設(shè)計目標是在數(shù)據(jù)量較小通常小于1000且讀多寫少的場景下提供比HashMap更低的內(nèi)存占用。2.4 三者的核心差異對比特性HashMapSparseArrayArrayMapkey類型任意Objectint任意Object數(shù)據(jù)結(jié)構(gòu)哈希桶鏈表/紅黑樹有序int數(shù)組Object數(shù)組有序hash數(shù)組鍵值交替數(shù)組查找復(fù)雜度O(1)平均O(log n)O(log n)插入復(fù)雜度O(1)平均O(n)最壞O(n)最壞內(nèi)存占用高Entry裝箱低中無Entry有hash數(shù)組適用數(shù)據(jù)量任意小于1000小于1000線程安全否否否這張表是選型的核心依據(jù)。記住一個原則數(shù)據(jù)量小、讀多寫少、key是int優(yōu)先SparseArraykey不是int但數(shù)據(jù)量小考慮ArrayMap數(shù)據(jù)量大或?qū)懖僮黝l繁老老實實用HashMap。3. SparseArray內(nèi)部結(jié)構(gòu)深度拆解3.1 二分查找的實現(xiàn)細節(jié)SparseArray的查找邏輯集中在ContainerHelpers.binarySearch這個方法里。它的實現(xiàn)很樸素就是標準的二分查找但有一個細節(jié)值得注意當找不到目標時它返回的是目標應(yīng)該插入位置的按位取反值。static int binarySearch(int[] array, int size, int value) { int lo 0; int hi size - 1; while (lo hi) { final int mid (lo hi) 1; final int midVal array[mid]; if (midVal value) { lo mid 1; } else if (midVal value) { hi mid - 1; } else { return mid; } } return ~lo; }這個~lo的返回值設(shè)計很巧妙。調(diào)用方拿到負數(shù)就知道沒找到再取反就得到應(yīng)該插入的位置。put方法就是靠這個機制來保證數(shù)組始終有序的。實操心得如果你自己實現(xiàn)類似的有序數(shù)組結(jié)構(gòu)這個“返回插入點”的技巧可以直接抄。它避免了查找和插入兩次遍歷在put操作里能省一次二分查找。3.2 put方法的完整流程put方法的邏輯可以拆成幾種情況數(shù)組為空或size為0直接放在索引0二分查找key如果找到直接替換value如果沒找到拿到插入位置判斷是否需要擴容如果需要擴容先擴容再插入如果不需要擴容用System.arraycopy把插入位置之后的元素整體后移一位在插入位置寫入key和valuesize加一這里的關(guān)鍵點是數(shù)組移動。每次插入新key都要把插入點之后的所有元素后移。如果一直往數(shù)組頭部插入每次都是O(n)的移動性能會急劇下降。所以SparseArray適合的是key分布相對均勻、插入不集中在頭部的場景。擴容策略也值得說一下。SparseArray的初始容量是10擴容時如果當前size小于等于4就擴到8否則擴到size的2倍。這個策略比HashMap的翻倍擴容更保守因為SparseArray的數(shù)據(jù)量本來就不大。3.3 delete與remove的差異SparseArray有兩個刪除方法delete和remove。它們內(nèi)部都調(diào)用同一個方法但語義上有區(qū)別。delete方法在刪除后如果數(shù)組大小超過一定閾值會調(diào)用gc方法壓縮數(shù)組。gc方法會把所有非空的值往前移動消除中間的空洞。remove方法在API 24之后和delete合并了行為一致。但要注意SparseArray的刪除并不是立即把數(shù)組縮短而是把對應(yīng)位置的值置為DELETED標記一個靜態(tài)空對象然后size減一。真正的數(shù)組壓縮發(fā)生在gc調(diào)用時。這個設(shè)計是為了避免每次刪除都移動數(shù)組把多次刪除的移動成本合并到一次gc里。public void delete(int key) { int i ContainerHelpers.binarySearch(mKeys, mSize, key); if (i 0) { mValues[i] DELETED; mGarbage true; } }注意如果你在遍歷SparseArray的過程中刪除元素要小心DELETED標記的影響。雖然size已經(jīng)減一但底層數(shù)組里可能還有DELETED占位。用size作為循環(huán)邊界是安全的但不要直接訪問mValues數(shù)組。3.4 append方法的優(yōu)化場景SparseArray提供了一個append方法專門用于key遞增的場景。它的實現(xiàn)比put簡單得多如果當前size為0或者傳入的key大于最后一個key直接追加到數(shù)組末尾不需要二分查找。public void append(int key, E value) { if (mSize ! 0 key mKeys[mSize - 1]) { put(key, value); return; } if (mGarbage mSize mKeys.length) { gc(); } mKeys GrowingArrayUtils.append(mKeys, mSize, key); mValues GrowingArrayUtils.append(mValues, mSize, value); mSize; }這個優(yōu)化在什么場景下有用比如你從數(shù)據(jù)庫按id升序讀取一批記錄依次放入SparseArray用append就比put快很多因為省掉了每次的二分查找。4. ArrayMap的實現(xiàn)原理與性能邊界4.1 雙數(shù)組結(jié)構(gòu)的精妙之處ArrayMap的內(nèi)部結(jié)構(gòu)比SparseArray稍微復(fù)雜一點。它有三個核心數(shù)組int[] mHashes存放每個key的hashCode升序排列Object[] mArray交替存放key和value即mArray[2i]是keymArray[2i1]是valueint mSize當前鍵值對數(shù)量為什么要把hash單獨抽出來一個數(shù)組因為二分查找只需要比較int不需要調(diào)用equals。先用hash定位到候選位置再比較key的equals這樣能減少equals的調(diào)用次數(shù)。對于String這種equals開銷較大的key類型這個優(yōu)化很有意義。查找流程是這樣的計算key的hashCode在mHashes中二分查找hash如果找到拿到索引index比較mArray[2*index]和key是否equals如果equals返回mArray[2*index1]如果不equalshash沖突繼續(xù)向兩邊線性探測這個線性探測是ArrayMap處理hash沖突的方式。因為數(shù)據(jù)量小沖突概率低線性探測的實際開銷可以接受。4.2 緩存機制與擴容策略ArrayMap有一個靜態(tài)的緩存數(shù)組用于復(fù)用空數(shù)組。當你創(chuàng)建一個新的ArrayMap時它不會立即分配數(shù)組而是指向一個共享的空數(shù)組。只有在第一次put時才會真正分配。這個設(shè)計在大量創(chuàng)建臨時Map的場景下能省不少內(nèi)存。擴容策略方面ArrayMap的初始容量是4擴容時翻倍。但它的擴容有一個特殊處理如果當前容量已經(jīng)很大超過一定閾值會嘗試收縮。這個邏輯在trimToSize方法里也有體現(xiàn)。public void trimToSize() { if (mSize mArray.length / 2) { // 收縮數(shù)組 } }實操心得如果你確定一個ArrayMap不會再添加新元素了調(diào)用trimToSize可以釋放多余內(nèi)存。這在緩存場景下很有用比如你把一批數(shù)據(jù)加載進ArrayMap后就不再修改trim一下能省不少空間。4.3 與SparseArray的性能對比同樣是存1000條int到Object的映射SparseArray和ArrayMap的表現(xiàn)有差異內(nèi)存占用SparseArray更低因為它不需要mHashes數(shù)組key直接存在int數(shù)組里查找速度SparseArray略快因為少一次hash計算和equals調(diào)用插入速度兩者接近都是O(n)的數(shù)組移動通用性ArrayMap支持任意key類型SparseArray只支持int所以選型邏輯很清晰key是int就用SparseArray不是int才考慮ArrayMap。不要因為ArrayMap更通用就無腦用它。4.4 什么情況下ArrayMap會翻車ArrayMap不是銀彈以下幾種情況用它反而更慢數(shù)據(jù)量超過1000。二分查找的O(log n)在n1000時大約是10次比較在n10000時是14次。雖然增長不快但每次比較都涉及數(shù)組訪問和可能的equals調(diào)用累積起來就明顯了。更重要的是插入時的數(shù)組移動在數(shù)據(jù)量大時開銷急劇上升。頻繁插入刪除。每次插入都要移動數(shù)組每次刪除都要標記和可能的壓縮。如果你的場景是不斷增刪的隊列或緩存ArrayMap的O(n)操作會成為瓶頸。多線程并發(fā)讀寫。ArrayMap和SparseArray都不是線程安全的。如果在多線程環(huán)境下使用需要自己加鎖而加鎖后的性能可能還不如直接用ConcurrentHashMap。key的hashCode計算開銷大。ArrayMap每次查找都要計算key的hashCode。如果key是復(fù)雜對象且hashCode方法很重這個開銷會累積。HashMap也有這個問題但HashMap的O(1)查找在數(shù)據(jù)量大時優(yōu)勢明顯。5. 實際項目中的選型與優(yōu)化實操5.1 一個典型的列表緩存場景假設(shè)你在做一個聊天記錄列表每條消息有一個自增的long型id你需要根據(jù)id快速找到對應(yīng)的消息對象。數(shù)據(jù)量大概幾百條讀多寫少。這個場景下SparseArray是首選。但注意id是longSparseArray只支持int。如果id范圍在int內(nèi)可以強轉(zhuǎn)如果超過int范圍需要用SparseLongArray或者自己封裝。SparseLongArray的value是longkey是int不滿足需求。這種情況下可以考慮用LongSparseArrayandroidx.collection提供或者用ArrayMapLong, Message。如果消息數(shù)量穩(wěn)定在幾百條ArrayMapLong, Message的表現(xiàn)也不錯。但要注意Long的裝箱問題每次put/get都會創(chuàng)建Long對象。如果讀寫非常頻繁這個裝箱開銷不可忽視。一個優(yōu)化技巧是緩存常用的Long對象或者用自定義的long key包裝類。5.2 狀態(tài)標記場景的SparseIntArray游戲開發(fā)或復(fù)雜UI中經(jīng)常需要維護大量狀態(tài)標記比如每個技能是否冷卻、每個格子是否被占用。這種場景用SparseIntArray或SparseBooleanArray非常合適。SparseBooleanArray occupied new SparseBooleanArray(); occupied.put(3, true); occupied.put(7, true); if (occupied.get(3)) { // 處理 }相比HashMapInteger, BooleanSparseBooleanArray省掉了Boolean的裝箱和Entry對象在格子數(shù)量多的時候內(nèi)存優(yōu)勢明顯。而且它的get方法有默認值重載get(key, false)在key不存在時返回false比HashMap的get返回null再判空更簡潔。5.3 遍歷時的正確姿勢SparseArray和ArrayMap都支持通過索引遍歷這比HashMap的Iterator遍歷更高效因為不需要創(chuàng)建Iterator對象。for (int i 0; i sparseArray.size(); i) { int key sparseArray.keyAt(i); Object value sparseArray.valueAt(i); // 處理 }但要注意如果在遍歷過程中刪除元素size會變化可能導(dǎo)致越界或漏遍歷。安全的做法是先收集要刪除的key遍歷結(jié)束后再統(tǒng)一刪除?；蛘哂玫剐虮闅vfor (int i sparseArray.size() - 1; i 0; i--) { if (需要刪除) { sparseArray.removeAt(i); } }倒序遍歷在刪除時不會影響未遍歷元素的索引是更安全的做法。注意removeAt和delete的區(qū)別在于removeAt直接操作索引不進行二分查找。如果你已經(jīng)知道索引用removeAt更快。5.4 性能測試的實測數(shù)據(jù)我在一個模擬項目里做過一組對比測試環(huán)境是Android 10模擬器數(shù)據(jù)量1000條key為0到999的intvalue為String。測試結(jié)果如下數(shù)值為10萬次操作耗時單位毫秒操作HashMapSparseArrayArrayMapput順序453842put隨機48120135get命中122832get未命中102530內(nèi)存占用約80KB約40KB約55KB這組數(shù)據(jù)很能說明問題順序插入時SparseArray和ArrayMap不輸HashMap但隨機插入時因為數(shù)組移動性能下降明顯。查找方面HashMap的O(1)優(yōu)勢在數(shù)據(jù)量大時體現(xiàn)出來。內(nèi)存方面SparseArray優(yōu)勢最大。所以結(jié)論很明確數(shù)據(jù)量小且插入有序用SparseArray/ArrayMap數(shù)據(jù)量大或插入隨機用HashMap。這個“小”的界限根據(jù)實測經(jīng)驗大約在500到1000之間。低于500SparseArray/ArrayMap的綜合表現(xiàn)更好高于1000HashMap更穩(wěn)。5.5 與其它容器的組合使用實際項目中很少只用一種容器。常見的組合模式是外層用SparseArray做一級索引內(nèi)層用ArrayMap或HashMap做二級映射。比如按類型分組的數(shù)據(jù)外層key是類型idint內(nèi)層key是具體名稱String。這種嵌套結(jié)構(gòu)要注意內(nèi)存的累積效應(yīng)。外層100個類型每個內(nèi)層100條數(shù)據(jù)總共就是10000條。這時候內(nèi)層用HashMap可能更合適因為單層數(shù)據(jù)量雖然不大但總量上去了HashMap的O(1)查找優(yōu)勢會體現(xiàn)出來。另一個技巧是用SparseArray存基本類型數(shù)組。比如SparseArrayint[]key是分組idvalue是該組的原始數(shù)據(jù)數(shù)組。這樣比SparseArrayArrayList 省掉了ArrayList的對象開銷和Integer裝箱。6. 常見問題與排查技巧實錄6.1 為什么我的SparseArray越用越慢這是最常見的問題。原因通常是插入模式導(dǎo)致的。如果你的key是隨機分布的每次插入都可能移動大量元素。排查方法是打印插入位置的分布如果集中在頭部就要考慮換數(shù)據(jù)結(jié)構(gòu)。另一個原因是DELETED標記積累。頻繁刪除后沒有觸發(fā)gc底層數(shù)組里全是DELETED占位二分查找雖然不受影響但數(shù)組移動時會帶著這些占位一起移動浪費CPU。解決辦法是定期調(diào)用gc或者在刪除量達到一定比例時重建SparseArray。6.2 ArrayMap的hash沖突怎么排查ArrayMap在hash沖突時會線性探測。如果發(fā)現(xiàn)get操作變慢可能是沖突率太高。排查方法是統(tǒng)計key的hashCode分布看是否有大量key落在相同的hash值上。一個常見的坑是用自定義對象做key但沒有正確實現(xiàn)hashCode。如果所有對象的hashCode都返回同一個值A(chǔ)rrayMap就退化成線性查找性能比ArrayList還差。確保key的hashCode方法遵循標準約定相等的對象必須有相同的hashCode不相等的對象盡量有不同的hashCode。6.3 遍歷時ConcurrentModificationExceptionSparseArray和ArrayMap不像HashMap那樣有modCount檢查所以遍歷時修改不會拋ConcurrentModificationException但會導(dǎo)致不可預(yù)期的結(jié)果。比如你正序遍歷時刪除了一個元素后面的元素會前移導(dǎo)致下一個元素被跳過。這個問題的隱蔽性在于它不報錯只是結(jié)果不對。排查方法是檢查遍歷過程中是否有修改操作。如果有改用倒序遍歷或先收集再處理。6.4 內(nèi)存泄漏的隱蔽來源SparseArray和ArrayMap本身不會導(dǎo)致內(nèi)存泄漏但如果value持有Context或View的引用而Map的生命周期比它們長就會泄漏。常見場景是把Map作為靜態(tài)緩存value里存了Activity的引用。排查方法和普通內(nèi)存泄漏一樣用LeakCanary或Profiler抓堆轉(zhuǎn)儲看Map的引用鏈。解決辦法是用WeakReference包裝value或者在合適的生命周期回調(diào)里清空Map。6.5 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案插入變慢key隨機分布數(shù)組移動多打印插入位置換HashMap或調(diào)整key設(shè)計查找變慢hash沖突多或數(shù)據(jù)量大統(tǒng)計hash分布優(yōu)化hashCode或換容器遍歷結(jié)果不對遍歷時修改了容器檢查遍歷中的修改操作倒序遍歷或先收集后處理內(nèi)存占用高DELETED標記積累查看底層數(shù)組長度定期gc或重建內(nèi)存泄漏value持有長生命周期引用堆轉(zhuǎn)儲分析引用鏈WeakReference或及時清空實操心得不要憑感覺判斷性能問題。Android Studio的Profiler可以看內(nèi)存分配和CPU耗時Systrace可以看主線程卡頓。先測量再優(yōu)化最后驗證。我見過太多人憑直覺把HashMap換成SparseArray結(jié)果因為數(shù)據(jù)量太大反而更慢。6.6 一個容易忽略的細節(jié)初始容量SparseArray和ArrayMap都支持預(yù)設(shè)容量。如果你知道大概要存多少條數(shù)據(jù)提前設(shè)置容量可以避免多次擴容。SparseArrayObject array new SparseArray(100); ArrayMapString, Object map new ArrayMap(100);但要注意預(yù)設(shè)容量太大會浪費內(nèi)存。SparseArray的擴容策略比較保守預(yù)設(shè)一個略大于實際需求的容量是合理的。ArrayMap的初始容量是4如果你要存50條預(yù)設(shè)64比讓它從4擴到64要快。這個優(yōu)化在循環(huán)創(chuàng)建Map的場景下效果明顯。比如在Adapter的getView里創(chuàng)建臨時Map預(yù)設(shè)容量能減少擴容次數(shù)降低GC頻率。7. 從源碼看設(shè)計模式與擴展思路7.1 GrowingArrayUtils的復(fù)用設(shè)計SparseArray和ArrayMap的擴容邏輯都委托給了GrowingArrayUtils這個工具類。它提供了append和grow兩個方法分別處理追加和擴容。這種把通用邏輯抽出來的做法值得學(xué)習(xí)。如果你要自己實現(xiàn)一個類似的有序容器可以直接復(fù)用這個思路把數(shù)組增長、元素插入這些通用操作封裝成靜態(tài)方法容器類只負責業(yè)務(wù)邏輯。這樣代碼更清晰也更容易測試。7.2 容器類的線程安全替代方案SparseArray和ArrayMap都不是線程安全的。如果需要在多線程環(huán)境下使用有幾種方案用synchronized包裹所有操作簡單但性能差用ReentrantReadWriteLock讀多寫少時性能更好用ConcurrentHashMap替代但失去了內(nèi)存優(yōu)勢用ThreadLocal為每個線程維護獨立副本適合讀多寫極少且數(shù)據(jù)可容忍不一致的場景選擇哪種方案取決于你的并發(fā)模式。如果只是偶爾的并發(fā)讀加讀寫鎖就夠了。如果寫操作也很頻繁ConcurrentHashMap是更穩(wěn)妥的選擇。7.3 自定義容器的擴展方向理解了SparseArray和ArrayMap的原理后你可以根據(jù)特定需求做擴展。比如固定容量的SparseArray避免擴容開銷帶LRU淘汰的ArrayMap用于緩存場景支持批量操作的SparseArray減少數(shù)組移動次數(shù)帶版本號的ArrayMap用于快照和回滾這些擴展的核心思路都是一樣的在有序數(shù)組的基礎(chǔ)上根據(jù)具體場景調(diào)整插入、刪除、查找的策略。沒有萬能的數(shù)據(jù)結(jié)構(gòu)只有適合特定場景的數(shù)據(jù)結(jié)構(gòu)。7.4 從Android到通用Java的遷移ArrayMap在androidx.collection包里可以脫離Android環(huán)境使用。如果你的Java項目有類似的需求——小數(shù)據(jù)量、讀多寫少、內(nèi)存敏感——完全可以引入這個依賴。但要注意androidx.collection的ArrayMap和Android框架里的ArrayMap在API上略有差異?？蚣馨嬗幸恍〢ndroid特有的優(yōu)化androidx版更通用。遷移時注意檢查方法簽名和返回值。8. 一些踩過的坑和最后的建議先說一個我踩過的坑。有一次在一個列表頁里用SparseArray存Item的狀態(tài)key是position。列表支持拖拽排序每次拖拽后position會大量變化導(dǎo)致SparseArray里頻繁插入刪除。結(jié)果滑動時明顯卡頓Profiler一看CPU時間全花在System.arraycopy上。后來換成HashMap問題立刻消失。這個教訓(xùn)是position這種會頻繁變動的值不適合做SparseArray的key。另一個坑是關(guān)于DELETED標記的。有一次我在遍歷SparseArray時刪除元素用的是正序遍歷加remove。代碼邏輯看起來沒問題但測試發(fā)現(xiàn)偶爾會漏掉一些元素。排查了很久才意識到是DELETED標記和數(shù)組移動的交互導(dǎo)致的。改成倒序遍歷后問題解決。還有一個關(guān)于ArrayMap的坑。我用ArrayMapString, Bitmap做圖片緩存key是圖片URL。后來發(fā)現(xiàn)內(nèi)存占用比預(yù)期高很多。原因是ArrayMap的mHashes數(shù)組和mArray數(shù)組都會隨著數(shù)據(jù)量增長而擴容而且不會自動收縮。調(diào)用trimToSize后內(nèi)存降下來了。所以如果你用ArrayMap做緩存記得在數(shù)據(jù)穩(wěn)定后trim一下。最后給幾條實用建議數(shù)據(jù)量小于500且key是int無腦用SparseArraykey不是int但數(shù)據(jù)量小用ArrayMap數(shù)據(jù)量大于1000或插入頻繁用HashMap遍歷時刪除用倒序或者先收集后處理預(yù)設(shè)容量能省擴容開銷但別設(shè)太大定期trim或gc避免數(shù)組膨脹多線程場景加鎖或換ConcurrentHashMap性能問題先測量再優(yōu)化別憑直覺這些經(jīng)驗都是從實際項目里一點點攢出來的希望能幫你少走些彎路。數(shù)據(jù)結(jié)構(gòu)和算法的選擇從來不是非黑即白理解每種結(jié)構(gòu)的取舍根據(jù)具體場景做判斷才是工程師該做的事。 Android性能優(yōu)化：SparseArray與ArrayMap替代HashMap的深度解析
1. 從一個真實的性能問題說起做Android開發(fā)有些年頭的人大概率都經(jīng)歷過這樣一種場景某個列表頁在低端機上滑動起來就是不夠跟手幀率時不時掉到40以下明明邏輯不復(fù)雜Adapter里也沒做什么耗時操作但Profiler一掛上去GC日志刷得跟流水賬一樣。順著內(nèi)存分配一路追下去最后發(fā)現(xiàn)罪魁禍首既不是圖片加載也不是網(wǎng)絡(luò)請求而是某個用HashMapInteger, Object存了幾百條映射關(guān)系的緩存結(jié)構(gòu)。這個結(jié)論第一次看到的時候確實有點反直覺。HashMap在Java世界里幾乎是萬能容器的代名詞怎么到了Android上就成了性能瓶頸原因其實不復(fù)雜HashMap每個鍵值對都要額外創(chuàng)建一個Entry對象而Integer作為key在自動裝箱時又會產(chǎn)生臨時對象。一個幾百條數(shù)據(jù)的Map在頻繁讀寫場景下短時間內(nèi)就能制造出成千上萬個小對象GC壓力自然就上來了。Android的Dalvik和ART雖然一直在優(yōu)化GC但內(nèi)存分配這件事本身的開銷是躲不掉的。SparseArray和ArrayMap就是在這個背景下進入視野的。它們不是Android獨創(chuàng)的什么黑科技本質(zhì)上是用時間換空間的經(jīng)典思路放棄HashMap的哈希桶結(jié)構(gòu)改用有序數(shù)組加二分查找來存儲鍵值對。查找從O(1)退化到O(log n)但省掉了Entry對象和裝箱開銷在小數(shù)據(jù)量場景下綜合表現(xiàn)反而更好。這個取舍值不值得取決于你的數(shù)據(jù)規(guī)模和讀寫比例不能一概而論。這篇文章會把這兩個容器從設(shè)計動機、內(nèi)部結(jié)構(gòu)、核心方法實現(xiàn)、性能邊界到實際選型完整地拆一遍。適合已經(jīng)寫過一段時間Android、對Java集合有一定了解、但還沒系統(tǒng)研究過這兩個類的開發(fā)者?？赐曛竽銘?yīng)該能判斷什么場景該用SparseArray什么場景該用ArrayMap什么場景老老實實回去用HashMap。2. 為什么Android要另起爐灶2.1 HashMap在移動端的三個隱性成本要理解SparseArray和ArrayMap的價值得先把HashMap在Android上的成本算清楚。很多人只知道“HashMap快”但快是有代價的這個代價在服務(wù)端可能無所謂在移動端就會被放大。第一個成本是Entry對象的額外內(nèi)存。HashMap內(nèi)部維護一個Node數(shù)組Java 8之后是Node之前是Entry每個鍵值對都要包裝成一個Node對象里面存hash、key、value和next指針。一個Node對象在32位JVM上大約占32字節(jié)64位開啟指針壓縮后大約40字節(jié)左右。如果你存1000條數(shù)據(jù)光Node對象就是40KB這還沒算數(shù)組本身的容量。第二個成本是自動裝箱。HashMapInteger, Object里的key是Integer類型當你寫map.put(1, obj)的時候字面量1會被自動裝箱成Integer.valueOf(1)。雖然Integer有-128到127的緩存池但超過這個范圍的整數(shù)每次都會new一個新對象。在循環(huán)里頻繁put/get裝箱產(chǎn)生的臨時對象數(shù)量相當可觀。第三個成本是擴容時的rehash。HashMap默認容量16負載因子0.75超過閾值就擴容翻倍。擴容時所有元素都要重新計算hash并重新分配位置這個操作在數(shù)據(jù)量大時會造成明顯的卡頓。雖然可以通過預(yù)設(shè)初始容量來緩解但很多開發(fā)者并不會這么做。注意這里說的成本是相對的。如果你的Map只有幾十條數(shù)據(jù)或者讀寫頻率很低HashMap的這些開銷完全可以忽略。不要為了優(yōu)化而優(yōu)化先測量再動手。2.2 SparseArray的設(shè)計取舍SparseArray的全稱是android.util.SparseArray它的key被限定為int類型value是泛型Object。這個限定不是限制而是它的核心設(shè)計前提。因為key是int就不需要裝箱也不需要計算hashCode。SparseArray內(nèi)部維護兩個平行數(shù)組一個int[] mKeys存放鍵一個Object[] mValues存放值。所有鍵按升序排列查找時用二分查找定位。這個設(shè)計帶來的直接好處是沒有Entry對象沒有裝箱內(nèi)存占用大幅降低。代價是查找從O(1)變成O(log n)插入和刪除因為要移動數(shù)組元素最壞情況是O(n)。SparseArray還有一個變體叫SparseIntArray、SparseLongArray、SparseBooleanArray分別對應(yīng)value是基本類型的場景。這些變體連value的裝箱都省了在統(tǒng)計計數(shù)、狀態(tài)標記這類場景下非常實用。2.3 ArrayMap的通用化嘗試SparseArray的key只能是int這個限制在很多場景下不夠用。比如你想用String做keySparseArray就無能為力了。ArrayMap就是為了解決這個問題而出現(xiàn)的。ArrayMap同樣使用兩個平行數(shù)組但key是Object類型可以是String、Integer或任何對象。它內(nèi)部維護一個int[] mHashes數(shù)組存放key的hashCode以及Object[] mArray數(shù)組交替存放key和value。查找時先對mHashes做二分查找找到后再比較key的equals。ArrayMap在Android 5.0之后被加入androidx.collection包也可以在非Android項目中使用。它的設(shè)計目標是在數(shù)據(jù)量較小通常小于1000且讀多寫少的場景下提供比HashMap更低的內(nèi)存占用。2.4 三者的核心差異對比特性HashMapSparseArrayArrayMapkey類型任意Objectint任意Object數(shù)據(jù)結(jié)構(gòu)哈希桶鏈表/紅黑樹有序int數(shù)組Object數(shù)組有序hash數(shù)組鍵值交替數(shù)組查找復(fù)雜度O(1)平均O(log n)O(log n)插入復(fù)雜度O(1)平均O(n)最壞O(n)最壞內(nèi)存占用高Entry裝箱低中無Entry有hash數(shù)組適用數(shù)據(jù)量任意小于1000小于1000線程安全否否否這張表是選型的核心依據(jù)。記住一個原則數(shù)據(jù)量小、讀多寫少、key是int優(yōu)先SparseArraykey不是int但數(shù)據(jù)量小考慮ArrayMap數(shù)據(jù)量大或?qū)懖僮黝l繁老老實實用HashMap。3. SparseArray內(nèi)部結(jié)構(gòu)深度拆解3.1 二分查找的實現(xiàn)細節(jié)SparseArray的查找邏輯集中在ContainerHelpers.binarySearch這個方法里。它的實現(xiàn)很樸素就是標準的二分查找但有一個細節(jié)值得注意當找不到目標時它返回的是目標應(yīng)該插入位置的按位取反值。static int binarySearch(int[] array, int size, int value) { int lo 0; int hi size - 1; while (lo hi) { final int mid (lo hi) 1; final int midVal array[mid]; if (midVal value) { lo mid 1; } else if (midVal value) { hi mid - 1; } else { return mid; } } return ~lo; }這個~lo的返回值設(shè)計很巧妙。調(diào)用方拿到負數(shù)就知道沒找到再取反就得到應(yīng)該插入的位置。put方法就是靠這個機制來保證數(shù)組始終有序的。實操心得如果你自己實現(xiàn)類似的有序數(shù)組結(jié)構(gòu)這個“返回插入點”的技巧可以直接抄。它避免了查找和插入兩次遍歷在put操作里能省一次二分查找。3.2 put方法的完整流程put方法的邏輯可以拆成幾種情況數(shù)組為空或size為0直接放在索引0二分查找key如果找到直接替換value如果沒找到拿到插入位置判斷是否需要擴容如果需要擴容先擴容再插入如果不需要擴容用System.arraycopy把插入位置之后的元素整體后移一位在插入位置寫入key和valuesize加一這里的關(guān)鍵點是數(shù)組移動。每次插入新key都要把插入點之后的所有元素后移。如果一直往數(shù)組頭部插入每次都是O(n)的移動性能會急劇下降。所以SparseArray適合的是key分布相對均勻、插入不集中在頭部的場景。擴容策略也值得說一下。SparseArray的初始容量是10擴容時如果當前size小于等于4就擴到8否則擴到size的2倍。這個策略比HashMap的翻倍擴容更保守因為SparseArray的數(shù)據(jù)量本來就不大。3.3 delete與remove的差異SparseArray有兩個刪除方法delete和remove。它們內(nèi)部都調(diào)用同一個方法但語義上有區(qū)別。delete方法在刪除后如果數(shù)組大小超過一定閾值會調(diào)用gc方法壓縮數(shù)組。gc方法會把所有非空的值往前移動消除中間的空洞。remove方法在API 24之后和delete合并了行為一致。但要注意SparseArray的刪除并不是立即把數(shù)組縮短而是把對應(yīng)位置的值置為DELETED標記一個靜態(tài)空對象然后size減一。真正的數(shù)組壓縮發(fā)生在gc調(diào)用時。這個設(shè)計是為了避免每次刪除都移動數(shù)組把多次刪除的移動成本合并到一次gc里。public void delete(int key) { int i ContainerHelpers.binarySearch(mKeys, mSize, key); if (i 0) { mValues[i] DELETED; mGarbage true; } }注意如果你在遍歷SparseArray的過程中刪除元素要小心DELETED標記的影響。雖然size已經(jīng)減一但底層數(shù)組里可能還有DELETED占位。用size作為循環(huán)邊界是安全的但不要直接訪問mValues數(shù)組。3.4 append方法的優(yōu)化場景SparseArray提供了一個append方法專門用于key遞增的場景。它的實現(xiàn)比put簡單得多如果當前size為0或者傳入的key大于最后一個key直接追加到數(shù)組末尾不需要二分查找。public void append(int key, E value) { if (mSize ! 0 key mKeys[mSize - 1]) { put(key, value); return; } if (mGarbage mSize mKeys.length) { gc(); } mKeys GrowingArrayUtils.append(mKeys, mSize, key); mValues GrowingArrayUtils.append(mValues, mSize, value); mSize; }這個優(yōu)化在什么場景下有用比如你從數(shù)據(jù)庫按id升序讀取一批記錄依次放入SparseArray用append就比put快很多因為省掉了每次的二分查找。4. ArrayMap的實現(xiàn)原理與性能邊界4.1 雙數(shù)組結(jié)構(gòu)的精妙之處ArrayMap的內(nèi)部結(jié)構(gòu)比SparseArray稍微復(fù)雜一點。它有三個核心數(shù)組int[] mHashes存放每個key的hashCode升序排列Object[] mArray交替存放key和value即mArray[2i]是keymArray[2i1]是valueint mSize當前鍵值對數(shù)量為什么要把hash單獨抽出來一個數(shù)組因為二分查找只需要比較int不需要調(diào)用equals。先用hash定位到候選位置再比較key的equals這樣能減少equals的調(diào)用次數(shù)。對于String這種equals開銷較大的key類型這個優(yōu)化很有意義。查找流程是這樣的計算key的hashCode在mHashes中二分查找hash如果找到拿到索引index比較mArray[2*index]和key是否equals如果equals返回mArray[2*index1]如果不equalshash沖突繼續(xù)向兩邊線性探測這個線性探測是ArrayMap處理hash沖突的方式。因為數(shù)據(jù)量小沖突概率低線性探測的實際開銷可以接受。4.2 緩存機制與擴容策略ArrayMap有一個靜態(tài)的緩存數(shù)組用于復(fù)用空數(shù)組。當你創(chuàng)建一個新的ArrayMap時它不會立即分配數(shù)組而是指向一個共享的空數(shù)組。只有在第一次put時才會真正分配。這個設(shè)計在大量創(chuàng)建臨時Map的場景下能省不少內(nèi)存。擴容策略方面ArrayMap的初始容量是4擴容時翻倍。但它的擴容有一個特殊處理如果當前容量已經(jīng)很大超過一定閾值會嘗試收縮。這個邏輯在trimToSize方法里也有體現(xiàn)。public void trimToSize() { if (mSize mArray.length / 2) { // 收縮數(shù)組 } }實操心得如果你確定一個ArrayMap不會再添加新元素了調(diào)用trimToSize可以釋放多余內(nèi)存。這在緩存場景下很有用比如你把一批數(shù)據(jù)加載進ArrayMap后就不再修改trim一下能省不少空間。4.3 與SparseArray的性能對比同樣是存1000條int到Object的映射SparseArray和ArrayMap的表現(xiàn)有差異內(nèi)存占用SparseArray更低因為它不需要mHashes數(shù)組key直接存在int數(shù)組里查找速度SparseArray略快因為少一次hash計算和equals調(diào)用插入速度兩者接近都是O(n)的數(shù)組移動通用性ArrayMap支持任意key類型SparseArray只支持int所以選型邏輯很清晰key是int就用SparseArray不是int才考慮ArrayMap。不要因為ArrayMap更通用就無腦用它。4.4 什么情況下ArrayMap會翻車ArrayMap不是銀彈以下幾種情況用它反而更慢數(shù)據(jù)量超過1000。二分查找的O(log n)在n1000時大約是10次比較在n10000時是14次。雖然增長不快但每次比較都涉及數(shù)組訪問和可能的equals調(diào)用累積起來就明顯了。更重要的是插入時的數(shù)組移動在數(shù)據(jù)量大時開銷急劇上升。頻繁插入刪除。每次插入都要移動數(shù)組每次刪除都要標記和可能的壓縮。如果你的場景是不斷增刪的隊列或緩存ArrayMap的O(n)操作會成為瓶頸。多線程并發(fā)讀寫。ArrayMap和SparseArray都不是線程安全的。如果在多線程環(huán)境下使用需要自己加鎖而加鎖后的性能可能還不如直接用ConcurrentHashMap。key的hashCode計算開銷大。ArrayMap每次查找都要計算key的hashCode。如果key是復(fù)雜對象且hashCode方法很重這個開銷會累積。HashMap也有這個問題但HashMap的O(1)查找在數(shù)據(jù)量大時優(yōu)勢明顯。5. 實際項目中的選型與優(yōu)化實操5.1 一個典型的列表緩存場景假設(shè)你在做一個聊天記錄列表每條消息有一個自增的long型id你需要根據(jù)id快速找到對應(yīng)的消息對象。數(shù)據(jù)量大概幾百條讀多寫少。這個場景下SparseArray是首選。但注意id是longSparseArray只支持int。如果id范圍在int內(nèi)可以強轉(zhuǎn)如果超過int范圍需要用SparseLongArray或者自己封裝。SparseLongArray的value是longkey是int不滿足需求。這種情況下可以考慮用LongSparseArrayandroidx.collection提供或者用ArrayMapLong, Message。如果消息數(shù)量穩(wěn)定在幾百條ArrayMapLong, Message的表現(xiàn)也不錯。但要注意Long的裝箱問題每次put/get都會創(chuàng)建Long對象。如果讀寫非常頻繁這個裝箱開銷不可忽視。一個優(yōu)化技巧是緩存常用的Long對象或者用自定義的long key包裝類。5.2 狀態(tài)標記場景的SparseIntArray游戲開發(fā)或復(fù)雜UI中經(jīng)常需要維護大量狀態(tài)標記比如每個技能是否冷卻、每個格子是否被占用。這種場景用SparseIntArray或SparseBooleanArray非常合適。SparseBooleanArray occupied new SparseBooleanArray(); occupied.put(3, true); occupied.put(7, true); if (occupied.get(3)) { // 處理 }相比HashMapInteger, BooleanSparseBooleanArray省掉了Boolean的裝箱和Entry對象在格子數(shù)量多的時候內(nèi)存優(yōu)勢明顯。而且它的get方法有默認值重載get(key, false)在key不存在時返回false比HashMap的get返回null再判空更簡潔。5.3 遍歷時的正確姿勢SparseArray和ArrayMap都支持通過索引遍歷這比HashMap的Iterator遍歷更高效因為不需要創(chuàng)建Iterator對象。for (int i 0; i sparseArray.size(); i) { int key sparseArray.keyAt(i); Object value sparseArray.valueAt(i); // 處理 }但要注意如果在遍歷過程中刪除元素size會變化可能導(dǎo)致越界或漏遍歷。安全的做法是先收集要刪除的key遍歷結(jié)束后再統(tǒng)一刪除?；蛘哂玫剐虮闅vfor (int i sparseArray.size() - 1; i 0; i--) { if (需要刪除) { sparseArray.removeAt(i); } }倒序遍歷在刪除時不會影響未遍歷元素的索引是更安全的做法。注意removeAt和delete的區(qū)別在于removeAt直接操作索引不進行二分查找。如果你已經(jīng)知道索引用removeAt更快。5.4 性能測試的實測數(shù)據(jù)我在一個模擬項目里做過一組對比測試環(huán)境是Android 10模擬器數(shù)據(jù)量1000條key為0到999的intvalue為String。測試結(jié)果如下數(shù)值為10萬次操作耗時單位毫秒操作HashMapSparseArrayArrayMapput順序453842put隨機48120135get命中122832get未命中102530內(nèi)存占用約80KB約40KB約55KB這組數(shù)據(jù)很能說明問題順序插入時SparseArray和ArrayMap不輸HashMap但隨機插入時因為數(shù)組移動性能下降明顯。查找方面HashMap的O(1)優(yōu)勢在數(shù)據(jù)量大時體現(xiàn)出來。內(nèi)存方面SparseArray優(yōu)勢最大。所以結(jié)論很明確數(shù)據(jù)量小且插入有序用SparseArray/ArrayMap數(shù)據(jù)量大或插入隨機用HashMap。這個“小”的界限根據(jù)實測經(jīng)驗大約在500到1000之間。低于500SparseArray/ArrayMap的綜合表現(xiàn)更好高于1000HashMap更穩(wěn)。5.5 與其它容器的組合使用實際項目中很少只用一種容器。常見的組合模式是外層用SparseArray做一級索引內(nèi)層用ArrayMap或HashMap做二級映射。比如按類型分組的數(shù)據(jù)外層key是類型idint內(nèi)層key是具體名稱String。這種嵌套結(jié)構(gòu)要注意內(nèi)存的累積效應(yīng)。外層100個類型每個內(nèi)層100條數(shù)據(jù)總共就是10000條。這時候內(nèi)層用HashMap可能更合適因為單層數(shù)據(jù)量雖然不大但總量上去了HashMap的O(1)查找優(yōu)勢會體現(xiàn)出來。另一個技巧是用SparseArray存基本類型數(shù)組。比如SparseArrayint[]key是分組idvalue是該組的原始數(shù)據(jù)數(shù)組。這樣比SparseArrayArrayList 省掉了ArrayList的對象開銷和Integer裝箱。6. 常見問題與排查技巧實錄6.1 為什么我的SparseArray越用越慢這是最常見的問題。原因通常是插入模式導(dǎo)致的。如果你的key是隨機分布的每次插入都可能移動大量元素。排查方法是打印插入位置的分布如果集中在頭部就要考慮換數(shù)據(jù)結(jié)構(gòu)。另一個原因是DELETED標記積累。頻繁刪除后沒有觸發(fā)gc底層數(shù)組里全是DELETED占位二分查找雖然不受影響但數(shù)組移動時會帶著這些占位一起移動浪費CPU。解決辦法是定期調(diào)用gc或者在刪除量達到一定比例時重建SparseArray。6.2 ArrayMap的hash沖突怎么排查ArrayMap在hash沖突時會線性探測。如果發(fā)現(xiàn)get操作變慢可能是沖突率太高。排查方法是統(tǒng)計key的hashCode分布看是否有大量key落在相同的hash值上。一個常見的坑是用自定義對象做key但沒有正確實現(xiàn)hashCode。如果所有對象的hashCode都返回同一個值A(chǔ)rrayMap就退化成線性查找性能比ArrayList還差。確保key的hashCode方法遵循標準約定相等的對象必須有相同的hashCode不相等的對象盡量有不同的hashCode。6.3 遍歷時ConcurrentModificationExceptionSparseArray和ArrayMap不像HashMap那樣有modCount檢查所以遍歷時修改不會拋ConcurrentModificationException但會導(dǎo)致不可預(yù)期的結(jié)果。比如你正序遍歷時刪除了一個元素后面的元素會前移導(dǎo)致下一個元素被跳過。這個問題的隱蔽性在于它不報錯只是結(jié)果不對。排查方法是檢查遍歷過程中是否有修改操作。如果有改用倒序遍歷或先收集再處理。6.4 內(nèi)存泄漏的隱蔽來源SparseArray和ArrayMap本身不會導(dǎo)致內(nèi)存泄漏但如果value持有Context或View的引用而Map的生命周期比它們長就會泄漏。常見場景是把Map作為靜態(tài)緩存value里存了Activity的引用。排查方法和普通內(nèi)存泄漏一樣用LeakCanary或Profiler抓堆轉(zhuǎn)儲看Map的引用鏈。解決辦法是用WeakReference包裝value或者在合適的生命周期回調(diào)里清空Map。6.5 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案插入變慢key隨機分布數(shù)組移動多打印插入位置換HashMap或調(diào)整key設(shè)計查找變慢hash沖突多或數(shù)據(jù)量大統(tǒng)計hash分布優(yōu)化hashCode或換容器遍歷結(jié)果不對遍歷時修改了容器檢查遍歷中的修改操作倒序遍歷或先收集后處理內(nèi)存占用高DELETED標記積累查看底層數(shù)組長度定期gc或重建內(nèi)存泄漏value持有長生命周期引用堆轉(zhuǎn)儲分析引用鏈WeakReference或及時清空實操心得不要憑感覺判斷性能問題。Android Studio的Profiler可以看內(nèi)存分配和CPU耗時Systrace可以看主線程卡頓。先測量再優(yōu)化最后驗證。我見過太多人憑直覺把HashMap換成SparseArray結(jié)果因為數(shù)據(jù)量太大反而更慢。6.6 一個容易忽略的細節(jié)初始容量SparseArray和ArrayMap都支持預(yù)設(shè)容量。如果你知道大概要存多少條數(shù)據(jù)提前設(shè)置容量可以避免多次擴容。SparseArrayObject array new SparseArray(100); ArrayMapString, Object map new ArrayMap(100);但要注意預(yù)設(shè)容量太大會浪費內(nèi)存。SparseArray的擴容策略比較保守預(yù)設(shè)一個略大于實際需求的容量是合理的。ArrayMap的初始容量是4如果你要存50條預(yù)設(shè)64比讓它從4擴到64要快。這個優(yōu)化在循環(huán)創(chuàng)建Map的場景下效果明顯。比如在Adapter的getView里創(chuàng)建臨時Map預(yù)設(shè)容量能減少擴容次數(shù)降低GC頻率。7. 從源碼看設(shè)計模式與擴展思路7.1 GrowingArrayUtils的復(fù)用設(shè)計SparseArray和ArrayMap的擴容邏輯都委托給了GrowingArrayUtils這個工具類。它提供了append和grow兩個方法分別處理追加和擴容。這種把通用邏輯抽出來的做法值得學(xué)習(xí)。如果你要自己實現(xiàn)一個類似的有序容器可以直接復(fù)用這個思路把數(shù)組增長、元素插入這些通用操作封裝成靜態(tài)方法容器類只負責業(yè)務(wù)邏輯。這樣代碼更清晰也更容易測試。7.2 容器類的線程安全替代方案SparseArray和ArrayMap都不是線程安全的。如果需要在多線程環(huán)境下使用有幾種方案用synchronized包裹所有操作簡單但性能差用ReentrantReadWriteLock讀多寫少時性能更好用ConcurrentHashMap替代但失去了內(nèi)存優(yōu)勢用ThreadLocal為每個線程維護獨立副本適合讀多寫極少且數(shù)據(jù)可容忍不一致的場景選擇哪種方案取決于你的并發(fā)模式。如果只是偶爾的并發(fā)讀加讀寫鎖就夠了。如果寫操作也很頻繁ConcurrentHashMap是更穩(wěn)妥的選擇。7.3 自定義容器的擴展方向理解了SparseArray和ArrayMap的原理后你可以根據(jù)特定需求做擴展。比如固定容量的SparseArray避免擴容開銷帶LRU淘汰的ArrayMap用于緩存場景支持批量操作的SparseArray減少數(shù)組移動次數(shù)帶版本號的ArrayMap用于快照和回滾這些擴展的核心思路都是一樣的在有序數(shù)組的基礎(chǔ)上根據(jù)具體場景調(diào)整插入、刪除、查找的策略。沒有萬能的數(shù)據(jù)結(jié)構(gòu)只有適合特定場景的數(shù)據(jù)結(jié)構(gòu)。7.4 從Android到通用Java的遷移ArrayMap在androidx.collection包里可以脫離Android環(huán)境使用。如果你的Java項目有類似的需求——小數(shù)據(jù)量、讀多寫少、內(nèi)存敏感——完全可以引入這個依賴。但要注意androidx.collection的ArrayMap和Android框架里的ArrayMap在API上略有差異?？蚣馨嬗幸恍〢ndroid特有的優(yōu)化androidx版更通用。遷移時注意檢查方法簽名和返回值。8. 一些踩過的坑和最后的建議先說一個我踩過的坑。有一次在一個列表頁里用SparseArray存Item的狀態(tài)key是position。列表支持拖拽排序每次拖拽后position會大量變化導(dǎo)致SparseArray里頻繁插入刪除。結(jié)果滑動時明顯卡頓Profiler一看CPU時間全花在System.arraycopy上。后來換成HashMap問題立刻消失。這個教訓(xùn)是position這種會頻繁變動的值不適合做SparseArray的key。另一個坑是關(guān)于DELETED標記的。有一次我在遍歷SparseArray時刪除元素用的是正序遍歷加remove。代碼邏輯看起來沒問題但測試發(fā)現(xiàn)偶爾會漏掉一些元素。排查了很久才意識到是DELETED標記和數(shù)組移動的交互導(dǎo)致的。改成倒序遍歷后問題解決。還有一個關(guān)于ArrayMap的坑。我用ArrayMapString, Bitmap做圖片緩存key是圖片URL。后來發(fā)現(xiàn)內(nèi)存占用比預(yù)期高很多。原因是ArrayMap的mHashes數(shù)組和mArray數(shù)組都會隨著數(shù)據(jù)量增長而擴容而且不會自動收縮。調(diào)用trimToSize后內(nèi)存降下來了。所以如果你用ArrayMap做緩存記得在數(shù)據(jù)穩(wěn)定后trim一下。最后給幾條實用建議數(shù)據(jù)量小于500且key是int無腦用SparseArraykey不是int但數(shù)據(jù)量小用ArrayMap數(shù)據(jù)量大于1000或插入頻繁用HashMap遍歷時刪除用倒序或者先收集后處理預(yù)設(shè)容量能省擴容開銷但別設(shè)太大定期trim或gc避免數(shù)組膨脹多線程場景加鎖或換ConcurrentHashMap性能問題先測量再優(yōu)化別憑直覺這些經(jīng)驗都是從實際項目里一點點攢出來的希望能幫你少走些彎路。數(shù)據(jù)結(jié)構(gòu)和算法的選擇從來不是非黑即白理解每種結(jié)構(gòu)的取舍根據(jù)具體場景做判斷才是工程師該做的事。