SparseArray 稀疏數組解析

前言

安卓提供了一個名為SparseArray的數據結構，用來替代小型的以int為key的HashMap，SparseArray犧牲了一些運行性能，用以換取內存節省。本文將針對SparseArray源碼進行相關剖析。

底層實現

SparseArray的底層實現為數組，在SparseArray中定義了下面兩個數據結構，分別用來記錄Key和Value，可以發現由於這個數據結構要求鍵必須是int，因此稀疏數組內部實現沒有使用包裝類，從而避免了拆裝箱的成本。

查詢操作

SparseArray的查詢操作是最基礎的操作，代碼如下所示。從代碼中可以看出，SparseArray的內部數組大小遠小於Integer範圍，因此採用了二分查找的映射方式。

如果二分查找結果0，或者目標點被標記為DELETED，則代表KEY無效。

SparseArray的具體映射方式如下所示，可以發現數組索引是連續的，但是KEY不是連續的，如果要查詢5，通過二分查找演算法，算出下標為1，因此直接訪問下標為1的Value即可。

增加/修改操作

增加操作第一步是通過二分查找找出元素應該存放的位置，如果當前KEY已存在，則直接覆蓋，因此修改操作的時間複雜度是O(log(n))。

如果當前KEY不存在，則證明要新插入一個KEY。插入新的KEY分為以下四種情況：

如果KEY對應的位置被標記刪除，則可以直接覆蓋。(對應第一個if)

如果KEY對應的位置已經被某個元素佔據，需要移動這個元素以後的所有元素，把位置空出來，然後放置KEY。

如果KEY對應的位置已經被某個元素佔據，並且此時沒辦法向後移動元素，因為所有的位置都已經被佔據，則需要執行GC操作，GC操作刪除一些被DELETE標記的元素，從而使得整個數組尾部有空閑位置，可以向後移動元素。(對應第二個if)

如果KEY對應的位置已經被某個元素佔據，並且通過GC操作依然沒辦法向後移動元素。此時代表數組容量確實不足，需要數組擴容。GrowingArrayUtils.insert函數當插入的下標大於數組長度時會自動擴容。

對於上述四種情況，除了第一種情況的時間複雜度為O(1)之外，其他的時間複雜度為O(n)。

刪除操作

SparseArray採用了標記刪除演算法，通過GC操作進行真正回收，從而可以減少數組移動次數。由於是標記刪除，因此刪除操作的時間複雜度為O(1)。

GC操作

GC操作演算法中維護了一個整數o，代表剩餘的元素數量，對於未標記為DELETE的元素，將下標o對應位置的Key和Object進行賦值，然後o 即可。

時間複雜度

總結

通過上述分析，可以發現SparseArray是一個適用於Key為Int，且數據量較小情況下，為了優化內存佔用，從而替代HashMap的工具。

根據官方文檔的描述，在數據量較大的情況下，SparseArray比HashMap性能要差，在數百條數據的情況下，兩個數據結構的差異並不是很明顯，性能差異小於50%。

SparseArray通過數組實現，避免了K,V結構體，從而減少了內存佔用。另一方面，避免裝箱和拆箱操作對於內存和速度都有輕微的優化效果。標記刪除使得數據結構的刪除複雜度為O(1)。

但是，由於底層基於數組拷貝實現插入操作，因此對於數據量較大的情況，SparseArray性能較差。另外，對於高並發情況，SparseArray不是線程安全的，需要特別注意。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！