Android - ArrayMap

ArrayMap 和 HashMap 区别

• HashMap :
  1.存储结构 : key-value结构 , 数组+链表+红黑树结构
  2.内存消耗较大
  3.查询使用HashCode进行查找,大量数据查询快
  4.key == null,value == null
• ArrayMap :
  1.存储结构 : key-value结构 , 数组存储(两个数组,一个存储HashCode值,一个存储Key-Value值)
  2.内存消耗较小,专门用于移动端优化内存使用(时间换空间)
  3.查询使用二分法查找,大量数据查找较慢
  4.key == null,value == null
  5.删除数据时会收缩数组

ArrayMap源码 - 重要字段

//默认创建数组的长度
private static final int BASE_SIZE = 4;
//数据释放时,缓存的累计次数(size == 4,或者size==8的情况下释放数组会用到缓存)
private static final int CACHE_SIZE = 10;
//生成空的ArrayMap
public static final ArrayMap EMPTY = new ArrayMap<>(-1);
static final int[] EMPTY_IMMUTABLE_INTS = new int[0];
//size == 4时,缓存的数组
static Object[] mBaseCache;
static int mBaseCacheSize;
//size == 8时,缓存的数组
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;
//生成HashCoe()的方法
final boolean mIdentityHashCode;
//存放Key HashCode()的值的数组
int[] mHashes;
//存放Key-Value 值的数组,长度是mHashes的2倍
Object[] mArray;
//实际的数据存储长度
int mSize;

ArrayMap源码 - mHashes 和 mArray 的关系图

3768281-1af0108b942ea976 (1).jpg

ArrayMap源码 - 构造方法

  public ArrayMap() {
    this(0, false);
  }
  public ArrayMap(int capacity) {
    this(capacity, false);
  }
  public ArrayMap(int capacity, boolean identityHashCode) {
    //HashCode的生成方式
    //True : System.identityHashCode(key)
    //False : key.hashCode()
    mIdentityHashCode = identityHashCode;
    if (capacity < 0) {
      //空的int[0] 数组
      mHashes = EMPTY_IMMUTABLE_INTS;
      mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
      mHashes = EmptyArray.INT;
      mArray = EmptyArray.OBJECT;
    } else {
      //根据大小进行扩容
      allocArrays(capacity);
    }
    mSize = 0;
  }
  private void allocArrays(final int size) {
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
      throw new UnsupportedOperationException("ArrayMap is immutable");
    }
    //BASE_SIZE 默认值=4,这里判断size == 8时候
    if (size == (BASE_SIZE*2)) {
      synchronized (ArrayMap.class) {
        if (mTwiceBaseCache != null) {
          //获取缓存的数组
          final Object[] array = mTwiceBaseCache;
          //数据快速赋值给当前使用的Key-Value数组
          mArray = array;
          // 这里的赋值可以查看freeArrays()中size == 8的情况
          mTwiceBaseCache = (Object[])array[0];
          mHashes = (int[])array[1];
          array[0] = array[1] = null;
          mTwiceBaseCacheSize--;
          if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
              + " now have " + mTwiceBaseCacheSize + " entries");
          return;
        }
      }
      //BASE_SIZE 默认值 = 4,这里判断size == 4 的时候
    } else if (size == BASE_SIZE) {
      synchronized (ArrayMap.class) {
        if (mBaseCache != null) {
          final Object[] array = mBaseCache;
          mArray = array;
          mBaseCache = (Object[])array[0];
          mHashes = (int[])array[1];
          array[0] = array[1] = null;
          mBaseCacheSize--;
          if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
              + " now have " + mBaseCacheSize + " entries");
          return;
        }
      }
    }
    //如果Size > 8 ,直接创建新的数组
    mHashes = new int[size];
    mArray = new Object[size<<1];
  }
  //释放数组数据
  private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    //hashes : 存储HashCode()的数组
    //array : 存储Key-Value的数组
    if (hashes.length == (BASE_SIZE*2)) {
      synchronized (ArrayMap.class) {
        //CACHE_SIZE = 10(常量值)
        if (mTwiceBaseCacheSize < CACHE_SIZE) {
          //Key-Value 的数组第一个值 = mTwiceBaseCache
          //Key-Value 的数组第二个值 = hashes
          array[0] = mTwiceBaseCache;
          array[1] = hashes;
          //循环遍历,数组上剩余的数据赋值为null
          for (int i=(size<<1)-1; i>=2; i--) {
            array[i] = null;
          }
          //临时数据赋值给缓存数组
          mTwiceBaseCache = array;
          //缓存Size++
          mTwiceBaseCacheSize++;
          if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
              + " now have " + mTwiceBaseCacheSize + " entries");
        }
      }
    } else if (hashes.length == BASE_SIZE) {
      synchronized (ArrayMap.class) {
        if (mBaseCacheSize < CACHE_SIZE) {
          array[0] = mBaseCache;
          array[1] = hashes;
          for (int i=(size<<1)-1; i>=2; i--) {
            array[i] = null;
          }
          mBaseCache = array;
          mBaseCacheSize++;
          if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
              + " now have " + mBaseCacheSize + " entries");
        }
      }
    }
  }

扩容流程 :
  size == (BASE_SIZE*2) 和 size == BASE_SIZE 需要结合freeArrays()进行分析
缓存作用 :
  在数据量较小的时候快速的复用原来的数据,不需要使用System.Copy...()

ArrayMap源码 - put

  @Override
  public V put(K key, V value) {
    //获取当前数据的长度
    final int osize = mSize;
    //Key的Hash值
    final int hash;
    //Key的Index值
    int index;
    if (key == null) {//Key == null时
      hash = 0;
      //查找null的index值,具体逻辑可以参考get()部分,大部分逻辑相同
      //1.if mSize == 0,index = ~0
      //2.binarySearchHashes(mHashes, mSize, 0) 二分法查找数组中数据Index,Index<0,直接返回Index
      //3.if null == mArray[index<<1],通过Index查找Key-Value数组中的Value,Value==Null,直接返回Index
      //4.以Index为中心,mHashes的两边分开查找
        //mHashes[Index] == 0&&null == mArray[Index << 1],直接返回Index
      index = indexOfNull();
    } else {
      //生成Key的HashCode()值
      hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
      //查找Key HashCode()在mHashes的位置
      index = indexOf(key, hash);
    }
    //Index >=0 表示mHashes中存在这个数据,直接修改Key-Value数组中Value的值,并返回旧Value
    if (index >= 0) {
      index = (index<<1) + 1;
      final V old = (V)mArray[index];
      mArray[index] = value;
      return old;
    }

    //~index :  表示数据取反,例子:index = -11,~index = 10
    index = ~index;
    //当前数据的长度>=HashCode()数组长度
    if (osize >= mHashes.length) {
      //计算扩容大小,>=8 : 扩容为原来1.5倍,>=4 : 扩容为8,否则 : 扩容为4
      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);  
    }
    //如果index小于size长度,表示要在数组中间插入数据,此时需要移动数组数据(因为数据是有序排列)
    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;
  }

ArrayMap源码 - get

  @Override
  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());
  }
  //indexOf()和indexOfNull()的逻辑一样
  int indexOf(Object key, int hash) {
    // 获取当前数据的长度
    final int N = mSize;
    //长度==0,直接返回-1,~0 = -1
    if (N == 0) {
      return ~0;
    }
    //通过二分法查找mHashes数组中key的Hash的index
    int index = binarySearchHashes(mHashes, N, hash);
    //小于 0 表示mHashes数组中不存在这个Key
    if (index < 0) {
      return index;
    }
    // 如果在Key-Value数组中找到对应的Key,并相同,返回Index
    if (key.equals(mArray[index<<1])) {
      return index;
    }
    //此时的index!=0,index>0,表示在mHashes中发生了Key的hash碰撞
    //从碰撞的index开始,向后查找hash相同并且key相同的index值
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
      if (key.equals(mArray[end << 1])) return end;
    }
    //向前查找
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
      if (key.equals(mArray[i << 1])) return i;
    }
    //如果前后都没有找到,返回~end,end = index +1 ,~end = ~(index + 1)
    return ~end;
  }

ArrayMap源码 - remove

  @Override
  public V remove(Object key) {
      //这里查看get()部分
      final int index = indexOfKey(key);
      if (index >= 0) {
          return removeAt(index);
      }
      return null;
  }
  public V removeAt(int index) {
    //通过Key-Value数组获取Value 的值
    final Object old = mArray[(index << 1) + 1];
    //当前数据的长度
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
      // Now empty.
      if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
      //释放所有的数组数据
      freeArrays(mHashes, mArray, osize);
      mHashes = EmptyArray.INT;
      mArray = EmptyArray.OBJECT;
      nsize = 0;
    } else {
      //数据remove后数组的长度
      nsize = osize - 1;
      //如果mHashes长度 >=8 && mSize (实际数据长度) < mHashes.length/3 (3分之一)
      if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
        //准备缩小数组的长度,具体逻辑 :
        //假如当前osize = mSize = 10,那么 n = 15
        //在方法结束时 mSize = nsize = 9(刚才-1)
        //下次再次执行这里是osize = mSize = 9,那么 n = 13,所以在缩小
        final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

        if (DEBUG) Log.d(TAG, "remove: shrink 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 (index > 0) {
          if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
          System.arraycopy(ohashes, 0, mHashes, 0, index);
          System.arraycopy(oarray, 0, mArray, 0, index << 1);
        }
        if (index < nsize) {
          if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize
              + " to " + index);
          System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
          System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
              (nsize - index) << 1);
        }
      } else {
        //假如mSize = 10,nsize = 9,index < 9
        if (index < nsize) {
          if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize
              + " to " + index);
          //数据直接重新复制(把index后面的数据复制到前面来,数组中最后一个数据为Null)
          System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
          System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
              (nsize - index) << 1);
        }
        mArray[nsize << 1] = null;
        mArray[(nsize << 1) + 1] = null;
      }
    }
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
      throw new ConcurrentModificationException();
    }
    //重新赋值长度
    mSize = nsize;
    //返回旧Value
    return (V)old;
  }