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

字节小站 等级 871 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技术干货的公众号。关注“字节小站”微信公众号一起成长~

收藏
评论区

相关推荐

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 关于算法金庸武侠小说中的主人公在成为绝世高手之前,都会学习一门玄门内功。郭靖有了全真派的内功才能修炼九阴真经、虚竹得到了无崖子的毕生功力后,武学造诣日渐精进、张无忌苦练五年九阳神功,日后才能融合乾坤大挪移。对于程序员,算法就是小说中的内功,编程语言就是不同门派的武功。张无忌因为有九阳神功加持仅用一天就学会了阳顶天几十年都学不成的乾
RecyclerView基础用法
是一款非常强大的 widget,它可以帮助您灵活地显示列表数据。当我开始学习 RecyclerView 的时候,我发现对于复杂的列表界面有很多资源可以参考,但是对于简单的列表展现就鲜有可参考的资源了。虽然 RecyclerView 的组成结构乍一看有些复杂,但是深入理解以后您会发现它其实非常简单明了。本文会通过创建一个简单的 RecyclerView 实现一
RecyclerView更全解析之 - 仿支付宝侧滑删除和拖动排序
1.概述 这是春节前的最后一篇分享技术的博客了,接下来的时间需要去完善视频讲解,至于今年都干了哪些事有什么成就吹牛的这里就不多说了,声明一下图片资源我是盗用的别人的。这是最后一期分享RecyclerView了,我们直接看这一期需要分享的效果:      这里写图片描述         视频讲解:相关文章:               
RecyclerView更全解析之 - 为它优雅的添加头部和底部
1.概述 上一期的,解决了几个坑。那么这一期我们来动态为RecyclerView去加载头部和底部,为上一期的RecyclerView列表数据添加广告轮播图,至于广告轮播大家可以看一下这一期 ,这里我就不多讲了,直接拿过来用。      视频讲解:相关文章:                                    
Android CoordinatorLayout实现多列表切换并和头布局联动;
注意:不是双列表联动,是多列表和头布局联动; 大概就是和饿了么店铺首页类似的布局框架吧,头布局显示时,列表RecyclerView或ScrollView和头布局一起滚动,头布局完全隐藏后列表再去滚动,可以多个列表切换; 有空再上图看效果吧; ### 1、主要的布局文件,注释写的很清楚; <?xml version="1.0" encoding
Android RecyclerView使用GridLayoutManager间距设置
使用RecyclerView设置间距,需要重写RecyclerView.ItemDecoration这个类。有如下的效果图需要实现,间距只有中间的格子和底部的格式之间有。 Paste\_Image.png 实现方法很简单,因为这个效果是每一行有3个格子,只要每行的第一个格式左边间距为0即可以。其他都设置左边距和底部距离。 代码如下: publ
Android Recyclerview隐藏item的所在区域显示大空白问题的解决方案
最近搞了下Recyclerview,做了增加、删除item的功能。item上方有卡签 ![](https://oscimg.oschina.net/oscnet/0145e835209331d61e7a761ab97fdce5bac.png)  插个图片看下效果,点击底下的添加上去,同时,底下的item消失,这个用notifyItemInserted和n
Android 解决NestedScrollView 嵌套 RecyclerView出现的卡顿,上拉刷新无效
解决卡顿的方法最简单的就是设置RecyclerView的android:nestedScrollingEnabled="false",放弃自己的滑动,交给外部的NestedScrollView处理,就没有出现卡顿的现象了 至于RecyclerView的上拉刷新,可以监听NestedScrollView的滑动监听,具体代码如下: mNestedSc
Android购物车的实现,仿淘宝天猫京东等APP。处理RecyclerView或listview中的选中事件;
很久之前的代码了,拉出来晾晾! ![](https://oscimg.oschina.net/oscnet/78e82c820157a15a259ea62aef8c8b60bc6.gif) ### 购物车大致思路: **分为:商品、店铺、全选;** 商品全部选中后--店铺自动选中;商品未全部选中(若有一个商品未选中)--店铺不选中。 店铺全部选
ListView+RecyclerView缓存类的封装
public class BaseViewHoler extends RecyclerView.ViewHolder { private Context context; //行布局的view private View mView; //用来装载id的集合 用法和map类似
RecyclerView实现倒序列表
RecyclerView实现倒序列表 ================== 标签(空格分隔): android RecyclerView 倒序 * * * ##1、写在前面 实现一个聊天界面,就是类似QQ那种,这里是讲一下倒序排列,不实现QQ的各种高级功能 ##2、ListView 反转数据 只要把数据倒序加入到adapter的数据集中,就可以实现倒
Recyclerview的多种条目
package comp.example.practise9.adapter; import android.content.Context; import android.support.v7.widget.RecyclerView; import android.view.LayoutInflater; import android.view.View

热门文章

最新文章