- 官方解释
//ArrayMap是比HashMap内存效率更高
ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional {@link java.util.HashMap}.
// ArrayMap维持了一个数组才承载map, 一个int[]承载hash值，一个Object[]才承载key/value
// 这样避免了为每个Entry创建一个额外的对象，也尝试更加积极的控制size的增长（增长到极限之后，只需要将这名Entry复制到一个新数组里，不用重新创建hashMap）
It keeps its mappings in an array data structure -- an integer array of hash codes for each item, and an Object array of the key/value pairs. This allows it to avoid having to create an extra object for every entry put in to the map, and it also tries to control the growth of the size of these arrays more aggressively (since growing them only requires copying the entries in the array, not rebuilding a hash map).
还是按照我习惯的定义的方法分析
Map<String, Object> arrayMap = new ArrayMap();
走无参的构造函数，默认capacity=0，创建一个长度为0的hash值数组和一个Object的数组。
put方法实现
不管key是否为null，先获取当前key的hash值，所在的index。
获取index的方法，虽然是不同的方法，但本质上是相同，
查询方法对应的key：一个是对应的值，一个是null，对应的hash值：一个是key对应的hash值，一个是0
在int[] hash数组中查找的过程采用二分查找法，返回对应位置的position，如果没有找到返回低位position的~，会得到一个负数
- 得到key对应的hash在int[] hash的位置
- 得到的是index<0 直接返回该值
- 得到的index经转化之后，在Object[]数组中，得到的key与我们的key一致，则直接返回
- 如果不等，即可能发生冲突，相同hash值有不同key，则往index前后推算，直到得到key相等的position，返回
- 如果都没有找到则返回一个无效的值~msize
- 得到了最终的index
如果之前存在相同的key，即index>=0
index >= 0 的话，index = (index<<1) +1 把Object[]对应index位置上原来的值取出，并覆盖，返回原来的旧值。
如果不存在，即index=-1
index = ~index 由无效的值，变为之前的值(标黄的值)
此时要做插入操作
- 如果size>int[] hash的长度
// 如果size超过BASE_SIZE*2设为原来size的1.5倍
// 重新设置size
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
: (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
// 创建数组
allocArrays(n)
// 数组之间copy
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);
-
如果index<size
需要两个数组在指定index位置上的后移，为即将加入的数据准备位置 -
加入到指定位置,
hash值，直接入int[] hash数组
key/value ，key入index<<1位置上，value入(index<<1)+1的位置 -
总长度+1
至此，put的过程结束。
由此可以看出ArrayMap是有序的，按hash值排序
get方法实现
public V get(Object key) {
// 获取当前key的Index，取出值即可
final int index = indexOfKey(key);
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
remove方法实现
大体步骤：找到对应key的位置，移除该位置的值，将之前位置重新调整
ArrayMap与HashMap对比
- 在扩容方面：HashMap采用new的方式，系统开销比较大，ArrayMap则采用System.copyArray()方法
- 存储结构：HashMap采用Node链表形式，ArrayMap采用了2个数组的形式
网友评论