SparseArray和ArrayMap是Android中的特有集合類數(shù)據(jù)結(jié)構(gòu)。
一、SparseArray
SparseArray直譯為稀疏數(shù)組，本質(zhì)上是通過數(shù)組實現(xiàn)的、key為整型的鍵值對集合。刷過算法題的應(yīng)該對類似的數(shù)據(jù)結(jié)構(gòu)很熟悉。
1. SparseArray的用法
SparseArray的一般使用類似于key為整型的HashMap。如下：
SparseArray<String> arr = new SparseArray<>();
arr.put(1, "one");
arr.put(100, "one hundred");
arr.put(10000, "ten thousand");
arr.remove(100);
另外：
- 使用
append方法與put方法類似的添加元素；不過如果待添加的key大于當前所有元素，則直接加在末尾，少了二分查找的這一步，所以比put方法效率要高。 - 使用
indexOfKey(key)和indexOfValue(value)可以查找對應(yīng)的key或者value在數(shù)組中的序號。 - 使用
keyAt(index)和valueAt(index)方法可以查找對應(yīng)序號的key或者value。
2. SparseArray的實現(xiàn)原理
SparseArray的實現(xiàn)原理是通過整型數(shù)組mKeys和值數(shù)組mValues建立的一一對應(yīng)關(guān)系，通過mSize屬性來標記其鍵值對的數(shù)量（mSize對應(yīng)的鍵值對是真實存在于集合中的元素，不包括已經(jīng)刪除的）。
mKeys數(shù)組是有序遞增的，這樣有助于進行二分查找。當往SparseArray中添加鍵值對時，會通過二分查找找到相應(yīng)的位置并插入。當進行刪除時，同樣會通過二分查找找到相應(yīng)的鍵值對，然后將mValues數(shù)組中對應(yīng)的值賦為DELETED（DELETED是一個常量對象，無實際含義，只作為該鍵值對已經(jīng)被刪除的標記）。
查找
當查找元素時，會使用二分查找，所以SparseArray的查找時間復(fù)雜度是O(logN)。
刪除
當刪除元素時，會先查找到該元素；這時并不會立即把這個元素刪除，而只是標記其值為DELETED，這是SparseArray的延時刪除機制，可以提高執(zhí)行效率。
添加
在使用put方法添加元素時，會先查找元素，如果找到對應(yīng)的key，那么就直接修改對應(yīng)的值；如果沒有找到對應(yīng)的key，那么就會添加新值。
在添加新值之前，會檢查二分查找最接近的那個元素，如果該元素值為DELETED，則直接將該元素替換為待添加的元素；否則，在此處插入新元素。
在插入元素之前，如果鍵值對數(shù)量mSize已經(jīng)大于等于mKeys數(shù)組長度，SparseArray會進行垃圾回收gc()。這里的垃圾回收不同于JVM的垃圾回收，而是刪除所有值為DELETED的鍵值對，并將其后面的元素依次靠攏。在垃圾回收之后，如果mSize仍舊大于等于mKeys的長度，數(shù)組會進行擴容。
特別地，當使用append方法添加數(shù)據(jù)，且添加的key大于當前數(shù)組中所有元素時，則會直接插入在數(shù)組最后；其他情況下append會直接調(diào)用put方法。所以，使用SparseArray添加元素時，優(yōu)先使用append方法而不是put。
如果沒有特別指定，SparseArray的初始大小為10，每次擴容之后大小為之前的2倍。
3. 時間復(fù)雜度分析
查找：當查找元素時，會使用二分查找，所以SparseArray的查找時間復(fù)雜度是O(logN)。
刪除：當刪除元素時，會先查找該元素，然后標記值為DELETED，所以刪除的時間復(fù)雜度也是O(logN)。
添加：當使用put方法添加元素時，會先查找元素，如果找到對應(yīng)的key，或者最接近的元素value是DELETED，那么就直接賦值，這種情況的時間復(fù)雜度是O(logN)。
如果觸發(fā)了垃圾回收或者擴容，那么時間復(fù)雜度就是O(N)，這是最壞時間復(fù)雜度。
當使用append方法添加數(shù)據(jù)，且數(shù)據(jù)為正序插入時，時間復(fù)雜度為O(1)，其他情況下時間復(fù)雜度同put。
4. 小結(jié)
- SparseArray用法類似于HashMap，但key恒定為整型。
- SparseArray通過
mKeys和mValues兩個相等長度的數(shù)組來實現(xiàn)鍵值對的一一對應(yīng)，其中mKeys是升序的。 - 時間復(fù)雜度分析：
因為查找元素使用二分法，所以SparseArray刪改查平均時間復(fù)雜度均為O(logN)；添加元素由于垃圾回收gc()和插入元素insert都可能會進行數(shù)組復(fù)制的原因，時間復(fù)雜度最好是O(logN)，最壞是O(N)。 - 和HashMap相比，SparseArray的優(yōu)勢是：
1、使用int[]保存key，不用拆裝箱，也沒有復(fù)雜的運算，在數(shù)據(jù)量小時實際效率比較高；
2、除了數(shù)組沒有額外的數(shù)據(jù)結(jié)構(gòu)，節(jié)省空間；
劣勢是：
1、在數(shù)據(jù)量較大以后，效率很低； - SparseArray可以看做是用時間換空間的數(shù)據(jù)結(jié)構(gòu)。
二、ArrayMap
ArrayMap是將key和value保存在同一個數(shù)組中的集合類數(shù)據(jù)結(jié)構(gòu)。
1. ArrayMap的用法
ArrayMap的用法也類似于SparseArray，就不多做贅述。
2. ArrayMap的原理
不同于SparseArray，ArrayMap將key和value儲存在同一個數(shù)組mArray中，并使用升序數(shù)組mHashes保存了各個元素的哈希值。
其中，第i個元素的哈希值為mHashes[i]，key為mArray[2i]，value為mArray[2i+1]。元素的總數(shù)量為mSize。
查找
ArrayMap的核心在于查找，也就是如何找到對應(yīng)的鍵值對在數(shù)組中的存放位置，對應(yīng)的是ArrayMap的indexOf()方法。
由于mHashes是升序數(shù)組，所以先計算對應(yīng)key的哈希值，通過二分法查找到mHashes中對應(yīng)的哈希值。如果查找到的key與待查找的key不同，則在mArray中以當前key為中心，往左右依次匹配，直到查找到對應(yīng)的key。
插入
在ArrayMap中插入新元素，首先檢查容量是否達到上限，如果達到上限會進行擴容；擴容后的大小為原大小的1.5倍。
然后，通過System.arraycopy將待插入元素右側(cè)的所有元素往右移動（mHashes移動一位，mArray移動兩位），將元素插入。
插入后，mSize加一。
刪除
刪除存在的元素，首先找到該元素，然后通過System.arraycopy將數(shù)組右邊的所有元素往左移動（mHashes移動一位，mArray移動兩位）。如果刪除元素之后，實際元素個數(shù)mSize小于閾值（mHashes數(shù)組長度的1/3），那么會進行減容；減容后的大小為mSize的1.5倍。
3. 時間復(fù)雜度分析
查找
查找元素要經(jīng)歷兩次：第一次是通過二分查找在mHashes數(shù)組中找到對應(yīng)的哈希值，第二次是通過第一次查找的結(jié)果在mArray中找到對應(yīng)的key。
第一次查找時間復(fù)雜度為O(logN)，第二次查找根據(jù)哈希碰撞的情況，最好為O(1)，最壞為O(n)。所以總的時間復(fù)雜度最好為O(logN)，最壞為O(N)。因為實際情況下哈希碰撞不會經(jīng)常出現(xiàn)，所以平均時間復(fù)雜度可以近似看做O(logN)。
插入
因為插入的過程會進行數(shù)組的復(fù)制，所以理論時間復(fù)雜度為O(N)。
刪除
同插入。
4. 小結(jié)
- ArrayMap通過升序數(shù)組
mHashes數(shù)組保存了元素的哈希值，mArray數(shù)組保存了元素的key-value。其中，對于第i個元素，其哈希值為mHashes[i]，key為mArray[2i]，value為mArray[2i+1]。 - ArrayMap在添加元素和刪除元素時，都會進行數(shù)組的復(fù)制。
- 與SparseArray類似，ArrayMap相對于HashMap節(jié)約了空間，但是降低了效率，是用時間換空間的數(shù)據(jù)結(jié)構(gòu)。
三、總結(jié)
SparseArray和ArrayMap都是通過數(shù)組實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，二者使用方式類似。其中SparseArray是通過兩個數(shù)組分別保存key和value，且key只能是整型；而ArrayMap是通過一個數(shù)組保存哈希值，另一個數(shù)組同時保存key和value。二者查找元素都是通過二分查找實現(xiàn)。
SparseArray和ArrayMap與HashMap相比，都是用時間換空間的數(shù)據(jù)結(jié)構(gòu)，可以節(jié)約運行內(nèi)存，但是會降低效率。如果應(yīng)用更追求占用較小的內(nèi)存，且數(shù)據(jù)量小，則使用SparseArray/ArrayMap；追求更快的運行速度，或數(shù)據(jù)量大，則使用HashMap。
SparseArray有延遲刪除的機制，可以有效的提高效率；ArrayMap即時刪除，且有減容機制，可以有效的節(jié)省空間。
當使用SparseArray添加數(shù)據(jù)時，優(yōu)先使用
append方法，而不是put方法。
