[TOC]
1. 為什么要用ArrayMap/ArraySet
在Android開發(fā)中虎敦，經(jīng)常會(huì)用到HashMap/HashSet等集合類，但是Java在設(shè)計(jì)集合類的時(shí)候并沒有考慮到內(nèi)存寶貴場(chǎng)景下優(yōu)化身隐。而對(duì)Android系統(tǒng)來說內(nèi)存是非常寶貴的資源，所以Google針對(duì)Android系統(tǒng)的特性提供了 HashMap/HashSet的代替品唯灵，即ArrayMap/ArraySet贾铝。這幾個(gè)類位于android.util.*包下面。
2. 簡單回憶下HashMap<K, V>的實(shí)現(xiàn)
2.1 數(shù)據(jù)接口
在Java中埠帕，HashMap是通過數(shù)組加引用組合實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)垢揩，結(jié)構(gòu)圖如下：
)
從圖中我們看到，數(shù)組的每個(gè)元素之后會(huì)跟著一條鏈表敛瓷。我們應(yīng)該很容易想到這是為了解決HashCode沖突而設(shè)計(jì)的叁巨，使用鏈地址法解決沖突。
順便提一下解決沖突的常用四個(gè)方法：
- 鏈地址法
- 再Hash法
- 開放地址發(fā)
- 建立公共溢出區(qū)
2.2 HashMap的數(shù)據(jù)結(jié)構(gòu)
HashMap有三個(gè)構(gòu)造方法：
HaspMap()
HaspMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)
- 其中 initialCapacity是一個(gè)初始化容量大小呐籽，指的是table數(shù)組的初始大小锋勺。
- loadFactor是負(fù)載因子，當(dāng)table數(shù)組的實(shí)際容量超過（initialCapacity*loadFactor）的時(shí)候绝淡，table數(shù)組就會(huì)擴(kuò)容宙刘。
- initialCapacity默認(rèn)值是15 而loadFactor的默認(rèn)值是0.75 他倆都是影響HashMap性能的重要因素。
首先看下構(gòu)造函數(shù)的源碼：
public HashMap(int initialCapacity, float loadFactor) {
// 首先檢查各個(gè)參數(shù)的合法性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
// 計(jì)算出大于 initialCapacity 的最小的 2 的 n 次方值牢酵。
// HashMap的實(shí)際數(shù)組大小都是2^n，是為了優(yōu)化而設(shè)計(jì)
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// 計(jì)算極限容量 超過后將會(huì)進(jìn)行擴(kuò)容
threshold = (int) (capacity * loadFactor);
//初始化table數(shù)組
table = new Entry[capacity];
init();
}
其中有一個(gè)Entry是HashMap的內(nèi)部類：
Entry() {
K key;
V value;
Entry<K, V> next;
int hash;
}
它是實(shí)際儲(chǔ)存Key和Value的實(shí)體衙猪。next是指向下一個(gè)元素的引用馍乙，hash是key的hash值布近。
2.3 數(shù)據(jù)的存放
再來看下put方法的源碼：
public V put(K key, V value) {
// 如果key的值是null，直接將其放在null位置上丝格，也就是第一個(gè)位置上
if (key == null)
return putForNullKey(value);
//計(jì)算key的hash值
int hash = hash(key.hashCode());
//計(jì)算key hash 值在 table 數(shù)組中的位置
int i = indexFor(hash, table.length);
//從i出開始迭代 e,找到 key 保存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷該條鏈上是否有hash值相同的(key相同)
//若存在相同撑瞧，則直接覆蓋value，返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回舊值
}
}
//修改次數(shù)增加1
modCount++;
//將key显蝌、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}
- 首先判斷key值是否為null预伺，如果是null，則將hash值當(dāng)成0處理 否則
- 根據(jù)key對(duì)象的
hashCode()方法計(jì)算出hash值曼尊，然后再將hash值轉(zhuǎn)化成在table中的索引 然后 - 查找該索引處的鏈表中是否存在key相同的對(duì)象酬诀，如果有則將其覆蓋，并且返回舊值 否則
- 將key骆撇、value存放于該數(shù)組索引處鏈表的第一個(gè)位置上瞒御，其中這一步是在
addEntry()方法中完成的
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取bucketIndex處的Entry
Entry<K, V> e = table[bucketIndex];
//將新創(chuàng)建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
//若HashMap中元素的個(gè)數(shù)超過極限了神郊，則容量擴(kuò)大兩倍
if (size++ >= threshold)
resize(2 * table.length);
}
2.4 數(shù)據(jù)的取出
對(duì)于HashMap肴裙，取出值是相對(duì)簡單的：
public V get(Object key) {
// 若為null，調(diào)用getForNullKey方法返回相對(duì)應(yīng)的value
if (key == null)
return getForNullKey();
// 根據(jù)該 key 的 hashCode 值計(jì)算它的 hash 碼
int hash = hash(key.hashCode());
// 取出 table 數(shù)組中指定索引處的值
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key與查找的key相同涌乳，則返回相對(duì)應(yīng)的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
2.5 HashMap的小結(jié)
從上面的分析中可以看出蜻懦，HashMap的存取速度都是相對(duì)比較快的，在一般情況下都能實(shí)現(xiàn)O(1)的速度夕晓，但是從初始容量和負(fù)載因子都可以看出阻肩，這種快速的讀取都是通過內(nèi)存來換取，而對(duì)于移動(dòng)設(shè)備來講运授，內(nèi)存又是很重要的烤惊，所以，Google為我們提供了Arraymap來代替它吁朦。
3. ArrayMap的簡單分析
在ArrayMap的內(nèi)部柒室，使用一個(gè)hash數(shù)組加一個(gè)kay，value數(shù)組來儲(chǔ)存逗宜。
當(dāng)你想獲取某個(gè)value的時(shí)候雄右，ArrayMap會(huì)計(jì)算輸入key轉(zhuǎn)換過后的hash值，然后對(duì)hash數(shù)組使用二分查找法尋找到對(duì)應(yīng)的index纺讲，然后我們可以通過這個(gè)index在另外一個(gè)數(shù)組中直接訪問到需要的鍵值對(duì)擂仍。如果在第二個(gè)數(shù)組鍵值對(duì)中的key和前面輸入的查詢key不一致，那么就認(rèn)為是發(fā)生了碰撞沖突熬甚。為了解決這個(gè)問題逢渔，我們會(huì)以該key為中心點(diǎn)，分別上下展開乡括，逐個(gè)去對(duì)比查找肃廓，直到找到匹配的值（開放地址法）智厌。如下圖所示：
可以看出，ArrayMap將內(nèi)存的使用率提高了很多盲赊，但是讀取的復(fù)雜度卻是O(lgN)（因?yàn)槎址ú檎遥┫撑簟Ｋ栽跀?shù)據(jù)量不是很大（千級(jí)以內(nèi)）的時(shí)候，我們使用ArrapMap可以優(yōu)化內(nèi)存哀蘑，并且存取速度幾乎是不受什么影響的诚卸。
其實(shí)這里還有一點(diǎn)，就是自動(dòng)裝箱問題绘迁，假設(shè)我們把一個(gè)key是int類型的數(shù)據(jù)存儲(chǔ)時(shí)合溺，HashMap會(huì)將int值自動(dòng)裝箱成Integer對(duì)象，一個(gè)對(duì)象和一個(gè)基本類型所占的內(nèi)存大小是差別很大的脊髓，所以為了避免這樣情況辫愉，Google提供了SparseIntArray,SparseBoolArray等一系列大禮包供我們使用。
4. 總結(jié)
總結(jié)一句話将硝，在數(shù)據(jù)量千級(jí)以內(nèi)恭朗，使用ArrayMap ArraySet或者SparseIntMap等來代替HashMap，以此節(jié)約寶貴的內(nèi)存資源依疼。
