ArrayMap和SparseArray

ArrayMap

ArrayMap是android特有的api，主要是用于提高内存效率。他比传统的hashmap要慢，所以不适合大数据的存储，因为添加和查找的时候用二分查找法寻找，并且不是线程安全的.

主要是由2个数组mArray和mHashes来存储，其中mArray是用来存key-value的,mHashes是用来存key的value的,整体put方法的逻辑是这样（下面的图我是粘贴的，但是总结的很好）：

mSize是ArrayMap中元素的个数，每次插入的时候都会计算这个size，扩大一次就是扩大2倍。

SparseArray

SparseArray是android上用来替代key是int而value是object的hashmap。更加节省空间，也是线程不安全的。原理也是2个数组，mKeys是int类型的数组，存储key的，mValues类型是object的。在需要节省空间的时候可以使用，一般在1000以内可以，超过了之后时间消耗会翻倍。

put方法逻辑：首先利用二分查找法找到待插入key的index，如果index>0说明这个key存在，直接覆盖value，如果<0，先取反，找到应该插入的位置，如果i没有越界，且对应位置是已删除的标记，，则复用这个空间。如果需要gc且需要扩容，先gc再扩容，然后再插入。