Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> 關於Android編程 >> Android源碼分析之SparseArray

Android源碼分析之SparseArray

編輯:關於Android編程

本來接下來應該分析MessageQueue了,可是我這幾天正好在實際開發中又再次用到了SparseArray(之前有用到過一次,那次只是   大概浏覽了下源碼,沒做深入研究),於是在興趣的推動下,花了些時間深入研究了下,趁著記憶還是新鮮的,就先在這裡分析了。   MessageQueue的分析應該會在本周末給出。     和以往一樣,首先我們來看看關鍵字段和ctor:   復制代碼     private static final Object DELETED = new Object();     private boolean mGarbage = false;       private int[] mKeys;     private Object[] mValues;     private int mSize;       /**      * Creates a new SparseArray containing no mappings.      */     public SparseArray() {         this(10);     }       /**      * Creates a new SparseArray containing no mappings that will not      * require any additional memory allocation to store the specified      * number of mappings.  If you supply an initial capacity of 0, the      * sparse array will be initialized with a light-weight representation      * not requiring any additional array allocations.      */     public SparseArray(int initialCapacity) {         if (initialCapacity == 0) {             mKeys = ContainerHelpers.EMPTY_INTS;             mValues = ContainerHelpers.EMPTY_OBJECTS;         } else {             initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);             mKeys = new int[initialCapacity];             mValues = new Object[initialCapacity];         }         mSize = 0;     } 復制代碼 常量DELETED對象用來標記刪除,如果某個位置的值是DELETED則表示這個位置沒對應的元素(被刪除了);   mGarbage在刪除操作中會被設置(置為true),表示接下來需要清理壓縮了(compacting);   mkeys,mValues分別表示SparseArray的內部存儲,即分別是key、value的存儲數組;   mSize表示有效的key-value對的數目;   接下來來看ctor,無參版本會調用帶參數的版本並且傳遞10,表示初始容量。我們可以看到如果initialCapacity=0的話,mkeys、mValues   會分別被初始化為EMPTY的東西,實際是長度為0的數組,不會產生內存分配;否則初始化2個數組為具體的大小,這裡要留意一點就是代碼   裡並沒有直接用你傳遞進來的值,而是調用了initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);來我們順便看一下:   復制代碼   public static int idealIntArraySize(int need) {         return idealByteArraySize(need * 4) / 4;     }     public static int idealByteArraySize(int need) {         for (int i = 4; i < 32; i++)             if (need <= (1 << i) - 12)                 return (1 << i) - 12;           return need;     } 復制代碼 Android認為它這個方式是比較ideal的,比客戶端直接傳的值要好,所以經過這一堆運算後,initialCapacity很可能已經不是你當初傳的值了。   最後都設置了mSize為0。     接下來看2個依據key來得到value的方法:   復制代碼   /**      * Gets the Object mapped from the specified key, or <code>null</code>      * if no such mapping has been made.      */     public E get(int key) {         return get(key, null);     }       /**      * Gets the Object mapped from the specified key, or the specified Object      * if no such mapping has been made.      */     @SuppressWarnings("unchecked")     public E get(int key, E valueIfKeyNotFound) {         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);           if (i < 0 || mValues[i] == DELETED) {             return valueIfKeyNotFound;         } else {             return (E) mValues[i];         }     } 復制代碼 看2個參數的get方法,你可以提供一個fallback的值,表示如果沒找到key對應的值就返回你提供的這個值;SparseArray內部是通過二分   查找算法來search key的,順便看看:   復制代碼     // This is Arrays.binarySearch(), but doesn't do any argument validation.     static int binarySearch(int[] array, int size, int value) {         int lo = 0;         int hi = size - 1;           while (lo <= hi) {             final int mid = (lo + hi) >>> 1;             final int midVal = array[mid];               if (midVal < value) {                 lo = mid + 1;             } else if (midVal > value) {                 hi = mid - 1;             } else {                 return mid;  // value found             }         }         return ~lo;  // value not present     } 復制代碼 如源碼所說,這個版本和java.util.Arrays.java裡的實現一樣,只是省略了參數檢查。二分查找大家大學都接觸過,應該印象都比較深刻,   這裡只說一點即最後沒找到時的返回值~lo。如方法的doc所說,沒找到的情況下會返回一個負值,那到底返回哪個負值呢,-1行不?其實   這裡的~lo(取反)就相當於-(lo+1)(參看Arrays.binarySearch的實現)。為什麼要這樣做,因為我們不僅想表示沒找到,還想返回   更多信息,即這個key如果要插進來應該在的位置(外面的代碼只需要再次~即取反就可以得到這個信息)。接下來回到剛才的get方法,   明白了這裡使用的二分查找這個方法就非常簡單明了了。get內部通過binarySearch的返回值來做判斷,如果是負的或i>=0但是位置i已經   被標記為刪除了則返回valueIfKeyNotFound,否則直接返回(E) mValues[i]。     接下來看一組delete/remove方法:   復制代碼   /**      * Removes the mapping from the specified key, if there was any.      */     public void delete(int key) {         int i = ContainerHelpers.binarySearch(mKeys, mSize, key);           if (i >= 0) {             if (mValues[i] != DELETED) {                 mValues[i] = DELETED;                 mGarbage = true;             }         }     }       /**      * Alias for {@link #delete(int)}.      */     public void remove(int key) {         delete(key);     }       /**      * Removes the mapping at the specified index.      */     public void removeAt(int index) {         if (mValues[index] != DELETED) {             mValues[index] = DELETED;             mGarbage = true;         }     }       /**      * Remove a range of mappings as a batch.      *      * @param index Index to begin at      * @param size Number of mappings to remove      */     public void removeAtRange(int index, int size) {         final int end = Math.min(mSize, index + size);         for (int i = index; i < end; i++) {             removeAt(i);         }     } 復制代碼 delete(key)和remove(key)一樣,都是先通過二分查找來找這個key,如果不存在則do nothing否則如果這個位置還沒被標記為刪除   則標記之,順便設置mGarbage(之前提到過刪除之類的操作都會設置這個值,表示接下來需要執行清理壓縮操作了)。注意這裡數組   的不同處理,沒有直接移動數組元素(壓縮處理)來刪除這個key,而僅僅是標記操作。這2個方法都是通過key來進行操作,有時你可能   想基於index來執行某些操作,下面的removeAt(index)和removeAtRange(index, size)就是這樣的方法,處理也都是如果位置i沒標記   刪除則標記之,並設置mGarbage的值。只是在removeAtRange中對上限做了保險處理即end = Math.min(mSize, index+size);   防止數組越界。     接下來該打起來精神,睜大眼睛了,讓我們一起來看看SparseArray的關鍵,我叫它清理壓縮,上代碼:   復制代碼   private void gc() {         // Log.e("SparseArray", "gc start with " + mSize);           int n = mSize;         int reusedIndex = 0;         int[] keys = mKeys;         Object[] values = mValues;           for (int i = 0; i < n; i++) {             Object val = values[i];               if (val != DELETED) {                 if (i != reusedIndex) {                     keys[reusedIndex] = keys[i];                     values[reusedIndex] = val;                     values[i] = null;                 }                   reusedIndex++;             }         }           mGarbage = false;         mSize = reusedIndex;           // Log.e("SparseArray", "gc end with " + mSize);     } 復制代碼 gc方法只有在mGarbage設置的時候才有可能調用,其總體思想是把靠後的有效元素(即沒被刪除的)往前(reusedIndex的位置)提,   從而達到清理壓縮的目的。我們仔細分析下,首先初始化一些接下來要用到的值,這裡特別留意下reusedIndex(源碼中叫o,實在不好   理解,我按自己的理解重新命名了),初始化為0,指向第一個元素。接下來是遍歷mValues數組的for循環,其內部是如果當前元素val是   DELETED則啥也不做,接著看下一個元素(注意此時reusedIndex不做任何改動);否則當前是個有效的元素,執行1,2:   1. reusedIndex不是當前的index則應該把當前元素拷貝到reusedIndex的位置(key和value都復制),當前位置的value清空(置null);   2. reusedIndex往前+1(每遇到一個有效元素),准備下次循環。   結束遍歷之後reset mGarbage(因為剛剛做過了,暫時不需要了),更新mSize為reusedIndex(因為每遇到一個有效元素,reusedIndex   就+1,所以它的值就是新的mSize)。     看完了刪除我們來看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);             }               if (mSize >= mKeys.length) {                 int n = ArrayUtils.idealIntArraySize(mSize + 1);                   int[] nkeys = new int[n];                 Object[] nvalues = new Object[n];                   // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);                 System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);                 System.arraycopy(mValues, 0, nvalues, 0, mValues.length);                   mKeys = nkeys;                 mValues = nvalues;             }               if (mSize - i != 0) {                 // Log.e("SparseArray", "move " + (mSize - i));                 System.arraycopy(mKeys, i, mKeys, i + 1, mSize - i);                 System.arraycopy(mValues, i, mValues, i + 1, mSize - i);             }               mKeys[i] = key;             mValues[i] = value;             mSize++;         }     } 復制代碼 put的實現一般都是有這個key則覆蓋原先的value,否則新插入一個。這裡的也一樣,首先先調用二分查找算法去找key,如果找到了   (i>=0)則直接更新mValues[i]為新值;否則就得想辦法插入這對key-value,具體做法是:   1. 首先把二分查找的返回值取反(~),拿到要插入的位置信息;   2. 接下來看如果這個位置i在有效范圍內(即不需要額外分配空間)且此位置被標記為刪除了,則這就是個可以重用的位置,也就是我們   要找的插入位置,插入之,完事(return);   3. 不然的話(也就是說i超出了有效范圍或者沒超出但位置i是有效元素),如果mGarbage被設置了且mSize >= mKeys.length,   表示該執行gc算法了,執行之,接著重新利用二分查找算法確定下key的新位置(因為index可能變了)。   接下來,如果mSize >= mKeys.length(即key數組不夠用了或者說到了要分配更多內存的臨界點了),利用mSize計算新的capacity,   int n = ArrayUtils.idealIntArraySize(mSize + 1); 分配新的數組,將舊內容拷過去,接著將mKeys, mValues指向新分配   的數組。然後看下i如果在有效范圍內,則應該把現在從位置i開始的元素移動到位置i+1處(把i的位置騰出來給新put的元素讓位),   以此類推,到mSize-1的位置為止(mSize-1位置的元素移動到mSize的位置)。最後將put的元素插在第i的位置上,mSize++,   最終結束整個put操作。     長舒一口氣啊,接著來看看幾個非常簡單的方法,   復制代碼   /**      * Returns the number of key-value mappings that this SparseArray      * currently stores.      */     public int size() {         if (mGarbage) {             gc();         }           return mSize;     }       /**      * Given an index in the range <code>0...size()-1</code>, returns      * the key from the <code>index</code>th key-value mapping that this      * SparseArray stores.      *      * <p>The keys corresponding to indices in ascending order are guaranteed to      * be in ascending order, e.g., <code>keyAt(0)</code> will return the      * smallest key and <code>keyAt(size()-1)</code> will return the largest      * key.</p>      */     public int keyAt(int index) {         if (mGarbage) {             gc();         }           return mKeys[index];     }       /**      * Given an index in the range <code>0...size()-1</code>, returns      * the value from the <code>index</code>th key-value mapping that this      * SparseArray stores.      *      * <p>The values corresponding to indices in ascending order are guaranteed      * to be associated with keys in ascending order, e.g.,      * <code>valueAt(0)</code> will return the value associated with the      * smallest key and <code>valueAt(size()-1)</code> will return the value      * associated with the largest key.</p>      */     @SuppressWarnings("unchecked")     public E valueAt(int index) {         if (mGarbage) {             gc();         }           return (E) mValues[index];     }       /**      * Given an index in the range <code>0...size()-1</code>, sets a new      * value for the <code>index</code>th key-value mapping that this      * SparseArray stores.      */     public void setValueAt(int index, E value) {         if (mGarbage) {             gc();         }           mValues[index] = value;     }       /**      * Returns the index for which {@link #keyAt} would return the      * specified key, or a negative number if the specified      * key is not mapped.      */     public int indexOfKey(int key) {         if (mGarbage) {             gc();         }           return ContainerHelpers.binarySearch(mKeys, mSize, key);     }       /**      * Returns an index for which {@link #valueAt} would return the      * specified key, or a negative number if no keys map to the      * specified value.      * <p>Beware that this is a linear search, unlike lookups by key,      * and that multiple keys can map to the same value and this will      * find only one of them.      * <p>Note also that unlike most collections' {@code indexOf} methods,      * this method compares values using {@code ==} rather than {@code equals}.      */     public int indexOfValue(E value) {         if (mGarbage) {             gc();         }           for (int i = 0; i < mSize; i++)             if (mValues[i] == value)                 return i;           return -1;     }       /**      * Removes all key-value mappings from this SparseArray.      */     public void clear() {         int n = mSize;         Object[] values = mValues;           for (int i = 0; i < n; i++) {             values[i] = null;         }           mSize = 0;         mGarbage = false;     } 復制代碼 size()方法返回當前有效的key-value對的數目,值得注意的是在其內部都會有條件的執行gc方法,因為之前的操作可能導致mGarbage   被設置了,所以必須執行下清理壓縮才能返回最新的值;keyAt(index)和valueAt(index)提供了遍歷SparseArray的方法,如下:     for (int i = 0; i < sparseArray.size(); i++) {         System.out.println("key = " + sparseArray.keyAt(i) + ", value = " + sparseArray.valueAt(i));     } 同樣和size()方法一樣其內部也都會有條件的執行gc方法,注意你傳遞的index必須在[0, size()-1]之間,否則會數組越界。   setValueAt讓你像使用數組一樣設置某個位置處的值,同樣會有條件的執行gc方法。   indexOfKey通過二分查找來search key的位置;indexOfValue在整個mValues數組中遍歷查找value,有則返回對應的index   否則返回-1。   clear()方法清空了mValues數組,重置了mSize,mGarbage,但請注意並沒動mKeys數組;     最後我們看下SparseArray的最後一個方法append,源碼如下:   復制代碼   /**      * Puts a key/value pair into the array, optimizing for the case where      * the key is greater than all existing keys in the array.      */     public void append(int key, E value) {         if (mSize != 0 && key <= mKeys[mSize - 1]) {             put(key, value);             return;         }           if (mGarbage && mSize >= mKeys.length) {             gc();         }           int pos = mSize;         if (pos >= mKeys.length) {             int n = ArrayUtils.idealIntArraySize(pos + 1);               int[] nkeys = new int[n];             Object[] nvalues = new Object[n];               // Log.e("SparseArray", "grow " + mKeys.length + " to " + n);             System.arraycopy(mKeys, 0, nkeys, 0, mKeys.length);             System.arraycopy(mValues, 0, nvalues, 0, mValues.length);               mKeys = nkeys;             mValues = nvalues;         }           mKeys[pos] = key;         mValues[pos] = value;         mSize = pos + 1;     } 復制代碼 看源碼我們知道,當mSize != 0且key<=SparseArray中最大的key時,則直接調用put方法;否則當key比現存所有的key都大,   這種情況下我們執行的只是put方法中i==mSize的部分(小分支,所以說是個優化相比直接調用put方法)。     目前為止,SparseArray類的所有關鍵代碼都已經分析完畢,希望對各位平時的開發有所幫助(由於本人水平有限,歡迎批評指正)。    
  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved