Android開發(fā)者都知道Lint在我們使用HashMap的時(shí)候會(huì)給出警告——使用SparseArray會(huì)優(yōu)化內(nèi)存。這可是一件好事情熬粗。那現(xiàn)在我們有幾個(gè)類要學(xué)習(xí)去使用虱朵。比如:ArrayMap和SimpleArrayMap布持，當(dāng)然還有各種類型的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);

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

java.util.HashMap

HashMap本質(zhì)上是一個(gè)HashMapEntry構(gòu)成的數(shù)組逞敷。每個(gè)Entry的實(shí)體都包括:

• 一個(gè)非基本類型的key
• 一個(gè)非基本類型的value
• 一個(gè)key的Hashcode
• 指向下一個(gè)Entry的指針
  如下代碼（因?yàn)槭欠盒退圆荒苁腔绢愋停?/li>

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

需要注意的是key和value都不是基本類型的。這是Java工程師做出的設(shè)計(jì)決策灌侣。所以我們不得不容忍它推捐。當(dāng)插入一個(gè)基本類型的時(shí)候會(huì)產(chǎn)生自動(dòng)裝箱的消耗。
當(dāng)HashMap插入一個(gè)object時(shí)：

• key的Hashcode會(huì)被計(jì)算出來并賦值到Entry類的變量中侧啼。
• java.util.HashMap.indexFor()這個(gè)方法依賴于hashcode牛柒。這個(gè)方法你也可以看成是利用Entry[]的size的取模函數(shù)堪簿。

 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);
    }

并用這個(gè)方法來決定當(dāng)前的Entry放在Entry[]的哪個(gè)index,這個(gè)index叫做"bucket（桶）"

• 如果這個(gè)桶已經(jīng)存在了元素，那么新的元素會(huì)被插入到上一個(gè)元素中指針指定的位置——這個(gè)結(jié)構(gòu)和LinkedList基本一樣皮壁。
  它查詢的復(fù)雜度是O(1)：
• 已經(jīng)計(jì)算好了插入的Key的hashcode椭更。
• java.util.HashMap.indexFor() 這個(gè)方法是基于hashcode的，所以我們獲取Entry的bucket（位置）就像查詢一個(gè)數(shù)組蛾魄。

O(1)的時(shí)間復(fù)雜度是所有的開發(fā)都樂意看到的虑瀑，但是內(nèi)存消耗也是應(yīng)該考慮的因素。特別是在移動(dòng)設(shè)備上滴须。
HashMap的缺點(diǎn)：

• 自動(dòng)裝箱意味著需要產(chǎn)生額外的對(duì)象舌狗，這對(duì)于內(nèi)存的使用和垃圾回收產(chǎn)生影響。
• HashMapEntity自己本身也會(huì)產(chǎn)生額外的對(duì)象扔水，這同樣會(huì)影響內(nèi)存的使用和垃圾回收產(chǎn)生痛侍。
• 每次HashMap的存儲(chǔ)對(duì)象減少或都增加的時(shí)候，這個(gè)開銷會(huì)隨著Hashmap的size增加而增加魔市。
• 哈希是很好的實(shí)現(xiàn)方案恋日，但是如果實(shí)現(xiàn)的不好將會(huì)讓我們的開銷回到O(N)
• 很多人都會(huì)忽略關(guān)于哈希的另外一個(gè)缺點(diǎn)：我們需要存儲(chǔ)它的key和對(duì)應(yīng)的hash值。這種冗余有助于解決沖突嘹狞。 非散列解決方案也可以在這方面有所幫助。

android.util.ArrayMap

ArrayMap 用了兩個(gè)數(shù)組誓竿。在它內(nèi)部用了Object[] mArray來存儲(chǔ)Object,還用了int[] mHashes 來存儲(chǔ)hashcode,當(dāng)存儲(chǔ)一對(duì)鍵值對(duì)的時(shí)候磅网。

• Key/Value會(huì)被自動(dòng)裝箱。
• key會(huì)存儲(chǔ)在mArray[]的下一個(gè)可用的位置筷屡。
• 而value會(huì)存儲(chǔ)在mArray[]中key的下一個(gè)位置涧偷。（key和value在mArray中交叉存儲(chǔ)）
• key的哈希值會(huì)被計(jì)算出來并存儲(chǔ)在mHashed[]中。
  當(dāng)查找一個(gè)key的時(shí)候：
• 計(jì)算key的hashcode毙死。
• 在mHashes[]中對(duì)這個(gè)hashcode進(jìn)行二分法查找燎潮。也就意味著時(shí)間復(fù)雜度增加到了O(logN)
• 一旦我們得到了這個(gè)哈希值的位置index。我們就知道這個(gè)key是在mArray的2index的位置扼倘，而value則在2index+1的位置确封。
  這個(gè)ArrayMap還是沒能解決自動(dòng)裝箱的問題。當(dāng)put一對(duì)鍵值對(duì)進(jìn)入的時(shí)候再菊，它們只接受Object爪喘，但是我們相對(duì)于HashMap來說每一次put會(huì)少創(chuàng)建一個(gè)對(duì)象(HashMapEntry)。這是不是值得我們用O(1)的查找復(fù)雜度來?yè)Q呢纠拔？對(duì)于大多數(shù)app應(yīng)用來說是值得的秉剑。

android.support.v4.util.ArrayMap

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

android.support.v4.util.SimpleArrayMap

在之前發(fā)布的代碼片段中你可以看到侦鹏，這個(gè)類沒有entrySet()這個(gè)支持迭代的方法诡曙。如果你查看它的文檔，你會(huì)發(fā)現(xiàn)很java標(biāo)準(zhǔn)集合的方法它都沒有略水。那我們?yōu)槭裁匆盟丶勐薄Ｗ屗ヅc其它java容器的相互操作的特性來減小apk的大小。這樣的話聚请，
Proguard(代碼優(yōu)化和混沌工具：可能是你代碼構(gòu)建生成的一部分)可以幫你減少大多數(shù)沒有使用的Collections API代碼從而減小你的apk大小荠雕。它的內(nèi)部工作和android.util.ArrayMap是一樣的。

android.util.SparseArray

和ArrayMap一樣驶赏，它里面也用了兩個(gè)數(shù)組炸卑。一個(gè)int[] mKeys和Object[] mValues。從名字都可以看得出來一個(gè)用來存儲(chǔ)key一個(gè)用來保存value的煤傍。
當(dāng)保存一對(duì)鍵值對(duì)的時(shí)候：

• key（不是它的hashcode）保存在mKeys[]的下一個(gè)可用的位置上盖文。所以不會(huì)再對(duì)key自動(dòng)裝箱了。
• value保存在mValues[]的下一個(gè)位置上蚯姆，value還是要自動(dòng)裝箱的五续，如果它是基本類型。
  查找的時(shí)候：
• 查找key還是用的二分法查找龄恋。也就是說它的時(shí)間復(fù)雜度還是O(logN)
• 知道了key的index疙驾，也就可以用key的index來從mValues中檢索出value。
  相較于HashMap,我們舍棄了Entry和Object類型的key,放棄了HashCode并依賴于二分法查找郭毕。在添加和刪除操作的時(shí)候有更好的性能開銷它碎。
  KitKat以前的版本用android.support.v4.util.SparseArrayCompat

android.util.LongSparseArray

SparseArray只接受int類型作為key,而LongSparseArray我們就可以用long作為key。實(shí)現(xiàn)原理和SparseArray一致显押。

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

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

結(jié)語(yǔ)

使用SparseArray和ArrayMap肯定會(huì)減少對(duì)象創(chuàng)建的數(shù)目兽肤。當(dāng)集合的的數(shù)目多達(dá)幾百個(gè)的時(shí)候套腹，性能差異也不會(huì)很明顯（少于50%）。將ArrayMap和SparseArray遷移到新代碼中是很有好處的资铡。并且由于方法簽名匹配沉迹，所以遷移也很容易。

注意：即使它們聽起來像數(shù)組(Array)害驹，ArrayMap和SparseArray不能保證保留它們的插入順序鞭呕，在迭代的時(shí)候應(yīng)該注意。
其中二分法查找方法是 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
    }
}

原文鏈接