1. 前言

1.1 关于算法

金庸武侠小说中的主人公在成为绝世高手之前，都会学习一门玄门内功。郭靖有了全真派的内功才能修炼九阴真经、虚竹得到了无崖子的毕生功力后，武学造诣日渐精进、张无忌苦练五年九阳神功，日后才能融合乾坤大挪移。对于程序员，算法就是小说中的内功，编程语言就是不同门派的武功。张无忌因为有九阳神功加持仅用一天就学会了阳顶天几十年都学不成的乾坤大挪移。一名优秀的程序员需要不断的修炼算法内功，才能取得更高的编程造诣。

1.2 Algorithm&Android系列

“算法在实际编程中应用很少，也就是去大厂面试能用得上”，相信这句话是很多程序员对算法误解的写照。其实不然，一个好的算法，它能让程序在最快的时间内执行完，花费最小的内存开销，甚至可以为用户服务更长的时间。算法既然如此重要，怎么样才能学好它呢？我觉得算法学习有两个痛点，其一不知道有哪些算法、其二知道有哪些算法，但是不知道如何使用。Algorithm&Android系列我将结合算法原理和它在Android中的使用场景，拆解Android源码中使用到的那些算法。

2. 位图算法

2.1 一个笑话引起的反思

昨天晚上下班回家，一民警迎面巡逻而来。突然对我大喊：站住！

民警：int类型占几个字节？

我：4个。

民警：你可以走了。

我感到很诧异。

我：为什么问这样的问题？

民警：深夜还在街上走，寒酸苦逼的样子，不是小偷就是程序员。

以上笑话纯属恶搞，如有雷同纯属巧合。我们知道程序的最小组成单位是bit，它要么是0，要么是1。而byte是字节跳动的最小组成单位，一个byte由8个bit组成。int类型由4个byte组成。干货|详解位图算法在Android RecyclerView中的应用

假设有5个int类型[0,2,4,5,7]。那么它将耗费计算机5个字节的内存，160个bit的内存。假设有5亿个不同的int类型数字，那么它将耗费500000000*160个bit。大约9.2G内存。如果能让一个bit代表一个int类型，那么我们将节省32倍内存。大概需要294M内存。

传统存储空间如下：干货|详解位图算法在Android RecyclerView中的应用

位图表示法。假设每个bit所在position值为1，表示position。例如，第2位的bit为1，表示值为2。那么[0,2,4,5,7]可以表示如下：干货|详解位图算法在Android RecyclerView中的应用

8个bit 就可以表示原本需要160个bit的5个数字。是不是非常节省空间呢？

使用bit以及位置来表示数字，叫做位图算法，它的优点是：

节省空间
快速排序
快速查询

2.2 位操作

赋值操作 mData |= 1 << index
清除操作 mData &= ~(1 << index)
查询操作 (mData & (1 << index)) != 0

2.2.1 赋值操作

干货|详解位图算法在Android RecyclerView中的应用

2.2.2 清除操作

干货|详解位图算法在Android RecyclerView中的应用

2.2.2 查询操作

干货|详解位图算法在Android RecyclerView中的应用

3. 位图算法在Android中的实现

3.1 ChildHelper.java

RecyclerView的构造函数，会调用initChildrenHelper()。

//RecyclerView.java
private void initChildrenHelper() {
    mChildHelper = new ChildHelper(new ChildHelper.Callback() {
         //...省略代码                          
    });
}

ChildHelper主要的功能是“逻辑隐藏”RecyclerView上的子View。当View做消失动画的时候，会调用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类中的实现。

干货|详解位图算法在Android RecyclerView中的应用

3.2 getChildCount()

RecyclerView有getChildCount()方法，LayoutManager也有getChildCount()方法，它们有什么区别呢？

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();
      }
});

我们可以看到，调用RecyclerView.getChildCount()方法，返回RecyclerView上所有的View。而调用LayoutManager.getChildCount()会过滤掉，正在做消失动画的View，比如调用了notifyItemRemoved(int position)方法的Item。或者被挤出屏幕而且需要做动画的View。关于更多RecyclerView动画原理，请参考深入理解RecyclerView布局和动画原理。