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

字节小站 等级 463 1 1

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以及位置来表示数字,叫做位图算法,它的优点是:

  1. 节省空间
  2. 快速排序
  3. 快速查询

2.2 位操作

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

2.2.1 赋值操作

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

2.2.2 清除操作

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

2.2.2 查询操作

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

干货|详解位图算法在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布局和动画原理

4. 更多干货(关注“字节小站”微信公众号慢慢看)


这是一个只分享Android技术干货的公众号。关注“字节小站”微信公众号一起成长~

收藏
评论区

相关推荐

使用 Payload 提高 RecyclerView 渲染效率
RecyclerView.Adapter 中有个带有 payloads 参数的函数,由于这个函数不是抽象函数,被很多人忽略了。该函数定义如下: public void onBindViewHolder(VH holder, int position, List<Object payloads) { onBindViewHolder(holder,
RecyclerView之ItemDecoration使用教程
译文的GitHub地址:RecyclerView之ItemDecoration由浅入深(https://link.jianshu.com?thttps://github.com/thinkSky1206/androidblog/blob/master/RecyclerView%E4%B9%8BItemDecoration%E7%94%B1%E6%B5
Android RecyclerView如何获取滑动距离
获取RecyclerView滑动的距离。 本文演示如何获取RecyclerView的滑动距离。 要实现这个功能,需要给RecyclerView添加滑动时监听RecyclerView.OnScrollListener。 recyclerView.addOnScrollListener(new RecyclerView.OnScrollListene
完美解决Android RyclerView嵌套滑动事件冲突
在Android项目开发中,为了实现需求和兼并用户体验,相信很多人都碰到滑动事件冲突的问题。在Android系统中事件分发机制是一个很重要的组成部分,由于这事件分发机制不是本文重点,故不在此多述,如果有想详细了解的可以自己搜下,网上有很多相关资料详细描述了Android事件分发机制。 一、问题场景 由于RecyclerView自身的优点,使得它已经基本
干货|详解位图算法在Android RecyclerView中的应用
1. 前言 1.1 关于算法金庸武侠小说中的主人公在成为绝世高手之前,都会学习一门玄门内功。郭靖有了全真派的内功才能修炼九阴真经、虚竹得到了无崖子的毕生功力后,武学造诣日渐精进、张无忌苦练五年九阳神功,日后才能融合乾坤大挪移。对于程序员,算法就是小说中的内功,编程语言就是不同门派的武功。张无忌因为有九阳神功加持仅用一天就学会了阳顶天几十年都学不成的乾
Android 自学必备网站
一,Android 自学网站给 Android 自学者朋友推荐几个自学网站:1. Android Developers作为一个Android开发者,官网的资料当然不可错过,从设计,培训,指南,文档,都不应该错过,在以后的学习过程中慢慢理解体会。网站:https://developer.android.com/2. Android专业中文社区Android专业
在微前端中,antd icon createFormIconfontCN 的本地化问题
首发于 <a name"tCbT2"</a 前言用过 antd icon 的朋友们可能知道,对于 createFormIconfontCN,其中介绍的用法是: 使用的是外链的方式javascriptimport { createFromIconfontCN } from '@antdesign/icons';const IconFon
RecyclerView基础用法
是一款非常强大的 widget,它可以帮助您灵活地显示列表数据。当我开始学习 RecyclerView 的时候,我发现对于复杂的列表界面有很多资源可以参考,但是对于简单的列表展现就鲜有可参考的资源了。虽然 RecyclerView 的组成结构乍一看有些复杂,但是深入理解以后您会发现它其实非常简单明了。本文会通过创建一个简单的 RecyclerView 实现一
Android AOSP基础(一)VirtualBox 安装 Ubuntu
AOSP基础 Android框架层本文首发于微信公众号「刘望舒」 前言在Android进阶三部曲第二部《Android进阶解密》的第一章,我介绍了两种阅读源码的方式,其中一种是从百度网盘:https://pan.baidu.com/s/1ngsZs 将源码下载下来,然后用SouceInsight来查看,这种方式很便捷,适合去阅读源码,但是有两个弊端,一个是无
RecyclerView更全解析之 - 基本使用和分割线解析
1.概述 昨天跟自己群里的人唠嗑的时候发现还有人在用Eclipse,我相信可能还是有很多人在用ListView,这里介绍一个已经出来的n年了的控件RecyclerView,实现ListView,GridView,瀑布流的效果。还可以轻松的实现一些复杂的功能,如QQ的拖动排序,侧滑删除等等。相关文章:                     
RecyclerView更全解析之 - 打造通用的万能Adapter
1.概述 离春节只有一个月,同时也在准备公司的节目所以每天有一段时间在练习吉他,刚刚群里有人问我什么时候开始分享仿内涵段子整个项目。算一下时间RecyclerView可能有4期左右的分享,自己又只能周末录讲解视频,所有可能会要等过完春节才能全部开始。   上一篇已经简单的讲解了一下。这一期我们来看一下怎么去打造一个万能的RecyclerView.Adap
RecyclerView更全解析之 - 打造通用的下拉刷新上拉加载
1.概述 这期我们在上一期的的基础上再去增加功能,我相信我们在真正的实践开发过程中肯定少不了下拉刷新和上拉加载。   我们需要思考一个问题上拉刷新下拉加载风格各式各样,淘宝和京东的列表刷新样式就肯定不一样,我们怎么样做到版本迭代的时候可以快速的更改样式。有时还需要显示正在加载数据或者无数据,比如筛选的时候有可能会出现没有数据的情况会显示无数据页面,怎么快
RecyclerView更全解析之 - 仿支付宝侧滑删除和拖动排序
1.概述 这是春节前的最后一篇分享技术的博客了,接下来的时间需要去完善视频讲解,至于今年都干了哪些事有什么成就吹牛的这里就不多说了,声明一下图片资源我是盗用的别人的。这是最后一期分享RecyclerView了,我们直接看这一期需要分享的效果:      这里写图片描述         视频讲解:相关文章:               
RecyclerView更全解析之 - 为它优雅的添加头部和底部
1.概述 上一期的,解决了几个坑。那么这一期我们来动态为RecyclerView去加载头部和底部,为上一期的RecyclerView列表数据添加广告轮播图,至于广告轮播大家可以看一下这一期 ,这里我就不多讲了,直接拿过来用。      视频讲解:相关文章:                                    
一文读懂Android View事件分发机制
Android View 虽然不是四大组件,但其并不比四大组件的地位低。而View的核心知识点事件分发机制则是不少刚入门同学的拦路虎。ScrollView嵌套RecyclerView(或者ListView)的滑动冲突这种老大难的问题的理论基础就是事件分发机制。 事件分发机制面试也会经常被提及,如果你能get到要领,并跟面试官深入的灵魂交流一下,那么一定会让

热门文章

最新文章