ArrayMap的使用与详解

数据集合在任何一门编程语言中都是很重要的一部分，在 Android 开发中，我们会实用到List,ArrayList, HashMap等。List和ArrayList配合使用，其中HashMap是用来处理键值对需求的常用集合。 而Android中引入了一个新的集合，叫做ArrayMap，为键值对存储需求增加了一种选择。而ArrayMap这个集合是从4.4版本的时候推出的，到现在已经经历过几个版本的修改，前期的append()方法，已经被删除了等。
至于今天为什么要把ArrayMap拿出来说呢，是因为ArrayMap在合适的场景中使用比HashMap这些集合效率更高和占用内存空间更少的情况。

1.ArrayMap是继承了SimpleArrayMap类，和对Map的扩展。

2.ArrayMap的内部结构
ArrayMap中有两个数组mHashes和mArray。


key的hashcode找到在mHashes数组中的索引值，然后将索引值2+1，得到mArray的数组下标
3.查找数据：get(Object key)、keyAt(int index)和valueAt(int index)
ArrayMap中的查找分为如下两步。
1.根据k值得到其hash值h，在mmHashes数组（从小到大排列的）根据二分法找到h值相等的所有索引。
2.在mHashes找到的可能有多个，比如index为n1,n2
3.再次比较k值，即mArray[2n1] 和mArray[2n2] 是否等于k值。假如mArray[2n2] == k
4.返回mArray[2*n2+1]
而这一步对mHashes查找使用的是二分查找，即Binary Search。所以ArrayMap的查询时间复杂度为 ‎O(log n)。

   public V get(Object key) {
        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
    }
   public int indexOfKey(Object key) {
        return key == null ? indexOfNull()
                : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
    }

4.插入数据
所提供的方法有：
arrayMap.put(“1”,"-");
arrayMap.putAll(new HashMap());

5.删除数据
arrayMap.remove(“1”);
arrayMap.removeAt(1);
arrayMap.removeAll();