ArrayMap分析

2019-02-20  本文已影响0人  小锡兵鸥

//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的~,会得到一个负数

  1. 得到的是index<0 直接返回该值
  2. 得到的index经转化之后,在Object[]数组中,得到的key与我们的key一致,则直接返回
  3. 如果不等,即可能发生冲突,相同hash值有不同key,则往index前后推算,直到得到key相等的position,返回
  4. 如果都没有找到则返回一个无效的值~msize

如果之前存在相同的key,即index>=0
index >= 0 的话,index = (index<<1) +1 把Object[]对应index位置上原来的值取出,并覆盖,返回原来的旧值。

如果不存在,即index=-1
index = ~index 由无效的值,变为之前的值(标黄的值)

此时要做插入操作

// 如果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);

至此,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对比

上一篇 下一篇

猜你喜欢

热点阅读