您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

SparseArray源码分析与性能优化

开发技术 481℃ 0 9个月前 (03-03)

摘要

SparseArray是Android提供的数据结构,在某些场景下可以替代HashMap实现更好的性能。SparseArray在Android Java Framework源码中有大量使用。

Spa

SparseArray是Android提供的数据结构,在某些场景下可以替代HashMap实现更好的性能。SparseArray在Android Java Framework源码中有大量使用。

SparseArray系列主要有:

  • SparseBooleanArray
  • SparseIntArray
  • SparseLongArray
  • SparseArray
  • LongSparseArray

SparseBooleanArray,SparseIntArray,SparseLongArray

这三者的代码几乎相同,都是int型的key,区别在于value分别是boolean、int、long型。

关键源码

以SparseIntArray为例分析,关键代码如下。

public class SparseIntArray {
    private int[] mKeys;
    private int[] mValues;
    private int mSize;

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

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

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

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

        if (i < 0) {
            return valueIfKeyNotFound;
        } else {
            return mValues[i];
        }
    }

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

        if (i >= 0) {
            removeAt(i);
        }
    }

    public void removeAt(int index) {
        System.arraycopy(mKeys, index + 1, mKeys, index, mSize - (index + 1));
        System.arraycopy(mValues, index + 1, mValues, index, mSize - (index + 1));
        mSize--;
    }

    public int size() {
        return mSize;
    }
}

class ContainerHelpers {
    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
    }
}

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

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

        int[] newArray = new int[growSize(currentSize)];
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index + 1, array.length - index);
        return newArray;
    }

    public static int growSize(int currentSize) {
        return currentSize <= 4 ? 8 : currentSize * 2;
    }
}

分析

SparseIntArray中有两个数组mKeys和mValues,分别保存对应的key和value,mSize用于保存数量。

二分法

Key在数组中按顺序插入,put、get、delete,都调用ContainerHelpers.binarySearch,使用二分法查找Key所在的Index。

  • 如果找到了Key,则返回index,index的值大于等于0。
  • 如果没找到,则返回lo按位取反后的结果,返回值是小于0的。对于put方法,此时的lo刚好是Key应该插入的位置。

get方法

  • 找到了Key则直接返回对应Value,没找到则返回valueIfKeyNotFound

put方法

  • 找到了Key则直接覆盖对应的value,没找到则将binarySearch返回的值取反得到lo的原始值,再调用GrowingArrayUtils.insert,将后面的数据往后移动一位,给新数据腾出位置,并在lo的位置插入新的数据。如果容量不够,则会重新分配内存扩大容量。

delete方法

  • 找到了Key,则直接调用System.arraycopy将后面的数据往前移动一位。

SparseArray,LongSparseArray与性能优化

前面三种API保存的都是boolean、int、long基本类型,而SparseArray和LongSparseArray都支持泛型,返回任意类型的数据,并且在SparseIntArray的基础上做了性能优化

关键源码

SparseArray的Key是int型,而LongSparseArray的Key是long型。这里以SparseArray为例分析。

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;

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

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

    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 void delete(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }

    public int size() {
        if (mGarbage) {
            gc();
        }

        return mSize;
    }

    private void gc() {
        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;
    }
}

分析

还是mKeymValues数组保存Key和Value,还是实用二分法查找Key的位置。但是多了一个优化逻辑。

在SparseArray中:

  • Value数组中保存的可能是有效数据,也可能是固定的DELETED对象,下面简称为无效数据

  • mSize并不是有效数据的数量,而是有效数据+无效数据的总数量。

  • mGarbage标志位,表示Value数组中是否包含了无效数据(准确来说是Value数组中0 ~ mSize-1的区间)。

delete方法

  • 在SparseIntArray中,删除元素操作会立即删除元素,将后面的数据往前挪,并改变mSize
  • 在SparseArray中,删除数据并不会立即删除,而是将数据标记为已删除。具体的做法是将Value设置为固定的DELETED对象,同时还会设置标志位mGarbage(这个标记删除的思路,有点像文件系统中删除文件的操作)。

get方法

  • 如果二分法找到了Key,同时对应的Value为有效数据,则返回Value。

put方法

  • 如果二分法找到了Key,无论Value是否为有效数据,都直接覆盖掉。
  • 如果没找到Key,则获取插入位置。如果碰巧这个位置保存的是无效数据,则直接覆盖Key和Value为新数据即可。
  • 如果已经获取插入位置,该位置已经被有效数据占据,Value数组中包含了无效数据(mGarbage==true),且已经存不下新数据了(mSize >= mKeys.length),则调用gc方法,将无效数据从数组中清理掉,然后重新搜索应该插入的位置。
  • 最后,和SparseIntArray的逻辑一样,移动后面的数据,给新数据腾出位置并插入。

size方法

  • SparseArray中的mSize保存的是有效数据+无效数据总数量,而不是有效数据的数量,因此在调用size方法时,也会触发gc,清理无效数据,并得到真实的Size。

gc方法

gc方法的实现比较简单,使用双指针的思路:

  • 指针i在数组中遍历一遍,指针o每次遇到有效数据就自增,并将Key和Value从位置i复制到位置o
  • 为了防止内存泄露,还有一句values[i] = null,将原始位置的重复引用清除掉。
  • 移动完成后,清除mGarbage标志,并修改mSize的值,因为此时已经没有无效数据了,mSize的值就等于有效数据的数量。

进一步优化点

在put方法触发gc的分支中,需要经过四步操作:

  • 二分搜索
  • gc
  • 重新二分搜索
  • 给新数据腾出空间并插入

实际上可以对这个分支进行优化,将后面的三步合并,只需要遍历一遍就可以同时实现gc和插入操作。

SparseArray性能分析

这里主要是对比HashMap和SparseArray / LongSparseArray,在处理int/long --> Object这种映射时的性能。

SparseArray的优势

  • 避免了HashMap中对于一些基本类型的装箱拆箱操作,对CPU和内存性能都会有提高。
  • 保存Value只需要数组,存储单个元素的成本更低。而HashMap比较复杂,需要用到Node,Node中包含了额外变量。
  • 对于Key的数量可以提前明确的情况,SparseArray可以设置刚好合适的容量,节省内存。而HashMap很难保证Key的哈希值刚好均匀分布,因此通常需要让容量比Key的数量更多,才能保持较好的时间性能。
  • SparseArray数据遍历速度比HashMap快,因为是直接数组操作,而HashMap是数组+链表,逻辑比较复杂。
  • HashMap在容量不足、Key发生哈希冲突的情况下,需要遍历链表逐个对比Key,就没有SparseArray的二分法速度快了。

SparseArray的缺点

  • 如果Key较多并且不能提前确定或变动频繁,SparseArray的数组就会很庞大,而插入、删除时又很容易触发移动、扩容操作,性能就会非常差。
  • HashMap在Key发生哈希冲突很少的情况下,计算hashCode比SparseArray的二分法性能更好。

使用SparseArray的建议

在SparseArray的JavaDoc中已经说明了,SparseArray并不是设计用来保存大量数据的,更适合数据较少的情况,能节省内存。

SparseArray首次插入某个Key时,如果按照Key从小到大插入,性能会很好,每次都会在数组尾部插入新数据。但是反过来性能就会很差,因为需要频繁移动已有数据。因此如果Key的取值很不稳定,忽大忽小,使用SparseArray效果可能就比较差了。

如果Key是提前明确的,建议使用SparseArray。初始化时可以指定SparseArray的容量,还可以提前按照Key从小到大的顺序,调用SparseArray.append方法预先存放到SparseArray中,之后使用时就不会触发移动、扩容操作了。

举例:

  • RecyclerView中按照ViewType缓存ViewHolder,使用了SparseArray。一般来说ViewType不会很多。

  • 用后台返回的id作为Key,保存较多Object。因为id的取值范围很大,其值的大小也不确定,因此SparseArray的性能不佳。

  • 使用RecyclerView的position为Key,给每个Item缓存数据(例如从本地或者网络加载数据)。这种场景适合SparseArray,一般来说,首次插入某个Key时,刚好是接近从小到大的顺序获取到数据的。

最后,欢迎扫码关注微信公众号。微软 / Shopee / Coupang / BAT等国内外企业内推、行业和技术交流,也可以加我微信 jzj2015(注明来自博客),拉你进技术群。

本文由原创,转载请注明来源:https://www.paincker.com/sparse-array
(标注了原文链接的文章除外)

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?