HashMap,ArrayMap,SparseArray 源码角度分析,Android中的数据结构你该如何去选择？

本文主要是介绍HashMap,ArrayMap,SparseArray 源码角度分析,Android中的数据结构你该如何去选择？，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

当我第一次调用put方法的时候我们的table数组为null，putVal方法内部，会帮我们调用resize()方法帮我们生成一个默认大小的

数组。默认大小就是我们的DEFAULT_INITIAL_CAPACITY的值，为16。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

数组初始化完成之后，会根据通过hash方法生成hash值与(n-1)做&运算计算出我们要存放数据的索引。n就是我们table的大小。

如果当前数组在这个索引没有值，则直接存储我们的value。如果当前数组在这个索引有值，三种情况去处理。

1.if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;

如果当前索引存放的值的key的hash值等于我们现在put的key的hash值，并且我们的key和当前索引存放的值是相等的，那我们就覆盖当前索引的值。(HashMap 数据不会重复，是否存放的同一个对象是通过key去判断的)。

2.else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果当前储存的值是TreeNode(树节点)。代表出现了hash冲突，我们为当前树新增一个叶子节点存放我们的数据。

3.else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }

否则我们生成一个新的节点，存放在当前值的后面形成一个链表。如果链表的节点数量大于TREEIFY_THRESHOLD - 1

则调用treeifyBin(tab, hash);把当前链表构造成一个树，存放在当前数组的索引上。

分析到这我们可以得出结论，HashMap是使用的链地址法解决的Hash冲突，如果链表的节点个数过多,我们就链表结构转换为

树结构。

我们继续往下看

if (++size > threshold)

resize();

如果当前存储存储的值的个数，大于threshold，我们调用resize方法。我们的threshold值等于什么呢 等于我们当前数组大小乘以一个DEFAULT_LOAD_FACTOR(装填因子)，通过HashMap源码我们可以看到我们的DEFAULT_LOAD_FACTOR默认为0.75.

所以我们默认threshold为(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)，等于12。

下面我们继续来分析resize()方法。

if (oldCap > 0) {

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

} else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

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 ArrayMap<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))

(osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

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数组的大小。我们对数组进行扩容。

最后

跳槽季整理面试题已经成了我多年的习惯！在这里我和身边一些朋友特意整理了一份快速进阶为Android高级工程师的系统且全面的学习资料。涵盖了Android初级——Android高级架构师进阶必备的一些学习技能。

附上：我们之前因为秋招收集的二十套一二线互联网公司Android面试真题（含BAT、小米、华为、美团、滴滴）和我自己整理Android复习笔记（包含Android基础知识点、Android扩展知识点、Android源码解析、设计模式汇总、Gradle知识点、常见算法题汇总。）

本文在开源项目：【GitHub 】中已收录，里面包含不同方向的自学编程路线、面试题集合/面经、及系列技术文章等，资源持续更新中…
理面试题已经成了我多年的习惯！在这里我和身边一些朋友特意整理了一份快速进阶为Android高级工程师的系统且全面的学习资料。涵盖了Android初级——Android高级架构师进阶必备的一些学习技能。

附上：我们之前因为秋招收集的二十套一二线互联网公司Android面试真题（含BAT、小米、华为、美团、滴滴）和我自己整理Android复习笔记（包含Android基础知识点、Android扩展知识点、Android源码解析、设计模式汇总、Gradle知识点、常见算法题汇总。）

[外链图片转存中…(img-IX7w5NBz-1644040536958)]

本文在开源项目：【GitHub 】中已收录，里面包含不同方向的自学编程路线、面试题集合/面经、及系列技术文章等，资源持续更新中…

这篇关于HashMap,ArrayMap,SparseArray 源码角度分析,Android中的数据结构你该如何去选择？的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！