精华内容
下载资源
问答
  • ArrayMap

    千次阅读 2017-02-12 22:35:19
    数据集合在任何一门编程语言中都是很重要的一... 而Android中引入了一个新的集合,叫做ArrayMap,为键值对存储需求增加了一种选择。ArrayMap是什么一个通用的key-value映射数据结构 相比HashMap会占用更少的内存空间

    数据集合在任何一门编程语言中都是很重要的一部分,在 Android 开发中,我们会实用到ArrayList, LinkedList, HashMap等。其中HashMap是用来处理键值对需求的常用集合。 而Android中引入了一个新的集合,叫做ArrayMap,为键值对存储需求增加了一种选择。

    ArrayMap是什么

    一个通用的key-value映射数据结构
    相比HashMap会占用更少的内存空间
    android.util和android.support.v4.util都包含对应的ArrayMap类
    ArrayMap的内部结构

    ArrayMap internal strucuture

    如上图所示,在ArrayMap内部有两个比较重要的数组,一个是mHashes,另一个是mArray。

    mHashes用来存放key的hashcode值
    mArray用来存储key与value的值,它是一个Object数组。
    其中这两个数组的索引对应关系是

    1
    2
    3
    mHashes[index] = hash;
    mArray[index<<1] = key; //等同于 mArray[index * 2] = key;
    mArray[(index<<1)+1] = value; //等同于 mArray[index * 2 + 1] = value;
    注:向左移一位的效率要比 乘以2倍 高一些。

    查找数据

    查找数据是容器常用的操作,在Map中,通常是根据key找到对应的value的值。

    ArrayMap中的查找分为如下两步

    根据key的hashcode找到在mHashes数组中的索引值
    根据上一步的索引值去查找key所对应的value值
    其中占据时间复杂度最多的属于第一步:确定key的hashCode在mHahses中的索引值。

    而这一步对mHashes查找使用的是二分查找,即Binary Search。所以ArrayMap的查询时间复杂度为 ‎O(log n)

    确定key的hashcode在mHashes中的索引的代码的逻辑

    int indexOf(Object key, int hash) {
        final int N = mSize;
        //快速判断是ArrayMap是否为空,如果符合情况快速跳出
        if (N == 0) {
            return ~0;
        }
        //二分查找确定索引值
        int index = ContainerHelpers.binarySearch(mHashes, N, hash);
    
        // 如果未找到,返回一个index值,可能为后续可能的插入数据使用。
        if (index < 0) {
            return index;
        }
    
        // 如果确定不仅hashcode相同,也是同一个key,返回找到的索引值。
        if (key.equals(mArray[index<<1])) {
            return index;
        }
    
        // 如果key的hashcode相同,但不是同一对象,从索引之后再次找
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            if (key.equals(mArray[end << 1])) return end;
        }
    
        // 如果key的hashcode相同,但不是同一对象,从索引之前再次找
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            if (key.equals(mArray[i << 1])) return i;
        }
        //返回负值,既可以用来表示无法找到匹配的key,也可以用来为后续的插入数据所用。
        // 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;
    }

    既然对mHashes进行二分查找,则mHashes必须为有序数组。

    插入数据

    ArrayMap提供给我们进行插入数据的API有

    append(key,value)
    put(key,value)
    putAll(collection)
    以put方法为例,需要注意的有

    新数据位置确定
    key为null
    数组扩容问题
    新数据位置确定

    为了确保mHashes能够进行二分查找,我们需要保证mHashes始终未有序数组。

    在确定新数据位置过程中

    根据key的hashcode在mHashes表中二分查找确定合适的位置。
    如果新添加的数据的索引不是最后位置,在需要对这个索引之后的全部数据向后移动
    ArrayMap put

    key为null时

    当key为null时,其实和其他正常的key差不多,只是对应的hashcode会默认成0来处理。

    public V put(K key, V value) {
        final int hash;
        int index;
        if (key == null) {
            hash = 0;//如果key为null,其hashcode算作0
            index = indexOfNull();
        }
      ...
    }

    数组扩容问题

    首先数组的容量会扩充到BASE_SIZE
    如果BASE_SIZE无法容纳,则扩大到2 * BASE_SIZE
    如果2 * BASE_SIZE仍然无法容纳,则每次扩容为当前容量的1.5倍。
    具体的计算容量的代码为

    /**
     * The minimum amount by which the capacity of a ArrayMap will increase.
     * This is tuned to be relatively space-efficient.
    */
    private static final int BASE_SIZE = 4;
    final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
      : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

    删除数据

    删除ArrayMap中的一项数据,可以分为如下的情况

    如果当前ArrayMap只有一项数据,则删除操作将mHashes,mArray置为空数组,mSize置为0.
    如果当前ArrayMap容量过大(大于BASE_SIZE*2)并且持有的数据量过小(不足1/3)则降低ArrayMap容量,减少内存占用
    如果不符合上面的情况,则从mHashes删除对应的值,将mArray中对应的索引置为null
    ArrayMap的缓存优化

    ArrayMap的容量发生变化,正如前面介绍的,有这两种情况

    put方法增加数据,扩大容量
    remove方法删除数据,减小容量
    在这个过程中,会频繁出现多个容量为BASE_SIZE和2 * BASE_SIZE的int数组和Object数组。ArrayMap设计者为了避免创建不必要的对象,减少GC的压力。采用了类似对象池的优化设计。

    这其中设计到几个元素

    BASE_SIZE 值为4,与ArrayMap容量有密切关系。
    mBaseCache 用来缓存容量为BASE_SIZE的int数组和Object数组
    mBaseCacheSize mBaseCache缓存的数量,避免无限缓存
    mTwiceBaseCache 用来缓存容量为 BASE_SIZE * 2的int数组和Object数组
    mTwiceBaseCacheSize mTwiceBaseCache缓存的数量,避免无限缓存
    CACHE_SIZE 值为10,用来控制mBaseCache与mTwiceBaseCache缓存的大小
    这其中

    mBaseCache的第一个元素保存下一个mBaseCache,第二个元素保存mHashes数组
    mTwiceBaseCache和mBaseCache一样,只是对应的数组容量不同
    具体的缓存数组逻辑的代码为

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

    具体的利用缓存数组的代码为

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

    在Android中的应用

    在Android Performance Pattern中,官方给出的使用场景为

    1.item数量小于1000,尤其是插入数据和删除数据不频繁的情况。

    2.Map中包含子Map对象

    展开全文
  • android 详解ArrayMap

    2020-12-04 11:30:56
    今天简单研究一下 ArrayMapArrayMap ArrayMap 是一种相较于 HashMap 具有更高内存效率的 key-value 对存储结构;ArrayMap 内部包括两个数组结构,分别是专门用来存储 HashCode 的 mHashes 和用来存储 key-value ...

    今天简单研究一下 ArrayMap;
    ArrayMap
    ArrayMap 是一种相较于 HashMap 具有更高内存效率的 key-value 对存储结构;ArrayMap 内部包括两个数组结构,分别是专门用来存储 HashCode 的 mHashes 和用来存储 key-value 的 Object 数组类型的 mArray;
    ArrayMap 是非线程安全的;

    源码分析
    构造函数
    public ArrayMap() {
    this(0, false);
    }

    public ArrayMap(int capacity) {
    this(capacity, false);
    }

    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 提供了三种构造方法,分别为无参的默认构造函数,添加默认容积的构造函数和一个隐藏的构造函数;若指定容积大小则直接分配相应大小的内存;若是默认构造函数,默认为 0,会在添加数据时动态扩容;

    元素查询
    int indexOf(Object key, int hash) {
    final int N = mSize;
    // ====== TAG 01 ======
    int index = binarySearchHashes(mHashes, N, hash);
    if (index < 0) {
    return index;
    }
    if (key.equals(mArray[index<<1])) {
    return index;
    }
    // ====== TAG 02 ======
    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;
    }
    return ~end;
    }
    ArrayMap 查找元素主要是通过 binarySearchHashes 二分查找方式来查找 index;若 HashCode 和 Key 均匹配则为要查找的 index;若只有 HashCode 相同但对象不同(即 HashCode 冲突),则从当前对应的 index 向后和向前分别遍历查找;注意:采用二分查找,则说明 mHashes 数组是有序的;

    元素添加
    ArrayMap 添加元素的方式主要有 put 和 append 方式;

    1. put()
      public V put(K key, V value) {
      final int osize = mSize;
      final int hash;
      int index;
      if (key == null) {
      hash = 0;
      index = indexOfNull();
      } else {
      hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
      // ====== TAG 01 ======
      index = indexOf(key, hash);
      }
      if (index >= 0) {
      // ====== TAG 02 ======
      index = (index<<1) + 1;
      final V old = (V)mArray[index];
      mArray[index] = value;
      return old;
      }
      // ====== TAG 03 ======
      index = ~index;
      if (osize >= mHashes.length) {
      final int n = osize >= (BASE_SIZE2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE2) : BASE_SIZE);
      final int[] ohashes = mHashes;
      final Object[] oarray = mArray;
      // ====== TAG 04 ======
      allocArrays(n);
      if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
      throw new ConcurrentModificationException();
      }
      // ====== TAG 05 ======
      if (mHashes.length > 0) {
      System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
      System.arraycopy(oarray, 0, mArray, 0, oarray.length);
      }
      freeArrays(ohashes, oarray, osize);
      }
      // ====== TAG 06 ======
      if (index < osize) {
      System.arraycopy(mHashes, index, mHashes, index + 1, osize - 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;
      }

    TAG 01: 主要用于二分查找的方式,在 mHashes 数组中查找 HashCode 值相等的 Key;
    TAG 02: 在 index > 0 即有对应 HashCode 相等的 Key 之后,更新其 Value 值;通过 index << 1 左移的方式相当于 index * 2 只是效率更高效,可多在实际项目中应用;
    TAG 03: 在 index < 0 即没有对应 HashCode 相等的 Key,此时需要插入新数据;
    TAG 04: 当需要扩容时,可采用 allocArrays() 方式分配更大的内存空间;且 ArrayMap 是非线程安全的,不可并行;
    TAG 05: 通过 System.arraycopy 将老的数组数据拷贝到新的数组中,再通过 freeArrays() 释放老的数组内存;
    TAG 06: 当需要插入的元素不在末尾时,拷贝完数据之后需要将 index 后移一位;
    2. append()
    public void append(K key, V value) {
    int index = mSize;
    final int hash = key == null ? 0 : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
    if (index >= mHashes.length) {
    throw new IllegalStateException(“Array is full”);
    }
    if (index > 0 && mHashes[index-1] > hash) {
    RuntimeException e = new RuntimeException(“here”);
    e.fillInStackTrace();
    // ====== TAG ======
    put(key, value);
    return;
    }
    mSize = index+1;
    mHashes[index] = hash;
    index <<= 1;
    mArray[index] = key;
    mArray[index+1] = value;
    }
    简单查看 append() 源码,与 put() 相比少了扩容和内存回收等步骤;其两者使用场景不同,append() 无需验证即可将元素追加到数组末尾的特殊快速路径,要求是数组必须足够大;当数据需要插入到数组中间时调用 put() 方式;

    元素删除
    public V remove(Object key) {
    final int index = indexOfKey(key);
    if (index >= 0) {
    return removeAt(index);
    }
    return null;
    }
    ArrayMap 可以通过 remove() 来删除固定元素;首先通过 indexOfKey 二分查找是否有对应要删除的元素,如果有通过 removeAt() 进行删除;

    public V removeAt(int index) {
    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    // ====== TAG 01 ======
    if (osize <= 1) {
    final int[] ohashes = mHashes;
    final Object[] oarray = mArray;
    mHashes = EmptyArray.INT;
    mArray = EmptyArray.OBJECT;
    freeArrays(ohashes, oarray, osize);
    nsize = 0;
    } else {
    nsize = osize - 1;
    // ====== TAG 02 ======
    if (mHashes.length > (BASE_SIZE2) && mSize < mHashes.length/3) {
    final int n = osize > (BASE_SIZE
    2) ? (osize + (osize>>1)) : (BASE_SIZE*2);
    final int[] ohashes = mHashes;
    final Object[] oarray = mArray;
    allocArrays(n);

            if (index > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            if (index < nsize) {
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1);
            }
        } else {
            // ====== TAG 03 ======
            if (index < nsize) {
                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;
        }
    }
    mSize = nsize;
    return (V)old;
    

    }
    TAG 01: 当数组只有一个要删除的元素时,直接将 mHashes 和 mArray 置空并通过 freeArrays 释放内存即可;
    TAG 02: 当数组内存大小大于 8 并且元素数量少于 1/3 空间大小时,通过 allocArrays 进行减少内存分配,将老数据拷贝到新的数组中,并清空老数据数组空间;这是 HashMap 不曾实现的;
    TAG 03: 当删除其中一个元素时,需要将该元素之后的所有元素向前移动一位;
    数组扩容
    HashMap 直接以容积的 2 倍进行扩容,而 ArrayMap 数组扩容是分阶段扩容的;与基础数组长度有关;

    final int n = osize >= (BASE_SIZE2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE2) : BASE_SIZE);
    当 osize >= 8 时,数组扩容为原来的 1.5 倍;其中 osize >> 1 相当于 osize / 2;
    当 4 <= osize < 8 时,此时扩展为 8;
    当 osize < 4 时,此时扩展为 4;
    内存机制
    // ArrayMap 扩容的最小容积(用于调整为相对节省空间方式)
    private static final int BASE_SIZE = 4;
    // 最大缓存数组数
    private static final int CACHE_SIZE = 10;
    // 用来缓存 BASE_SIZE = 4 的数组内容
    static Object[] mBaseCache;
    // mBaseCache 缓存的数量
    static int mBaseCacheSize;
    // 用来存储 BASE_SIZE * 2 = 8 的数组内容
    static Object[] mTwiceBaseCache;
    // mTwiceBaseCache 缓存的数量
    static int mTwiceBaseCacheSize;
    ArrayMap 为了避免频繁的创建和销毁,提供了 mBaseCache 和 mTwiceBaseCache 两个数组缓冲池,同时提供了 allocArrays 和 freeArrays 内存分配和释放的方法,两者相互对应,都通过缓冲池分配和释放内存;

    private void allocArrays(final int size) {
    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–;
    return;
    }
    }
    } else if (size == BASE_SIZE) {

    }
    mHashes = new int[size];
    mArray = new Object[size<<1];
    }
    当需要分配内存大小为 BASE_SIZE 或 BASE_SIZE * 2 时,会先查看对应的缓存池中取出 mArray 和 mHashes;其方式是先将缓存池指向上一条缓存地址,将缓存池的第 array[1] 个元素赋值为 mHashes ,再把 mArray 的第 array[0] 和第 array[1] 个位置的数据置为 null;

    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++;
    }
    }
    } else if (hashes.length == BASE_SIZE) {

    }
    }
    当内存需要释放时,释放大小为 BASE_SIZE 或 BASE_SIZE * 2 时,会将数组加入到缓冲池中;其方she式是先将原缓冲池和哈希数组分别指向 array 前两位,之后的元素全部置空,最后将缓存池的头部指向最新的数组位置;

    注意事项
    ArrayMap 不适合大量的数据结构,Google 建议在 1000 以内的数据量比较好;ArrayMap 内部采用了二分查找方式查询,时间复杂度 O(logN),每次添加和删除元素都需要移动其后面的元素,速度相对较慢;而 HashMap 查找和删除时间复杂度为 O(1);

      ArrayMap 相对于 HashMap 增加了内存缓存策略,避免频繁创建对象而分配内存与 GC 操作,同时限制了缓冲池的上限(10 个);与此同时,ArrayMap 还提供了灵活的扩容和缩容机制,这两种机制比 HashMap 更灵活且节省时间;
    
      ArrayMap 还解决了 HashMap 稀疏数组的问题,相对占用内存更少;
    

    案例尝试
    ArrayMap map01 = new ArrayMap();
    ArrayMap map02 = new ArrayMap(4);
    // 元素添加
    for (int i = 0;i < 6;i ++) {
    map01.put(“index_”+(i+1), “map01.value_”+(i +1));
    map02.put(“index_”+(i+1), “map02.value_”+(i +1));
    }
    for(int i = 0 ;i < map01.size();i ++){
    Log.e(“ArrayMap 01 -->”, map01.get(“index_”+(i+1)).toString()+“HashCode”+map01.get(“index_”+(i+1)).hashCode());
    }
    for(int i = 0 ;i < map02.size();i ++){
    Log.e(“ArrayMap 02 -->”, map02.get(“index_”+(i+1)).toString()+“HashCode”+map02.get(“index_”+(i+1)).hashCode());
    }
    // 元素删除
    map01.remove(“index_3”);
    // 元素修改
    map01.put(“index_4”, “map01.value_4 changed!”);
    map02.remove(“index_1”);
    map02.remove(“index_2”);
    for(int i = 0 ;i < map01.size();i ++){
    if (map01.get(“index_”+(i+1)) != null) {
    Log.e(“ArrayMap 01 -->”, map01.get(“index_” + (i + 1)).toString() + “HashCode” + map01.get(“index_” + (i + 1)).hashCode());
    }
    }
    for(int i = 0 ;i < map02.size();i ++){
    if (map02.get(“index_”+(i+1)) != null) {
    Log.e(“ArrayMap 02 -->”, map02.get(“index_” + (i + 1)).toString() + “HashCode” + map02.get(“index_” + (i + 1)).hashCode());
    }
    }

    查看更多

    展开全文
  • ArrayMap详解

    2018-04-09 11:16:34
    首先说下为什么要用ArrayMap.java中的hashmap在初始化对象的时候便会分配16个大小的数组作为默认数组,无论你何时使用,若一个app中有特别多的hashmap用来存储少量数据的时候,就会造成特别多的内存浪费。...
    首先说下为什么要用ArrayMap.java中的hashmap在初始化对象的时候便会分配16个大小的数组作为默认数组,无论你何时使用,若一个app中有特别多的hashmap用来存储少量数据的时候,就会造成特别多的内存浪费。因此出于此原因,google推出了ArrayMap这一数据结构作为移动端的用来存储键值对的轻量级的数据机构。首先我们在new对象的时候,并不会立即去申请存储空间除非你自己制定初始化空间。这样就能够在我们初始化了map之后并未使用时为系统节省空间。ArrayMap的第一次初始化是在我们往map中存放东西的时候,向系统申请一个BASE_SIZE个大小的数组也就是4个大小的数组。在这个类中存在一个10个数组的缓存池,当缓存池中有缓存时。在申请的时候会根据申请的大小,由这个缓存池中提取数组。ArrayMap中他有两个数组用来存储信息。一个用来存储key的hash值,另外一个用来存储键和值。存储键和值的数组大小始终为存储Key的hash值的两倍。put的时候先会采用二分法查找这个值的hash值的位置,如果找到的话就返回此hash值在数组中的下标,如果没找到就会返回此hash值应该存在的下标。然后根据返回值将键值对存入。伴随着存入元素的越来越多,当超过4个元素的时候,便会进行扩容操作。扩容的时候若扩容前的数组是4或者8个元素的时候,则在扩容的时候会将原数组进行回收,放进缓冲池中,具体的操作是将之前的缓存池放入到待回收数组的0号位置,将hash数组放到数组的一号位置,并将1号位置后的元素全部置空方便虚拟机GC,然后将这个数组置成缓存数组,完成回收对象的操作。这样便能够很好的利用对象的生命周期,避免不必要的GC,以及性能开销。
    展开全文
  • 分析源码之前先来介绍一下ArrayMap的存储结构,ArrayMap数据的存储不同于HashMap和SparseArray。  Java提供了HashMap,但是HashMap对于手机端而言,对空间的利用太大,所以Android提供了SparseArray和ArrayMap。...
  • ArrayMap和SpareseArray

    千次阅读 2018-05-22 14:30:25
    一,基本使用 ... arrayMap = new ArrayMap(); //要求版本19以上 arrayMap.put("1",null); arrayMap.put(null,"2"); arrayMap.put(null,"3"); 二,概念介绍 public final class Arra...

       

    一,基本使用     

     

    Map<String,String> arrayMap = new ArrayMap(); //要求版本19以上
    arrayMap.put("1",null);
    arrayMap.put(null,"2");
    arrayMap.put(null,"3");

     

    二,概念介绍

     

             ArrayMap是一个<key,value>映射的数据结构,它设计上更多的是考虑内存的优化,内部是使用两个数组进行数据存储,一个数组记录key的hash值,另外一个数组记录Value值,它和SparseArray一样,也会对key使用二分法进行从小到大排序

     

    public final class ArrayMap<K, V> implements Map<K, V> {

             1,ArrayMap是一个关联数组,哈希表,线程不安全,效率高.允许null键null值.

             2,效率相对比HashMap高,内部基于两个数组,一个int[],用于保存每个item的hashcode,一个object[]数组,用于保存key/value键值对.容量上市上一个数组的2倍.

            3,但不适合大容量的数据存储,存储大数据时,性能将退化至少50%.

            4,它可以避免在将数据插入Map集合中额外的空间消耗,并且它扩容更合适,扩容时,只需要拷贝数组,不需要重建哈希表.

            5,扩容规则:如果容量大于8,则扩容一半,(类似于ArrayList)

            6,如果出现了hash冲突,则需要从目标点向两头遍历,找到正确的index.

     

          总结:适用于存储数据量不大的时候

     

    三,SpareseArray

     

    SparseArray简介:

    1,SparseArray比HashMap更省内存,

    在某些条件下性能更好,主要是因为它避免了对key的自动装箱(int转为Integer类型),它内部则是通过两个数组来进行数据存储的,一个存储key,另外一个存储value,为了优化性能,它内部对数据还采取了压缩的方式来表示稀疏数组的数据,从而节约内存空。

     

     

    2,SparseArray只能存储key为int类型的数据

     

    3,SparseArray在存储和读取数据时候,使用的是二分查找法。

    put添加数据的时候,会使用二分查找法和之前的key比较当前我们添加的元素的key的大小,然后按照从小到大的顺序排列好,所以,SparseArray存储的元素都是按元素的key值从小到大排列好的。

     

    4,总结:

    虽说SparseArray性能比较好,但是由于其添加、查找、删除数据都需要先进行一次二分查找,所以在数据量大的情况下性能并不明显,将降低至少50%。

     

         它和ArrayMap基本相似,但SpareseArray只允许null值,并且在性能上做了优化.比如在删除操作上:

           当删除一个元素时,并不是立即从value数组中删除,并压缩数组;而是将其在value数组中标记为已删除.这样当储存相同的key为value时,可以重用空间.如果该空间没有被重用随后将在合适的时机里执行gc(垃圾回收)操作,将数组压缩,以免浪费空间.

     

    SparseArray<String> sparseArray = new SparseArray<>();
    sparseArray.put(1,null);
    sparseArray.put(2,"测试");
    //Android的SDK中,还提供了三个类似思想的集合:
    SparseBooleanArray sparseBooleanArray = new SparseBooleanArray();
    SparseIntArray sparseIntArray = new SparseIntArray();
    SparseLongArray sparseLongArray = new SparseLongArray(); //要求版本api18以上
    //他们和SparseArray唯一的区别在于value的类型,SparseArray的value可以是任意类型,.
    //而它们三个是拆箱后的基本类型

    四、SparseArray和ArrayMap都差不多,使用哪个呢? 

    假设数据量都在千级以内的情况下:

    1、如果key的类型已经确定为int类型,那么使用SparseArray,因为它避免了自动装箱的过程,如果key为long类型,它还提供了一个LongSparseArray来确保key为long类型时的使用

     

    2、如果key类型为其它的类型,则使用ArrayMap

     

    3,SparseArray相比ArrayMap进一步优化空间提高性能。

    SparseArray的目的是专门针对基本类型做优化,Key只能是可排序的基本类型,比如int型key的SparseArray,long型key的LongSparseArray,对于Value,除了泛型Value,对每种基本类型都有单独的实现,比如SparseBooleanArray,SparseLongArray等等。

    五、ArrayMap和HashMap区别

    1, 扩容

    这个是ArrayMap优于HashMap的地方。

    HashMap的下标位置是和数组容量相关的,带来一个问题,每次数组容量改变都需要重新计算所有键值对的下标,也就是rehash。而ArrayMap则没有这个问题,只需要创建一个更大的数组,用System.arrayCopy把元素复制过去。

     

    2,空间

    ArrayMap相对于HashMap,无需为每个键值对创建Node对象,并且在数组中连续存放,这就是为什么ArrayMap相对HashMap要节省空间。

     

    3,选择

    HashMap在元素非常多时性能要高于ArrayMap。 ArrayMap适合数量不多、对内存敏感、频繁扩容的地方,而在元素比较多时HashMap更优

     

     

     

    展开全文
  • ArrayMap源码分析

    2019-12-05 17:09:04
    ArrayMap源码分析-待处理
  • ArrayMap 源码分析

    2019-12-19 19:43:15
    ArrayMap 是 Android 的 API,它和 Java 的 HashMap 相比,虽然在查找效率上不如 HashMap(HashMap 查找的时间复杂度是 O(1), ArrayMap 查找的时间复杂度是 O(logn)),但是 ArrayMap 的空间消耗更小,它内部使用...
  • ArrayMap 笔记整理

    千次阅读 2019-05-04 22:24:55
    主要参考文章:面试必备:ArrayMap源码解析 1、概述 截图自:面试必备:ArrayMap源码解析 在开始讲解源码之前,需要说明 ArrayMap 的底层实现结构,即两个数组: int[] mHashes; // 用于存储 key 对应的 hash 值 ...
  • ArrayMap数据结构分析

    千次阅读 2019-12-29 12:01:18
    ArrayMap是Android上特有的一个性能比较高的Map,和HashMap一样,也实现了Map接口。 这里只分析其数据结构部分,不分析其高效缓存部分。 分析 ArrayMap的结构是int[] mHashes,记录每个key的hash值;Object[] mArray...
  • ArrayMap和SparseArray

    2020-11-01 18:49:56
    ArrayMap 存放key-value键值对,key可以是多种类型 实现原理 存储结构,两个数组存储,一个存key的hash,一个存key和value mHashes[],递增有序数组 mArray[],一个key对象mArray里面2个位置,保持key和value ArrayMap...
  • ArrayMap与HashMap

    2019-09-18 20:51:57
    ArrayMap是用两个数组进行数据存储。ArrayList是一个数组和链表进行数据的存储。 1. 设计目的 ArrayMap是一个用于存储“key/value”的数据结构,用于在某些场景下代替HashMap。相比HashMap,ArrayMap更加节省内存...
  • ArrayMap源码注释

    2020-07-18 18:23:30
    ArrayMap源码详解 本文的分析基于Android SDK 6.0源码进行,通过对ArrapMap的源码的分析,了解它的使用和特点。代码中保留了原有的英文注释,并增加了自己学习过程中添加的中文注释。 package android.util; import...
  • ArrayMAP介绍

    2016-06-07 23:11:15
    它不是一个适应大数据的数据结构,相比传统的HashMap速度要慢,因为查找方法是二分法,并且当你删除或者...ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient
  • HashMap/ArrayMap

    2017-08-15 10:05:18
    ArrayMap ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional HashMap, this implementation is a version of the platform's ArrayMap
  • HashMap与ArrayMap

    2018-12-07 14:40:34
    HashMap与ArrayMap HashMap创建就会分配内存空间,其扩容方式简单粗暴,在android中比较耗费内存。 ArrayMap存储方式使用两个数组,key的hash值,和keyvalue数组,扩容方式逐渐增加,节省内存。 HashMap查找,使用...
  • Android优化之ArrayMap

    千次阅读 2016-09-11 15:53:06
    ArrayMap的介绍 官方对ArrayMap也有说明:它不是一个适应大数据的数据结构,相比传统的HashMap速度要慢,因为查找方法是二分法,并且当你删除或者添加数据时,会对空间重新调整,在使用大量数据时,效率并不明显,...
  • 你 #WindowHelper类中的 ArrayMap 最好用android.support.v4.util.ArrayMap下的,不要用android.util.ArrayMap下的,不然有api 19下的会有问题!!!</p><p>该提问来源于开源项目&#...
  • 参考: ArrayMap完全剖析 面试必备:ArrayMap源码解析 ArrayMap详解及源码分析
  • HashMap和ArrayMap对比

    2020-06-08 18:18:00
    HashMap和ArrayMap各自的优势 1.查找效率: HashMap因为其根据hashcode的值直接算出index,所以其查找效率是随着数组长度增大而增加的。 ArrayMap使用的是二分法查找,所以当数组长度每增加一倍时,就需要多进行一次判断...
  • 深入分析ArrayMap

    2016-12-18 17:21:29
    Android也提供了一个key不用局限于int的Map的实现,ArrayMap。老规矩我们通过调试来深入的分析一下ArrayMap(看本文章需要知道SparseArray的原理,可以参考我前面写的深入分析SparseArray文章)。 And
  • android的ArrayMap

    2017-12-16 18:05:44
    java.lang.NoClassDefFoundError: android.util.ArrayMap http://stackoverflow.com/questions/24574323/crash-with-android-4-1-with-arraymap 找到的答案: ArrayMap was introduced in Api le
  • SparseArray、ArrayMap 实现原理学习

    千次阅读 2017-08-16 19:33:26
    SparseArray、ArrayMap 实现原理学习 SparseArray源码来自:android-25/java/util/SparseArray ArrayMap源码来自:25.3.1/support-compat-25.3.1/android/android.support.v4.util.ArrayMap 一、SparseArray...
  • JAVA基础 - ArrayMap

    2020-02-17 15:01:01
    ArrayMap mIdentityHashCode 优势: 1. 相比 hashMap 不会重建 hash映射,不会创建额外的对象。 2. 删除时 缩小存储当前数组 劣势: 1. 不合适大量数据,效率比hashmap 低。 ...
  • SparseArray和ArrayMap

    2017-04-01 09:26:55
    1、如果key的类型已经确定为int类型,那么使用SparseArray,因为它避免了自动装箱的过程,如果key为long类型,它还提供了一个LongSparseArray来确保key为long类型时的...2、如果key类型为其它的类型,则使用ArrayMap
  • ArrayMap代替HashMap

    2017-10-31 19:04:00
    ArrayMap是一个<key,value>映射的数据结构,它设计上更多的是考虑内存的优化,内部是使用两个数组进行数据存储,一个数组记录key的hash值,另外一个数组记录Value值,它和SparseArray一样,也会对key使用...
  • HashMap SparseArray ArrayMap

    千次阅读 2017-06-13 09:50:24
    Android为移动操作系统特意编写了一些更加高效的容器,例如SparseArray,ArrayMap。 我们经常会使用到HashMap这个容器,它非常好用,但是却很占用内存。 HashMap HashMap内部是使用一个默认容量为16的数组来存储...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 855
精华内容 342
关键字:

arraymap