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