SparseArray 的使用及实现原理

傷城~ 2022-10-05 05:46 190阅读 0赞

#### 一、SparseArray出现的背景 ####

相信大家都用过HashMap用来存放键值对，最近在项目中使用HashMap的时候发现，有时候 IDE 会提示我这里的HashMap可以用SparseArray或者SparseIntArray等等来代替。  
细心的朋友可能也发现了这个提示，并且会发现并不是所有的HashMap都会提示替换。今天就来一探究竟，到底SparseArray跟HaspMap相比有什么优缺点，又是在什么场景下来使用的呢？

#### 二、SparseArray 的使用 ####

##### 1、创建 #####

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

首先来看看如何创建一个SparseArray，前文说了SparseArray是用来替换HashMap的，而SparseArray只需要指定一个泛型，似乎说明key的类型在SparseArray内部已经指定了呢？  
SparseArray有两个构造方法，一个默认构造方法，一个传入容量。

##### 2、put() #####

sparseArray.put(int key,Student value);

原来SparseArray存放的键值对中的键是int型的数据，为什么呢？后面分析源码的时候再讲。

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

##### 3、get() #####

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

##### 4、index #####

前面几个都跟HashMap没有什么太大区别，而这个index就是SparseArray所特有的属性了，这里为了方便理解先提一嘴，SparseArray从名字上看就能猜到跟数组有关系，事实上他底层是两条数组，一组存放key，一组存放value，知道了这一点应该能猜到index的作用了。  
index — key在数组中的位置。SparseArray提供了一些跟index相关的方法：

sparseArray.indexOfKey(int key);
    sparseArray.indexOfValue(T value);
    sparseArray.keyAt(int index);
    sparseArray.valueAt(int index);
    sparseArray.setValueAt(int index);
    sparseArray.removeAt(int index);
    sparseArray.removeAt(int index,int size);

#### 三、SparseArray 实现原理 ####

前面简单的介绍了 SparseArray 的使用，为了在实际工作中最合理的选用数据结构，深入的了解每种数据结构的实现原理是很有必要的，这样可以更好的理解和比较不同数据结构之间的优缺点，比死记概念要更好，甚至可以根据自己的具体需求去实现最适合需求的数据结构。

> SparseArrays map integers to Objects. Unlike a normal array of Objects,there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Objects, both because it avoids auto-boxing keys and its data structure doesn’t rely on an extra entry object for each mapping.

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

##### 1、put源码解析 #####

/** * 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);
             }
    
             mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
             mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
             mSize++;
         }
     }

插入的逻辑大概就这几点：

*  存放key的数组是有序的（二分查找的前提条件）
 *  如果冲突，新值直接覆盖原值，并且不会返回原值（HashMap会返回原值）
 *  如果当前要插入的 key 的索引上的值为DELETE，直接覆盖
 *  前几步都失败了，检查是否需要gc()并且在该索引上插入数据

#### 四、总结 ####

了解了SparseArray的实现原理，就该来总结一下它与HashMap之间来比较的优缺点

##### 1、优势： #####

*  避免了基本数据类型的装箱操作
 *  不需要额外的结构体，单个元素的存储成本更低
 *  数据量小的情况下，随机访问的效率更高

##### 2、缺点 #####

*  插入操作需要复制数组，增删效率降低
 *  数据量巨大时，复制数组成本巨大，gc()成本也巨大
 *  数据量巨大时，查询效率也会明显下降