AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

初识 ArrayMap

2020-11-02 1464
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 简单了解 ArrayMap 的基本应用！

      小菜在之前学习 SharedPreferences 源码时注意到，其数据存储主要用到了 ArrayMap，小菜在日常中对于 key-value 方式主要是 HashMap 居多，今天简单研究一下 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_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : 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；

  1. TAG 01: 主要用于二分查找的方式，在 mHashes 数组中查找 HashCode 值相等的 Key；
  2. TAG 02: 在 index > 0 即有对应 HashCode 相等的 Key 之后，更新其 Value 值；通过 index << 1 左移的方式相当于 index * 2 只是效率更高效，可多在实际项目中应用；
  3. TAG 03: 在 index < 0 即没有对应 HashCode 相等的 Key，此时需要插入新数据；
  4. TAG 04: 当需要扩容时，可采用 allocArrays() 方式分配更大的内存空间；且 ArrayMap 是非线程安全的，不可并行；
  5. TAG 05: 通过 System.arraycopy 将老的数组数据拷贝到新的数组中，再通过 freeArrays() 释放老的数组内存；
  6. 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_SIZE*2) && 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;
}
  1. TAG 01: 当数组只有一个要删除的元素时，直接将 mHashes 和 mArray 置空并通过 freeArrays 释放内存即可；
  2. TAG 02: 当数组内存大小大于 8 并且元素数量少于 1/3 空间大小时，通过 allocArrays 进行减少内存分配，将老数据拷贝到新的数组中，并清空老数据数组空间；这是 HashMap 不曾实现的；
  3. TAG 03: 当删除其中一个元素时，需要将该元素之后的所有元素向前移动一位；

数组扩容

      HashMap 直接以容积的 2 倍进行扩容，而 ArrayMap 数组扩容是分阶段扩容的；与基础数组长度有关；

final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
  1. 当 osize >= 8 时，数组扩容为原来的 1.5 倍；其中 osize >> 1 相当于 osize / 2；
  2. 当 4 <= osize < 8 时，此时扩展为 8；
  3. 当 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 的源码了解还不够深入，与其他存储方式的横向对比也不够全面；如有错误请多多指导！

来源： 阿策小和尚

文章标签：
Java
安全
缓存
存储
阿策～
目录
相关文章
ST小智
|
Linux SoC
linux系统中SPI驱动框架的基本原理与实现
linux系统中SPI驱动框架的基本原理与实现
ST小智
235 0
开发者小助手_LS
|
自然语言处理 Java Go
Fury：一个基于JIT动态编译的高性能多语言原生序列化框架
Fury是一个基于JIT动态编译的多语言原生序列化框架，支持Java/Python/Golang/C++等语言，提供全自动的对象多语言/跨语言序列化能力，以及相比于别的框架最高20~200倍的性能。
开发者小助手_LS
4069 1
Fury：一个基于JIT动态编译的高性能多语言原生序列化框架
aliyun8599273441-30642
|
6月前
|
缓存 监控 算法
深入理解操作系统：进程调度与性能优化
在现代计算机系统的核心，操作系统承担着资源管理和任务调度的关键职责。进程调度作为操作系统的一个复杂而重要的组成部分，它直接影响到系统的响应时间、吞吐量以及用户体验。本文将详细探讨进程调度的机制、算法以及它们如何影响操作系统的性能。同时，我们还将分析不同的性能优化策略，并讨论它们在实际系统中的实现和效果。
aliyun8599273441-30642
232 0
weixin_836869520
|
4月前
|
Oracle Java 关系型数据库
Java中的编码规范与代码审查实践
Java中的编码规范与代码审查实践
weixin_836869520
119 2
一歲抬頭
|
6月前
|
API Android开发
Android Framework增加API 报错 Missing nullability on parameter
Android Framework增加API 报错 Missing nullability on parameter
一歲抬頭
325 1
小小工匠
|
6月前
|
缓存 JavaScript 前端开发
WebView完全解读
WebView完全解读
小小工匠
266 0
路宇
|
Android开发
Android 中使用AlarmManager设置闹钟详解
Android 中使用AlarmManager设置闹钟详解
路宇
294 0
myysophia
|
存储 Linux
Linux pid的取值范围
每个进程都有一个进程号（PID），进程号是一个正数，用以唯一标识系统中的某个进程。对各种系统调用而言，进程号有时可以作为传入参数，有时可以作为返回值。
myysophia
403 0
风正豪
|
监控 IDE 开发工具
ESP32CAM---利用Vscode阅读源码
ESP32CAM---利用Vscode阅读源码
风正豪
244 0
cczhengv
|
Java Android开发 C++
Framework 全局监听屏幕点击事件 INPUT_EVENT_INJECTION
Framework 全局监听屏幕点击事件 INPUT_EVENT_INJECTION
cczhengv
303 0