SparseArray到底哪點比HashMap好

sparsearray是android裡為<interger,object>這樣的hashmap而專門寫的class,目的是提高效率，其核心是折半查找函數（binarysearch）。

是以android開發中官方推薦：當使用hashmap(k, v),如果k為整數類型時,使用sparsearray的效率更高。

那我們看源碼來分析下，

和hashmap的資料結構不同,hashmap是使用數組+連結清單的資料結構存儲鍵值對,而sparsearray隻是用了兩個數組進行存儲。

我們知道連結清單的時間複雜度是很高的，這估計也是造成hashmap時間複雜度高的一個原因。

containerhelpers類提供了二分查找算法，這也一定程度上提高了查找的效率

put函數的邏輯：

通過二分查找算法,計算key的索引值.

如果索引值大于0,說明有key對應的value存在,直接替換value即可.

如果索引值小于0,對索引值取反,擷取key應該插入的坐标i.

判斷是否需要擴容:1.需要擴容,則先擴容; 2.不需要擴容,則利用system.arraycopy移動相應的元素,進行(key,value)鍵值對插入.

get函數就是利用二分查找擷取key的下标,然後從object[] value數組中根據下标擷取值. 

之是以sparsearray号稱比hashmap有更好的性能:

sparsearray更加節約記憶體,一個int[]數組存儲所有的key,一個object[] 數組存儲所有的value.

hashmap遇到沖突時,時間複雜度為o(n).而sparsearray不會有沖突,采用二分搜尋算法,時間複雜度為o(lgn).

通過上面的源碼分析，我們不難得出：

正式因為sparsearray采用了數組這種形式，才使得我們的key在做hash運算的時候，通過二分查找時間複雜度降低了，進而提高了效率。

通過二分查找保證查詢效率為o(lgn).而hashmap在未沖突的情況下是o(1),沖突的情況下是o(n).