ArrayMap源码解析

article/2025/4/20 11:43:37

一、数据结构

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

它映射到两个数组结构：一个整数数组mHashes，用来保存key的hashcode；一个对象数组mArray，保存key-value

 它不适用于大量数据的存储，通常会比HashMap慢，因为查找需要二分查找。

二、源码解析

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

由上面可知，ArrayMap是Map的子类

1、成员变量

//默认的最小容量
private static final int BASE_SIZE = 4;
//缓存的容量
private static final int CACHE_SIZE = 10;
//是否使用 System.identityHashCode(key)来获取hashcode
private final boolean mIdentityHashCode;
//存放key的hashcode的数组
int[] mHashes;
//按顺序存放key、value的数组
Object[] mArray;
//mHashes的大小
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。

2、构造函数

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提供了三种构造方法，其中第三个构造方法，从外部传入mHash数组的初始容量capacity。

  • 如果capacity<0,那么mHashes就被赋值一个不可变的int数组，mArray被赋值一个空对象数组。
  • 如果capacity=0，那么mHashes就被赋值一个空int数组，mArray被赋值一个空对象数组。
  • 如果capacity>0,那么就会调用allocArray(capacity)方法，申请指定容量大小的数组。

3、元素查询

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])) {//走到这里，说明已经通过Hashcode找到对的key，这里再判断下查找到索引位置的key与要找的key是否相同，如果相同，则证明找到了，直接返回。如果不相同，则说明hash冲突了。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向后和向前分别遍历查找。（ArrayMap处理Hash冲突的解决办法就是，采用开放地址法，即如果hash值对应的index已经存在值了，则需要从index的两边去寻找与当前key匹配时对应的索引。如果没有找到，则表示当前key原本不存在，需要新插入进来，而插入的位置，就是有着相同hash值且连续的子数组序列的末尾位置）

4、元素添加

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 01:主要用于二分查找，在mHashes数组中查找HashCode相等的key

TAG 02：如果index>0说明已经找到，即有对应HashCode相等的Key，然后更新其Value值。

TAG 03：在index<0,说明没有找到，即没有对应的HashCode相等的Key，此时需要插入新数据。

这里需要注意下，会先判断是否需要扩容，如果mHashes数组已满，那么就需要调用allocArrays扩容，这里扩容的大小：

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

可以看出，如果扩容前的容量大小是否>=BASE_SIZE*2（即8），那么扩容为之前容量的1.5倍。如果扩容前容量小于8再判断之前容量是否>=4,如果>=4,那么扩容为8；如果<4那么扩容为4.

TAG 04:当需要扩容时，可采用allocArrays()方式分配更大的内存空间；

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方法会优先判断需要插入到的数组中的位置，如果要插入到的位置在mHashes数组的中间，则调用put方法，如果插入的位置在mHashes数组的末尾，直接在末尾处添加。

5、元素删除

public V remove(Object key) {final int index = indexOfKey(key);if (index >= 0) {return removeAt(index);}return null;
}

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

TAG 01：当数组只有一个要删除的元素时，直接将mHashes和mArray置空并通过freeArrays释放内存

TAG02：当数组内存大小大于8并且元素的数量少于1/3空间大小时，通过allocArrays进行减少分配内存

TAG03：当删除其中一个元素时，需要将该元素之后的所有元素向前移动一位

ArrayMap为了避免频繁的创建和销毁，提供了mBaseCache和mTwiceBaseCash两个数组缓冲池，同时提供了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 时，会将数组加入到缓冲池中；其方式是先将原缓冲池和哈希数组分别指向 array 前两位，之后的元素全部置空，最后将缓存池的头部指向最新的数组位置；

三、HashMap和ArrayMap对比

1、查找效率

  • HashMap因为其根据hashcode的值直接算出index，所以其查找效率是随着数组长度增大而增加的
  • ArrayMap使用的是二分查找法，所以每当数组长度增加一倍时，就需要多进行一次判断，效率下降。

2.扩容数量

  • HashMap初始值16个长度，每次扩容时，直接申请双倍的数组空间
  • ArrayMap每次扩容时候，如果size长度大于8时申请size*1.5个长度，大于4小于8申请8个，小于4时申请4个。
  • 这样比较，ArrayMap是申请了更少的内存空间，但是扩容的频率比较高。因此，如果数据量较大的时候，还是使用HashMap比较合适，因为其扩容次数要比ArrayMap少很多。
  • ArrayMap没有实现Serializable，不便在Android bundle进行传输
  • ArrayMap扩容比HashMap高效，因为HashMap扩容需要重新计算hash值和移动元素。而ArrayMap只需要拷贝。


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

相关文章

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 函数传参

阅读更多...
js函数传参

js函数传参

也许大家对于函数的参数都不会太在意&#xff0c;简单来说&#xff0c;把函数外部的值复制给函数内部的参数&#xff0c;就和把值从一个变量复制到另一个变量一样。深入研究&#xff0c;你会发现其实没那么简单&#xff0c;这个传参是要分俩种情况&#xff08;其实这是个错误的…
阅读更多...
关于js函数传参的问题

关于js函数传参的问题

js在拼接函数时&#xff0c;当传递的值为字符串是会出现问题&#xff0c;直接报错&#xff0c;不会进入到函数里&#xff0c;这是受就需要转义符来操作&#xff0c; 例如 var can object; onClickUpdateCollege(" can ") 这时事件触发之后&#xff0c;浏览器会报错…
阅读更多...
js 立即执行函数传参问题

js 立即执行函数传参问题

正确的执行函数写法如下&#xff1a; (function func(i) {console.log(i);})(j);(function func(i) {console.log(i);}(j));!(function func(i) {console.log(i);})(j); 看看下面这段代码有什么问题&#xff1f; let testStr "test string"(function func(params) …
阅读更多...
js函数传参，如何在JavaScript函数中不传递先前参数的情况下传递第n个可选参数?

js函数传参，如何在JavaScript函数中不传递先前参数的情况下传递第n个可选参数?

普通函数 function fn(name,age,sex){console.log(name,age,sex);}使用方法 函数的规则是&#xff0c;按顺序传递&#xff0c;如果接收参数是三位&#xff0c;而你只穿了两位&#xff0c;不会报错但是会返回undefined 箭头函数 箭头函数和普通函数使用起来没有太多的区别。 …
阅读更多...
JavaScript函数传参原理详解——值传递还是引用传递

JavaScript函数传参原理详解——值传递还是引用传递

讨论JavaScript的传参原理之前&#xff0c;我们先来看一段曾经让笔者困惑了一段时间的代码 var testA1; var testB{}; function testNumber(example){example2; }function testObj(example) {example.test1; }testNumber(testA); testObj(testB); console.log(testA);//输出1 …
阅读更多...
javascript 函数传参

javascript 函数传参

通过值传递参数 在函数中调用的参数是函数的隐式参数。 JavaScript 隐式参数通过值来传递&#xff1a;函数仅仅只是获取值。 如果函数修改参数的值&#xff0c;不会修改显式参数的初始值&#xff08;在函数外定义&#xff09;。 隐式参数的改变在函数外是不可见的。 通过对…
阅读更多...
前端基础知识点：JS中的参数传递详解

前端基础知识点：JS中的参数传递详解

JS语法中的传递参数&#xff0c;对于初学者是一个非常重要的概念。很多小伙伴在学习“值传递”和“引用传递”时&#xff0c;会有不少烦恼。今天我们就来通过各种姿势全方位剖析JS中的值传递。 本文章将会用10分钟时间无死角的解析JS的传参方式&#xff0c;希望能对您有所帮助…
阅读更多...
Javascript基础知识（三）：函数参数（传参）

Javascript基础知识（三）：函数参数（传参）

1.函数参数分类及使用 上一篇博客已经讲到函数参数有实参和形参两种。 函数参数使用时需要注意以下几点&#xff1a; 1.如果形参有两个赋值&#xff0c;而实参只给了一个值&#xff0c;那么就要把这个值赋予第一个形参.第二个形参没有赋值。 示例&#xff1a; <script&g…
阅读更多...
推荐文章

Copyright @ 2022~2023