ArrayMap 源码的详细解析

article/2025/3/4 14:59:16

最近在写framework层的系统服务，发现Android 12中用来去重注册监听的map都是用的ArrayMap，因此仔细研究了ArrayMap的原理。

目录

一. ArrayMap概述

二. ArrayMap源码解析

1.主要包含的成员变量

2.构造函数

3. public boolean containsKey(Object key)

4. public int indexOfKey(Object key)

5. public boolean containsValue(Object value)

6. public int indexOfValue(Object value)

7.核心get方法

8.核心put方法

9. public V remove(Object key)

10. public V removeAt(int index)

11. public void clear()

12.public void erase()

13. public K keyAt(int index)

14. public V valueAt(int index)

15. 二分查找的实现

16. System.arraycopy()

一. ArrayMap概述

ArrayMap是一个key-value的数据结构，它比HashMap有更高的内存效率。

它映射到两个数组结构：一个整数数组mHashes，保存key的hash code；一个对象数据mArray，顺序保存key-value。

它可以避免为push到map的item创建额外的对象，而且它试图控制这些数组大小的增长（因为增长数据大小只需要复制数组中的item即可，不需要重建hash map）。

它不适用于大量数据的存储，通常会比HashMap慢，因为查找需要二分法，而且添加和删除操作需要对数组中entries进行相应的插入和删除（通常数组中间元素的插入和删除效率很低，因为会导致插入或者删除位置之后的元素整体移动，请参考后边的remove和put函数解析），对于包含数百个元素的容器来说，性能差异不显著，小于50%。

因为ArrayMap是为了更好的平衡内存，和大部多数Java标准containers不同，当删除item时它会缩小数组。目前你无法控制这种（shrinking）缩小——如果您设置了capacity然后删除一个item，他可能会减少capacity来匹配目前大小。将来明确设置capacity应该会关闭这种激进的shriking行为。

二. ArrayMap源码解析

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

1.主要包含的成员变量

private static final int BASE_SIZE = 4;
private static final int CACHE_SIZE = 10;private final boolean mIdentityHashCode;
int[] mHashes;
Object[] mArray;
int mSize;
private MapCollections<K, V> mCollections;

注意：mSize表示数组mHashes的大小，而mArray的大小为2*mSize。mHashes中升序存放key的hash值，mArray中顺序存储了key和value。若key的hash在mHashes的位置索引为index，key在mArray中的位置keyIndex= index<<1 = index*2，value在mArray中的位置valueIndex= (index<<1) + 1 = index*2 + 1。

ArrayMap的两个数组存储结构如下：

2.构造函数

public ArrayMap()public ArrayMap(int capacity)public ArrayMap(int capacity, boolean identityHashCode)public ArrayMap(ArrayMap<K, V> map)

3. public boolean containsKey(Object key)

判断Array中是否存在该key，如果该key存在则返回true，否则false。该方法调用indexOfKey(key) >= 0来实现。

4. public int indexOfKey(Object key)

如果该key在数组中，则返回其index，否则返回一个负数。

它核心就是根据该key是否是null，来判断调用indexOf(Object key, int hash)还是indexOfNull()，该这两个方法中使用二分查找key。

5. public boolean containsValue(Object value)

如果该value存在则返回true，否则返回false。该方法调用indexOfValue(value) >= 0来实现。

6. public int indexOfValue(Object value)

如果该Object存在，则返回其index，否则返回-1。

该方法的查找效率没有indexOfKey()快，因为该方法是线性查找数组mArray，分为object = null和object = null的情况。

7.核心get方法

public V get(Object key)
public V get(Object key) {final int index = indexOfKey(key);return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

注意：<<代表左移运算符，<<1表示左移1位，低位补0，相当于乘以2。

8.核心put方法

public V put(K key, V value)

给ArrayMap中添加一个新的value，如果key已存在，则会用参数中的value覆盖其原来对应的value值。返回值是给定key对应的老的value，如果该key不存在，则返回null。

该方法很长主要分为以下部分

  • 根据key是否为null，调用indexOf()或者indexOfNull()方法二分查找该key是否存在。
  • 如果mHashes数组中该key存在，则用新的value值覆盖旧的value。
public V put(K key, V value) {final int osize = mSize;final int hash;int index;//查找key是否存在，若存在，则返回其indexif (key == null) {hash = 0;index = indexOfNull();} else {hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();index = indexOf(key, hash);}//key存在，用新value替换就的value，覆盖旧值if (index >= 0) {index = (index<<1) + 1;final V old = (V)mArray[index];mArray[index] = value;return old;}
...
}
  • 如果mHashes数组中该key不存在，则二分查找返回的iindex取反就是要该key要插入的位置。（请参考后边的二分查找算法）

  • 给mHashes数组和mArray数组扩容，如果ArrayMap现有数组长度osize > (BASE_SIZE*2)，则扩容到3*osize，否则扩容为8或者4。

public V put(K key, V value) {...index = ~index;if (osize >= mHashes.length) {//osize=mSize，插入前mHashes数组的长度，BASE_SIZE=4final 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在mHashes数组中间，则把mHashes和mArray中index及之后的元素整体后移一位，即使用System.arraycopy()实现。
  • 然后把要put的key和value分别插入对应下标的数组中。
public V put(K key, V value) {...if (index < osize) {if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)+ " to " + (index+1));//要插入的key的index在mHashes数组中间，则需要将mHashes中index及之后的元素整体后移一位。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();}}//把要push的key和value分别加入mHashes数组以及mArray数组中mHashes[index] = hash;mArray[index<<1] = key;mArray[(index<<1)+1] = value;//数组长度加1mSize++;return null;
}

以上就是ArrayMap的整个put方法过程，因为新增元素涉及到插入位置后的两个数组元素的整体后移（复制），这就是ArrayMap顺序存储效率慢的原因。

9. public V remove(Object key)

删除给定key对应的元素，该方法会同时删除mHashes中和mArray数组中的元素，并引起Shrink数组。

如果该key存在，则会返回删除的该key对应的value，否则返回null。

该方法先调用indexOfKey()二分查找该key对应的index，如果index>=0，则调用removeAt()实现删除。

10. public V removeAt(int index)

该方法是ArrayMap删除数据的核心，我们解析下代码：

  • 已知要删除的index，可以获取该index对应的value值，仅通过一行代码就可以实现 
    final Object old = mArray[(index << 1) + 1];
  • 判断当前数组的长度mSize<=1，如果true，直接把mHashes和mArray数组赋值为EmptyArray，然后释放空间。这是一次shrink。
public V removeAt(int index) {if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {// The array might be slightly bigger than mSize, in which case, indexing won't fail.// Check if exception should be thrown outside of the critical path.throw new ArrayIndexOutOfBoundsException(index);}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");final int[] ohashes = mHashes;final Object[] oarray = mArray;mHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;freeArrays(ohashes, oarray, osize);nsize = 0;}
...if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {throw new ConcurrentModificationException();}mSize = nsize;return (V)old;
}
  • 如果mHashes数组长度>8或者mSize<mHashes.length/3，则会触发shrink数组，并删除该元素。
  • 否则删除该index对应的mHashes和mArray中的元素。
System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1);

11. public void clear()

清空arraymap，会释放所有的存储空间。该方法中将数组mHashes和mArray赋值EmptyArray，并释放存储空间。

12.public void erase()

该方法只将mArray数组中的元素全部置为null，不释放ArrayMap的存储空间。

13. public K keyAt(int index)

获取指定index对应的Key值。

public K keyAt(int index) {if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {// The array might be slightly bigger than mSize, in which case, indexing won't fail.// Check if exception should be thrown outside of the critical path.throw new ArrayIndexOutOfBoundsException(index);}return (K)mArray[index << 1];
}

14. public V valueAt(int index)

获取指定index对应的value值

public V valueAt(int index) {if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) {// The array might be slightly bigger than mSize, in which case, indexing won't fail.// Check if exception should be thrown outside of the critical path.throw new ArrayIndexOutOfBoundsException(index);}return (V)mArray[(index << 1) + 1];
}

15. 二分查找的实现

ArrayMap的二分查找是调用的ContainerHelper工具类中的binarySearch()方法。

static int binarySearch(int[] array, int size, int value) {int lo = 0;int hi = size -1;while (lo <= hi) {final int mid = (lo + li) >>> 1;final int minVal = array[mid];if (midVal < value) {lo = mid + 1;} else if (midVal > value) {hi = mid - 1;} else {return mid;}  }return ~lo;
}

16. System.arraycopy()

private static void arraycopy(int[] src, int srcPos, int[] dst, int dstPos, int length)

http://chatgpt.dhexx.cn/article/pu6KFiJD.shtml

相关文章

SparseArray和ArrayMap

SparseArray和ArrayMap

首先我们来介绍一下HashMap&#xff0c;了解它的优缺点&#xff0c;然后再对比一下其他的数据结构以及为什么要替代它。 HashMap HashMap是由数组单向链表的方式组成的&#xff0c;初始大小是16&#xff08;2的4次方&#xff09;&#xff0c;首次put的时候&#xff0c;才会真…
阅读更多...
SparseArray与ArrayMap

SparseArray与ArrayMap

SparseArray SparseArray核心代码 两个构造函数默认数组容量10 public SparseArray() {this(10); } public SparseArray(int initialCapacity) {if (initialCapacity 0) {mKeys EmptyArray.INT;mValues EmptyArray.OBJECT;} else {mValues ArrayUtils.newUnpaddedObjectA…
阅读更多...
arraymap android,深入剖析 Android中的 ArrayMap

arraymap android,深入剖析 Android中的 ArrayMap

数据集合在任何一门编程语言中都是很重要的一部分&#xff0c;在 Android 开发中&#xff0c;我们会实用到ArrayList, LinkedList, HashMap等。其中HashMap是用来处理键值对需求的常用集合。 而Android中引入了一个新的集合&#xff0c;叫做ArrayMap&#xff0c;为键值对存储需…
阅读更多...
ArrayMap 笔记整理

ArrayMap 笔记整理

源码基于 API 25 主要参考文章&#xff1a;面试必备&#xff1a;ArrayMap源码解析 1、概述 截图自&#xff1a;面试必备&#xff1a;ArrayMap源码解析 在开始讲解源码之前&#xff0c;需要说明 ArrayMap 的底层实现结构&#xff0c;即两个数组&#xff1a; int[] mHashes; /…
阅读更多...
ArrayMap 原理

ArrayMap 原理

一 概述 在移动设备端&#xff0c;内存资源很珍贵&#xff0c;HashMap 为实现快速查询带来了很大内存的浪费。为此&#xff0c;2013年5月20日 Google 工程师 Dianne Hackborn 在 Android 系统源码中新增 ArrayMap 类&#xff0c;从 Android 源码中发现有不少提交&#xff0c;专…
阅读更多...
不再害怕面试问ArrayMap一文完全看懂Android ArrayMap源码解析

不再害怕面试问ArrayMap一文完全看懂Android ArrayMap源码解析

作者&#xff1a;VIjolie 前言 ArrayMap是谷歌推出的在安卓等设备上用于替代HashMap的数据结构&#xff0c;和HashMap相比&#xff0c;具有更高的内存使用率&#xff0c;因此适合在Android等内存较为紧张的移动设备&#xff0c;下面结合源码分析ArrayMap实现原理&#xff0c;主…
阅读更多...
ArrayMap原理解析

ArrayMap原理解析

1.ArrayMap是什么 一个通用的key-value映射数据结构 相比HashMap会占用更少的内存空间 android.util和android.support.v4.util都包含对应的ArrayMap类 2.为什么要使用ArrayMap ArrayMap是一个普通的键值映射的数据结构&#xff0c;这种数据结构比传统的HashMap有着更好的内…
阅读更多...
ArrayMap源码解析

ArrayMap源码解析

一、数据结构 ArrayMap是一个key-value的数据结构&#xff0c;它比HashMap有更高的内存效率 它映射到两个数组结构&#xff1a;一个整数数组mHashes&#xff0c;用来保存key的hashcode&#xff1b;一个对象数组mArray&#xff0c;保存key-value 它不适用于大量数据的存储&…
阅读更多...
ArrayMap的使用与详解

ArrayMap的使用与详解

数据集合在任何一门编程语言中都是很重要的一部分&#xff0c;在 Android 开发中&#xff0c;我们会实用到List,ArrayList, HashMap等。List和ArrayList配合使用&#xff0c;其中HashMap是用来处理键值对需求的常用集合。 而Android中引入了一个新的集合&#xff0c;叫做ArrayM…
阅读更多...
ipdb 调试 - 终端显示正常，日志显示乱码

ipdb 调试 - 终端显示正常，日志显示乱码

问题描述 ipdb调试模型&#xff0c;在 vscode 终端正常显示&#xff0c;但日志文件中&#xff0c;输入流将ipdb调试信息的颜色代码记录在文件中&#xff0c;日志文件无法查阅。 解决方案&#xff1a; 提示&#xff1a;修改ipdb的终端颜色属性 点击 ipdb&#xff0c;进入 ipdb …
阅读更多...
ipdb调试dataloader

ipdb调试dataloader

ipdb不可以直接放入__init__/__len__/__getitem__进行调试 需要在主函数中中断调试&#xff0c;例如colab中&#xff1a; 输入需要查询的变量即可
阅读更多...
初次使用python(2)之如何下载ipdb模块

初次使用python(2)之如何下载ipdb模块

上次提到了ipdb这个python中用于进行调试的模块&#xff0c;但在python中是额外的package。所以&#xff0c;这篇文章写得是如何下载ipdb模块。 在Windows环境中&#xff0c;需要用pip来下载所有模块。 1.安装pip 我们仍需要在python官网上找到pip文件&#xff0c;下载地址是&a…
阅读更多...
python ipdb 调试代码

python ipdb 调试代码

python ipdb 调试代码 安装 pip install ipdb使用 第一种方法 python -m ipdb xxx.py #单步调试也可以写一个.py文件&#xff0c;如下&#xff0c;来执行。 import os os.system(python -m ipdb xxx.py)第二种方法 在需要断点的地方插入两句话 from ipdb import set_tra…
阅读更多...
python debug ipdb

python debug ipdb

pudb使用 to be continued… ipdb和pdb区别 实际上ipdb是pdb的扩展版本&#xff0c;在pdb的基础上添加了如下功能&#xff1a; 可以使用tab&#xff08;提示&#xff09;补全代码的功能&#xff08;我觉得这一点上我就完全倒戈了…&#xff09;调试不再是黑白的&#xff0c…
阅读更多...
Python调试pdb和ipdb

Python调试pdb和ipdb

什么是pdb和ipdb 不知道大家在用Python写代码出现报错时是怎样调试的&#xff0c;从报错提示定位回去一步一步check每一行&#xff1f;如果没有IDE或者命令行写代码时又该怎样快速调试&#xff1f;这时如果使用pdb进行调试将会异常方便。 Pdb就是Python debugger&#xff0c;…
阅读更多...
python调试模块ipdb

python调试模块ipdb

1. 调试python ipdb是用来python中用以交互式debug的模块&#xff0c;可以直接利用pip安装; 其功能类似于pycharm中　python控制台&#xff0c; 而使用ipdb 的优点&#xff0c;便是直接在代码中调试&#xff0c; 避免了在python控制台&#xff0c;或者重新设置一些简单变量。…
阅读更多...
python调试器 ipdb

python调试器 ipdb

文章目录 1. 介绍1.1 常用调试方式1.2 安装 ipdb 2. 用法3. 命令3.1、查看源代码3.2、添加断点3.3 添加临时断点3.4 清除断点3.5、打印变量值3.6、逐行调试命令3.7、非逐行调试命令3.8 跳出函数&#xff0c;跳入函数3.9、查看当前函数所有参数3.10 打印变量的值3.11、打印变量类…
阅读更多...
ipdb python下的debug利器

ipdb python下的debug利器

ipdb是一个IPython的python下debug神器&#xff0c;支持在代码中添加断点&#xff0c;进行单步调试&#xff0c;支持在调试过程中查看各种变量的值&#xff0c;新增修改断点&#xff0c;或跳过特定断点。以往进行python代码的调试都是通过pycharm或vscode添加断点&#xff0c;在…
阅读更多...
js中函数传参的问题

js中函数传参的问题

在使用ajax或者js拼接信息在页面中显示的时候&#xff0c;需要向函数传参的时候往往会有问题。 如果传递的是数字类型&#xff0c;则是可以直接传递。不需要进行转义。 如果是字符串类型&#xff0c;则需要进行转义&#xff0c;才会以存入字符串的参数。
阅读更多...
js 函数传参

js 函数传参

阅读更多...
推荐文章

Copyright @ 2022~2023