本來接下來應該分析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類的所有關鍵代碼都已經分析完畢,希望對各位平時的開發有所幫助(由於本人水平有限,歡迎批評指正)。