Java中HashMap和SparseArray的数据结构

浏览数：43 / 时间：2015年06月08日

最近听同事说使用SparseArray代替HashMap可以提高性能，于是边对这两个类的数据结构进行简单的分析。

Hashmap的数据结构

Hashmap是一个数组和链表的结合体（在数据结构称“链表散列“），如下图示：

技术分享

图片来源：Java的HashMap和HashTable

SparseArray的数据结构

SparseArray指的是稀疏数组(Sparse array)，为了节省内存空间，并且不影响数组中原有的内容值。其内部有两个关键成员，分别是mKeys和mValues, 都是数组，如下所示：

查看其 put(int key, E value),如下：

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是android里为<Interger,Object>这样的Hashmap而专门写的类, 其核心是折半查找函数（binarySearch），这样可以加快查找效率，但有数据插入或删除时，效率不见得高。内存效率应该和HashMap差不多，不能直观判断出好坏，需要分情况讨论。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java中HashMap和SparseArray的数据结构