Java - HashMap VS ArrayMap VS SparseArray

HashMap

基于哈希表的 Map 接口实现。此实现提供了所有可选的映射操作，并允许空 value 和空 key。（HashMap 类大致相当于 Hashtable，只不过它是不同步的并且允许 null。）
该类不保证映射的顺序；特别是，它不保证顺序随着时间的推移保持不变。

该实现为基本操作（get 和 put）提供恒定时间性能，假设 hash 函数将元素正确地分散在 bucket 中。迭代集合视图所需的时间与 HashMap 实例的 “capacity”（bucket 的数量）加上其大小（key-value 映射的数量）成正比。
因此，如果迭代性能很重要，那么不要将初始 capacity 设置得太高（或 load factor 太低），这一点非常重要。

HashMap 实例有两个影响其性能的参数：初始 capacity 和 load factor。 capacity 是 hash table 中 bucket 的数量，初始 capacity 就是创建 hash table 时的 capacity。
load factor 是衡量 hash table 在其 capacity 自动增加之前允许达到的满度的指标。当 hash table 中的条目数超过 load factor 与当前 capacity 的乘积时，hash table 将被重新哈希（即重建内部数据结构），使得 hash table 的 bucket 数大约为两倍。

作为一般规则，默认 load factor (0.75) 在时间和空间成本之间提供了良好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。
在设置其初始 capacity 时应考虑映射中的预期条目数及其 load factor，以尽量减少重新哈希操作的次数。如果初始 capacity 大于最大条目数除以 load factor，则不会发生重新哈希操作。

如果要在 HashMap 实例中存储许多映射，那么创建一个足够大的 capacity 将允许更有效地存储映射，而不是让它根据需要执行自动重新哈希来增长表。
请注意，使用具有相同 hashCode() 的多个 key 肯定会降低任何哈希表的性能。为了减轻影响，当 key 是 Comparable 时，此类可以使用 key 之间的比较顺序来帮助打破平局。

请注意，此实现不是同步的。如果多个线程同时访问 hash map，并且至少有一个线程在结构上修改了该 map，则必须进行外部同步。（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的 key 关联的 value 不是结构修改。）
这通常是通过在自然封装映射的某个对象上进行同步来完成的。如果不存在这样的对象，则应使用 Collections.synchronizedMap 方法“包装”映射。最好在创建时完成此操作，以防止意外地不同步访问 map：

1	Map m = Collections.synchronizedMap(new HashMap(...));

此类的所有“集合视图方法”返回的 iterator 都是快速失败的：如果在创建 iterator 后的任何时间对 map 进行结构修改，除了通过 iterator 自己的删除方法之外的任何方式，iterator 都会抛出 ConcurrentModificationException 。
因此，面对并发修改，iterator 会快速而干净地失败，而不是在未来不确定的时间冒任意、非确定性行为的风险。

请注意，iterator 的快速失败行为无法得到保证，因为一般来说，在存在不同步并发修改的情况下不可能做出任何硬保证。快速失败 iterator 会尽力抛出 ConcurrentModificationException。因此，编写依赖于此异常来确保其正确性的程序是错误的： iterator 的快速失败行为应该仅用于检测错误。

初始化

transient Node<K,V>[] table;

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

添加

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            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;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

ArrayMap

ArrayMap 是一种通用的 key -> value 映射数据结构，其设计比传统的 HashMap 具有更高的内存效率。
它将映射保存在数组数据结构中——每个 item 的哈希码的整数数组，以及 key/value 对的对象数组。
这使得它可以避免为放入 map 中的每个条目创建一个额外的对象，并且它还尝试更积极地控制这些数组大小的增长（因为增长它们只需要复制数组中的条目，而不需要重建哈希映射）。

请注意，此实现并不适合可能包含大量 item 的数据结构。它通常比传统的 HashMap 慢，因为查找需要二分搜索，添加和删除需要在数组中插入和删除条目。对于容纳数百个 item 的容器，性能差异并不显着，小于 50%。

由于此容器旨在更好地平衡内存使用，因此与大多数其他标准 Java 容器不同，当从中删除 item 时，它会缩小其数组。目前无法控制这种缩小 - 如果设置 capacity 然后删除 item，则可能会减少 capacity 以更好地匹配当前大小。将来，设置 capacity 的显式调用应该会关闭这种激进的收缩行为。

该结构不是线程安全的。

初始化

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


public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;

    // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
    // instance instead of the usual EmptyArray.INT. The reference
    // is checked later to see if the array is allowed to grow.
    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;
}

添加

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();
        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 (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);
    }

    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
        if (osize != mSize || index >= mHashes.length) {
            throw new ConcurrentModificationException();
        }
    }
    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;
    }

    int index = binarySearchHashes(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.
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // 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;
}

查找

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

SparseArray

SparseArray 将整数映射到对象，与普通的对象数组不同，它的索引可以包含间隙。 SparseArray 旨在比 HashMap 更节省内存，因为它避免了自动装箱键，并且其数据结构不依赖于每个映射的额外条目对象。

请注意，此容器将其映射保存在数组数据结构中，使用二分搜索来查找 key。该实现并不适合可能包含大量项目的数据结构。它通常比 HashMap 慢，因为查找需要二分搜索，并且添加和删除需要在数组中插入和删除条目。对于容纳数百个 item 的容器，性能差异小于 50%。

为了提高性能，容器在删除 key 时进行了优化：它不会立即压缩其数组，而是将删除的条目标记为已删除。然后，该条目可以重新用于相同的 key，或者稍后在所有已删除条目的单个垃圾收集中进行压缩。
每当数组需要增长时，或者当检索 map 大小或条目值时，都必须执行此垃圾收集。

可以使用 keyAt(int) 和 valueAt(int) 迭代此容器中的 item。使用 keyAt(int) 和索引的升序值迭代 key 会按升序返回 key。在 valueAt(int) 的情况下，与 key 对应的值按升序返回。

初始化

private int[] mKeys;
private Object[] mValues;
private int mSize;


public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

添加

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++;
    }
}

查找

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];
    }
}