ArrayMap是Android專門針對內(nèi)存優(yōu)化而設(shè)計的，用于取代Java API中的HashMap數(shù)據(jù)結(jié)構(gòu)。為了更進一步優(yōu)化key是int類型的Map，Android再次提供效率更高的數(shù)據(jù)結(jié)構(gòu)SparseArray，可避免自動裝箱過程。對于key為其他類型則可使用ArrayMap。HashMap的查找和插入時間復(fù)雜度為O(1)的代價是犧牲大量的內(nèi)存來實現(xiàn)的，而SparseArray和ArrayMap性能略遜于HashMap，但更節(jié)省內(nèi)存。
1.HashMap
JavaAPI提供的散列表，用來存儲key-value對，內(nèi)部的實現(xiàn)結(jié)構(gòu)是一個數(shù)組和鏈表，提供了O（1）的查找和插入速度，但代價是大量內(nèi)存。JDK1.8版本當(dāng)鏈表長度超過8則轉(zhuǎn)換為紅黑樹，讓最壞情況的時間復(fù)雜度為O(logn)。當(dāng)前實際鍵值對個數(shù)是否大于或等于閾值threshold（默認為0.75*capacity）即進行擴容，每次擴容是至少是當(dāng)前大小的2倍，擴容的大小一定是2^n。
問題：HashMap容量或者擴容的大小為什么必須是2的冪?
n 是2的次冪，那么 n-1 通過 二進制表示就能確保永遠都是尾端以連續(xù)1的形式表示（00001111，00000011）。因此在求mod運算決定放在數(shù)組哪個位置的時候，可以通過（n-1）&hash極大加快了運算速度。同理，在做擴容的時候，能確保node要不就是維持不變，要不就是在原本位置+oldCap的新位置上。
2.HashTable
HashTable是HashMap的線程安全版本，通過使用synchronized修飾方法的方式來實現(xiàn)多線程同步。因為Hashtable的同步會鎖住整個數(shù)組，在高并發(fā)的情況下，性能會非常差。
問題：Synchronized容器和Concurrent容器有什么區(qū)別？
多線程安全的容器主要分為兩種：Synchronized和Concurrent，雖然它們都是線程安全的，但是它們在性能方面差距比較大。Synchronized容器（同步容器）主要通過synchronized關(guān)鍵字來實現(xiàn)線程安全，在使用的時候會對所有的數(shù)據(jù)加鎖。代價是嚴重降低了并發(fā)性，當(dāng)多個線程競爭容器時，吞吐量會嚴重降低。于是引入了Concurrent容器（并發(fā)容器），Concurrent容器采用了更加智能的方案，該方案不是對整個數(shù)據(jù)加鎖，而是采取了更加細粒度的鎖機制，因此，在大并發(fā)量的情況下，擁有更高的效率。
3. ConcurrentHashMap
為了解決HashTable并發(fā)效率低問題，引入了Concurrent容器，采用分段鎖的機制來提升并發(fā)能力。JDB1.8版本廢棄了分段鎖segment的機制，采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)，利用CAS+synchronized 來保證并發(fā)更新的安全。
3.ArrayMap
Android專門針對內(nèi)存優(yōu)化而設(shè)計的，用于取代Java API中的HashMap數(shù)據(jù)結(jié)構(gòu)。
mHashes是一個記錄所有key的hashcode值組成的數(shù)組，是從小到大的排序方式；mArray是一個記錄著key-value鍵值對所組成的數(shù)組，是mHashes大小的2倍。
為了減少頻繁地創(chuàng)建和回收Map對象，ArrayMap采用了兩個大小為10的緩存隊列來分別保存大小為4和8的Map對象,用于ArrayMap所在進程的全局緩存。為了節(jié)省內(nèi)存有更加保守的內(nèi)存擴張以及內(nèi)存收縮策略。特別注意該緩存只會緩存大小為4或者為8的array，所以在使用ArrayMap的時候生成new一個ArrayMap要把大小設(shè)置為4或者8，用起緩存機制。假如設(shè)置為ArrayMap[7]那么就會重新分配內(nèi)存，沒有使用起緩存機制。擴容策略是1.5倍擴容，即4,8,12,18等等?？s緊策略是已存儲數(shù)據(jù)的個數(shù)小于數(shù)組空間大小的1/3的情況下，內(nèi)存數(shù)組會收緊50%。put方法插入數(shù)據(jù)時間復(fù)雜度為O(logN)，因為要做二分查找找到對應(yīng)的index，此外還有個消耗是需要在插入位置把數(shù)組往后拷貝騰挪出位置來。
4.SparseArray
為了更進一步優(yōu)化key是int類型的Map，Android再次提供效率更高的數(shù)據(jù)結(jié)構(gòu)SparseArray，可避免自動裝箱過程。SparseArray對應(yīng)的key只能是int類型，它不會對key進行裝箱操作。它使用了兩個數(shù)組，一個保存key，一個保存value。 從內(nèi)存使用上來說，SparseArray不需要保存key所對應(yīng)的哈希值，所以比ArrayMap還能再節(jié)省1/3的內(nèi)存。?延遲回收，當(dāng)執(zhí)行delete()或者removeAt()刪除數(shù)據(jù)的操作，只是將相應(yīng)位置的數(shù)據(jù)標記為DELETE，并設(shè)置mGarbage=true，而不會直接執(zhí)行數(shù)據(jù)拷貝移動的操作。
5.總結(jié)
數(shù)據(jù)結(jié)構(gòu)：ArrayMap和SparseArray采用的都是兩個數(shù)組，Android專門針對內(nèi)存優(yōu)化而設(shè)計的，HashMap采用的是數(shù)據(jù)+鏈表+紅黑樹
內(nèi)存優(yōu)化：ArrayMap比HashMap更節(jié)省內(nèi)存，綜合性能方面在數(shù)據(jù)量不大的情況下，推薦使用ArrayMap。Hash需要創(chuàng)建一個額外對象來保存每一個放入map的entry，且容量的利用率比ArrayMap低，整體更消耗內(nèi)存。SparseArray比ArrayMap節(jié)省1/3的內(nèi)存，但SparseArray只能用于key為int類型的Map，所以int類型的Map數(shù)據(jù)推薦使用SparseArray。
性能方面：ArrayMap查找時間復(fù)雜度O(logN)，ArrayMap增加、刪除操作需要移動成員，速度相比較慢，對于個數(shù)小于1000的情況下，性能基本沒有明顯差異。HashMap查找、修改的時間復(fù)雜度為O(1)，SparseArray適合頻繁刪除和插入來回執(zhí)行的場景，性能比較好。
緩存機制：ArrayMap針對容量為4和8的對象進行緩存，可避免頻繁創(chuàng)建對象而分配內(nèi)存與GC操作，這兩個緩存池大小的上限為10個，防止緩存池?zé)o限增大，HashMap沒有緩存機制。SparseArray并沒有緩存，但有延遲回收機制（刪除時只是標記下，并不挪到數(shù)組），提供刪除效率，同時減少數(shù)組成員來回拷貝的次數(shù)。
擴容機制：ArrayMap是在容量滿的時機觸發(fā)容量擴大至原來的1.5倍，在容量不足1/3時觸發(fā)內(nèi)存收縮至原來的0.5倍，更節(jié)省的內(nèi)存擴容機制。HashMap是在容量的0.75倍時觸發(fā)容量擴大至原來的2倍，且沒有內(nèi)存收縮機制。HashMap擴容過程有hash重建，相對耗時。所以能大致知道數(shù)據(jù)量，可指定創(chuàng)建指定容量的對象，能減少性能浪費。
并發(fā)問題：ArrayMap是非線程安全的類，大量方法中通過對mSize判斷是否發(fā)生并發(fā)，來決定拋出異常。但沒有覆蓋到所有并發(fā)場景，比如大小沒有改變而成員內(nèi)容改變的情況就沒有覆蓋。HashMap是在每次增加、刪除、清空操作的過程將modCount加1，在關(guān)鍵方法內(nèi)進入時記錄當(dāng)前mCount，執(zhí)行完核心邏輯后，再檢測mCount是否被其他線程修改，來決定拋出異常。這一點的處理比ArrayMap更有全面。ConcurrentModificationException這種異常機制只是為了提醒開發(fā)者不要多線程并發(fā)操作，千萬不要并發(fā)操作ArrayMap和HashMap。
