ArrayMap 源码分析

发表于 | 分类于 | 阅读次数：

概述

ArrayMap 是 Android 的 API，它和 Java 的 HashMap 相比，虽然在查找效率上不如 HashMap（HashMap 查找的时间复杂度是 O(1), ArrayMap 查找的时间复杂度是 O(logn)），但是 ArrayMap 的空间消耗更小，它内部使用数组存储 hash 和键值对，不用花费多余的指针维护链表或树结构，扩容的时候只扩容 1.5 倍，并且元素小于一定量后还会收缩数组来回收空间。所以在数据量不大并且需要节省空间的时候可以考虑 ArrayMap。

下面就从源码的角度看下 ArrayMap 的实现原理，主要看它的增删查方法。

主要属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
final boolean mIdentityHashCode;    // 是否利用 System.identityHashCode(key) 获取唯一 hashCode

/**
 * 保存每个元素的 hash，长度为容量大小
 * mHashes 是有序的，按照元素的 hash 值由小到大排序，hash 值相同的元素，先插入的排在前面
 * 由于 mHashes 是有序的，所以使用二分法查找元素的位置，时间复杂度为 O(logn)
 */
int[] mHashes; 

/**
 * 保存键值对，长度为容量的两倍
 * 根据 key 的 hash 在 mHashes 的存放位置 index，可以确定键值对在 mArray 的存放位置
 * key 存放在 index << 1 处，value 存放在 (index << 1) + 1 处
 */
Object[] mArray;  

int mSize;          // 当前键值对数量

构造方法

ArrayMap()

1
2
3
public ArrayMap() {
    this(0, false);
}

默认构造方法，初始容量为 0，第一次插入元素时再扩容

ArrayMap(int)

1
2
3
public ArrayMap(int capacity) {
    this(capacity, false);
}

指定初始容量

ArrayMap(int, boolean)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;

    if (capacity < 0) { // 容量小于 0，创建一个不可变的 ArrayMap
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) { // 容量等于 0，创建一个空 ArrayMap
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        // 容量大于 0，根据指定容量初始化 mHashes 和 mArray 数组
        // 如果容量是 4 或 8 的话，会查看之前是否有缓存的数组，有就使用缓存
        allocArrays(capacity);  
    }
    mSize = 0;
}

指定初始容量和 mIdentityHashCode

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
  public V put(K key, V value) {
      final int osize = mSize;
      final int hash;		// 存放 key 的 hash
      int index;	// 通过该 index 得到 hash 在 mHashes 的存放位置以及键值对在 mArray 的存放位置

      if (key == null) {
          hash = 0;		// null 的 hash 为 0
          index = indexOfNull();	// 得到 null 的存放位置
      } else {
          hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();	// 得到 key 的 hash
          index = indexOf(key, hash);		// 得到 key 的 index
      }

// 存在相同的 key，更新 value，返回旧的 value
      if (index >= 0) {
          index = (index<<1) + 1;
          final V old = (V)mArray[index];
          mArray[index] = value;
          return old;
      }

      index = ~index;
// 判断是否要扩容
      if (osize >= mHashes.length) {
	// n 为新数组长度
	// 如果旧数组长度小于 4，那么新数组长度为 4
	// 如果旧数组长度大于等于 4 并且小于 8，那么新数组长度为 8
	// 如果旧数组长度大于等于 8，新数组长度是原来的 1.5 倍
          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;
          allocArrays(n);		// 创建新数组

          if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
              throw new ConcurrentModificationException();
          }

	// 移动旧元素到新数组中
          if (mHashes.length > 0) {
              System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
              System.arraycopy(oarray, 0, mArray, 0, oarray.length);
          }

	// 如果旧的 mHashes 数组长度为 4 或 8，会缓存起来
          freeArrays(ohashes, oarray, osize);
      }

// 如果元素要插入到 mHashes 和 mArray 的中间，那么在该元素后面的先后移，给新元素腾出位置
      if (index < osize) {
          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();
          }
      }

// 新元素插入到 mHashes 和 mArray 的合适位置
      mHashes[index] = hash;
      mArray[index<<1] = key;
      mArray[(index<<1)+1] = value;
      mSize++;
      return null;
  }

首先得到 key 的 hash 值，null 的 hash 值为 0，对于非 null 的 key，默认情况下使用 key 的 hashCode() 作为它的 hash 值，如果在创建 ArrayMap 时指定 mIdentityHashCode 为 true，则 key 的 hash 值为 System.identityHashCode(key)。

然后使用二分法在 mHashes 数组查找 key 的 hash 所在位置索引 index。如果 index >= 0，说明存在相同元素，更新 value，返回旧的 value。否则就要根据 index 将新元素插入到合适位置。

在插入前，判断是否要扩容，当键值对数量大于等于 mHashes 数组的长度时，进行扩容。扩容过程和 ArrayList 相似，得到新数组长度，创建新数组，并将旧数组的元素复制过去。新数组长度和旧数组长度有关：

如果旧数组长度小于 4，那么新数组长度为 4；如果旧数组长度大于等于 4 并且小于 8，那么新数组长度为 8；如果旧数组长度大于等于 8，新数组长度是原来的 1.5 倍。

插入元素的时候，如果不是插入到最后，那么需要先将位于插入位置及其后面的元素后移，腾出位置，然后将 hash 和键值对插入到 mHashes 和 mArray 的相应位置。

得到 index 使用的是 indexOfNull() 和 indexOf 方法：

indexOfNull()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
  int indexOfNull() {
      final int N = mSize;

      // 当前集合为空，返回
      if (N == 0) {
          return ~0;
      }
// 二分查找，找到 mHashes 数组中元素为 0 的索引，不存在返回一个负数
      int index = binarySearchHashes(mHashes, N, 0);

      // 找到的 index 小于 0，说明之前没有存储过 null，直接返回 index
      if (index < 0) {
          return index;
      }

      // 根据 index 找到 mArray 中的对应 key，如果该 key 为 null，说明 index 有效，返回 index
      if (null == mArray[index<<1]) {
          return index;
      }

      // 下面两个循环是在出现 hash 冲突的时候，从左右两边寻找其他 hash 值相同的元素，看下是否有相同的元素
      int end;
      for (end = index + 1; end < N && mHashes[end] == 0; end++) {
          if (null == mArray[end << 1]) return end;
      }
      for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
          if (null == mArray[i << 1]) return i;
      }

// 找不到相同的元素，说明 null 是新的元素，返回一个负数，指示 null 的存放位置
      return ~end;
  }

indexOf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
  int indexOf(Object key, int hash) {
      final int N = mSize;

      // 当前集合为空，返回
      if (N == 0) {
          return ~0;
      }
// 二分查找，找到 mHashes 数组中元素为 hash 的索引，不存在返回一个负数
      int index = binarySearchHashes(mHashes, N, hash);

      // 找到的 index 小于 0，说明之前没有存储过该 hash，直接返回 index
      if (index < 0) {
          return index;
      }

      // 根据 index 找到 mArray 中的对应 key，如果该 key 相同，说明存在相同元素，返回 index
      if (key.equals(mArray[index<<1])) {
          return index;
      }

      // 下面两个循环是在出现 hash 冲突的时候，从左右两边寻找其他 hash 值相同的元素，看下是否有相同的元素
      int end;
      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;
  }

remove

1
2
3
4
5
6
7
8
public V remove(Object key) {
    final int index = indexOfKey(key);
    if (index >= 0) {
        return removeAt(index);
    }

    return null;
}

先找到 key 的 index，然后调用 removeAt 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
  public V removeAt(int index) {
      final Object old = mArray[(index << 1) + 1];	// 保存旧的 value
      final int osize = mSize;
      final int nsize;
      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;
	// 当容量大于 8，并且键值对数量小于容量的 1/3 时
          if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {

		// 键值对数量大于 8，n 为键值对数量的 1.5 倍
		// 键值对数量小于等于 8，n 为 8
              final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

              final int[] ohashes = mHashes;
              final Object[] oarray = mArray;
		// 收缩数组
              allocArrays(n);

              if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                  throw new ConcurrentModificationException();
              }

		// 将元素复制到新数组上
              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 {
              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;
          }
      }
      if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
          throw new ConcurrentModificationException();
      }

// 更新键值对数量，并返回旧 value
      mSize = nsize;
      return (V)old;
  }

在删除元素后，如果发现当前容量大于 8，并且剩余的键值对数量小于容量的 1/3 时，将收缩数组，如果键值对数量小于等于 8，那么新数组长度为 8；如果键值对数量大于 8，那么新数组长度为键值对数量的 1.5 倍。

get

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

它的 get 方法比较简单，得到 key 的 hash 在 mHashes 的 index 后，如果 index 大于等于 0，通过索引可以直接从 mArray 数组得到 value。如果 index 小于 0，说明不存在该元素，返回 null。

参考

-------------　　　　本文到此结束　　感谢您的阅读　　　　-------------
0%