ArrayMap and SparseArray are Android system apis that are customized for mobile devices. Used in some cases to replace HashMap to save memory.
Source code analysis (due to space constraints, source code analysis will be placed in a separate article). Comparison of realization principle and data structure iii. Performance test comparison iv. conclusion
Source code analysis will be covered later in the next article (all in one, too long)
Comparison of implementation principle and data structure 1. HashMap
As can be seen from the structure of hashMap, the key value is first hash, and the position in the table array is determined according to the hash result. When hash conflicts occur, the open-chain address method is used to deal with them. The data structure of map.entity is as follows:
static class HashMapEntry<K, V> implements Entry<K, V> {
final K key;
V value;
final int hash;
HashMapEntry<K, V> next;
}Copy the codeThe details of the hashMap source code will be analyzed in other articles. As you can see from a spatial perspective, the HashMap will have a table array whose utilization does not exceed the load factor (default is 0.75). Secondly, A HashMapEntry is used to record each piece of data in a HashMap. In addition to keys and values, hash values and Pointers to the next entity are also recorded. In terms of time efficiency, using hash algorithm, insert, search and other operations are very fast, and in general, there will not be a long linked list behind each array value (because hash conflicts account for a relatively small proportion after all), so the efficiency of HashMap is very high without considering space utilization.
2.ArrayMap
ArrayMap uses two arrays, mHashes to hold the hash value of each key, and mArrray twice the size of mHashes to hold the key and value in sequence. The details of the source code will be covered in the next article. Now let’s skip the details and focus on the key statements:
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;Copy the codeAnd I think that makes sense to you. But how does it query? The answer is binary search. When inserting, the hash value is obtained according to the hashcode() method of the key, and the index position of the mArrays is calculated. Then the binary lookup is used to find the corresponding position for insertion. When a hash conflict occurs, the adjacent position of the index is inserted. To summarize, for every piece of information an ArrayMap stores, it needs to store a hash value, a key value, and a value value. A rough look at a HashMap only reduces the pointer to the next entity. Also, the memory savings on the visible space are not particularly significant. Is that right? This will be verified later. Time efficiency, the insert and search for all to use dichotomy, there should be no when searching the hash lookup fast, when inserted, if order insert efficiency must be high, but if it is a random insertion, move, will involve a lot of array data, certainly not, think about it again, if it is not happened, Each time the hash value is smaller than the last one, it will have to be moved again and again, and the efficiency will become unbearable.
3.SparseArray
SparseArray is relatively simple, but don’t assume it will replace the first two. SparseArray can only be used if the key is an int, not an Integer. . Since the key is int, we don’t need a hash value, as long as the int values are equal, it’s the same object. Inserts and lookups are also based on dichotomy, so the principle is basically the same as Arraymap, which I won’t go into here. To sum up: compared with HashMap, the storage space of Hash value is removed. There is no next pointer, and some other small memory usage, which looks like a lot of savings. Time comparison: Inserts and lookups are basically the same as Arraymap, and there may be a lot of array movement. But it avoids the loading process, so don’t underestimate the loading process, which is very time consuming. So from the point of view of the source code, efficiency who is fast, depends on the size of the data.
Well, after all this talk about analysis, let’s get down to the facts and use the data!
Performance test comparison Let’s compare the two aspects of insert and query.
1. Insert performance time comparison test code:
long start = System.currentTimeMillis();
Map<Integer, String> hash = new HashMap<Integer, String>();
for (int i = 0; i < MAX; i++) {
hash.put(i, i+"");
}
long ts = System.currentTimeMillis() - start;Copy the codeI’ll leave it there. The other two pieces of code just replace the HashMap and compare it by changing the Max value.
Analysis: In terms of results, SparseArray is the fastest and HashMap the slowest when the amount of data is greater than 5000. At first glance, SparseArray seems to be the fastest. But notice that this is inserted sequentially. That’s the ideal case for SparseArray and Arraymap.
Let’s try a reverse insertion
long start = System.currentTimeMillis();
HashMap<Integer, String> hash = new HashMap<Integer, String>();
for (int i = 0; i < MAX; i++) {
hash.put(MAX-1-i, i+"");
}
long ts = System.currentTimeMillis() - start;Copy the code
Analysis: From the results, sure enough, HashMap is far superior to Arraymap and SparseArray, and is consistent with the previous analysis. Of course, when the amount of data is small, such as less than 1000, this time difference can be ignored.
Let’s look at the space comparison: first, let’s talk about the test method, because the test memory, so we should pay special attention to the point that the test process does not occur GC, if GC occurs, then the data is not accurate, think about it, use a relatively simple method:
Runtime.getruntime ().totalmemory ()// obtains the totalMemory allocated by the applicationCopy the codeRuntime.getruntime ().freememory ()// Gets the free portion of the application memoryCopy the codeThe difference between the two methods is the amount of memory already used by the application.
It is worth noting that when the MAX value is very high, GC may occur during code execution. In this case, you can also use the Memory window of Android Monitor to Monitor the Memory, and only the results of the process without GC are valid. Assume that when the amount of data is relatively large, every time after the test, manual GC once, so that basically every test can succeed; Because the amount of data is not very large, only a few cases of GC will occur in the test process, so I did not further explore other methods, such as setting virtual machine parameters to prolong the GC time, I can do it when I have time. Data on:
SparseArray’s memory footprint is much better than that of HashMap and ArrayMap, with a roughly 30% reduction in data. ArrayMap’s performance, as mentioned above, is limited and almost identical to That of HashMap.
2. Search for performance comparison
long start = System.currentTimeMillis();
SparseArray<String> hash = new SparseArray<String>();
for (int i = 0; i < MAX; i++) {
hash.get(i);
}
long ts = System.currentTimeMillis() - start;Copy the code
SparseArray is the fastest, HashMap is the slowest, and binary lookup is faster than Hash. On second thought, since it’s a little unfair to test with this code, since SparseArray doesn’t have a boxing, HashMap has a boxing process, which doesn’t seem fair. So think of a way to test it again,
ArrayList<IntEntity> intEntityList=new ArrayList<IntEntity>(); private void boxing(){ for(int i=0; i<MAX; i++){ IntEntity entity=new IntEntity(); entity.i1=i; entity.i2=Integer.valueOf(i); intEntityList.add(entity); } } class IntEntity{ int i1; Integer i2; }Copy the codeIt seems fair to box HashMap and ArrayMap ahead of time.
long start = System.currentTimeMillis();
HashMap<Integer, String> hash = new HashMap<Integer, String>();
for (int i = 0; i < MAX; i++) {
// hash.get(i);
hash.get(intEntityList.get(i).i2);
}
long ts = System.currentTimeMillis() - start;Copy the code
The result is different, HashMap is the fastest query, which is logical, but we normally use whether or not the box, so the overall use of SparseArray is the most efficient.
Having pulled so much, it’s finally time to sum up. 1. SparseArray is a good choice for small numbers of data. If your key is int, you can save about 30% of your memory. So the average time performance is better than HashMap, recommended! 2. Compared with SparseArray, ArrayMap is characterized by the unrestricted key value type and can replace HashMap in any case. However, through research and testing, it is found that the memory saving of ArrayMap is not obvious, which is only about 10%, but the time performance is the worst. The amount of data up to 1000 does not matter, plus it can only be used in API>=19, personal advice is not necessary to use! You might as well use HashMap. That’s probably why Google didn’t ask us to use it when we created a new HashMap.