HashMap,ArrayMap,SparseArray 源码角度分析,Android中的数据结构你该如何去选择？
table = newTab;
可以看到當我們的table數組存儲的節點值大于threshold時,會按我們的當前數組大小的兩倍生成一個新的數組，并把舊數組上的數據復制到新數組上這就是我們的HashMap擴容。伴隨著一個新數組的生成和數組數據的copy，會有一定性能上的損耗。如果我們在使用HashMap的是能夠明確HashMap能夠一開始就清楚的知道HashMap存儲的鍵值對個數，我建議我們使用HashMap的另一個構造方法。
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
注意了這個initialCapacity值最好去2的整數次冪。如果我們要存放40個鍵值對，那我們這個initialCapacity最好傳64。至于為什么這樣，我們下次在去討論。
下面我們來分析HashMap的get方法：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
在get的時候，我們首先會根據我們的key去計算它的hash值，如果這個hash值不存在，我們直接反回null。
如果存在，在沒有發生hash沖突的情況下也就是根據當前hash值計算出的索引上的存儲數據不是以樹和鏈表的形式存儲的時候，我們直接返回當前索引上存儲的值，如果時鏈表樹，我們就去遍歷節點上的數據通過equals去比對，找到我們需要的在返回。
通過上面我可以得出結論，當HashMap沒有發生hash沖突時，hashMap的查找和插入的時間復雜度都是O(1),效率時非常高的。
當我們發生擴容和hash沖突時，會帶來一定性能上的損耗。
HashMap大致分析完了。
下面我們來分析分析Android為我們提供的ArrayMap和SparseArray。
二.我們在來看看ArrayMap:
public class A
rrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> {
MapCollections<K, V> mCollections;
int[] mHashes;
Object[] mArray;
通過源碼我們可以看到ArrayMap繼承自SimpleArrayMap實現了Map接口,ArrayMap內部是兩個數組，一個存放hash值，一個存放Obeject對象也就是value值，這一點就和HashMap不一樣了。我們現來看看ArrayMap的構造方法：
public ArrayMap(int capacity) {
super(capacity);
}
public SimpleArrayMap() {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
我們發現ArrayMap的初始化會給我們初始化兩個空數組，并不像HashMap一樣為我們默認初始化了一個大小為16的table數組，下面我們繼續往下看：
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (osize >= mHashes.length) {
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
throw new ConcurrentModificationException();
}
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, “put: copy 0-” + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, osize);
}
if (index < osize) {
if (DEBUG) Log.d(TAG, "put: move " + index + “-” + (osize-index)
- " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
if (osize != mSize || index >= mHashes.length) {
throw new ConcurrentModificationException();
}
}
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}
我們先看看put方法的實現。首先就是判段key是否null，是null，hash值直接置為0，如果不為null，通過Obejct的hashCode()方法計算出hash值。然后通過indexfOf方法計算出index的值。下面我們來看看indexOf方法：
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 = binarySearchHashes(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;
}
// Search for a matching key after the index.
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;
}
// Key not found – return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;
}
我們可以看到indexOf方法內部是根據binarySearchHashes()去搜索hash值得，下面我們再來看看binarySearchHashes()
內部調用了ContainerHelpers.binarySearch(hashes, N, hash);我們在看來看看binarySearch方法。
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
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
}
可以發現binarySearch是典型得二叉搜索算法。所以我們可以得出結論，ArrayMap插入和索引是基于二叉搜索實現得。這種搜索得效率也很高，他的時間復雜度O(log(n))，但是和HashMap O(1)還是有點差距的。
下面我們繼續看indexOf方法，如果我們通過二叉搜索查到得index值小于0，代表我們沒有存儲過該數據則直接返回，如果index大于0，我們就去通過equals去比對原來索引得上得key，如果相等，代表我們存儲過該值，直接返回index，到時候我們存儲的時候會直接覆蓋掉當前已經存儲得值。如果不相等，出現Hash沖突，重新計算出一個index值返回。
下面我們來看看ArrayMap如何處理Hash沖突和擴容的(我們沒有指定容量的時候，ArrayMap默認初始化了兩個空數組)。
if (osize >= mHashes.length)
出現hash沖突后，如果我們的存儲數據數量大小已經大于等于我們的hash數組的大小。我們對數組進行擴容。
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, “put: copy 0-” + osize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
如果我們的osize(已經存儲的多少value個數)大于等于兩倍的BASE_SIZE(常量為4)我們就在原來osize的基礎上擴容0.5倍，
如果我們的osize小于8(兩個BASE_SIZE)并且大于4（一個BASE_SIZE），我們將數組擴容到8，否則我們將數組大小擴容到4。
根據上面的分析，我們可以得出結論，ArrayMap的插入和索引是基于二分法的。查找和索引效率不如HashMap。但是要比HashMap占用更少的內存空間，HashMap擴容實是在原來起table的基礎上擴容一倍，而ArrayMap實在存儲數據的個數上擴容0.5倍，不會造成太多的空間浪費。在移動設備上內存遠比PC設備上值錢的多。ArrayMap的設計就是用時間換取空間。
三.SparseArray：
public SparseArray() {
this(10);
}
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
Capacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
public void put(int key, E value) {
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
if (i >= 0) {
mValues[i] = value;
} else {
i = ~i;
if (i < mSize && mValues[i] == DELETED) {
mKeys[i] = key;
mValues[i] = value;
return;
}
if (mGarbage && mSize >= mKeys.length) {
gc();
總結
以上是生活随笔為你收集整理的HashMap,ArrayMap,SparseArray 源码角度分析,Android中的数据结构你该如何去选择？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 稻盛和夫的人生法则，所谓人生赢家，不过是
- 下一篇： Hex编码