• 原文地址：Android App Optimization Using ArrayMap and SparseArray
• 原文作者：Amit Shekhar
• 譯文出自：掘金翻譯計劃(翻譯不易，歡迎 Star 支持)
• 譯者：Jamweak
• 校對者：Jacksonke, Siegeout

如何通過 ArrayMap 和 SparseArray 優化 Android App

這篇文章會講述為何要使用 ArrayMap 和 SparseArray 來優化 Android 應用，以及什麼情形下適用。

當你需要存儲鍵 -> 值這樣的數據類型時，你腦海里想到的第一個數據類型應該是 HashMap。然後你開始肆無忌憚的到處使用它，而從不考慮它所帶來的副作用。

當你使用 HashMap 時，你的 Android 集成開發環境 (Android Studio) 會給出警告，提示你使用 ArrayMap 來代替 HashMap，但通常被你忽視了。

Android 給你提供了 ArrayMap，你應該優先考慮使用它而不是 HashMap。

現在，讓我們來理解 ArrayMap 的內部實現，以便探求在哪種場景下使用它，以及為什麼這樣做。

HashMap vs ArrayMap

HashMap 的位置在 java.util.HashMap 包中。

ArrayMap 的位置在 android.util.ArrayMap 和 android.support.v4.util.ArrayMap 包中。

它存在於 support.v4 包中，以便兼容較低的 Android 版本。

這裡 是直接出自 Android 開發者頻道的 youtube 視頻，強烈建議你看一下。

ArrayMap 是一種通用的鍵->值映射數據結構，它在設計上比傳統的 HashMap 更多考慮內存優化。 它使用兩個數組來存儲數據——一個整型數組存儲鍵的哈希值，另一個對象數組存儲鍵/值對。這樣既能避免為每個存入 map 中的鍵創建額外的對象，還能試圖更j積極地控制這些數組的長度的增加（因為增加長度只需拷貝數組中的鍵，而不是重新構建一個哈希表）。

需要注意的是，ArraryMap 並不適用於可能含有大量條目的數據類型。它通常比 HashMap 要慢，因為在查找時需要進行二分查找，增加或刪除時，需要在數組中插入或刪除鍵。對於一個最多含有幾百條目的容器來說，它們的性能差異並不巨大，相差不到 50%。

HashMap

HashMap 基本上就是一個 HashMap.Entry 的數組（Entry 是 HashMap 的一個內部類）。更準確來說，Entry 類中包含以下欄位：

• 一個非基本數據類型的 key
• 一個非基本數據類型的 value
• 保存對象的哈希值
• 指向下一個 Entry 的指針

當有鍵值對插入時，HashMap 會發生什麼 ?

• 首先，鍵的哈希值被計算出來，然後這個值會賦給 Entry 類中對應的 hashCode 變數。
• 然後，使用這個哈希值找到它將要被存入的數組中「桶」的索引。
• 如果該位置的「桶」中已經有一個元素，那麼新的元素會被插入到「桶」的頭部，next 指向上一個元素——「桶」在本質上形成為鏈表。

現在，當你用 key 去查詢值時，時間複雜度是 O(1)。

雖然時間上 HashMap 更快，但同時它也花費了更多的內存空間。

缺點:

• 自動裝箱的存在意味著每一次插入都會有額外的對象創建。這跟垃圾回收機制一樣也會影響到內存的利用。
• HashMap.Entry 對象本身是一層額外需要被創建以及被垃圾回收的對象。
• 「桶」 在 HashMap 每次被壓縮或擴容的時候都會被重新安排。這個操作會隨著對象數量的增長而變得開銷極大。

在Android中，當涉及到快速響應的應用時，內存至關重要，因為持續地分發和釋放內存會出發垃圾回收機制，這會拖慢應用運行。

垃圾回收機制會影響應用性能表現

垃圾回收時間段內，應用程序是不會運行的，最終應用使用上就顯得卡頓。

ArrayMap

ArrayMap 使用2個數組。它的對象實例內部有用來存儲對象的 Object[] mArray 和 存儲哈希值的 int[] mHashes。當插入一個鍵值對時：

• 鍵/值被自動裝箱。
• 鍵對象被插入到 mArray[] 數組中的下一個空閑位置。
• 值對象也會被插入到 mArray[] 數組中與鍵對象相鄰的位置。
• 鍵的哈希值會被計算出來並被插入到 mHashes[] 數組中的下一個空閑位置。

對於查找一個 key :

• 鍵的哈希值先被計算出來
• 在 mHashes[] 數組中二分查找此哈希值。這表明查找的時間複雜度增加到了 O(logN)。
• 一旦得到了哈希值所對應的索引 index，鍵值對中的鍵就存儲在 mArray[2index] ，值存儲在 mArray[2index+1]。
• 這裡的時間複雜度從 O(1) 上升到 O(logN)，但是內存效率提升了。當我們在 100 左右的數據量範圍內嘗試時，沒有耗時的問題，察覺不到時間上的差異，但我們應用的內存效率獲得了提高。

推薦的數據結構:

• ArrayMap<K,V> 替代 HashMap<K,V>
• ArraySet<K,V> 替代 HashSet<K,V>
• SparseArray<V> 替代 HashMap<Integer,V>
• SparseBooleanArray 替代 HashMap<Integer,Boolean>
• SparseIntArray 替代 HashMap<Integer,Integer>
• SparseLongArray 替代 HashMap<Integer,Long>
• LongSparseArray<V> 替代 HashMap<Long,V>

推薦閱讀：