转载

内存优化（使用SparseArray和ArrayMap代替HashMap）

HashMap

关于HashMap的知识请看这篇优秀文章:http://tryenough.com/java-hashmap

SparseArray

SparseArray 的使用

创建

SparseArray 有两个构造方法，一个默认构造方法，一个传入容量。

SparseArray sparseArray = new SparseArray<>();
SparseArray sparseArray = new SparseArray<>(capacity);

首先来看看如何创建一个 SparseArray ，而 SparseArray 只需要指定一个泛型表示value类型，而 key 的类型在 SparseArray 内部已经指定了为int类型

put()

看看怎么往里面存放数据吧

sparseArray.put(int key,Student value);

put() 就跟 HashMap 的使用方法一样。

get()

sparseArray.get(int key);
sparseArray.get(int key,Student valueIfNotFound);

SparseArray 实现原理

简介：

用int[]数组存放key，避免了HashMap中基本数据类型需要装箱的步骤，其次不使用额外的结构体（Entry)，单个元素的存储成本下降。

要理解SparseArray 的实现原理，需要看代码：

SparseArray用两个数组来存放key和value：

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

key的存放按照从小到大的顺序，这样就能保证使用二分查找，而SparseArray内部查找数据也就是使用的二分查找，这样查找的效率比较高。我们来看下put方法，就能大概理解SparseArray的原理了：

//参数是传进来的 int类型的key 和 范形的value 
public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  //使用二分查找寻找key应该在的位置，具体实现请先看下面的讲解

        if (i >= 0) {
            mValues[i] = value;  //如果寻找到lo就直接覆盖value
        } else {
            i = ~i;

            if (i < mSize && mValues[i] == DELETED) { //如果没有找到，并且返回的数组索引对应的值是DELETED那就直接覆盖value
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }

            if (mGarbage && mSize >= mKeys.length) { //如果当前数组已满，检查数组中是否有DELETED的值，然后将其删除gc的操作：可查看下面具体源码
                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++;
        }
    }

二分查找

//这里传递过来的value是上面的key
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 找到，直接返回key的索引
            }
        }
        return ~lo;  // 没有找到就直接返回最终lo的取反值，此时的lo值就正好是排好序的lo
    }

gc：

private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);

        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;

        for (int i = 0; i < n; i++) {
            Object val = values[i];

            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }

                o++;
            }
        }

        mGarbage = false;
        mSize = o;

        // Log.e("SparseArray", "gc end with " + mSize);
    }

总结：

SparseArray的优点：

避免了基本数据类型的装箱操作

不需要额外的结构体，单个元素的存储成本更低

数据量小的情况下，随机访问的效率更高

SparseArray的缺点：

插入操作需要复制数组，增删效率降低

数据量巨大时，复制数组成本巨大，gc()成本也巨大

数据量巨大时，查询效率也会明显下降

ArrayMap的原理

ArrayMap是一个<key,value>映射的数据结构，它设计上更多的是考虑内存的优化，内部是使用两个数组进行数据存储，一个数组记录key的hash值，另外一个数组记录Value值，它和SparseArray一样，也会对key使用二分法进行从小到大排序，在添加、删除、查找数据的时候都是先使用二分查找法得到相应的index，然后通过index来进行添加、查找、删除等操作，所以，应用场景和SparseArray的一样，如果在数据量比较大的情况下，那么它的性能将退化至少50%。

总结：

假设数据量都在千级以内的情况下：

 1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用
 2、如果key类型为其它的类型，则使用ArrayMap

热度: 12

原文 https://tryenough.com/java-sparseArray

正文到此结束

所属分类：编程技术 Java

本文标签： map 总结 tar final 构造方法参数索引 https value HashMap 源码 key id java parse 文章代码删除数据 http
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

内存优化（使用SparseArray和ArrayMap代替HashMap）

HashMap

SparseArray

SparseArray 的使用

创建

put()

get()

SparseArray 实现原理

ArrayMap的原理

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流