神刀安全网

ArrayMap源码解析

分析版本:support-v4-22.2.1

ArrayMap 继承于 SimpleArrayMap ,实现了 Map 接口中的所有方法。

ArrayMap

public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> {
MapCollections<K, V> mCollections;

public ArrayMap() {
super();
}

/**
* 给定大小的ArrayMap
*/

public ArrayMap(int capacity) {
super(capacity);
}

/**
* 通过一个ArrayMap或者SimpleArrayMap来实现一个ArrayMap
*/

public ArrayMap(SimpleArrayMap map) {
super(map);
}

/**
* 得到Map集合
*/

private MapCollections<K, V> getCollection() {
if (mCollections == null) {
mCollections = new MapCollections<K, V>() {
@Override
protected int colGetSize() {
return mSize;
}

//mArray存的是值,该变量在SimpleArrayMap中
@Override
protected Object colGetEntry(int index, int offset) {
return mArray[(index<<1) + offset];
}

//通过key得到位置索引
@Override
protected int colIndexOfKey(Object key) {
return indexOfKey(key);
}

//通过value得到位置索引
@Override
protected int colIndexOfValue(Object value) {
return indexOfValue(value);
}

@Override
protected Map<K, V> colGetMap() {
return ArrayMap.this;
}

@Override
protected void colPut(K key, V value) {
put(key, value);
}

@Override
protected V colSetValue(int index, V value) {
return setValueAt(index, value);
}

@Override
protected void colRemoveAt(int index) {
removeAt(index);
}

@Override
protected void colClear() {
clear();
}
};
}
return mCollections;
}

/**
* 通过调用MapCollections的containsAllHelper来判断该ArrayMap是否包含collection
*/

public boolean containsAll(Collection<?> collection) {
return MapCollections.containsAllHelper(this, collection);
}

/**
* 将Map的类中的内容添加到ArrayMap中
*/

@Override
public void putAll(Map<? extends K, ? extends V> map) {
ensureCapacity(mSize + map.size());
for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}

/**
* 通过调用MapCollections的removeAllHelper来除掉collection中有的值
*/

public boolean removeAll(Collection<?> collection) {
return MapCollections.removeAllHelper(this, collection);
}

/**
* 取ArrayMap和collection的交集
*/

public boolean retainAll(Collection<?> collection) {
return MapCollections.retainAllHelper(this, collection);
}

/**
* 返回一个set用来遍历,注意:这是一个小效率非常低的方法,会产生很多平时变量
*
* Note: the semantics of this
* Set are subtly different than that of a HashMap: most important,
* the Map.Entry object returned by its iterator is a single
* object that exists for the entire iterator, so you can not hold on to it
* after calling Iterator.next.
*/

@Override
public Set<Entry<K, V>> entrySet() {
return getCollection().getEntrySet();
}

/**
* 返回一个set用来遍历key,注意:这是一个小效率非常低的方法,会产生很多平时变量
*/

@Override
public Set<K> keySet() {
return getCollection().getKeySet();
}

/**
* 返回一个Collections用来遍历value,注意:这是一个小效率非常低的方法,会产生很多平时变量
*/

@Override
public Collection<V> values() {
return getCollection().getValues();
}
}

ArrayMap 中的具体实现方法是在 SimpleArrayMap 中实现的,而 ArrayMap 中实现 Map 接口的方法中,许多不建议使用,因为相比起 HashMap 等,效率要低的多。

SimpleArrayMap

public class SimpleArrayMap<K, V> {

/**
* The minimum amount by which the capacity of a ArrayMap will increase.
* This is tuned to be relatively space-efficient.
*/

private static final int BASE_SIZE = 4;

/**
* Maximum number of entries to have in array caches.
*/

private static final int CACHE_SIZE = 10;

int[] mHashes;
Object[] mArray;
int mSize;

/**
* Caches of small array objects to avoid spamming garbage. The cache
* Object[] variable is a pointer to a linked list of array objects.
* The first entry in the array is a pointer to the next array in the
* list; the second entry is a pointer to the int[] hash code array for it.
*/

static Object[] mBaseCache;
static int mBaseCacheSize;
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;

/**
* 创建一个空的ArrayMap,默认容量是0
*/

public SimpleArrayMap() {
mHashes = ContainerHelpers.EMPTY_INTS;//static final int[] EMPTY_INTS = new int[0];
mArray = ContainerHelpers.EMPTY_OBJECTS;// static final Object[] EMPTY_OBJECTS = new Object[0];
mSize = 0;
}

/**
* 创建一个给定容量的ArrayMap
*/

public SimpleArrayMap(int capacity) {
if (capacity == 0) {
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
} else {
allocArrays(capacity);
}
mSize = 0;
}

/**
* 通过一个ArrayMap来创建一个新的ArrayMap
*/

public SimpleArrayMap(SimpleArrayMap map) {
this();
if (map != null) {
putAll(map);
}
}

/**
* 扩容,分配新的数组
*/

private void allocArrays(final int size) {
//如果是8
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
//如果mTwiceBaseCache不为null
if (mTwiceBaseCache != null) {
//将mTwiceBaseCache赋值给mArray
final Object[] array = mTwiceBaseCache;
mArray = array;
//将之前保存在0和1的拿出来
mTwiceBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
//清空
array[0] = array[1] = null;
mTwiceBaseCacheSize--;
return;
}
}
} else if (size == BASE_SIZE) {//如果是4
synchronized (ArrayMap.class) {
//如果mBaseCache不为null
if (mBaseCache != null) {
//将mBaseCache赋值给mArray
final Object[] array = mBaseCache;
mArray = array;
//将之前保存在0和1的拿出来
mBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
//清空
array[0] = array[1] = null;
mBaseCacheSize--;
return;
}
}
}
//创建mHashes数组和mArray数组
mHashes = new int[size];
mArray = new Object[size<<1];
}

public void putAll(SimpleArrayMap<? extends K, ? extends V> array) {
final int N = array.mSize;
//确认目前数组放的下
ensureCapacity(mSize + N);
//当前数组没有值
if (mSize == 0) {
if (N > 0) {//将内容复制到mHash和mArray中
System.arraycopy(array.mHashes, 0, mHashes, 0, N);
System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
mSize = N;
}
} else {//如果原来就有值,那么直接通过for循环将信息写入
for (int i=0; i<N; i++) {
put(array.keyAt(i), array.valueAt(i));
}
}
}

/**
* 判断目前数组是否够大
*/

public void ensureCapacity(int minimumCapacity) {
if (mHashes.length < minimumCapacity) {
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//分配数组(创建新的数组)
allocArrays(minimumCapacity);
//把旧的数组信息整到新的数组上
if (mSize > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, mSize);
System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
}
//释放
freeArrays(ohashes, oarray, mSize);
}
}

private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
//如果是8
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {
//此时mTwiceBaseCacheSize值为0,必然小于CACHE_SIZE
if (mTwiceBaseCacheSize < CACHE_SIZE) {
//将现有的mTwiceBaseCache赋值给数组的第一个
array[0] = mTwiceBaseCache;
array[1] = hashes;
//清除剩下的
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
//将数组赋值给mTwiceBaseCache,就是将mTwiceBaseCache替换掉了,原来的mTwiceBaseCache在该数组的第0位置上
mTwiceBaseCache = array;
mTwiceBaseCacheSize++;
}
}
} else if (hashes.length == BASE_SIZE) {//如果是4
synchronized (ArrayMap.class) {
if (mBaseCacheSize < CACHE_SIZE) {
//将mBaseCache赋值给数组的第一个
array[0] = mBaseCache;
array[1] = hashes;
//清除剩下的
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
//将数组赋值给mBaseCache
mBaseCache = array;
mBaseCacheSize++;
}
}
}
}
}

put(K key, V value)

public class SimpleArrayMap<K, V> {

public V put(K key, V value) {
//当前值的hash
final int hash;
//当前值的索引
int index;
if (key == null) {//如果key为null,那么hash为0
hash = 0;
index = indexOfNull();//找得到返回正数,找不到返回负数
} else {//如果key不为null,那么hash就是keyhashCode值
hash = key.hashCode();
index = indexOf(key, hash);//找得到返回正数,找不到返回负数
}
//如果index的值是大于等于0的
if (index >= 0) {
//index*2+1,即value的位置
index = (index<<1) + 1;
//得到旧的value
final V old = (V)mArray[index];
//将新的value赋值进去
mArray[index] = value;
//返回旧的value
return old;
}
//如果index为负,那么这里变为正数
index = ~index;
if (mSize >= mHashes.length) {//现有的值的数量与hash数组大小对比
//mSize如果大于等于8,那么n=mSize+mSize/2;如果mSize小于8且大于等4,n=8;如果mSize小于4,n=4
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
//准备临时变量存放旧数据
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//扩容
allocArrays(n);

if (mHashes.length > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//释放
freeArrays(ohashes, oarray, mSize);
}
//将index后面的内容往后面移
if (index < mSize) {
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;
}

int indexOf(Object key, int hash) {
final int N = mSize;

// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
//二分查找hash值对应的key
int index = ContainerHelpers.binarySearch(mHashes, N, hash);

// If the hash code wasn't found, then we have no entry for this key.
//没有找到直接返回
if (index < 0) {
return index;
}

// If the key at the returned index matches, that's what we want.
//如果找到,判断key是否正确
if (key.equals(mArray[index<<1])) {
return index;
}

//找对应的key
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == hash; end++) {
if (key.equals(mArray[end << 1])) return end;
}

// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
if (key.equals(mArray[i << 1])) return i;
}

// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;
}

int indexOfNull() {
final int N = mSize;

// Important fast case: if nothing is in here, nothing to look for.
if (N == 0) {
return ~0;
}
//二分查找hash值对应的key
int index = ContainerHelpers.binarySearch(mHashes, N, 0);

// If the hash code wasn't found, then we have no entry for this key.
//没有找到直接返回
if (index < 0) {
return index;
}

// If the key at the returned index matches, that's what we want.
//如果找到,判断key是否正确
if (null == mArray[index<<1]) {
return index;
}

//找对应的key
// Search for a matching key after the index.
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
if (null == mArray[end << 1]) return end;
}

// Search for a matching key before the index.
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
if (null == mArray[i << 1]) return i;
}

// Key not found -- return negative value indicating where a
// new entry for this key should go. We use the end of the
// hash chain to reduce the number of array entries that will
// need to be copied when inserting.
return ~end;
}
}

removeAt(int index)

public class SimpleArrayMap<K, V> {

public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];
if (mSize <= 1) {//清空
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);
//临时变量存放旧hash数组和array数组
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//分配新的数组
allocArrays(n);

mSize--;
//将原先的数组的index之前的值传进去
if (index > 0) {
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
//要删除的index值小于现在的大小
if (index < mSize) {
//将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) {
//将index后面的往前移
System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
(mSize - index) << 1);
}
//对应的位置设为null
mArray[mSize << 1] = null;
mArray[(mSize << 1) + 1] = null;
}
}
return (V)old;
}
}

其他 API

public class SimpleArrayMap<K, V> {

//清空
public void clear() {
if (mSize != 0) {
freeArrays(mHashes, mArray, mSize);
mHashes = ContainerHelpers.EMPTY_INTS;
mArray = ContainerHelpers.EMPTY_OBJECTS;
mSize = 0;
}
}

//是否包含这个key
public boolean containsKey(Object key) {
return indexOfKey(key) >= 0;
}

//key的索引
public int indexOfKey(Object key) {
return key == null ? indexOfNull() : indexOf(key, key.hashCode());
}

//value的索引
int indexOfValue(Object value) {
final int N = mSize*2;
final Object[] array = mArray;
if (value == null) {
for (int i=1; i<N; i+=2) {
if (array[i] == null) {
return i>>1;
}
}
} else {
for (int i=1; i<N; i+=2) {
if (value.equals(array[i])) {
return i>>1;
}
}
}
return -1;
}

//是否包含这个value
public boolean containsValue(Object value) {
return indexOfValue(value) >= 0;
}

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

//得到index索引位置上的key
public K keyAt(int index) {
return (K)mArray[index << 1];
}

//得到index索引上的value
public V valueAt(int index) {
return (V)mArray[(index << 1) + 1];
}

//设置index索引上的value
public V setValueAt(int index, V value) {
index = (index << 1) + 1;
V old = (V)mArray[index];
mArray[index] = value;
return old;
}

//通过key来删除
public V remove(Object key) {
final int index = indexOfKey(key);
if (index >= 0) {
return removeAt(index);
}
return null;
}

//大小
public int size() {
return mSize;
}
}

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » ArrayMap源码解析

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址