SimpleArrayMap
SimpleArrayMap 是 Andorid V4 包提供的一種用來代替 HashMap 的數(shù)據(jù)結(jié)構(gòu)讼庇，由于 HashMap 在數(shù)據(jù)容量過大時(shí)時(shí)間復(fù)雜度會(huì)越來與趨近于 O(N) , 故而效率不高昵仅。SimpleArrayMap 的實(shí)現(xiàn)方式和工作過程使其內(nèi)存占用更小，在數(shù)據(jù)量不大時(shí)效率更高须眷，所以在 Android 開發(fā)中我們可以擇機(jī)選擇適合的方式來實(shí)現(xiàn) Map
下面我們就來一步步分析，為什么 SimpleArrayMap 可以實(shí)現(xiàn)更小的內(nèi)存占用和更加高效查找
一、成員變量
/**
* ArrayMap 擴(kuò)容的最小數(shù)量
*/
private static final int BASE_SIZE = 4;
/**
* 緩存數(shù)組的最大數(shù)量，使用小的緩存數(shù)組可以避免垃圾回收
*/
private static final int CACHE_SIZE = 10;
// 緩存所用的數(shù)組韭畸，以及已經(jīng)換的數(shù)量
static Object[] mBaseCache;
static int mBaseCacheSize;
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
/**
* 存放 key 的 hash 值的數(shù)組
*/
int[] mHashes;
/**
* 存放 key 和 value 的數(shù)組
*/
Object[] mArray;
/**
* 已存鍵值對的數(shù)量
*/
int mSize;
二宇智、構(gòu)造方法
/**
* 創(chuàng)建容量為空的 mHashes 和 mArray 數(shù)組
*/
public SimpleArrayMap() {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
/**
* 根據(jù)給定的初始容量創(chuàng)建 mHashes 和 mArray 數(shù)組
*/
public SimpleArrayMap(int capacity) {
if (capacity == 0) {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
} else {
allocArrays(capacity);
}
mSize = 0;
}
/**
* 根據(jù)給定的 ArrayMap 初始化
*/
public SimpleArrayMap(SimpleArrayMap map) {
this(); // 調(diào)用無參數(shù)構(gòu)造函數(shù)
if (map != null) {
// 將給定的 ArrayMap 添加
putAll(map);
}
}
/**
* 將給定的 ArrayMap 添加本身
*/
public void putAll(SimpleArrayMap<? extends K, ? extends V> array) {
final int N = array.mSize;
// 確認(rèn)容量支持添加給定的 ArrayMap
ensureCapacity(mSize + N);
if (mSize == 0) { // 如果原數(shù)組容量為 0蔓搞，則將給定數(shù)組添加進(jìn)新創(chuàng)建的數(shù)組中
if (N > 0) {
System.arraycopy(array.mHashes, 0, mHashes, 0, N);
System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
mSize = N;
}
} else { // 如果原數(shù)組容量不為 0，則遍歷給定數(shù)組随橘，將給定數(shù)組的值添加到原數(shù)組中
for (int i=0; i<N; i++) {
put(array.keyAt(i), array.valueAt(i));
}
}
}
/**
* 確認(rèn)容量支持指定的最小數(shù)量喂分，如果當(dāng)前容量小于指定的數(shù)量，則以給定數(shù)量創(chuàng)建新的數(shù)組
*/
public void ensureCapacity(int minimumCapacity) {
if (mHashes.length < minimumCapacity) {
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 以給定容量創(chuàng)建新的數(shù)組
allocArrays(minimumCapacity);
if (mSize > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, mSize);
System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
}
// 緩存舊的 hash 數(shù)組
freeArrays(ohashes, oarray, mSize);
}
}
SimpleArrayMap 有三個(gè)重載的構(gòu)造方法机蔗，其中給定容量和給定 ArrayMap 的構(gòu)造方法中涉及到的方法我們下面回一一解析
三蒲祈、插入方法 put()
public V put(K key, V value) {
final int hash;
int index;
if (key == null) {
hash = 0;
// 查找對應(yīng) key 在 hash 值數(shù)組中的位置
index = indexOfNull();
} else {
hash = key.hashCode();
// 查找對應(yīng) key 在 hash 值數(shù)組中的位置
index = indexOf(key, hash);
}
if (index >= 0) { // 存在甘萧，直接替換 array 數(shù)組中對應(yīng)位置的 value 值，并將舊值返回
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index; // 未找到情況梆掸，需要執(zhí)行插入操作
if (mSize >= mHashes.length) { // 為新插入數(shù)組需要擴(kuò)容舊數(shù)組
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) // 當(dāng)前鍵值對數(shù)量大于等于最小擴(kuò)容數(shù)量的 2 倍時(shí)扬卷，n 等于 mSeze 的 1.5 倍
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); // 當(dāng)前鍵值對數(shù)量大于等于最小擴(kuò)容數(shù)量時(shí)，n 等于最小擴(kuò)容量的 2 倍酸钦，否則就等于最小擴(kuò)容量
// 保存舊的 hash 數(shù)組
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 以最新的容量創(chuàng)建 hash 和 mArray 數(shù)組
allocArrays(n);
if (mHashes.length > 0) { // 大于 0 的情況是創(chuàng)建新數(shù)組時(shí)使用了緩存
// 將舊數(shù)組中的數(shù)據(jù)復(fù)制到新數(shù)組中
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
// 將舊數(shù)組添加到緩存
freeArrays(ohashes, oarray, mSize);
}
if (index < mSize) { // 需要插入到舊數(shù)組中間
// 將需要插入位置之后的數(shù)據(jù)右移一位
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
// 在 hash 和 array 數(shù)組的對應(yīng)位置插入新值
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++; // 鍵值對數(shù)量加 1
return null;
}
/**
* 計(jì)算 key 為 null 的時(shí)候應(yīng)該插入的位置
*/
int indexOfNull() {
final int N = mSize;
// 鍵值對為 0 怪得，直接返回 0
if (N == 0) {
return ~0;
}
// 二分法找到對應(yīng) 0 值在 mHashes 數(shù)組中的位置
int index = ContainerHelpers.binarySearch(mHashes, N, 0);
// index 小于 0 說明 mHashes 數(shù)組中不存存在 0，則直接返回
if (index < 0) {
return index;
}
// mHashes 中有對應(yīng)值時(shí)卑硫，mArray 數(shù)組中對應(yīng)位置為 null徒恋，新值可以直接插入，此時(shí)直接返回 0 在 mHashes 中的位置
if (null == mArray[index<<1]) {
return index;
}
// mArray 數(shù)組中對應(yīng)位置不為 null欢伏，此時(shí)向后尋找 hash 為 0 但 mArray 對應(yīng)位置為 null 的索引
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}
// mArray 數(shù)組中對應(yīng)位置不為 null入挣，此時(shí)向前尋找 hash 為 0 但 mArray 對應(yīng)位置為 null 的索引
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return i;
}
// 如果未找到 mHashes 中值為 0 且 mArray 數(shù)組中對應(yīng)位置為 null 的索引，則返回當(dāng)前 hash 數(shù)組的長度值加 1 的值取反作為新插入的位置硝拧，表明需要插入新的位置
return ~end;
}
/**
* 計(jì)算 key 應(yīng)該插入的位置
*/
int indexOf(Object key, int hash) {
final int N = mSize;
// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
int index = ContainerHelpers.binarySearch(mHashes, N, hash);
// If the hash code wasn't found, then we have no entry for this key.
if (index < 0) {
return index;
}
// If the key at the returned index matches, that's what we want.
if (key.equals(mArray[index<<1])) {
return index;
}
// 這里與 indexOfNull() 方法中類似径筏，只不過將 mArray 數(shù)組中對應(yīng)位置的是否為 null 改為了判斷 mHashes 數(shù)組中的 key 是否相同，如果匹配成功則返回對應(yīng)位置
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}
// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}
// 未匹配成功則返回需要插入的位置取反后的值障陶，表明需要插入新的位置
return ~end;
}
/**
* 緩存數(shù)據(jù) 由代碼分析可以看到最終添加到緩存的只是 mHashes 數(shù)組
* hashes 的長度為最小擴(kuò)容量或者為最小擴(kuò)容量的兩倍匠璧，并且緩存的數(shù)量小于最大緩存容量時(shí)，才執(zhí)行緩存操作
*/
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if (mTwiceBaseCacheSize < CACHE_SIZE) {
array[0] = mTwiceBaseCache; // 將舊的緩存數(shù)據(jù)放入 array[0] 的位置
array[1] = hashes; // 將新的需要緩存的 hash 數(shù)組放入 array[1] 的位置
// 通過遍歷 array 數(shù)組咸这，將其他位置置空
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
// 將緩存索引重新指向最新的緩存數(shù)組
mTwiceBaseCache = array;
// 緩存數(shù)量加 1
mTwiceBaseCacheSize++;
}
}
} else if (hashes.length == BASE_SIZE) { // 同上
synchronized (ArrayMap.class) {
if (mBaseCacheSize < CACHE_SIZE) {
array[0] = mBaseCache;
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
mBaseCache = array;
mBaseCacheSize++;·
}
}
}
}
/**
* 有緩存時(shí)使用緩存創(chuàng)建 hash 數(shù)組
*/
private void allocArrays(final int size) {
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
if (mTwiceBaseCache != null) {
final Object[] array = mTwiceBaseCache;
mArray = array;
mTwiceBaseCache = (Object[])array[0];
mHashes = (int[])array[1]; // 使用緩存的 hash 數(shù)組
array[0] = array[1] = null; // 緩存數(shù)量減 1
mTwiceBaseCacheSize--;
if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
+ " now have " + mTwiceBaseCacheSize + " entries");
return;
}
}
} else if (size == BASE_SIZE) {
synchronized (ArrayMap.class) {
if (mBaseCache != null) {
final Object[] array = mBaseCache;
mArray = array;
mBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
array[0] = array[1] = null;
mBaseCacheSize--;
if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
+ " now have " + mBaseCacheSize + " entries");
return;
}
}
}
// 沒有緩存或者與緩存長度不匹配時(shí)夷恍，則直接創(chuàng)建對應(yīng)長度的 mHashes 數(shù)組和 mArray 數(shù)組
mHashes = new int[size];
mArray = new Object[size<<1];
}
從構(gòu)造函數(shù)和 put 方法來看，SimpleArrayMap 的實(shí)現(xiàn)方式為媳维，由一個(gè)存儲(chǔ) int 類型 key 的 hash 值的數(shù)組 mHashes 和一個(gè)同時(shí)存儲(chǔ) key 和 value 的 Object 類型的 mArray 數(shù)組構(gòu)成酿雪，mArray 會(huì)依次按照 key-value 的順序存儲(chǔ)數(shù)據(jù)
四、查找方法 get()
/**
* 根據(jù) key 獲取 value 值
*/
public V get(Object key) {
// 找到 key 的 hash 值在 mHashes 數(shù)組中的索引
final int index = indexOfKey(key);
// 返回 mArray 數(shù)組中對應(yīng)的 value 值
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
/**
* 找到 key 的 hash 值在 mHashes 數(shù)組中的索引
*/
public int indexOfKey(Object key) {
// indexOfNull 時(shí)當(dāng) key 為 null 時(shí)查找侄刽，indexOf 為 key 不為 null 時(shí)的查找指黎，上面分析 put() 方法時(shí)已經(jīng)解析過了
return key == null ? indexOfNull() : indexOf(key, key.hashCode());
}
/**
* 根據(jù) value 獲取 value 對應(yīng) key 在 mHashes 數(shù)組中的索引，區(qū)分 null 可非 null 情況
*/
int indexOfValue(Object value) {
final int N = mSize*2;
final Object[] array = mArray;
if (value == null) {
for (int i=1; i<N; i+=2) {
if (array[i] == null) {
return i>>1;
}
}
} else {
for (int i=1; i<N; i+=2) {
if (value.equals(array[i])) {
return i>>1;
}
}
}
return -1;
}
/**
* 判斷 Map 中是否有指定 key
*/
public boolean containsKey(Object key) {
return indexOfKey(key) >= 0;
}
五州丹、移除方法
/**
* 移除指定 key 的鍵值對
*/
public V remove(Object key) {
final int index = indexOfKey(key);
if (index >= 0) {
return removeAt(index);
}
return null;
}
/**
* 移除指定 hash 數(shù)組中位置對應(yīng)的鍵值對
*/
public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
if (mSize <= 1) { // 如果鍵值對數(shù)量為小于等于 1醋安，添加緩存后直接清空數(shù)組
// Now empty.
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
} else {
// 如果數(shù)組長度過大，并且數(shù)組重的鍵值對太小墓毒，則需要縮小足夠的容量以降低數(shù)組的大小吓揪，但是不會(huì)縮小到 BASE_SIZE*2 的值，避免數(shù)組容量的搖擺
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// 計(jì)算壓縮后的容量大小
final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 根據(jù)給定容量創(chuàng)建數(shù)組
allocArrays(n);
mSize--;
if (index > 0) { // index 大于 0所计，則將舊數(shù)組中索引在 0-index 的 hash 對應(yīng)內(nèi)容復(fù)制到新的數(shù)組柠辞，不包含 index 位置
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
// index 小于 mSize 說明，移除的 index 位置的值不是在數(shù)組中的最后主胧，此時(shí)需要將 index 以后的值同樣添加到新的數(shù)組中
if (index < mSize) {
System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
} else { // 不需要壓縮時(shí)叭首，直接將 index 以后的內(nèi)容全部左移一個(gè)單位习勤，再將最后一個(gè)鍵值對置空即可
mSize--;
if (index < mSize) {
System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
mArray[mSize << 1] = null;
mArray[(mSize << 1) + 1] = null;
}
}
// 返回移除的 value 值
return (V)old;
}
移除對應(yīng)位置鍵值對的過程中還對數(shù)組做了縮容處理，可以節(jié)省內(nèi)存焙格，并提升執(zhí)行查詢功能速度
六图毕、其他方法
/**
* 清空 Map
*/
public void clear() {
if (mSize != 0) {
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
}
/**
* 獲取指定 hash 數(shù)組中位置對應(yīng)的鍵
*/
public K keyAt(int index) {
return (K)mArray[index << 1];
}
/**
* 獲取指定 hash 數(shù)組中位置對應(yīng)的值
*/
public V valueAt(int index) {
return (V)mArray[(index << 1) + 1];
}
/**
* 設(shè)置 hash 數(shù)組中位置對應(yīng)的值為指定的 value
*/
public V setValueAt(int index, V value) {
index = (index << 1) + 1;
V old = (V)mArray[index];
mArray[index] = value;
return old;
}
/**
* 判斷 Map 是否為空
*/
public boolean isEmpty() {
return mSize <= 0;
}
/**
* 獲取鍵值對數(shù)量
*/
public int size() {
return mSize;
}
/**
* equals 方法
* 如果要對比的 object 不是一個(gè) Map 或者不是一個(gè) SimpleArrayMap 則直接返回 false ，鍵值對數(shù)量不想同時(shí)也直接返回 false
* 如果以上對比通過眷唉，則會(huì)對比每一個(gè)鍵值對都會(huì)對比吴旋，如果鍵值對都相同則返回 true，否則返回 false
*/
public boolean equals(Object object) {
if (this == object) {
return true;
}
if (object instanceof SimpleArrayMap) {
SimpleArrayMap<?, ?> map = (SimpleArrayMap<?, ?>) object;
if (size() != map.size()) {
return false;
}
try {
// 遍歷當(dāng)前數(shù)組厢破，對比每一個(gè)鍵值對
for (int i=0; i<mSize; i++) {
K key = keyAt(i);
V mine = valueAt(i);
Object theirs = map.get(key);
if (mine == null) {
if (theirs != null || !map.containsKey(key)) {
return false;
}
} else if (!mine.equals(theirs)) {
return false;
}
}
} catch (NullPointerException ignored) {
return false;
} catch (ClassCastException ignored) {
return false;
}
return true;
} else if (object instanceof Map) {
Map<?, ?> map = (Map<?, ?>) object;
if (size() != map.size()) {
return false;
}
try {
// 遍歷當(dāng)前數(shù)組荣瑟，對比每一個(gè)鍵值對
for (int i=0; i<mSize; i++) {
K key = keyAt(i);
V mine = valueAt(i);
Object theirs = map.get(key);
if (mine == null) {
if (theirs != null || !map.containsKey(key)) {
return false;
}
} else if (!mine.equals(theirs)) {
return false;
}
}
} catch (NullPointerException ignored) {
return false;
} catch (ClassCastException ignored) {
return false;
}
return true;
}
return false;
}
public int hashCode() {
final int[] hashes = mHashes;
final Object[] array = mArray;
int result = 0;
for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) {
Object value = array[v];
result += hashes[i] ^ (value == null ? 0 : value.hashCode());
}
return result;
}
/**
* 打印所有鍵值對
*/
public String toString() {
if (isEmpty()) {
return "{}";
}
StringBuilder buffer = new StringBuilder(mSize * 28);
buffer.append('{');
for (int i=0; i<mSize; i++) {
if (i > 0) {
buffer.append(", ");
}
Object key = keyAt(i);
if (key != this) {
buffer.append(key);
} else {
buffer.append("(this Map)");
}
buffer.append('=');
Object value = valueAt(i);
if (value != this) {
buffer.append(value);
} else {
buffer.append("(this Map)");
}
}
buffer.append('}');
return buffer.toString();
}
七、總結(jié)
到這里整個(gè) SimpleArrayMap 的源碼就分析完了摩泪，重點(diǎn)要掌握的是由兩個(gè)數(shù)組實(shí)現(xiàn) SimpleArrayMap 的這種數(shù)據(jù)結(jié)構(gòu)笆焰，相比較 HashMap ，SimpleArrayMap 避免了每個(gè)鍵值對都使用 Entry 來包裝见坑，并且在查詢時(shí)如果數(shù)據(jù)量不大時(shí)使用二分法速度更快嚷掠。并且 SimpleArrayMap 每次 remove 操作時(shí)都會(huì)做縮容操作，這樣可以降低內(nèi)存使用荞驴，并且進(jìn)一步提升查找時(shí)的時(shí)間消耗不皆。所以在 Android 開發(fā)中，如果鍵值對的數(shù)量級較小情況下使用 SimpleArrayMap 虧更加高效熊楼！
