How to use SparseArray performance optimization in Android

In a previous article, after studying the horizontal secondary menu, I found that SparseArray was used to replace the use of HashMap. So I checked some relevant data and tested the performance at the same time. First, let's talk about the principle of SparseArray

SparseArray (sparse array). It is a unique API in Android. The standard JDK does not have this class. It is used to replace HashMap < integer, E > in Android. Using SparseArray saves more memory space. SparseArray also saves data in key and value. When using, you only need to specify the type of value. And the key does not need to be encapsulated into an object type

According to the owner's personal test, the memory space occupied by SparseArray to store data is indeed smaller than HashMap. The test data will be released for analysis later. Let's first look at the structural characteristics of the two

HashMap is a combination of array and linked list, which is called linked list hash

SparseArray is a combination of simple arrays. It is called sparse array. There will be no additional overhead when saving data. The structure is as follows:

This is the structure of the two. We need to see the difference between the two

First, insert:

Positive order insertion of HashMap:

Results after execution:

Positive order insertion of SparseArray:

We can see that the efficiency of SparseArray is higher than that of HashMap when 100000 pieces of data are inserted in positive order. And the memory occupied is smaller than that of HashMap.. the positive order insertion here indicates that the value of I increases from small to large.. the sequence depends on the value of I, not how to execute in the for loop

Through the running results, we can find that SparseArray is much faster than HashMap when inserting in positive order, and also saves some memory. There are many opinions on the Internet about the efficiency of both. Many people mistakenly think that sparsearay is faster than HashMap insertion and search. Others think that hash search is much faster than sparsearay binary search

In fact, I think the essential purpose of recommending sparsearay when saving < integer, value > in Android is not for efficiency reasons, but for memory reasons. We do see that sparsearay is faster than HashMap when inserting. But this is only positive order insertion. Let's take a look at the reverse order insertion

HashMap insertion in reverse order:

SparseArray insertion in reverse order:

From the above running results, we can still see that no matter how to insert SparseArray and HashMap, the amount of data is the same. The former saves some memory than the latter, but what is the efficiency? We can see that when inserting in reverse order, the insertion time of sparsearay and that of HashMap are far from the same order of magnitude. Because sparsearay uses binary search to determine whether the same value is inserted every time it is inserted, this reverse order is when sparsearay is the most inefficient

SparseArray's insertion source code, let's have a simple look

This is the source code of SparseArray insertion function. Each insertion method needs to call binary search. Therefore, when inserting in reverse order, the situation will be very bad, In terms of efficiency, it is absolutely lost to HashMap. Everyone who has studied data structure knows that map will make corresponding decisions on conflict factors when inserting. It has a very good way to deal with conflicts. It does not need to traverse every value. Therefore, the efficiency of inserting in reverse order or positive order depends on the way to deal with conflicts, so the time sacrificed during inserting is basically the same

By inserting, we can still see the difference between the two

Let's take another look at the search. The first is the search of HashMap

SparseArray lookup:

I have also simply tested the search efficiency here. For the query of one data or several data, the difference between the two is still very small. When the amount of data is 100000, the efficiency of checking 100000 is faster than that of map. When the amount of data is 10000, the difference is smaller. But the efficiency of map search does win

In fact, in my opinion, the main reason for using SparseArray to replace HashMap when saving < integer, E > is due to memory. We can see that whether the amount of data saved is large or small, The memory occupied by map is always greater than SparseArray. SparseArray saves 27% more memory than HashMap when the amount of data is 100000. That is, it saves memory space at the expense of efficiency. We know that Android is extremely demanding on memory use. The maximum memory allowed in the heap is only 16m. Oom phenomenon is easy to occur. Therefore, the use of memory in Android is very important It's important. Therefore, the official recommends using SparseArray < E > to replace HashMap < integer, E >. The official also does state that the difference will not exceed 50%. Therefore, sacrificing some efficiency for memory is actually a good choice in Android