SparseArray details

1. SparseArray Used for mapping integers To object. But unlike ordinary arrays ,sparseArray There are no useless elements between the elements of .  In mapping integers To object In the process of ,SparseArray Due to the adoption of the keys And its data structure does not depend on additional Object to store the implementation of the mapping relationship , So it's better than hashMap More efficient use of memory . 
   
2. SparseArray Looking for keys Binary search is used in the process of ,  This implementation is not suitable for a large amount of data . Because the binary search is used in the search , Adding or deleting involves moving other elements of the array ,
3. So usually SparseArray than hashMap slow . When processing hundreds of data , This difference in performance is not particularly obvious , The performance difference does not exceed 50%. 
4. In order to optimize performance ,SparseArray in the light of remove case Optimized ,remove It does not immediately squash the array space , It's marked as delete.  This tagged element is either reused , want
5. Many times remove Then pass it once gc Squeezed out during operation .gc It needs to be executed before ： The array needs to be expanded ;get map size;get values;
6. The core put The code is as follows ：
7. 
   
8. 1. 1.     /** 
      2.      * Adds a mapping from the specified key to the specified value, 
      3.      * replacing the previous mapping from the specified key if there 
      4.      * was one. 
      5.      */  
      6.     public void put(int key, E value) {  
      7.         // Let's look in two , Determine the insertion position , To ensure the key The order of arrays   
      8.         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);  
      9.   
      10.         if (i >= 0) {  
      11.             // eureka , Direct replacement   
      12.             mValues[i] = value;  
      13.         } else {  
      14.             // A little trick , It is related to the return value of binary search   
      15.             // If you don't find it i The meaning is  i = -insertPoint -1, such as i=-2, be insertPoint=1  
      16.             // and -2 What is stored in memory is the complement , It's just right to reverse him insertPoint, It is the same as the above calculation , But bit operation is more efficient   
      17.             i = ~i;  
      18.   
      19.             // if i stay size Within the scope of , And the corresponding position is marked as delete 了 , Put it directly in   
      20.             if (i < mSize && mValues[i] == DELETED) {  
      21.                 mKeys[i] = key;  
      22.                 mValues[i] = value;  
      23.                 return;  
      24.             }  
      25.   
      26.             // If the front if Don't set up , namely i Beyond the size Range , Or the element of the corresponding position is valid   
      27.             if (mGarbage && mSize >= mKeys.length) {  
      28.                 // Compress space   
      29.                 gc();  
      30.   
      31.                 // Find insertion point again   
      32.                 // Search again because indices may have changed.  
      33.                 i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);  
      34.             }  
      35.   
      36.             // Insert , If there is not enough space, the array will be reallocated   
      37.             mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);  
      38.             mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);  
      39.             mSize++;  
      40.         }  
      41.     } 
   3. }