1, Background of SparseArray

I believe everyone has used HashMap to store key value pairs. Recently, when using HashMap in the project, I found that sometimes the IDE will prompt me that the HashMap here can be replaced by SparseArray or SparseIntArray.
Careful friends may also find this prompt, and will find that not all hashmaps will prompt replacement. Today, let's find out what are the advantages and disadvantages of SparseArray compared with HaspMap, and what scenarios are used in it?

2, Use of SparseArray

1. Create

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

First, let's take a look at how to create a sparsearay. As mentioned earlier, sparsearay is used to replace HashMap, and sparsearay only needs to specify a generic type. It seems that the type of key has been specified inside sparsearay?
SparseArray has two construction methods, one is the default construction method and the other is the incoming capacity.

2,put()

sparseArray.put(int key,Student value);

Originally, the key in the key value pair stored in SparseArray is int data. Why? We'll talk about it later when we analyze the source code.

put() is used in the same way as HashMap.

3,get()

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

sparseArray.remove(int key);

4,index

The first few are not much different from HashMap, and this index is a unique attribute of sparsearay. To facilitate understanding, sparsearay can guess that it has something to do with arrays from the name. In fact, there are two arrays at the bottom, one for storing key s and the other for storing value s. After knowing this, you should be able to guess the role of index.
Index - the position of the key in the array. SparseArray provides some index related methods:

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);

3, SparseArray implementation principle

The use of SparseArray was briefly introduced earlier. In order to select the most reasonable data structure in practical work, it is necessary to deeply understand the implementation principle of each data structure, so as to better understand and compare the advantages and disadvantages of different data structures, which is better than memorizing the concept, You can even implement the most suitable data structure according to your specific needs.

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.

This comment basically explains the function of this class: using int [] array to store key s avoids the steps of packing basic data types in HashMap. Secondly, no additional entries are used, and the storage cost of a single element is reduced.

1. put source code analysis

/**
  * 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++;
     }
 }

The logic of insertion is about these points:

• The array for storing key s is ordered (prerequisite for binary search)
• In case of conflict, the new value directly overwrites the original value and will not return the original value (HashMap will return the original value)
• If the value on the index of the key to be inserted is DELETE, it will be overwritten directly
• The previous steps failed. Check whether gc() is needed and insert data on the index

4, Summary

After understanding the implementation principle of SparseArray, it is time to summarize its advantages and disadvantages compared with HashMap

1. Advantages:

• The boxing operation of basic data types is avoided
• No additional structure is required, and the storage cost of a single element is lower
• When the amount of data is small, the efficiency of random access is higher

2. Shortcomings

• The insertion operation needs to copy the array, which reduces the efficiency of addition and deletion
• When the amount of data is huge, the cost of copying array is huge, and the cost of gc() is also huge
• When the amount of data is huge, the query efficiency will also decrease significantly