久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

1、SparseArray內(nèi)部使用雙數(shù)組，分別存儲Key和Value，Key是int[]，用于查找Value對應(yīng)的Index，來定位數(shù)據(jù)在Value中的位置。 2、使用二分查找來定位Key數(shù)組中對應(yīng)值的位置，所以Key數(shù)組是有序的。 3、使用數(shù)組就面臨刪除數(shù)據(jù)時(shí)數(shù)據(jù)遷移的問題，所以引入了DELETE標(biāo)記。 ## 雙數(shù)組  mValue數(shù)組和mKey數(shù)組的關(guān)系是一一對應(yīng)的，通過Key的值，可以定位出該Key在mKey數(shù)組中的index，進(jìn)而可以操作MValue數(shù)組中對應(yīng)位置的數(shù)據(jù)。 ## 二分查找 ```java 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]; } } ``` SparseArray源碼中，所有和Key有關(guān)的操作，第一步都是先通過二分查找，定位出該Key的index，再進(jìn)行后續(xù)處理。 二分查找的前提條件，就是必須是針對有序并且支持下標(biāo)隨機(jī)訪問的數(shù)據(jù)結(jié)構(gòu)，所以它在執(zhí)行插入操作的時(shí)候，必須保證 mKey 數(shù)據(jù)中的數(shù)據(jù)有序。 SparseArray的插入代碼如下： ```java 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); } mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } } ``` 同樣會(huì)使用二分定位查找Key的index，GrowingArrayUtils的insert方法會(huì)完成兩個(gè)任務(wù)： 1、將數(shù)據(jù)插入到指定數(shù)組對應(yīng)的位置上。 2、如果發(fā)現(xiàn)數(shù)組空間不夠，就生成一個(gè)更大的新數(shù)組，將數(shù)組通過復(fù)制的方式，動(dòng)態(tài)擴(kuò)容后搬到新數(shù)組中，并返回新數(shù)組。 ## DELETE標(biāo)記  對數(shù)組的刪除，如果不做數(shù)據(jù)遷移，數(shù)組中必然存在數(shù)據(jù)空洞，SparseArray引入DELETE標(biāo)記，來減少刪除數(shù)據(jù)時(shí)對數(shù)據(jù)的搬運(yùn)次數(shù)。 在插入時(shí)，如遇到DELETE標(biāo)識，標(biāo)識當(dāng)前數(shù)據(jù)已經(jīng)刪除掉了，直接進(jìn)行替換，減少一次插入數(shù)據(jù)帶來的數(shù)據(jù)搬運(yùn)。  DELETE標(biāo)識是在mValue數(shù)組中存儲的，mKey中仍然存儲著它上一次對應(yīng)數(shù)據(jù)的Key值。在一些必要條件下，會(huì)觸發(fā)gc()邏輯，來清理數(shù)組中的DELETE標(biāo)識。在gc()方法中，用了一個(gè)布爾類型的mGarbage屬性，來記錄當(dāng)前 mValue 中，是否存在 DELETE 標(biāo)識，這是判定是否需要 GC 的依據(jù)。SparseArray的**所有和 size 相關(guān)的操作**以及**和數(shù)組擴(kuò)容相關(guān)的操作**時(shí)需要進(jìn)行g(shù)c操作。 ## 參考文檔 [https://juejin.im/post/5da1481e6fb9a04de96e8b72](https://juejin.im/post/5da1481e6fb9a04de96e8b72)