ArrayMap SparseArray
問(wèn)題：ArrayMap SparseArray的數(shù)據(jù)結(jié)構(gòu)是怎么樣的？
雙數(shù)組結(jié)構(gòu)。ArrayMap第一個(gè)數(shù)組元素是key的hashValue，對(duì)應(yīng)第二個(gè)數(shù)組的一對(duì)key-value。通過(guò)二分查找進(jìn)行插入。 SparseArray第一個(gè)數(shù)組是int類型的key，第二個(gè)數(shù)組元素是value
為了更進(jìn)一步優(yōu)化key是int類型的Map，Android再次提供效率更高的數(shù)據(jù)結(jié)構(gòu)SparseArray，可避免自動(dòng)裝箱過(guò)程。對(duì)于key為其他類型則可使用ArrayMap。HashMap的查找和插入時(shí)間復(fù)雜度為O(1)的代價(jià)是犧牲大量的內(nèi)存來(lái)實(shí)現(xiàn)的，而SparseArray和ArrayMap性能略遜于HashMap，但更節(jié)省內(nèi)存。
ArrayMap
ArrayMap相比HashMap內(nèi)存更少，速度更慢。 ArraySet， ArrayList類似。
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" cid="n6" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-color: rgb(51, 51, 51); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 10px 10px 30px; width: inherit; background-position: initial initial; background-repeat: initial initial;" lang="Java">public final class ArrayMap<K, V> implements Map<K, V> {
?
private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;
private static final int BASE_SIZE = 4; // 容量增量的最小值
private static final int CACHE_SIZE = 10; // 緩存數(shù)組的上限
?
static Object[] mBaseCache; //用于緩存大小為4的ArrayMap
static int mBaseCacheSize;
static Object[] mTwiceBaseCache; //用于緩存大小為8的ArrayMap
static int mTwiceBaseCacheSize;
?
final boolean mIdentityHashCode;
int[] mHashes; //由key的hashcode所組成的數(shù)組
Object[] mArray; //由key-value對(duì)所組成的數(shù)組，是mHashes大小的2倍
int mSize; //成員變量的個(gè)數(shù)
}</pre>
<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" cid="n21" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-color: rgb(51, 51, 51); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 10px 10px 30px; width: inherit; background-position: initial initial; background-repeat: initial initial;" lang="Java">public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false; //標(biāo)記是否存在待回收的鍵值對(duì)
?
private int[] mKeys;
private Object[] mValues;
private int mSize;
}</pre>
SparseArray使用二分查找來(lái)找到key對(duì)應(yīng)的插入位置，保證mKeys數(shù)組從小到大的排序。
SparseArray對(duì)應(yīng)的key只能是int類型，它不會(huì)對(duì)key進(jìn)行裝箱操作。它使用了兩個(gè)數(shù)組，一個(gè)保存key，一個(gè)保存value。 從內(nèi)存使用上來(lái)說(shuō)，SparseArray不需要保存key所對(duì)應(yīng)的哈希值，所以比ArrayMap還能再節(jié)省1/3的內(nèi)存。
SparseArray，key是int類型的Map，更加memory-efficient。
SparseArray
如果當(dāng)前數(shù)組內(nèi)容已填充滿時(shí)，則會(huì)先進(jìn)行擴(kuò)容，再通過(guò)System.arraycopy來(lái)進(jìn)行數(shù)據(jù)拷貝，最后在相應(yīng)位置寫(xiě)入數(shù)據(jù)。
將修改已有鍵值對(duì)和插入新的鍵值對(duì)合在一個(gè)put()方法中，主要是依賴indexOf()過(guò)程中采用的二分查找法，在mHashes數(shù)組中查找值等于hash的key，當(dāng)找到相應(yīng)key時(shí)則返回正值，但找不到key則返回負(fù)值，按位取反所對(duì)應(yīng)的值代表的是需要插入的位置index。
Put原理
為了減少頻繁地創(chuàng)建和回收，特意設(shè)計(jì)了兩個(gè)緩存池，分別緩存大小為4和8的ArrayMap對(duì)象。
緩存
mHashes是一個(gè)記錄所有key的hashcode值組成的數(shù)組，是從小到大的排序方式；
mArray是一個(gè)記錄著key-value鍵值對(duì)所組成的數(shù)組，是mHashes大小的2倍；
用一句話總結(jié)就是ArrayMap使用兩個(gè)數(shù)組進(jìn)行數(shù)據(jù)存儲(chǔ)，一個(gè)int[]數(shù)組，用于保存每個(gè)item的hashCode. 一個(gè)Object[]數(shù)組，保存key/value鍵值對(duì)。容量是上一個(gè)數(shù)組的兩倍。
