Android ArrayMap源代码分析

      分析源码之前先来介绍一下arraymap的存储结构，arraymap数据的存储不同于hashmap和sparsearray。

　java提供了hashmap，但是hashmap对于手机端而言，对空间的利用太大，所以android提供了sparsearray和arraymap。二者都是基于二分查找，所以数据量大的时候，最坏效率会比hashmap慢很多。因此建议数量在千以内比较合适。

 一、sparsearray

　　sparsearray对应的key只能是int类型，它不会对key进行装箱操作。它使用了两个数组，一个保存key，一个保存value。

　　sparsearray使用二分查找来找到key对应的插入位置。所以要保证mkeys数组有序。

　　remove的时候不会立刻重新清理删除掉的数据，而是将对一个的数据标记为delete(一个object对象)。在必要的环节调用gc清理标记为delete的空间。

 二、arraymap

　　重点介绍一下arraymap。

　　首先从arraymap的四个数组说起。mhashes，用于保存key对应的hashcode；marray，用于保存键值对（key，value），其结构为[key1,value1,key2,value2,key3,value3,......]；mbasecache，缓存，如果arraymap的数据量从4，增加到8，用该数组保存之前使用的mhashes和marray，这样如果数据量再变回4的时候，可以再次使用之前的数组，不需要再次申请空间，这样节省了一定的时间；mtwicebasecache，与mbasecache对应，不过触发的条件是数据量从8增长到12。

 　　上面提到的数据量有8增长到12，为什么不是16？这也算是arraymap的一个优化的点，它不是每次增长1倍，而是使用了如下方法（msize+(msize>>1)），即每次增加1/2。

 　　有了上面的说明，读懂代码就容易多了。

　　1、很多地方用到的indexof

　　　　这里使用了二分查找来查找对应的index

int indexof(object key, int hash) {
    final int n = msize;

    // important fast case: if nothing is in here, nothing to look for.
    //数组为空，直接返回
    if (n == 0) {
      return ~0;
    }

    //二分查找，不细说了
    int index = containerhelpers.binarysearch(mhashes, n, hash);

    // if the hash code wasn't found, then we have no entry for this key.
    //没找到hashcode，返回index，一个负数
    if (index < 0) {
      return index;
    }

    // if the key at the returned index matches, that's what we want.
    //对比key值，相同则返回index
    if (key.equals(marray[index<<1])) {
      return index;
    }

    // search for a matching key after the index.
    //如果返回的index对应的key值，与传入的key值不等，则可能对应的key在index后面
    int end;
    for (end = index + 1; end < n && mhashes[end] == hash; end++) {
      if (key.equals(marray[end << 1])) return end;
    }

    // search for a matching key before the index.
    //接上句，后面没有，那一定在前面。
    for (int i = index - 1; i >= 0 && mhashes[i] == hash; i--) {
      if (key.equals(marray[i << 1])) return i;
    }

    // key not found -- return negative value indicating where a
    // new entry for this key should go. we use the end of the
    // hash chain to reduce the number of array entries that will
    // need to be copied when inserting.
    //毛都没找到，那肯定是没有了，返回个负数
    return ~end;
  }

 

　　2、看一下put方法

public v put(k key, v value) {
    final int hash;
    int index;
    //key是空，则通过indexofnull查找对应的index；如果不为空，通过indexof查找对应的index
    if (key == null) {
      hash = 0;
      index = indexofnull();
    } else {
      hash = key.hashcode();
      index = indexof(key, hash);
    }
    
    //index大于或等于0，一定是之前put过相同的key，直接替换对应的value。因为marray中不只保存了value，还保存了key。
    //其结构为[key1,value1,key2,value2,key3,value3,......]
    //所以，需要将index乘2对应key，index乘2再加1对应value
    if (index >= 0) {
      index = (index<<1) + 1;
      final v old = (v)marray[index];
      marray[index] = value;
      return old;
    }

    //取正数
    index = ~index;
    //msize的大小，即已经保存的数据量与mhashes的长度相同了，需要扩容啦
    if (msize >= mhashes.length) {
      //扩容后的大小，有以下几个档位，base_size（4），base_size的2倍（8），msize+(msize>>1)（比之前的数据量扩容1/2）
      final int n = msize >= (base_size*2) ? (msize+(msize>>1))
          : (msize >= 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 (mhashes.length > 0) {
        if (debug) log.d(tag, "put: copy 0-" + msize + " to 0");
        system.arraycopy(ohashes, 0, mhashes, 0, ohashes.length);
        system.arraycopy(oarray, 0, marray, 0, oarray.length);
      }

      //看看被废弃的数组是否还有利用价值
      //如果被废弃的数组的数据量为4或8，说明可能利用价值，以后用到的时候可以直接用。
      //如果被废弃的数据量太大，扔了算了，要不太占内存。如果浪费内存了，还费这么大劲，加了类干啥。
      freearrays(ohashes, oarray, msize);
    }

    //这次put的key对应的hashcode排序没有排在最后（index没有指示到数组结尾），因此需要移动index后面的数据
    if (index < msize) {
      if (debug) log.d(tag, "put: move " + index + "-" + (msize-index)
          + " to " + (index+1));
      system.arraycopy(mhashes, index, mhashes, index + 1, msize - index);
      system.arraycopy(marray, index << 1, marray, (index + 1) << 1, (msize - index) << 1);
    }

    //把数据保存到数组中。看到了吧，key和value都在marray中；hashcode放到mhashes
    mhashes[index] = hash;
    marray[index<<1] = key;
    marray[(index<<1)+1] = value;
    msize++;
    return null;
  }

　　　　3、remove方法

　　remove方法在某种条件下，会重新分配内存，保证分配给arraymap的内存在合理区间，减少对内存的占用。但是从这里也可以看出，android使用的是用时间换空间的方式。无论从任何角度，频繁的分配回收内存一定会耗费时间的。

　　remove最终使用的是removeat方法，此处只说明removeat

 /**
   * remove the key/value mapping at the given index.
   * @param index the desired index, must be between 0 and {@link #size()}-1.
   * @return returns the value that was stored at this index.
   */
  public v removeat(int index) {
    final object old = marray[(index << 1) + 1];
    //如果数据量小于等于1，说明删除该元素后，没有数组为空，清空两个数组。
    if (msize <= 1) {
      // now empty.
      if (debug) log.d(tag, "remove: shrink from " + mhashes.length + " to 0");
      //put中已有说明
      freearrays(mhashes, marray, msize);
      mhashes = emptyarray.int;
      marray = emptyarray.object;
      msize = 0;
    } else {
      //如果当初申请的数组最大容纳数据个数大于base_size的2倍（8），并且现在存储的数据量只用了申请数量的1/3，
      //则需要重新分配空间，已减少对内存的占用
      if (mhashes.length > (base_size*2) && msize < mhashes.length/3) {
        // shrunk enough to reduce size of arrays. we don't allow it to
        // shrink smaller than (base_size*2) to avoid flapping between
        // that and base_size.
        //新数组的大小
        final int n = msize > (base_size*2) ? (msize + (msize>>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);

        msize--;
        //index之前的数据拷贝到新数组中
        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);
        }
        //将index之后的数据拷贝到新数组中，和（index>0）的分支结合，就将index位置的数据删除了
        if (index < msize) {
          if (debug) log.d(tag, "remove: copy from " + (index+1) + "-" + msize
              + " to " + index);
          system.arraycopy(ohashes, index + 1, mhashes, index, msize - index);
          system.arraycopy(oarray, (index + 1) << 1, marray, index << 1,
              (msize - index) << 1);
        }
      } else {
        msize--;
        //将index后的数据向前移位
        if (index < msize) {
          if (debug) log.d(tag, "remove: move " + (index+1) + "-" + msize
              + " to " + index);
          system.arraycopy(mhashes, index + 1, mhashes, index, msize - index);
          system.arraycopy(marray, (index + 1) << 1, marray, index << 1,
              (msize - index) << 1);
        }
        //移位后最后一个数据清空
        marray[msize << 1] = null;
        marray[(msize << 1) + 1] = null;
      }
    }
    return (v)old;
  }

　　4、freearrays

　　　　put中有说明，这里就不进行概述了，直接上代码，印证上面的说法。

　　private static void freearrays(final int[] hashes, final object[] array, final int size) {
    //已经废弃的数组个数为base_size的2倍（8），则用mtwicebasecache保存废弃的数组；
    //如果个数为base_size（4），则用mbasecache保存废弃的数组
    if (hashes.length == (base_size*2)) {
      synchronized (arraymap.class) {
        if (mtwicebasecachesize < cache_size) {
          //array为刚刚废弃的数组，mtwicebasecache如果有内容，则放入array[0]位置，
          //在allocarrays中会从array[0]取出，放回mtwicebasecache
          array[0] = mtwicebasecache;
          //array[1]存放hash数组。因为array中每个元素都是object对象，所以每个元素都可以存放数组
          array[1] = hashes;
          //清除index为2和之后的数据
          for (int i=(size<<1)-1; i>=2; i--) {
            array[i] = null;
          }
          mtwicebasecache = array;
          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");
        }
      }
    }
  }

　　5、allocarrays

　　　　算了，感觉没啥好说的，看懂了freearrays，allocarrays自然就理解了。

　　　　总体来说，通过新数组的个数产生3个分支，个数为base_size（4），从mbasecache取之前废弃的数组；base_size的2倍（8），从mtwicebasecache取之前废弃的数组；其他，之前废弃的数组没有存储，因为太耗费内存，这种情况下，重新分配内存。

　　6、clear和erase

　　　　clear清空数组，如果再向数组中添加元素，需要重新申请空间；erase清除数组中的数组，空间还在。

　　7、get

　　　　主要的逻辑都在indexof中了，剩下的代码不需要分析了，看了的都说懂（窃笑）。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！