Android中的HashMap,ArrayMap和SparseArray

Android開發者都知道Lint在我們使用HashMap的時候會給出警告——使用SparseArray會優化內存。這可是一件好事情。那現在我們有幾個類要學習去使用。比如:ArrayMap和SimpleArrayMap，當然還有各種類型的SparseArray。這篇文章將講解這些類及它們的原理。

先從如何使用它們開始吧。

java.util.HashMap<String, String> hashMap = new java.util.HashMap<String, String>(16);
hashMap.put("key", "value");
hashMap.get("key");
hashMap.entrySet().iterator();

android.util.ArrayMap<String, String> arrayMap = new android.util.ArrayMap<String, String>(16);
arrayMap.put("key", "value");
arrayMap.get("key");
arrayMap.entrySet().iterator();

android.support.v4.util.ArrayMap<String, String> supportArrayMap =
        new android.support.v4.util.ArrayMap<String, String>(16);
supportArrayMap.put("key", "value");
supportArrayMap.get("key");
supportArrayMap.entrySet().iterator();

android.support.v4.util.SimpleArrayMap<String, String> simpleArrayMap =
        new android.support.v4.util.SimpleArrayMap<String, String>(16);
simpleArrayMap.put("key", "value");
simpleArrayMap.get("key");
//simpleArrayMap.entrySet().iterator();      <- will not compile

android.util.SparseArray<String> sparseArray = new android.util.SparseArray<String>(16);
sparseArray.put(10, "value");
sparseArray.get(10);

android.util.LongSparseArray<String> longSparseArray = new android.util.LongSparseArray<String>(16);
longSparseArray.put(10L, "value");
longSparseArray.get(10L);

android.util.SparseLongArray sparseLongArray = new android.util.SparseLongArray(16);
sparseLongArray.put(10, 100L);
sparseLongArray.get(10);

接下我們一個一個的討論。java中的集合基本都是基于數組。在我們了解這些替代類之前我們需要理解HashMap是怎么樣工作的。

java.util.HashMap

HashMap本質上是一個HashMapEntry構成的數組。每個Entry的實體都包括:

• 一個非基本類型的key
• 一個非基本類型的value
• 一個key的Hashcode
• 指向下一個Entry的指針
  如下代碼（因為是泛型所以不能是基本類型）

  final K key;
  V value;
  HashMapEntry<K,V> next;
  int hash;

  需要注意的是key和value都不是基本類型的。這是Java工程師做出的設計決策。所以我們不得不容忍它。當插入一個基本類型的時候會產生自動裝箱的消耗。
  當HashMap插入一個object時：
• key的Hashcode會被計算出來并賦值到Entry類的變量中。
• java.util.HashMap.indexFor()這個方法依賴于hashcode。這個方法你也可以看成是利用Entry[]的size的取模函數。

  static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

  并用這個方法來決定當前的Entry放在Entry[]的哪個index,這個index叫做"bucket（桶）"
• 如果這個桶已經存在了元素，那么新的元素會被插入到上一個元素中指針指定的位置——這個結構和LinkedList基本一樣。
  它查詢的復雜度是O(1)：
• 已經計算好了插入的Key的hashcode。
• java.util.HashMap.indexFor() 這個方法是基于hashcode的，所以我們獲取Entry的bucket（位置）就像查詢一個數組。

O(1)的時間復雜度是所有的開發都樂意看到的，但是內存消耗也是應該考慮的因素。特別是在移動設備上。

HashMap的缺點：

• 自動裝箱意味著需要產生額外的對象，這對于內存的使用和垃圾回收產生影響。
• HashMapEntity自己本身也會產生額外的對象，這同樣會影響內存的使用和垃圾回收產生。
• 每次HashMap的存儲對象減少或都增加的時候，這個開銷會隨著Hashmap的size增加而增加。
• 哈希是很好的實現方案，但是如果實現的不好將會讓我們的開銷回到O(N)
• 很多人都會忽略關于哈希的另外一個缺點：我們需要存儲它的key和對應的hash值。這種冗余有助于解決沖突。 非散列解決方案也可以在這方面有所幫助。

  android.util.ArrayMap

  ArrayMap 用了兩個數組。在它內部用了Object[] mArray來存儲Object,還用了int[] mHashes 來存儲hashcode,當存儲一對鍵值對的時候。
• Key/Value會被自動裝箱。
• key會存儲在mArray[]的下一個可用的位置。
• 而value會存儲在mArray[]中key的下一個位置。（key和value在mArray中交叉存儲）
• key的哈希值會被計算出來并存儲在mHashed[]中。
  當查找一個key的時候：
• 計算key的hashcode。
• 在mHashes[]中對這個hashcode進行二分法查找。也就意味著時間復雜度增加到了O(logN)
• 一旦我們得到了這個哈希值的位置index。我們就知道這個key是在mArray的2 index的位置，而value則在2 index+1的位置。
  這個ArrayMap還是沒能解決自動裝箱的問題。當put一對鍵值對進入的時候，它們只接受Object，但是我們相對于HashMap來說每一次put會少創建一個對象(HashMapEntry)。這是不是值得我們用O(1)的查找復雜度來換呢？對于大多數app應用來說是值得的。

  android.support.v4.util.ArrayMap

  android.util.ArrayMap只能在api不小于19（Kitkat）的平臺才能使用。而Support library則支持在舊平臺上提供相同的功能。

  android.support.v4.util.SimpleArrayMap

  在之前發布的代碼片段中你可以看到，這個類沒有entrySet()這個支持迭代的方法。如果你查看它的文檔，你會發現很java標準集合的方法它都沒有。那我們為什么要用它呢。讓它失去與其它java容器的相互操作的特性來減小apk的大小。這樣的話，
  Proguard(代碼優化和混沌工具：可能是你代碼構建生成的一部分)可以幫你減少大多數沒有使用的Collections API代碼從而減小你的apk大小。它的內部工作和android.util.ArrayMap是一樣的。

  android.util.SparseArray

  和ArrayMap一樣，它里面也用了兩個數組。一個int[] mKeys和Object[] mValues。從名字都可以看得出來一個用來存儲key一個用來保存value的。
  當保存一對鍵值對的時候：
• key（不是它的hashcode）保存在mKeys[]的下一個可用的位置上。所以不會再對key自動裝箱了。
• value保存在mValues[]的下一個位置上，value還是要自動裝箱的，如果它是基本類型。
  查找的時候：
• 查找key還是用的二分法查找。也就是說它的時間復雜度還是O(logN)
• 知道了key的index，也就可以用key的index來從mValues中檢索出value。
  相較于HashMap,我們舍棄了Entry和Object類型的key,放棄了HashCode并依賴于二分法查找。在添加和刪除操作的時候有更好的性能開銷。
  KitKat以前的版本用android.support.v4.util.SparseArrayCompat

android.util.LongSparseArray

SparseArray只接受int類型作為key,而LongSparseArray我們就可以用long作為key。實現原理和SparseArray一致。

android.util.SparseIntArray, android.util.SparseLongArray and android.util.SparseBooleanArray

對于key是int類型而value是int 或者long再或者是boolean,我們可以對應使用SparseIntArray,SparseLongArray ,SparseBooleanArray 。它們使用方式是和SparseArray一樣的。它的好處是mValues[]是基本類型的數組。也就意味著無論是key還是value都不用裝箱。并且相對于HashMap來說我們節約了3個對象的初始化（Entry,Key和Value），但是我們將查看復雜度從O(1)上升到了O(logN)

結語

使用SparseArray和ArrayMap肯定會減少對象創建的數目。當集合的的數目多達幾百個的時候，性能差異也不會很明顯（少于50%）。將ArrayMap和SparseArray遷移到新代碼中是很有好處的。并且由于方法簽名匹配，所以遷移也很容易。

注意： 即使它們聽起來像數組(Array)，ArrayMap和SparseArray不能保證保留它們的插入順序，在迭代的時候應該注意。

其中二分法查找方法是 android.util.ContainerHelpers中的方法。

class ContainerHelpers {

    // This is Arrays.binarySearch(), but doesn't do any argument validation.
    static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }

    static int binarySearch(long[] array, int size, long value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final long midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }
}

來自：http://www.jianshu.com/p/aff3b8990ab3