? ?SparseArray是android里為<Integer,Object>的HashMap這樣的數(shù)據(jù)類型所寫的類，目的是提高效率，其核心算法是折半查找函數(shù)。
不同點(diǎn)：
?1.SparseArray的key是int型，不是對象。
?2.HashMap底層是數(shù)組+鏈表結(jié)構(gòu)，SparseArray是數(shù)組+數(shù)組結(jié)構(gòu)。因?yàn)殒湵淼臅r(shí)間復(fù)雜度比較高，所以SparseArray效率更高。
SparseArray源碼
/**??
?*?存儲(chǔ)索引集合.??
?*/??
private?int[]?mKeys;??
/**??
?*?存儲(chǔ)對象集合.??
?*/??
private?Object[]?mValues;??
/**??
?*?存儲(chǔ)的鍵值對總數(shù).??
?*/??
private?int?mSize;??
/**??
?*?采用默認(rèn)的構(gòu)造函數(shù),則初始容量為10.??
?*/??
public?SparseArray()?{??
????this(10);??
}??
/**??
?*?使用指定的初始容量構(gòu)造SparseArray.??
?*??
?*?@param?initialCapacity?初始容量??
?*/??
public?SparseArray(int?initialCapacity)?{??
if?(initialCapacity?==?0)?{??
????????//?Effective?Java中第43條:返回零長度的數(shù)組或者集合,而不是:null??
mKeys?=?ContainerHelpers.EMPTY_INTS;??
mValues?=?ContainerHelpers.EMPTY_OBJECTS;??
????}?else?{??
????????//?構(gòu)造initialCapacity大小的int數(shù)組和object數(shù)組??
mKeys?=?new?int[initialCapacity];??
mValues?=?new?Object[initialCapacity];??
????}??
//?設(shè)置SparseArray存儲(chǔ)的鍵值對個(gè)數(shù)為0.??
mSize?=?0;??
}??
重要方法：
put函數(shù)的邏輯：
通過二分查找算法,計(jì)算key的索引值.
如果索引值大于0,說明有key對應(yīng)的value存在,直接替換value即可.
如果索引值小于0,對索引值取反,獲取key應(yīng)該插入的坐標(biāo)i.
判斷是否需要擴(kuò)容:1.需要擴(kuò)容,則先擴(kuò)容; 2.不需要擴(kuò)容,則利用System.arraycopy移動(dòng)相應(yīng)的元素,進(jìn)行(key,value)鍵值對插入.
get函數(shù)就是利用二分查找獲取key的下標(biāo),然后從object[] value數(shù)組中根據(jù)下標(biāo)獲取值.
之所以SparseArray號稱比HashMap有更好的性能:
SparseArray更加節(jié)約內(nèi)存,一個(gè)int[]數(shù)組存儲(chǔ)所有的key,一個(gè)object[] 數(shù)組存儲(chǔ)所有的value.
HashMap遇到?jīng)_突時(shí),時(shí)間復(fù)雜度為O(n).而SparseArray不會(huì)有沖突,采用二分搜索算法,時(shí)間復(fù)雜度為O(lgn).
ContainerHelpers:采用二分法查找，提高了一定效率。
