Osheep

时光不回头,当下最重要。

源码的魅力 - ArrayMap的工作原理

ArrayMap的工作原理(Android 7.1源码)

简介

鉴于HashMap的内存使用率太低,而内存又是Android设备系统中极其宝贵的资源,所以Google开发出ArrayMap来一定条件下取代HashMap (几乎平时的开发都可以使用这个结构,而不用HashMap)。

初始化


    int[] mHashes;
    Object[] mArray;

   public ArrayMap(int capacity, boolean identityHashCode) {
       mIdentityHashCode = identityHashCode;

       if (capacity < 0) {
           mHashes = EMPTY_IMMUTABLE_INTS;
           mArray = EmptyArray.OBJECT;
       } else if (capacity == 0) {
           mHashes = EmptyArray.INT;
           mArray = EmptyArray.OBJECT;
       } else {
           allocArrays(capacity);
       }
       mSize = 0;
   }

ArrayMap的内部主要依靠mHashes以及mArray,构造函数中可以看出和HashMap一样一上来创建时并不会分配内存空间。此处的mhashes就是存放HashCode的数组,mArray时存放key与Value的数组。

put 方法

    @Override
    public V put(K key, V value) {
        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
            index = indexOf(key, hash);
        }
        if (index >= 0) {
            index = (index<<1) + 1;
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }

        index = ~index;
        if (mSize >= mHashes.length) {
            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);
            }

            freeArrays(ohashes, oarray, mSize);
        }

        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);
        }

        mHashes[index] = hash;
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;
        return null;
    }
  • 当key为空时直接通过indexOfNull获取
    index
  • 当key不为空时,hash = key.hashCode获取hash值,并且通过indexOf方法来获取位置(indexOf与indexOfNull将在下面详细分析)
  • 如果返回的index大于零,直接通过index = (index << 1)+ 1来获取到mArray数组的索引直接替换数据(由于mArray存放的数据是一个key然后一个Value形式的, index* 2就是key的位置,再加一就是value的位置)
  • 当没有找到key的位置时,返回的index是负数,通过取反来获取到新插入的位置。
  • 当mHash列表满了的时候,执行扩容方法allocArrays() allocArrays与下面的freeArrays方法将在后面进行分析
  • 将老数据分配到分配到新数组中。
  • 由于此时需要在index位置新插入数据,所以需要将mHashcodes以及mArray中的数据向右移动,在mHashcodes数组中腾出一个位置,mArray中腾出两个位置。
  • 将新数据插入,mSize自增
《源码的魅力 - ArrayMap的工作原理》

结构图

indexOf以及indexOfNull方法

由于indexOfNull其实就是hash参数为0的特殊版本,基本上是一样的所以就不赘述了。

  //获取索引值
  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.
      if (index < 0) {
          return index;
      }

      // If the key at the returned index matches, that's what we want.
      if (key.equals(mArray[index<<1])) {
          return index;
      }

      // Search for a matching key after the 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;
  }

  static int binarySearch(int[] array, int size, int value) {
        int lo = 0;
        int hi = size - 1;

        while (lo <= hi) {
            final int mid = (lo + hi) >>> 1;
            final int midVal = array[mid];

            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                return mid;  // value found
            }
        }
        return ~lo;  // value not present
    }
  • 当之前没有数据时,则返回0的取反值。
  • 通过二分法在ContainerHelpers.binarySearch()中查找数据
  • 在binarySearch函数当数值并没有的时候,会返回lo的取反值,这个lo此时指向的位置是Value插入的位置。(其实这个取反以及其他位置的取反就是整个ArrayMap中巧妙的地方之一,binarySearch通过返回取反值既做到了数据不存在时返回负数,又提供了数据新插入的位置,一举多得。
  • 当返回的index为负数时,直接返回索引值。
  • 如果key正好是在mArray的2*index的位置的数据,则直接返回index
  • 如果还是不对,则通过mHashs向下查找,如果存在相同的hash值,并且对应的key也相等则返回index值。
  • 反之则向下查找。
  • 如果还是没有找到,直接返回end(end 是 等于index + 1)的值取反值

总结:indexOf函数返回正数时是存在key值的mHashCodes数组的索引值,否则返回负值就是在mHashCode新插入位置的索引的取反值,再取反就可以得到插入的位置

allocArrays以及freeArrays函数


    private void allocArrays(final int size) {
        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCache != null) {
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    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;
                }
            }
        } 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;
                }
            }
        }

        mHashes = new int[size];
        mArray = new Object[size<<1];
    }

    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
                    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");
                }
            }
        }
    }

ArrayMap通过两个数组mTwiceBaseCache以及mBaseCache两个数组来提供缓存内存空间,但只有在数组大小是4与8时发挥作用。

final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
       : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

前面的put中扩展数组部分代码中,当小于4时扩展成4,小于8时扩展成8,否则增加一半的 mSize大小。
allocArrays与freeArrays在缓存部分是相对应的,作用是将原先的那部分内存空间保存住,不然垃圾回收器回收掉。

总结

ArrayMap在内存使用率上比HashMap高不少,但是插入速度在数据很多时会很慢,所以ArrayMap在数据量少时(千以内)比较适用,否则还是要使用HashMap。

点赞