程序內(nèi)存的管理是否合理高效對應用的性能有著很大的影響雾家，有的時候?qū)θ萜鞯氖褂貌划斠矔е聝?nèi)存管理效率低下。Android為移動操作系統(tǒng)特意編寫了一些更加高效的容器绍豁，例如SparseArray芯咧，今天要介紹的是一個新的容器，叫做ArrayMap。

我們經(jīng)常會使用到HashMap這個容器唬党，它非常好用鹃共，但是卻很占用內(nèi)存。下圖演示了HashMap的簡要工作原理：

?HashMap工作原理

工作原理2

HashMap內(nèi)部存儲結(jié)構(gòu)是使用哈希表的拉鏈結(jié)構(gòu)（數(shù)組+鏈表）

HashMap的鏈表結(jié)構(gòu)

且每一個結(jié)點都是Entry類型，那么Entry是什么呢？我們來看看HashMap中Entry的屬性：

Entry屬性

從中我們得知Entry存儲的內(nèi)容有key缺谴、value编振、hash值、和next下一個Entry彤避，那么，這些Entry數(shù)據(jù)是按什么規(guī)則進行存儲的呢？就是通過計算元素key的hash值永丝，然后對HashMap中數(shù)組長度取余得到該元素存儲的位置，計算公式為hash(key)%len箭养，比如：假設(shè)hash(14)=14,hash(30)=30,hash(46)=46慕嚷，我們分別對len取余，得到：hash(14)%16=14毕泌，hash(30)%16=14喝检，hash(46)%16=14，所以key為14撼泛、30挠说、46的這三個元素存儲在數(shù)組下標為14的位置，如：

Entry值的獲取

從中可以看出愿题，如果有多個元素key的hash值相同的話损俭，后一個元素并不會覆蓋上一個元素，而是采取鏈表的方式潘酗，把之后加進來的元素加入鏈表末尾杆兵，從而解決了hash沖突的問題，由此我們知道HashMap中處理hash沖突的方法是鏈地址法崎脉，在此補充一個知識點拧咳，處理hash沖突的方法有以下幾種：

1.開放地址法

2.再哈希法

3.鏈地址法

4.建立公共溢出區(qū)

講到這里，重點來了囚灼，我們知道HashMap中默認的存儲大小就是一個容量為16的數(shù)組骆膝，所以當我們創(chuàng)建出一個HashMap對象時，即使里面沒有任何元素灶体，也要分別一塊內(nèi)存空間給它阅签，而且，我們再不斷的向HashMap里put數(shù)據(jù)時蝎抽，當達到一定的容量限制時（這個容量滿足這樣的一個關(guān)系時候?qū)U容：HashMap中的數(shù)據(jù)量>容量*加載因子政钟，而HashMap中默認的加載因子是0.75）路克，HashMap的空間將會擴大，而且擴大后新的空間一定是原來的2倍养交，我們可以看put()方法中有這樣的一行代碼：

所以精算，重點就是這個，只要一滿足擴容條件碎连，HashMap的空間將會以2倍的規(guī)律進行增大灰羽。假如我們有幾十萬、幾百萬條數(shù)據(jù)鱼辙，那么HashMap要存儲完這些數(shù)據(jù)將要不斷的擴容廉嚼，而且在此過程中也需要不斷的做hash運算，這將對我們的內(nèi)存空間造成很大消耗和浪費倒戏，而且HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應的元素怠噪，在數(shù)據(jù)量很大時候會比較慢，所以在Android中杜跷，HashMap是比較費內(nèi)存的傍念，我們在一些情況下可以使用SparseArray和ArrayMap來代替HashMap。

SparseArray

SparseArray比HashMap更省內(nèi)存葛闷，在某些條件下性能更好捂寿，主要是因為它避免了對key的自動裝箱（int轉(zhuǎn)為Integer類型），它內(nèi)部則是通過兩個數(shù)組來進行數(shù)據(jù)存儲的孵运，一個存儲key，另外一個存儲value蔓彩，為了優(yōu)化性能治笨，它內(nèi)部對數(shù)據(jù)還采取了壓縮的方式來表示稀疏數(shù)組的數(shù)據(jù)，從而節(jié)約內(nèi)存空間赤嚼，我們從源碼中可以看到key和value分別是用數(shù)組表示：

SparseArray

我們可以看到旷赖，SparseArray只能存儲key為int類型的數(shù)據(jù)，同時更卒，SparseArray在存儲和讀取數(shù)據(jù)時候等孵，使用的是二分查找法，我們可以看看：

SparseArray的put和get方法

也就是在put添加數(shù)據(jù)的時候蹂空，會使用二分查找法和之前的key比較當前我們添加的元素的key的大小俯萌，然后按照從小到大的順序排列好，所以上枕，SparseArray存儲的元素都是按元素的key值從小到大排列好的咐熙。

而在獲取數(shù)據(jù)的時候，也是使用二分查找法判斷元素的位置辨萍，所以棋恼，在獲取數(shù)據(jù)的時候非常快，比HashMap快的多爪飘，因為HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應的元素义起。

SparseArray的方法

SparseArray的特有方法

SparseArray應用場景：

雖說SparseArray性能比較好，但是由于其添加师崎、查找默终、刪除數(shù)據(jù)都需要先進行一次二分查找，所以在數(shù)據(jù)量大的情況下性能并不明顯抡诞，將降低至少50%穷蛹。

滿足下面兩個條件我們可以使用SparseArray代替HashMap：

1.數(shù)據(jù)量不大，最好在千級以內(nèi)

2.key必須為int或者long類型昼汗，這中情況下的HashMap可以用SparseArray或者longSparseArray代替：

ArrayMap

ArrayMap的原理

當你想獲取某個value的時候肴熏，ArrayMap會計算輸入key轉(zhuǎn)換過后的hash值，然后對hash數(shù)組使用二分查找法尋找到對應的index顷窒，然后我們可以通過這個index在另外一個數(shù)組中直接訪問到需要的鍵值對蛙吏。如果在第二個數(shù)組鍵值對中的key和前面輸入的查詢key不一致，那么就認為是發(fā)生了碰撞沖突鞋吉。為了解決這個問題鸦做，我們會以該key為中心點，分別上下展開谓着，逐個去對比查找泼诱，直到找到匹配的值。如下圖所示：

查詢原理

隨著數(shù)組中的對象越來越多赊锚，查找訪問單個對象的花費也會跟著增長治筒，這是在內(nèi)存占用與訪問時間之間做權(quán)衡交換。

既然ArrayMap中的內(nèi)存占用是連續(xù)不間斷的舷蒲，那么它是如何處理插入與刪除操作的呢耸袜？請看下圖所示，演示了Array的特性：

刪除插入原理

很明顯牲平，ArrayMap的插入與刪除的效率是不夠高的堤框，但是如果數(shù)組的列表只是在一百這個數(shù)量級上，則完全不用擔心這些插入與刪除的效率問題纵柿。HashMap與ArrayMap之間的內(nèi)存占用效率對比圖如下：

內(nèi)存占用對比

與HashMap相比蜈抓，ArrayMap在循環(huán)遍歷的時候也更加簡單高效，如下圖所示：

前面演示了很多ArrayMap的優(yōu)點藐窄，但并不是所有情況下都適合使用ArrayMap资昧，我們應該在滿足下面2個條件的時候才考慮使用ArrayMap：

1.對象個數(shù)的數(shù)量級最好是千以內(nèi)

2.數(shù)據(jù)組織形式包含Map結(jié)構(gòu)

我們需要學會在特定情形下選擇相對更加高效的實現(xiàn)方式。

假設(shè)數(shù)據(jù)量都在千級以內(nèi)的情況下：

1荆忍、如果key的類型已經(jīng)確定為int類型格带，那么使用SparseArray撤缴，因為它避免了自動裝箱的過程，如果key為long類型叽唱，它還提供了一個LongSparseArray來確保key為long類型時的使用

2屈呕、如果key類型為其它的類型，則使用ArrayMap

否則還是HashMap吧