HashMap、ArrayMap和SparseArray解析

2022-10-08 本文已影响0人就叫汉堡吧

HashMap

put方法

HashMap中会维护一个hash表：

transient Node<K,V>[] table;

put方法会调用putVal方法，传入通过key生成的hashCode，putVal方法中，首先会先判断hash表是否存在，否则则创建它：

Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

可见tab在resize方法中创建：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果之前存在hash表，则先判断是否大于最大容量，若是则扩大至Interger的最大值，否则扩大一倍
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //如果之前存在过但是又全部删除了，则使用之前的容量值作为再次创建的容量，这是尝试复用上次容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //如果是初次创建，则使用默认大小
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //如果不是第一次创建，则扩容后需要变更新的起始点（即newCap-1），所以需要重新整理链表
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

在这个方法中，我们整理出以下几点：

首先，扩容的新容量会有四种变化，一种是需要大于最大容量时会被赋值成整型的最大值，因为这种情况下猜测场景需要很多容量；第二种是之前创建过table但是又清空了的话会使用之前容量的75%的容量作为此次的最新扩容容量，这是猜测当前场景和上次的没有变化而采用的复用逻辑，如果场景没变，则在超过之前场景最大容量的75%之前都不需要花时间去扩容，因为场景没变，所以很可能这些容量空间都会被使用，所以也不存在浪费空间；第三种是未超过默认最大容量的情况下扩容，此时会扩容一倍；最后一种是初次创建时采用默认初始容量。
因为链表的头节点使用的是(n-1)&hash，所以扩容后n会发生变化，因此如果table之前已存在且有数据的话，则需要重新整理链表的连接顺序。
上面的讲到第一点中第二种情况时为什么说是75%呢，因为DEFAULT_LOAD_FACTOR是0.75，newThr会被保存到threshold，这个值只在resize()方法中会变化，在put的时候会被拿来和元素个数比较：
```
if (++size > threshold)
    resize();
```
说明元素个数在增长到最大容量75%的时候就会引起扩容了，当然，你可以通过构造时传入一个loadFactor can参数来自定义。

回到putVal方法，接下来：

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

这一步是找到头节点，头节点的索引方式是(n-1)&hash，如果头节点为空，则说明没有数据，直接创建一个头节点。

你可能会疑问(n-1)&hash不会数据越界吗？不会！因为n-1和任何数值进行相与操作都不会大于n-1，更不会小于0，所以大可放心。

还有一点就是，hash是通过底层接口按照内存地址生成的“唯一”码，为什么要加引号，是因为算法的原因可能会出现使不同的对象生成相同的hash码的情况，因此它并不是很保险。

如果(n-1)&hash下标取得的值不为空的话：

Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

这里首先判断hash值是否一样，如果一样的话再判断key的内存地址是否相同或对key进行equals比较是否相同，都符合的话则表示之前存在相同的节点，只需要更新之前节点的value即可。这里也能看出来hash作为唯一判断并不保险。

然后，会循环找到最后一个节点，然后把新Node加到它的后面：

for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

可见，get方法也是从头节点开始一个一个的找目标节点，再取出它的value。

ArrayMap

ArrayMap中有三个字段，mHashes存放key的hash值，mArray存放key和value。mArray中的数量是键值对数量的两倍，因为mArray数组中同时保存了key和value，每一对的key和value都相邻。

put方法

ArrayMap实现了Map接口，自然也有put方法。

首先，根据key是否为空有两段不同的逻辑：

if (key == null) {
    hash = 0;
    index = indexOfNull();
} else {
    hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
    index = indexOf(key, hash);
}

其实indexOfNull和indexOf方法是几乎一样的逻辑：

final int N = mSize;

if (N == 0) {
    return ~0;
}

int index = binarySearchHashes(mHashes, N, 0);
//这是indexOf不同的地方
//int index = binarySearchHashes(mHashes, N, hash);

if (index < 0) {
    return index;
}

//这是indexOf不同的地方
//if (key.equals(mArray[index<<1])) {  
if (null == mArray[index<<1]) {
    return index;
}

// 为了防止hash值出现多个相同的，再一次检索
// 查找index的前半部分元素
int end;
for (end = index + 1; end < N && mHashes[end] == 0; end++) {
    if (null == mArray[end << 1]) return end;
}

// 查找index的后半部分元素
for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
    if (null == mArray[i << 1]) return i;
}

return ~end;

可见，不管是indexOf还是indexOfNull方法，都是先从mHashes中按照hash值找到index，因为在put中mArray使用同一个index做操作来生成下标，所以这里也使用同一个index来取。

mArray存放的规则是index<<1的位置保存key，(index<<1)+1的位置保存value，也就是mArray中紧靠的每一对都是一组key-value，比如(0,1)、(2,3)、(4,5)等，可这样一来不就越界了吗，其实在put方法中，如果需要扩容，则扩容后在allocArrays方法中都会重新定义mArray，它的大小会被设置为mSize的两倍，正好用来盛放key和value。

新建或扩容后会首先把之前的mHashes和mArray中index之前的部分拷贝到新的mHashed和mArray中，然后判断如果index不是最后一个，则再把index之后的元素放到对应的index+1之后的位置上：

//前面的indexOf方法或者indexOfNull方法如果没找到的话则会对最后一个空位置的下标取反再返回，这里取反得到就是该下标，即需要放置新元素的位置
index = ~index;
if (osize >= mHashes.length) {
    final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
            : (osize >= 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 (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }

    if (mHashes.length > 0) {
        if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
        System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
        System.arraycopy(oarray, 0, mArray, 0, oarray.length);
    }

    freeArrays(ohashes, oarray, osize);
}

if (index < osize) {
    if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
            + " to " + (index+1));
    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++;

get方法

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

public int indexOfKey(Object key) {
    return key == null ? indexOfNull()
             : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}

取值的方法也是通过indexOf和indexOfNull方法来获取的。

SparseArray

put方法

public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

SparseArray是一个仿Map数据结构，它的内部没有维护hash值，只有mKeys和mValues两个数组，它也使用二分查找目标元素，如果没查到，同样会返回最后一个下标的取反值，这里再次取反拿到下标值，然后分别把key和value放到mKeys和mValues中：

static int binarySearch(int[] array, int size, int value) {
    int lo = 0;
    int hi = size - 1;

    while (lo <= hi) {
        final int mid = (lo + hi) >>> 1;
        final int midVal = array[mid];

        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            return mid;  // value found
        }
    }
    return ~lo;  // value not present
}

GrowingArrayUtils.insert内部和ArrayMap中的处理一样，都是new一个新数组，然后把旧数组的元素拷贝进去：

public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    assert currentSize <= array.length;

    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }

    @SuppressWarnings("unchecked")
    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
            growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

get方法

get方法同样很简单：

public E get(int key, E valueIfKeyNotFound) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

其他类型的SparseArray

SparseArray中的mKeys和mValues都是Object类型，为了省略装箱拆箱和类型转换，还有针对不同类型的SparseArray，比如SparseIntArray、SparseBooleanArray、SparseDoubleArray等。

总结

通过以上的分析，我们可以总结出它们的优缺点。

HashMap的链表结构查询需要从头节点开始逐一查询，因此查找速度很慢，但HashMap也可以通过TreeNode实现二分查找，但是HashMap中的每个元素都封装成一个Node，这在拆解的时候也会多一步而影响速度。优点是在插入的时候不需要移动元素的位置，只需要断开上下节点的连接然后重新连接即可，但是还是需要从头节点开始检索先找到目标位置，因为它是根据key来遍历找到对应Node的。总之，虽然HashMap是用数组来存放Node，但是每次添加新元素都会添加到数组的最后，然后通过每个节点的指针来确定顺序，解决了链表结构插入或删除会导致大量元素移动的问题，但是正因为这个，读取的时候会从头节点开始遍历整个链表，从而失去了数组的读取优势。

ArrayMap丢弃了链表结构，把Hash提取成一个数组，而不是放在Node中，这样一来，就可以直接通过查询Hash数组来拿到下标，同样Key和Value会放在mArray数组中，可见，这样一来，读取元素只需要按照下标读取即可，这样可以把数组内存地址连续的优势体现出来。这样做带来的缺点就是插入的时候需要新建数组且需要移动所有元素的位置（如果插入的位置不是最后一个的话），而且数组是连续的内存结构，这就会导致有很多空间可能被浪费（指的是扩容的标准不是按照刚好来扩的，因为考虑到扩容动作本身也是消耗性能的），这是使用数组结构的通病。

SparseArray同样使用数组来实现，和ArrayMap不同的是，它去掉了Hash数组，这样一来，就省掉了key.equals方法的判断，因为SparseArray的mKeys数组是int数组，所以它直接通过比较大小进行二分查找，由于也是使用数组，所以同样具有读取效率高的优势，但也因此执行插入或删除操作会引起两个数组元素元素的移动，SparseArray要和ArrayMap做对比，Hash的意义在于通过算法把不同类型的key值转化成占用内存少的类型，去掉Hash自然省略了算法转换时间，但是因此原类型作为key会增加内存容量。此外，SparseArray还有很多兄弟类针对特定类型的数据存储。

HashMap、ArrayMap和SparseArray解析

HashMap

put方法

get方法

ArrayMap

put方法

get方法

SparseArray

put方法

get方法

其他类型的SparseArray

总结

猜你喜欢

热点阅读