ArrayMap详解
下文笔者讲述ArrayMap容器的详解说明,如下所示
ArrayMap简介
ArrayMap: 是非线程安全 ArrayMap: 拥有高效的内存效率 ArrayMap底层采用两个数组进行数据存储 这两个数组分别用于存储key和value 当我们需使用数据时,直接去两个数组中提取数据即可
ArrayMap构造函数
ArrayMap提供三种构造方法
分别:
1.无参的默认构造函数
2.添加默认大小的构造函数
3.指定容积大小则直接分配相应大小的内存
当默认构造函数,默认为 0,会在添加数据时动态扩容
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元素查询方法
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即为我们要查找的Index
当只有HashCode相同但对象不同(即HashCode冲突)
则从当前对应index向后和向前分别遍历查找
ArrayMap元素添加
ArrayMap中添加元素有以下两种方式:
1.put方法添加元素
2.append方法添加元素
ArrayMap之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;
}
put源码注意点说明
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 后移一位；
Arraymap之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方法追加元素,则可以将元素插入到指定位置
ArrayMap之元素删除
public V remove(Object key) {
final int index = indexOfKey(key);
if (index >= 0) {
return removeAt(index);
}
return null;
}
ArrayMap删除元素使用key删除指定元素
删除元素时,先查找出待删除的元素
然后使用removeAt删除元素
ArrayMap之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;
}
源码说明
TAG 01:
当数组只有一个要删除的元素时
直接将 mHashes 和 mArray 制空并通过 freeArrays 释放内存即可；
TAG 02:
当数组内存大小大于 8 并且元素数量少于 1/3 空间大小时
使用allocArrays 进行减少内存分配，将老数据拷贝到新的数组中，并清空老数据数组空间；这是 HashMap 不曾实现的；
TAG 03:
当删除其中一个元素时
需要将该元素之后的所有元素向前移动一位；
ArrayMap数组扩容
HashMap直接以容积2倍进行扩容
而ArrayMap数组扩容是分阶段扩容
与基础数组长度有关
final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
当 osize >= 8 时
数组扩容为原来的 1.5 倍；其中 osize >> 1 相当于 osize / 2；
当 4 <= osize < 8 时
此时扩展为 8；
当 osize < 4 时
此时扩展为 4；
ArrayMap之内存机制
// 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
ArrayMap之释放数组
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) {
...
}
}
ArrayMap内存释放源码说明
当内存需要释放时
释放大小为 BASE_SIZE 或 BASE_SIZE * 2 时
会将数组加入到缓冲池中
释放内存的实现思路:
先将原缓冲池和哈希数组分别指向array前两位
之后的元素全部置空
最后将缓存池的头部指向最新的数组位置；
ArrayMap和HashMap对比
1.ArrayMap不适合大量的数据结构
Google 建议在 1000 以内的数据量比较好
ArrayMap 内部采用了二分查找方式查询，时间复杂度 O(logN)
每次添加和删除元素都需要移动其后面的元素,速度相对较慢
而HashMap 查找和删除时间复杂度为 O(1)；
ArrayMap相对于HashMap增加内存缓存策略
避免频繁创建对象而分配内存与GC操作
同时限制了缓冲池的上限(10 个)
同时ArrayMap还提供灵活的扩容和缩容机制
这两种机制比HashMap更灵活且节省时间
ArrayMap还解决HashMap稀疏数组的问题
相对占用内存更少
ArrayMap示例分享
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());
}
}
版权声明
本文仅代表作者观点，不代表本站立场。
本文系作者授权发表，未经许可，不得转载。
