性能優(yōu)化是我們做開發(fā)的必須要熟練掌握的技能，所以我打算寫一個性能優(yōu)化專題，把平時(shí)用到的一些優(yōu)化方法記錄下來，以便忘記的時(shí)候可以快速查找，同時(shí)也給給其他開發(fā)者提供微薄之力吧：這篇文章講述的是在一些**特定的場景**使用使用ArrayMap與SparseArray代替HashMap,提高對數(shù)據(jù)的操作；先看看官方文檔的描述：

ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional HashMap, this implementation is a version of the platform's ArrayMap that can be used on older versions of the platform.SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn't rely on an extra entry object for each mapping.Note that for containers holding up to hundreds of items, the performance difference is not significant, less than 50%.

從官方文檔可以看出使用ArrayMap與SparseArray都要比傳統(tǒng)的HashMap 更有效率；但是最后有一個note，也就是當(dāng)數(shù)據(jù)量達(dá)到千級以上的時(shí)候，ArrayMap與SparseArray都要比傳統(tǒng)的HashMap 效率更低50%；

HashMap

HashMap允許使用 null 值和 null 鍵，是基于hashing原理，我們通過put()和get()方法儲存和獲取對象。HashMap的結(jié)構(gòu)：

HashMap結(jié)構(gòu)

HashMap 有兩個參數(shù)影響其性能：初始容量 和加載因子。容量是哈希表中桶的數(shù)量（默認(rèn)16組），初始容量只是哈希表在創(chuàng)建時(shí)的容量。加載因子 是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)，則要對該哈希表進(jìn)行 rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有大約兩倍的桶數(shù)。加載因子默認(rèn)值為0.75 。當(dāng)我們將鍵值對傳遞給put()方法時(shí)，它調(diào)用鍵對象的hashCode()方法來計(jì)算hashcode，讓后找到bucket位置來儲存值對象。當(dāng)獲取對象時(shí)，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用LinkedList來解決碰撞問題，當(dāng)發(fā)生碰撞了，對象將會儲存在LinkedList的下一個節(jié)點(diǎn)中。 HashMap在每個LinkedList節(jié)點(diǎn)中儲存鍵值對對象。

put()方法

當(dāng)兩個Key同時(shí)hash到一個值時(shí)，就會出現(xiàn)這樣的沖突。這個沖突主要有2種解決方法。

1、開放地址，亦即如果hash沖突，則在空閑的位置進(jìn)行插入

2、hash復(fù)用，同一個hash值，鏈?zhǔn)降丶尤攵鄠€value

get()方法

HashMap還有很多方法，這里就不一一例舉了；

通過get與put的源碼，可以看出HashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應(yīng)的元素，在數(shù)據(jù)量很大時(shí)候會比較慢，所以在Android中，HashMap是比較費(fèi)內(nèi)存的，我們在一些情況下可以使用SparseArray和ArrayMap來代替HashMap。

SparseArray

可以看出SparseArray由兩個數(shù)組mKeys和mValues存放;其中key的類型為int型，這就顯得SparseArray比HashMap更省內(nèi)存一些，SparseArray在存儲和讀取數(shù)據(jù)時(shí)候，使用的是二分查找法，那何為二分法呢？

先看一下put()方法：

在上面代碼中有一個ContainerHelpers.binarySearch(mKeys, mSize, key)方法，這是Arrays提供了一個方便查詢的方法，也就是我們所說的“二分法”;

get()方法：

使用二分查找法和之前的key比較當(dāng)前我們添加的元素的key的大小，然后按照從小到大的順序排列好，所以，SparseArray存儲的元素都是按元素的key值從小到大排列好的。而在獲取數(shù)據(jù)的時(shí)候，也是使用二分查找法判斷元素的位置，所以，在獲取數(shù)據(jù)的時(shí)候非常快，比HashMap快的多，因?yàn)镠ashMap獲取數(shù)據(jù)是通過遍歷Entry[]數(shù)組來得到對應(yīng)的元素。

其他的一些方法：

ArrayMap

ArrayMap是一個鍵值對映射的數(shù)據(jù)結(jié)構(gòu)，它設(shè)計(jì)上更多的是考慮內(nèi)存的優(yōu)化，內(nèi)部是使用兩個數(shù)組進(jìn)行數(shù)據(jù)存儲，一個數(shù)組記錄key的hash值，另外一個數(shù)組記錄Value值，它和SparseArray一樣，也會對key使用二分法進(jìn)行從小到大排序，區(qū)別是ArrayMap的key是hash值，

可以看出ArrayMap的構(gòu)造方法直接調(diào)用的父類的構(gòu)造方法：

put()方法：

get()方法與SparseArray的一樣，就不哆嗦了：

總結(jié)

因?yàn)锳rrayMap與SparseArray內(nèi)部都使用了二分法進(jìn)行從小到大的排序，所以當(dāng)數(shù)據(jù)量很大的時(shí)候，效率至少降低一半，所以谷歌推薦數(shù)據(jù)量在千級以內(nèi)時(shí)使用ArrayMap與SparseArray，數(shù)據(jù)量非常大時(shí)使用HashMap；