干貨|詳解位圖算法在Android RecyclerView中的應(yīng)用
1. 前言
1.1 關(guān)于算法
金庸武俠小說中的主人公在成為絕世高手之前，都會學(xué)習(xí)一門玄門內(nèi)功。郭靖有了全真派的內(nèi)功才能修煉九陰真經(jīng)、虛竹得到了無崖子的畢生功力后，武學(xué)造詣日漸精進(jìn)、張無忌苦練五年九陽神功，日后才能融合乾坤大挪移。對于程序員，算法就是小說中的內(nèi)功，編程語言就是不同門派的武功。張無忌因為有九陽神功加持僅用一天就學(xué)會了陽頂天幾十年都學(xué)不成的乾坤大挪移。一名優(yōu)秀的程序員需要不斷的修煉算法內(nèi)功，才能取得更高的編程造詣。
1.2 Algorithm&Android系列
“算法在實際編程中應(yīng)用很少，也就是去大廠面試能用得上”，相信這句話是很多程序員對算法誤解的寫照。其實不然，一個好的算法，它能讓程序在最快的時間內(nèi)執(zhí)行完，花費最小的內(nèi)存開銷，甚至可以為用戶服務(wù)更長的時間。算法既然如此重要，怎么樣才能學(xué)好它呢？我覺得算法學(xué)習(xí)有兩個痛點，其一不知道有哪些算法、其二知道有哪些算法，但是不知道如何使用。Algorithm&Android系列我將結(jié)合算法原理和它在Android中的使用場景，拆解Android源碼中使用到的那些算法。
2. 位圖算法
2.1一個笑話引起的反思
?昨天晚上下班回家，一民警迎面巡邏而來。突然對我大喊：站住！
民警：int類型占幾個字節(jié)？
我：4個。
民警：你可以走了。
我感到很詫異。
我：為什么問這樣的問題？
民警：深夜還在街上走，寒酸苦逼的樣子，不是小偷就是程序員。
?
以上笑話純屬惡搞，如有雷同純屬巧合。我們知道程序的最小組成單位是bit，它要么是0，要么是1。而byte是
字節(jié)跳動
的最小組成單位，一個byte由8個bit組成。int類型由4個byte組成。
假設(shè)有5個int類型[0,2,4,5,7]。那么它將耗費計算機(jī)20字節(jié)的內(nèi)存，160個bit的內(nèi)存。假設(shè)有5億個不同的int類型數(shù)字，那么它將耗費500000000*160個bit。大約 2G內(nèi)存。如果能讓一個bit代表一個int類型，那么我們將節(jié)省32倍內(nèi)存。大概需要 64M內(nèi)存。
傳統(tǒng)存儲空間如下：
位圖表示法。假設(shè)每個bit所在position值為1，表示position。例如，第2位的bit為1，表示值為2。那么[0,2,4,5,7]可以表示如下：
8個bit 就可以表示原本需要160個bit的5個數(shù)字。是不是非常節(jié)省空間呢？
使用bit以及位置來表示數(shù)字，叫做位圖算法，它的優(yōu)點是：
節(jié)省空間 快速排序 快速查詢
2.2 位操作
賦值操作 mData |= 1 << index 清除操作 mData &= ~(1 << index) 查詢操作 (mData & (1 << index)) != 0
2.2.1 賦值操作
2.2.2 清除操作
2.2.2 查詢操作
3. 位圖算法在Android中的實現(xiàn)
3.1 ChildHelper.java
RecyclerView的構(gòu)造函數(shù)，會調(diào)用initChildrenHelper()。
//RecyclerView.java
private void initChildrenHelper() {
mChildHelper = new ChildHelper(new ChildHelper.Callback() {
//...省略代碼
});
}
ChildHelper主要的功能是“邏輯隱藏”RecyclerView上的子View。當(dāng)View做消失動畫的時候，會調(diào)用RecyclerView#addAnimatingView(ViewHolder viewHolder) -> mChildHelper.addView(view, true)
//ChildHelper.java
void addView(View child, boolean hidden) {
addView(child, -1, hidden);
}
void addView(View child, int index, boolean hidden) {
final int offset;
if (index < 0) {
offset = mCallback.getChildCount();
} else {
offset = getOffset(index);
}
mBucket.insert(offset, hidden);
if (hidden) {
hideViewInternal(child);
}
mCallback.addView(child, offset);
if (DEBUG) {
Log.d(TAG, "addViewAt " + index + ",h:" + hidden + ", " + this);
}
}
注意到「mBucket.insert(offset, hidden);」 Bucket類就是位圖算法在RecyclerView ChildHelper類中的實現(xiàn)。
3.2 getChildCount()
RecyclerView有g(shù)etChildCount()方法，LayoutManager也有g(shù)etChildCount()方法，它們有什么區(qū)別呢？
RecyclerView繼承于ViewGroup
//ViewGroup.java
public int getChildCount() {
return mChildrenCount;
}
//LayoutManager.java
public int getChildCount() {
return mChildHelper != null ? mChildHelper.getChildCount() : 0;
}
//ChildHelper.java
int getChildCount() {
return mCallback.getChildCount() - mHiddenViews.size();
}
mChildHelper = new ChildHelper(new ChildHelper.Callback() {
@Override
public int getChildCount() {
return RecyclerView.this.getChildCount();
}
});
我們可以看到，調(diào)用RecyclerView.getChildCount()方法，返回RecyclerView上所有的View。而調(diào)用LayoutManager.getChildCount()會過濾掉，正在做消失動畫的View，比如調(diào)用了notifyItemRemoved(int position)方法的Item。或者被擠出屏幕而且需要做動畫的View。關(guān)于更多RecyclerView動畫原理，請參考深入理解RecyclerView布局和動畫原理。
4. 更多干貨（關(guān)注我慢慢看）
深入理解RecyclerView布局和動畫原理 RecyclerView滾動時回收和復(fù)用機(jī)制 詳細(xì)聊聊RecyclerView緩存機(jī)制 事件分發(fā)四部曲之一：深度遍歷講解Android事件分發(fā)機(jī)制 事件分發(fā)四部曲之二：嵌套滑動事件分析 事件分發(fā)四部曲之三：CoordinatorLayout事件分析 事件分發(fā)四部曲之四：一文搞懂BottomSheetBehavior
這是一個只分享Android技術(shù)干貨的公眾號。關(guān)注“字節(jié)小站”微信公眾號，讓我們一起成長~