27
2017
09

Android SparseArray与HashMap与ArrayMap的性能差别

google官方推荐,当使用HashMap时,Key值为整数类型时,建议使用SparseArray的效率更高

下面我们来见识一下SparseArray、HashMap、ArrayMap的性能区别,首先我们先看一下google官方推荐的SparseArray,SparseArray是Android的API,JDK中没有的该类。

SparseArray的源码分析:

当我们在Android中使用HashMap<Integer, String>时,我们会看到编译器会弹如下提示:

大概意思就是建议我们使用SparseArray来代替HashMap<Integer, String>

SparseArray源码:(直接在代码中讲解)

public class SparseArray<E> implements Cloneable {  
    //用于删除元素的时候使用,当删除某个元素,我们需要将int-values中的values赋值为DELETED
    private static final Object DELETED = new Object();  
    //判断此时是否需要垃圾回收(也就是数据是否需要重新整理,将数组中mValues值为DELETED的int-values从数组中删除掉)
    private boolean mGarbage = false;  

    //存储索引集合.
    private int[] mKeys;  
    //存储对象集合.
    private Object[] mValues;  
    //存储的键值对总数.
    private int mSize;  

    /** * 创建默认大小为10 * Creates a new SparseArray containing no mappings. */  
    public SparseArray() {  
        this(10);  
    }  

    /** * 初始化键值对 * Creates a new SparseArray containing no mappings that will not * require any additional memory allocation to store the specified * number of mappings. If you supply an initial capacity of 0, the * sparse array will be initialized with a light-weight representation * not requiring any additional array allocations. */  
    public SparseArray(int initialCapacity) {  
        //如果传入的值是0,则键值对都是empty,否则按照传入的值申请最初的数组大小
        if (initialCapacity == 0) {  
            mKeys = ContainerHelpers.EMPTY_INTS;  
            mValues = ContainerHelpers.EMPTY_OBJECTS;  
        } else {  
            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);  
            mKeys = new int[initialCapacity];  
            mValues = new Object[initialCapacity];  
        }  
        //键值对的总个数为0
        mSize = 0;  
    }  

    //深拷贝,创建新的空间存储这些键值对
    @Override  
    @SuppressWarnings("unchecked")  
    public SparseArray<E> clone() {  
        SparseArray<E> clone = null;  
        try {  
            clone = (SparseArray<E>) super.clone();  
            clone.mKeys = mKeys.clone();  
            clone.mValues = mValues.clone();  
        } catch (CloneNotSupportedException cnse) {  
            /* ignore */  
        }  
        return clone;  
    }  

    //通过键获取值
    /** * Gets the Object mapped from the specified key, or <code>null</code> * if no such mapping has been made. */  
    public E get(int key) {  
        return get(key, null);  
    }  

    //通过键获取值,如果没有则返回valueIfKeyNotFound
    /** * Gets the Object mapped from the specified key, or the specified Object * if no such mapping has been made. */  
    @SuppressWarnings("unchecked")  
    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];  
        }  
    }  


    //删除第key个位置的数
    /** * Removes the mapping from the specified key, if there was any. */  
    public void delete(int key) {  
        //二分查找
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  

        if (i >= 0) {  
            //确定删除的数,将其置为DELETED,然后将垃圾回收置为true
            if (mValues[i] != DELETED) {  
                mValues[i] = DELETED;  
                mGarbage = true;  
            }  
        }  
    }  

    /** * Alias for {@link #delete(int)}. */  
    public void remove(int key) {  
        delete(key);  
    }  

    /** * Removes the mapping at the specified index. */  
    public void removeAt(int index) {  
        if (mValues[index] != DELETED) {  
            mValues[index] = DELETED;  
            mGarbage = true;  
        }  
    }  

    /** * Remove a range of mappings as a batch. * * @param index Index to begin at * @param size Number of mappings to remove */  
    public void removeAtRange(int index, int size) {  
        final int end = Math.min(mSize, index + size);  
        for (int i = index; i < end; i++) {  
            removeAt(i);  
        }  
    }  

    //垃圾回收方法
    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) {  
                    //最开始我被这儿给绕了一道
                    //Java中的除基本类型以外的数据使用“=”都是引用(如果没有重写的话)
                    //所以这儿可以通过这种方式改变对象数组的值
                    keys[o] = keys[i];  
                    values[o] = val;  
                    values[i] = null;  
                }  

                o++;  
            }  
        }  

        mGarbage = false;  
        mSize = o;  

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

    //向键值对中放值
    /** * Adds a mapping from the specified key to the specified value, * replacing the previous mapping from the specified key if there * was one. */  
    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);  
            }  

            //如果数组的大小依旧大于等于初始化的大小,则申请一段mSize+1大小的数组
            if (mSize >= mKeys.length) {  
                int n = ArrayUtils.idealIntArraySize(mSize + 1);  

                int[] nkeys = new int[n];  
                Object[] nvalues = new Object[n];  

                //表示将数组mKeys从0开始复制到数组nkeys从0开始,复制的长度为mKeys的长度
                // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 
                System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);  
                System.arraycopy(mValues, 0, nvalues, 0, mValues.length);  

                mKeys = nkeys;  
                mValues = nvalues;  
            }  

            // i为插入位置,如果i<mSize,则i之后的元素需要依次向后移动一位.
            if (mSize - i != 0) {  
                // Log.e("SparseArray", "move " + (mSize - i)); 
                //将数组mKeys从i开始复制到mKeys从i+1开始,复制的长度为数组的长度减去当前插入的位置
                System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);  
                System.arraycopy(mValues, i, mValues, i + 1, mSize - i);  
            }  

            mKeys[i] = key;  
            mValues[i] = value;  
            mSize++;  
        }  
    }  

    /** * Returns the number of key-value mappings that this SparseArray * currently stores. */  
     //返回数据的大小
    public int size() {  
        if (mGarbage) {  
            gc();  
        }  

        return mSize;  
    }  

    /** * Given an index in the range <code>0...size()-1</code>, returns * the key from the <code>index</code>th key-value mapping that this * SparseArray stores. * * <p>The keys corresponding to indices in ascending order are guaranteed to * be in ascending order, e.g., <code>keyAt(0)</code> will return the * smallest key and <code>keyAt(size()-1)</code> will return the largest * key.</p> */  
     //返回当前第index个值的键是多少
    public int keyAt(int index) {  
        if (mGarbage) {  
            gc();  
        }  

        return mKeys[index];  
    }  

    /** * Given an index in the range <code>0...size()-1</code>, returns * the value from the <code>index</code>th key-value mapping that this * SparseArray stores. * * <p>The values corresponding to indices in ascending order are guaranteed * to be associated with keys in ascending order, e.g., * <code>valueAt(0)</code> will return the value associated with the * smallest key and <code>valueAt(size()-1)</code> will return the value * associated with the largest key.</p> */  
     //返回当前index位置的值是多少
    @SuppressWarnings("unchecked")  
    public E valueAt(int index) {  
        if (mGarbage) {  
            gc();  
        }  

        return (E) mValues[index];  
    }  

    /** * Given an index in the range <code>0...size()-1</code>, sets a new * value for the <code>index</code>th key-value mapping that this * SparseArray stores. */  
     //给index位置的值设置为value
    public void setValueAt(int index, E value) {  
        if (mGarbage) {  
            gc();  
        }  

        mValues[index] = value;  
    }  

    /** * Returns the index for which {@link #keyAt} would return the * specified key, or a negative number if the specified * key is not mapped. */  
     //返回键为key的位置
    public int indexOfKey(int key) {  
        if (mGarbage) {  
            gc();  
        }  

        return ContainerHelpers.binarySearch(mKeys, mSize, key);  
    }  

    /** * Returns an index for which {@link #valueAt} would return the * specified key, or a negative number if no keys map to the * specified value. * <p>Beware that this is a linear search, unlike lookups by key, * and that multiple keys can map to the same value and this will * find only one of them. * <p>Note also that unlike most collections' {@code indexOf} methods, * this method compares values using {@code ==} rather than {@code equals}. */  
     //返回值为value的位置
    public int indexOfValue(E value) {  
        if (mGarbage) {  
            gc();  
        }  

        for (int i = 0; i < mSize; i++)  
            if (mValues[i] == value)  
                return i;  

        return -1;  
    }  

    /** * Removes all key-value mappings from this SparseArray. */  
     //清除当前键值对
    public void clear() {  
        int n = mSize;  
        Object[] values = mValues;  

        for (int i = 0; i < n; i++) {  
            values[i] = null;  
        }  

        mSize = 0;  
        mGarbage = false;  
    }  

    /** * Puts a key/value pair into the array, optimizing for the case where * the key is greater than all existing keys in the array. */  
     //在数组中插入键值对
    public void append(int key, E value) {  
        if (mSize != 0 && key <= mKeys[mSize - 1]) {  
            put(key, value);  
            return;  
        }  

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

        int pos = mSize;  
        if (pos >= mKeys.length) {  
            int n = ArrayUtils.idealIntArraySize(pos + 1);  

            int[] nkeys = new int[n];  
            Object[] nvalues = new Object[n];  

            // Log.e("SparseArray", "grow " + mKeys.length + " to " + n); 
            System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);  
            System.arraycopy(mValues, 0, nvalues, 0, mValues.length);  

            mKeys = nkeys;  
            mValues = nvalues;  
        }  

        mKeys[pos] = key;  
        mValues[pos] = value;  
        mSize = pos + 1;  
    }  

    /** * {@inheritDoc} * * <p>This implementation composes a string by iterating over its mappings. If * this map contains itself as a value, the string "(this Map)" * will appear in its place. */  
     //返回键值对
    @Override  
    public String toString() {  
        if (size() <= 0) {  
            return "{}";  
        }  

        StringBuilder buffer = new StringBuilder(mSize * 28);  
        buffer.append('{');  
        for (int i=0; i<mSize; i++) {  
            if (i > 0) {  
                buffer.append(", ");  
            }  
            int key = keyAt(i);  
            buffer.append(key);  
            buffer.append('=');  
            Object value = valueAt(i);  
            if (value != this) {  
                buffer.append(value);  
            } else {  
                buffer.append("(this Map)");  
            }  
        }  
        buffer.append('}');  
        return buffer.toString();  
    }  
}

SparseArry结构图解:

SparseArray只能存储当键为int的键值对,通过源码我们可以看到这儿键是int而不是Integer,所以SparseArray提高效率的方式是去箱的操作,因为键是int型数据,所以就不需要hash值的方式来存储数据,插入和查询都是通过二分查找的方式进行,插入数据时可能会存在大量的数据搬移。但是它避免了装箱,所以这时就要看数据量的大小来对比时间的快慢,如果数据少,即使数据搬移也不会很多,所以效率上SparseArray比HashMap要好,空间上装箱过后的Integer要比int占的空间要大,所以空间效率上SparseArray要比HashMap好!

HashMap结构图解:

HashMap的数据结构:

static class HashMapEntry<K, V> implements Entry<K, V> {    
    //键
    final K key;    
    //值
    V value; 
    //键生成的hash值
    final int hash;   
    //如果Hash值一样,则它下一个键值对
     HashMapEntry<K, V> next;
}

从数据结构中我们可以看出首先对key值求Hash值,如果该Hash值在Hash数组中不存在,则添加进去,如果存在,则跟着Hash值的链表在尾部添加上这个键值对,在时间效率方面,使用Hash算法,插入和查找的操作都很快,每个数组后面一般不会存在很长的链表,所以不考虑空间利用率,HashMap的效率是非常高的

ArrayMap的结构图解

当插入时,根据key的hashcode()方法得到hash值,计算出在mArrays的index位置,然后利用二分查找找到对应的位置进行插入,当出现哈希冲突时,会在index的相邻位置插入。
空间角度考虑,ArrayMap每存储一条信息,需要保存一个hash值,一个key值,一个value值。对比下HashMap 粗略的看,只是减少了一个指向下一个entity的指针。
时间效率上看,插入和查找的时候因为都用的二分法,查找的时候应该是没有hash查找快,插入的时候呢,如果顺序插入的话效率肯定高,但如果是随机插入,肯定会涉及到大量的数组搬移,数据量大,肯定不行,再想一下,如果是不凑巧,每次插入的hash值都比上一次的小,那就得次次搬移,效率一下就扛不住了的感脚。

参考资料:

  1. HashMap,ArrayMap,SparseArray源码分析及性能对比
  2. Android内存优化(使用SparseArray和ArrayMap代替HashMap)
  3. Android 之Map容器替换 SparseArray,ArrayMap,ArraySet
  4. Android学习笔记之性能优化SparseArray
  5. SparseArray 的使用及实现原理
  6. SparseArray源码解析
  7. Android SparseArray源码分析
上一篇:Android 自定义空数据提示界面 EmptyView 下一篇:142. Linked List Cycle II。