Android 特有的數(shù)據(jù)結(jié)構(gòu)SpareArray 詳解

在android developer 的開發(fā)文當(dāng)中是這么描述SparesArray的：

SparseArrays map integers to Objects. Unlike a normal array ofObjects, there can be gaps in the indices. It is intended to be more efficientthan using a HashMap to map Integers to Objects.

大概意思是SparseArrays是映射Integer—> Objects 類型的，就像這樣: SparseArrays< Object>而且在指數(shù)級別的數(shù)量的增長上來說和HashMap相比較的話，性能方面SparseArrays更好。

為什么會突然說SparseArrays呢？因為我在看Activity源碼的時候看到了這段代碼：

privatestaticclassManagedDialog {

        Dialog mDialog;

        Bundle mArgs;

   }

private SparseArray<ManagedDialog> mManagedDialogs;

我不知道SparseArray是什么，然后點進去繼續(xù)看這個類的實現(xiàn)，和開始介紹

/**

 * 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 toObjects, both because it avoids

 * auto-boxing keys and its data structure doesn'trely on an extra entry object

 * for each mapping.

 **/

前半段和上面api文檔上介紹的一樣，后半段的意思就是因為數(shù)據(jù)結(jié)構(gòu)的實體類不依賴外在實體并且避免了自動裝箱時候的key,所以效率更高。(效率高的另外一個原因我們等下再說)

我繼續(xù)回來看代碼發(fā)現(xiàn)在下面這段代碼中用到了SparseArray.

finalint[]ids = b.getIntArray(SAVED_DIALOG_IDS_KEY);

finalintnumDialogs = ids.length;

 mManagedDialogs = newSparseArray<ManagedDialog>(numDialogs);

    for(inti = 0; i < numDialogs; i++) {

        final Integer dialogId = ids[i];

         Bundle dialogState = b.getBundle(savedDialogKeyFor(dialogId));

       if (dialogState != null) {

         // Calling onRestoreInstanceState() below will invoke dispatchOnCreate

          // so tell createDialog() not to do it, otherwise we get an exception

                final ManagedDialog md = new ManagedDialog();

                md.mArgs = b.getBundle(savedDialogArgsKeyFor(dialogId));

                md.mDialog = createDialog(dialogId, dialogState, md.mArgs);

                if (md.mDialog != null) {

                    mManagedDialogs.put(dialogId, md);

                    onPrepareDialog(dialogId,md.mDialog,md.mArgs);

                    md.mDialog.onRestoreInstanceState(dialogState);

                }

          }

      }

上面這段代碼做的事情就是根據(jù)對話框id的個數(shù)來創(chuàng)建SparesArrays的大小。并且根據(jù)ManagedDialog的id存dialogState，也就是存dialog的狀態(tài)。說白了就是<Integer,Object>格式的HashMap。

我回去繼續(xù)閱讀SparesArrays的源碼發(fā)現(xiàn)：

它的構(gòu)造方法設(shè)置了默認(rèn)大小為10，

和List一樣，獲取元素的方法有兩個如圖所示我們可以發(fā)現(xiàn)

public E get(int key)方法還是調(diào)用的public E get(int key, E valueIfKeyNotFound)。只是在找不到元素的時候設(shè)置了默認(rèn)的返回值為null。

值得注意的是，它查找的時候用的是二分查找（折半查找）算法，所以快。

感覺整個SparesArrays的核心就是binarySearch。我們看下它的源代碼：

static int binarySearch(int[] array, int size, intvalue) {

        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

    }

    static intbinarySearch(long[] array, int size, long value) {

        int lo =0;

        int hi =size - 1;

        while(lo <= hi) {

           final int mid = (lo + hi) >>> 1;

           final long 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

    }

再來看它刪除的時候有四種方法；

前三種中

public void delete(int key)是根據(jù)折半查找刪除，

public void remove(int key)調(diào)用的是delete(int key)

public void removeAt(int index)根據(jù)index刪除

public void removeAtRange(int index, int size)這個是調(diào)用publicvoid removeAt(int index)（上面截圖中沒有）

添加數(shù)據(jù)方法有public voidput(int key, E value)

在紅框中的代碼表示 put的時候會先查案當(dāng)前的SparesArrays中是否存在此數(shù)據(jù)，如果存在那么就是修改這個數(shù)值，不會添加，如果沒有查找到那么久會添加。

還有一個方法是修改數(shù)組中的數(shù)值的

public void setValueAt(int index, Evalue)

如注釋中說的，會給index的位置的value進行修改。

public int keyAt(int index)這個方法是根據(jù)index來獲取key值。范圍是0-size-1.

同樣的public E valueAt(int index)就是根據(jù)index來獲取對應(yīng)位置的object。如圖：

還有public void append(int key,E value)方法，這個方法是在key遠遠大于數(shù)組中所有的key的時候添加數(shù)據(jù)提高性能的方法，如果key>0 并且key小于等等數(shù)組中最后一個的key的情況下還是調(diào)用的put方法。

最后一個方法就是toString，也就是打印出整個數(shù)組的字符串。這個沒多大意思就不貼出代碼了。

另外 想要閱讀android源碼的一種方式可以戳這里：

http://poarry.blog.51cto.com/5970996/1630731

以上純屬個人見解，如有失誤，歡迎指正poarryScript@gmail.com