ArrayMap
2019-02-16 本文已影响0人
miky_zheng
ArrayMap是android.support.v4.util中的工具类，用来处理key-value类型的数据。
先说优缺点：
优点：
1.节约内存。
a)不用像java的hashmap那样，每个条目添加会创建额外的entry对象（如下代码段）。ArrayMap增长它们只需要复制数组中的条目，而不需要重建散列图。
b)删除会缩小空间
2.遍历查询方便，可以不使用笨重的iteartor。
缺点：
1.查询、添加、删除较java的map慢（查找需要二分查找，添加删除都会插入以及删除条目）。官方建议使用的数量控制在百数据的级别，速度相差低于50%。
2.存在hash冲突。（Java的hashmap是通过entry单链表结合hash算法，来避免hash冲突）
NOTE:由于现在的手机内存都足够，将来也会越来越充足。所以ArrayMap还是少用为好。数据超过百级别，会很耗性能。以下只是通过它的源代码，学习下大神的设计思路。
// hashmap添加元素代码。
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);//新增entry
return null;
}
//object 默认hash函数。（如果两个对象equals return true，则他们的hash值是一样的。所以一般hashCode是和equals一起重写的，子类）
public int hashCode() {
int lockWord = shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
return System.identityHashCode(this);
}
下面看下和普通的hashmap的区别。
构造函数：
public ArrayMap() {
super();
}
/**
* Create a new ArrayMap with a given initial capacity.
*/
public ArrayMap(int capacity) {
super(capacity);
}
/**
* Create a new ArrayMap with the mappings from the given ArrayMap.
*/
public ArrayMap(SimpleArrayMap map) {
super(map);
}
自己没有单独增删改查的方法，是调用父类的增删改查方法。
继承关系,实现了Java 的Map，继承SimpleArrayMap，同java的其他api无关。
public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V>
下面着重看SimpleArrayMap的api
1）增：
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = key.hashCode();
index = indexOf(key, hash);
}
if (index >= 0) {
index = (index<<1) + 1;
final V old = (V)mArray[index];
mArray[index] = value;
return old;
}
index = ~index;
if (mSize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= 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 (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
freeArrays(ohashes, oarray, mSize);
}
if (index < mSize) {
if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
+ " to " + (index+1));
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - 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;
上面的步骤：
- 获取key的hash值，并根据key和hash找索引index。
- 如果index>=0，说明arraymap中已有相同的key，则将新值插入index的2倍+1位置，并返回索引为index的2倍+1的旧值。
- 如果index为负数，取反 ～index。
a)若arraymap的数据大小大于hash数组的大小。则扩容。
b) 若索引小于数据总大小，则将mHashes中index老的数据移到 index + 1 中，mArray移动index << 1到(index + 1) << 1
c)添加mHashes和mArray。 key和value相差一位，并且key在mArray 中的索引 是对应的hash值在mHashes数组的索引的两倍。
删
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];
if (mSize <= 1) {
// Now empty.
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
} else {
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// Shrunk enough to reduce size of arrays. We don't allow it to
// shrink smaller than (BASE_SIZE*2) to avoid flapping between
// that and BASE_SIZE.
final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
mSize--;
if (index > 0) {
if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
if (index < mSize) {
if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
+ " to " + index);
System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
} else {
mSize--;
if (index < mSize) {
if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
+ " to " + index);
System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
mArray[mSize << 1] = null;
mArray[(mSize << 1) + 1] = null;
}
}
return (V)old;
}
删除步骤：
1.若 mSize <= 1释放数组空间
2.若 mSize>1,又分两种情况。
a)mHashes长度大于8并且 mSize < mHashes.length/3，
比b)多了复制的动作：
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
b)其他情况， mHashes和mArray 前移1位。并将mArray保存的key，value清空。
改：（见增）
查：
a) 普通index遍历
//例子
for(int i=0;i<map.size();i++){
key=map.keyAt(i);
value= map.valueAt(i);
}
//ArrayMap 父类SimpleArrayMap 获取key,value方法。
public K keyAt(int index) {
return (K)mArray[index << 1];
}
public V valueAt(int index) {
return (V)mArray[(index << 1) + 1];
}
b)同普通map遍历的方式
public Set<Entry<K, V>> entrySet() {
return getCollection().getEntrySet();
}
@Override
public Set<K> keySet() {
return getCollection().getKeySet();
}
核心实现：android.support.v4.util.MapCollections类的内部类ArrayIterator和MapIterator
当然也可以用它来添加删除。
