Android數據結構-SparseArray實現原理

来源:https://www.cnblogs.com/lixuejian/archive/2023/03/21/17241463.html
-Advertisement-
Play Games

SparseArray家族 SparseArray基於鍵值對存儲數據,key為int,value為object,簡單使用如下: //聲明 SparseArray<String> sparseArray= new SparseArray<>(); //增加元素,append方式 sparseArray ...


SparseArray家族

SparseArray基於鍵值對存儲數據,key為int,value為object,簡單使用如下:

        //聲明
        SparseArray<String> sparseArray= new SparseArray<>();
        //增加元素,append方式
        sparseArray.append(0, "myValue");
        //增加元素,put方式
        sparseArray.put(1, "myValue");
        //刪除元素,二者等同
        sparseArray.remove(1);
        sparseArray.delete(1);
        //修改元素,put或者append相同的key值即可
        sparseArray.put(1,"newValue");
        sparseArray.append(1,"newValue");
        //查找,遍歷方式1
        for(int i=0;i<sparseArray.size();i++){
            Log.d(TAG,sparseArray.valueAt(i));
        }
        //查找,遍歷方式2
        for(int i=0;i<sparseArray.size();i++){
            int key = sparseArray.keyAt(i);
            Log.d(TAG,sparseArray.get(key));
        }

LongSparseArray 和SparseArray 相比,唯一的不同就是key值為long,所以LongSparseArray可以存儲的數據元素就比SparseArray多,int的範圍是-2^31 到 231-1,而long是-263 到 2^63-1。

SparseBooleanArray,SparseIntArray,SparseLongArray,這三個數據結構的key值的類型也是int,value值的類型也固定,SparseBooleanArray的value固定為boolean類型,SparseIntArray的value固定為int類型,SparseLongArray的value固定為long類型。

總結一下這四種數據結構的key,value類型:

SparseArray          <int, Object>
LongSparseArray      <long, Object>
SparseBooleanArray   <int, boolean>
SparseIntArray       <int, int>
SparseLongArray      <int, long>

上述四種數據結構的key類型都是int,而不是Integer,相較於使用HashMap的話,省去了裝箱拆箱過程,查詢、存儲等操作效率更高,而且int的存儲開銷也遠小於Integer。

SparseArray實現原理

SparseArray內部的重要屬性:

public class SparseArray<E> implements Cloneable {
    private static final Object DELETED = new Object();
    private boolean mGarbage = false;
    private int[] mKeys;
    private Object[] mValues;
    private int mSize;
}

DELETED

static final 的一個靜態Object實例,當一個鍵值對被remove後,會在對應key的value下放置該對象,標記該元素已經被刪除,只是標記刪除,沒有真正的刪除。

mGarbage

當值為true,標誌數據結構中有元素被刪除,可以觸發gc對無效數據進行回收,真正刪除。

mKeys

用於存放Key的數組,通過int[] 進行存儲,與HashMap相比減少了裝箱拆箱的操作,同時一個int只占4位元組;一個重要特點,mKeys的元素是升序排列的,也是基於此,我們才能使用二分查找。

mValues

用於存放與Key對應的Value,通過數組的position 進行映射;如果存放的是int型等,可以用SparseIntArray ,存放的Values也是int數組,性能更高。

mSize

mSize的大小等於數組中mValues的值等於非DELETED的元素個數。

remove方法源碼:

    public void delete(int key) {
        //查找對應key在數組中的下標,如果存在,返回下標,不存在,返回下標的取反;
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //key存在於mKeys數組中,將元素刪除,用DELETED替換原value,起標記作用;
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                mValues[i] = DELETED;
                mGarbage = true;
            }
        }
    }
     
    /**
     * @hide
     * Removes the mapping from the specified key, if there was any, returning the old value.
     */
    public E removeReturnOld(int key) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
     
        if (i >= 0) {
            if (mValues[i] != DELETED) {
                final E old = (E) mValues[i];
                mValues[i] = DELETED;
                mGarbage = true;
                return old;
            }
        }
        return null;
    }
     
    /**
     * Alias for {@link #delete(int)}.
     */
    public void remove(int key) {
        delete(key);
    }

二分查找:

class ContainerHelpers {

    // This is Arrays.binarySearch(), but doesn't do any argument validation.
    //第一個參數array為keys的數組,第二個為數組中元素個數(與keys的length不一定相等),第三個value為目標的key
    static int binarySearch(int[] array, int size, int value) {
        //lo為二分查找的左邊界
        int lo = 0;
        //hi為二分查找的右邊界
        int hi = size - 1;
        //還沒找到,繼續查找
        while (lo <= hi) {
            //左邊界+右邊界處以2,獲取到mid 的index
            final int mid = (lo + hi) >>> 1;
            //獲取中間元素
            final int midVal = array[mid];
            // 目標key在右部分  。。。。感覺這部分太簡單了
            if (midVal < value) {
                lo = mid + 1;
            } else if (midVal > value) {
                hi = mid - 1;
            } else {
                //相等,找到了,返回key對應在array的下標;
                return mid;  // value found
            }
        }
        //沒有找到該元素,對lo取反!!!!!很重要
        return ~lo;  // value not present
    }

該方法是通過二分查找返回了當前key的對應於mKeys數組的下標,如果沒有找到,就返回一個特殊的負數。二分法返回的數值如果非負數,我們則對其所對應的value進行替換成DELETED,用於標記該key已經被刪除,但是key仍然存在於mKeys數組,因此刪除是一個偽刪除同時,我們將garbage賦值true,代表數組中可能存在垃圾。

put方法源碼:

    public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        //原來已經有key,可能是remove後,value存放著DELETED,也可能是存放舊值,那麼就替換
        if (i >= 0) {
            mValues[i] = value;
        } else {
            //沒有找到,對i取反,得到i= lo(ContainerHelpers.binarySearch)
            i = ~i;
            //如果i小於數組長度,且mValues==DELETED(i對應的Key被延遲刪除了)
            if (i < mSize && mValues[i] == DELETED) {
                //直接取代,實現真實刪除原鍵值對
                mKeys[i] = key;
                mValues[i] = value;
                return;
            }
            //數組中可能存在延遲刪除元素且當前數組長度滿,無法添加
            if (mGarbage && mSize >= mKeys.length) {
                //真實刪除,將所有延遲刪除的元素從數組中清除;
                gc();
                //清除後重新確定當前key在數組中的目標位置;
                // Search again because indices may have changed.
                i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
            }
            //不存在垃圾或者當前數組仍然可以繼續添加元素,不需要擴容,則將i之後的元素全部後移,數組中仍然存在被DELETED的垃圾key;
            mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
            mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
            //新元素添加成功,潛在可用元素數量+1
            mSize++;
        }
    }

put方法也調用了ContainerHelpers.binarySearch方法先進行查找,查找到大於0,則在數組中找到了對應的key,此時,直接將value進行替換即可;如果沒有找到,返回的是~lo,將i取反後,此時i就是我們需要插入的位置。

此刻,我們找到了i,就是目標位置,如果沒有設置延遲刪除(DELETED),那麼由於數組的特點,我們需要將i序號之後的數組後移,這樣就會產生一個較大的性能損耗;,但是如果我們設置了延遲刪除且mValue[i]上當前的元素恰巧為DELETED,那麼此時我們可以用當前的key替換原來mKeys的key,且用當前value替換DELETED;這樣就成功避免了一次數組的遷移操作。

但是事情不可能永遠湊巧,如果,i上的元素並非恰好被刪除呢?那麼此時我們會判斷mGarbage,如果為true那麼我們執行一次gc,將無效數據移除,再進行一次二分查找,然後將i之後的數據全部後移,將當前key插入;如果mGarbage為false,那麼證明其中的數據全部存在,因此不需要gc,直接進行元素插入並將數組後移。

Get方法源碼:

    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];
        }
    }

與HashMap做比較

1、key類型都是int,而不是Integer,相較於使用HashMap的話,省去了裝箱拆箱過程,查詢、存儲等操作效率更高,而且int的存儲開銷也遠小於Integer

2、使用二分查找法判斷元素的位置,所以,在獲取數據的時候非常快,時間複雜度為O(lgN),比HashMap快的多,因為HashMap獲取數據是通過遍歷Entry[]數組來得到對應的元素。

3、使用場景

雖說SparseArray性能比較好,但是由於其添加、查找、刪除數據都需要先進行一次二分查找,所以在數據量大的情況下性能並不明顯,將降低至少50%。滿足下麵兩個條件我們可以使用SparseArray代替HashMap:

a:數據量不大,最好在千級以內,如果在數據量比較大時,它的性能將退化至少50%。
b:key必須為int類型,這中情況下的HashMap可以用SparseArray代替。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 一、項目代碼 #vim /usr/local/src/mail_api_flask/run.py """ mail_api_flask 為基於Flask web框架開發的線上發送郵件api,實現功能復用。支持html模板郵件。 """ from flask import Flask from fla ...
  • Linux 中的 Bash 腳本支持對變數的操作,下麵鹹魚將介紹 Linux Bash Shell 中關於變數的 5 個易錯點 因為編程習慣,這類現象往往發生在大多數使用過其他流行編程語言的程式員身上 變數賦值 對於許多編程語言(例如 Python),變數賦值的時候在等號兩邊添加空格是一個好的習慣 ...
  • MySQL基礎:函數 函數是指一段可以直接被另一段程式調用的程式或代碼。 字元串函數 MySQL中內置了很多字元串函數,常用的幾個如下: | 函數 | 功能 | | : : | : : | | CONCAT(S1,S2,...Sn) | 字元串拼接,將S1,S2,...Sn拼接成一個字元串 | | ...
  • SQL:DML、DQL、DCL DML:Data Manipulation Language(數據操作語言) DML用來對資料庫中的數據記錄進行增刪改操作。 DML-添加數據 給指定欄位添加數據(一條數據) INSERT INTO 表名(欄位名1,欄位名2,...) VALUES(值1,值2,... ...
  • 摘要:本文就針對因USING子句的書寫方式可能導致MERGE INTO語句的執行不下推的場景,對USING子句的SQL語句進行改寫一遍,整個SQL語句可以下推。 本文分享自華為雲社區《GaussDB(DWS)運維 -- values子句做MERGE數據源導致SQL執行不下推的改寫方案》,作者: 譡里 ...
  • 什麼是主數據? 主數據是一組用於提供有關業務數據(如位置、客戶、產品、資產等)情境的標識符。它是企業或單位內運行業務必不可少的核心數據。否則,將無法統一比較系統之間的數據。但是,並非所有主數據都是一樣的。被指定為主數據的數據類型可能因行業而異。即使在同一行業的不同業務實體中,主數據的示例也可能是離散 ...
  • 眾所周知Redis有以下幾種常見的數據類型 String(字元串)、List(列表)、Set(集合)、Hash(哈希)、Sorted set(有序集合)、Stream(流)、Geo(地理空間索引)、Bitmap(點陣圖)、HyperLogLog(基數統計)等。 我們最常用的就是String(字元串)... ...
  • 資料庫優化是一個綜合工程,不僅僅是需要DBA參與,更重要的是研發設計人員針對PG資料庫的特點來進行相關的優化設計。不過對於DBA來說,一旦接到上線和運維任務,基本上都是木已成舟,軟體設計方面留下的坑已經挖好,DBA的作為已經十分有限了。不過既然要乾運維,那麼少不了就要參與優化。PG的優化工作該如何開... ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...