00:00
各位同学大家好,接下来为大家介绍red位图bit map这样的一种数据结构好了,那么如果对red有一定基础的同学,前五个传统经典版的数据结构或多或少都要了解过,那接下来就要看一下这个bit map它是什么,怎么会出现的,主要用在什么地方,他能干些什么。来吧,同学们,后面的每一个类型啊,新的这些都是诸如此类的灵魂提问,学技术不要只学操作,操作只是基本功,重要是学以致用。那杨哥你给我介绍一种新的位图数据结构,怎么用,用在哪,解决什么问题,走起。一句话啊,首先我们来对它定位,位图是干嘛的?是由零和一状态表现的二进制位的比特数组。说白了是什么?它首先是一个位数组,那么既然是位数组,二进制的说明它的值只能是多少零和一。
01:04
听懂了吧,你可以把它理解为现在。假如说换以前啊,我们呢,有一个数据结构,它是叫string,这个key是这样的,那么这个value它可以是乱七八糟的,什么东西都可以,只要你能写的出来玩活,但是现在不好意思了,哥们,我呢为陀那。它是一个只能保存零和一状态的,那我不管你是什么东东,我现在这个里面,你要么存零,你要么存一存其他的不可以好,那为什么会出这样的一种数据结构,它干嘛的呢?那么下面请注意零和一是最经典的,是不是代表有就是错一,没有就是FALSE0,那么看一下我们的需求,它为什么会出现这种东东呢?用在哪些地方呢?大家请看用户是否登录过,Yes,比如京东APP每日签到送金豆,第二个电影广告是不是被点击过,那么大家都清楚,在互联网行业里面有一个非常厉害,非常挣钱的一个业务,那就是互联网广告,那右下角或者浏览器屏幕两边你点一下,你点了那么广告公司就收费。
02:23
广告厂商就认为投到你这,别人看了,就算你把它关了,只要你点了一下,我就认为今天就应该,比如说点一下一毛钱啊,就像发了条短信一样,给我们的互联网公司,那么第三一个钉钉打卡上班上下签到,那么这样的话呢,类似于这样的需求。假设我们就说每日签到啊,这样就是你今天来了。不要个你今天没有来写个零,那么假设我想统计一下某个用户你这一个月签到情况,或者我想统计一下钉钉上你这一个月统计考勤,你给我来了打个一,比如说从第一天到第30天,把一的全部拿出来,如果二十二天,那么说明是不是你这个月全勤啊,OK,好,类似于这样的需求,就是非常适合我们的bit map,只需要记录零跟一的。
03:09
交给我,那么下面为什么要这个呢?那好,杨哥,我不服气。咱们还是那还是那句话,咱们学技术不要学操作,不要噼里啪啦的往下走,我不用这个。那了不起,我头铁,你不就是一个签到吗?我建一张表不可以吗?第一种。我这建立一张签到表。有个用户ID,谁先来,我就插入一条记录,对吧,你假设一个用户,我最极端的一个情况,我就拿一张表记录一些VIP用户,你今天来了音色推一条记录,今天来了音色一条记录。那么请问对于京东。阿里巴巴、天猫这样的体量,每天都有新的数据逛上去,你这个马赛克是不是天天就满了?好,那杨哥懂了。差弱不可以,我不服气,你继续头铁。
04:02
那我修改吗?Update。固定好。我们的这个用户好更狠一点,我为了更加明确的统计他今天来没来,我这开30个字段,反正每个月就最多12,每一年最多12个月,每个月30天。好,我这开31个字段。今天来了写个一没来,默认值就是写个零,最后来统计一下这个user ID,这条记录有几个一,几个零就知道了,他今天来没来没问题,但是你要搞清楚,这个时候你会发现每一天。你是不是要做这个,还是那句话,如果对于大厂这样的体量,千万级的用户量,你这个买扛不扛得住,每天要么不是插入叫update,天天有频繁的写操作,那这个时候你告诉我你的数据吃得住吗?所以我们能不能既要完成,既要又要还要,我不但要保存你每天的是否登录成功的,是否签到的状态外。
05:04
而且还要保证别太大,你要用单纯的买车票来干,太大了,所以呢,各位同学走一眼,我们干脆就来这么一个动作。首先。一个字节是一个贝等于八位,那么零到七是不是刚好就是一周,你可以把它理解为对吧,你可以七位都用,或者你个第零位,你不用,你从第一位开始,那这个时候我们就会发现上面呢,有许多小格子组成,那么都是01010101只放010101是不是可以用它来判断以所谓呢?那么这样说的专业一点,是不是每一个小格格就是一位,每一位就代表你今天的某种状态,与之都要外面做好业务的定义或者规则的映射,有了写个意见,今天签到了写个意见,今天没有来写个零,好,所以我们却可以拿到,这样如果你只是用,假设你七天啊,我只用一个字节就来保存,但是你要用MYSQL的话,你肯定要用七条记录,或者要更新数据库七次,那么你告诉我哪一种更方便?
06:08
所以我们呢,设计出了bit map位图这样的一种数据结构,它的来龙去脉用在哪,是这个意思,那接下来请看它的底层什么类型,String,哎,也就是说细分的话啊。我们呢,String在表现层一个叫string类型,一个叫bit map,但是玩底层bit map,它的底噪还是string,它是以用string类型作为底层数据结构,实现了一种统计二值状态的数据类型。那么大家都清楚啊,我们在Java里面都明白,你们一定学过一种数据类型是不是叫哈希迈普,那么假设我问你,我们对外是还有一种数据类型叫哈希赛特,如果现在问你哈希赛特的底层源码是什么?这个不用我解释了吧,OK,好,那接下来我们大家看位图的本质是什么?数组类型是什么?是string,那么它是基于死终类型按位的一种操作速度,那么每一个位都有二进制零和一构成,那么每一个对应的一个偏移量,我们称之为一个什么索引,那再直白一点啊。
07:10
再来再来四七二十八,那么假设这个下标第是16,那么我们就定解第16天这个月的,比如说。7月16号你来了,第16位加个一,17号你没来,就是个零,18号你又来了,再加个,那么这样告诉我是不是30,就是相当于说32位就可以统计某一个用户一个月他是否来过,是否签到,是否打卡的一个状态呀,诶所以说这个时候我们就会发现我既统计了,而且bit特map支持的最大位数是02:32次方,使用512兆内存可以存达多少,接近40个G,那么这个时候是不是就完成了我们的既可以标注统计,而且占用的内存还比较小,不用频繁的花销,数据库的开销,就这么简单,OK,好,那么我们就明白了,他能干些什么呢?那么一句话。
08:02
用于状态记录或者统计耶耶温类似于奥米布尔型,原子布尔型。好了,那么同学们基本命令1234,主要就这四个啊,他的命令不多,重要的是对于某月问题,这个就是一把尖刀,就是一个先锋部队,非常适合解决,尤其是什么尖到记录,来吧,同学们。首先啊,Set be开高,它的公式是set bit key offset就偏移外,那也就是说,比如说你第几天想签到,写个一好,那第这个K的第多少位多少多少位,第几个比特位有多少值?那么答案请看一下啊,Set be k1,一,Set be k1。这个K的第七位有个一,那么按照零到七的话,那是不是就是我们的零幺,然后00000。1OK,那么get k1注意比特位的底子是不是也是string,也可以用string来取来取,那么对应的二进制它阿斯克码就是A,那么下面我们可以看一下啊。
09:08
对应的假设我们先保存塔K1,一和一,由于啊,它的上面是它的一,01010的值,下面是它的下标,那么看好一这个KE1的第一位零,一第一位是多少就是一,那么如果我们执行了这么一条命令,它保存到re里面的样子就是这样的,切记啊,Bit map的偏移量式通计零开始好,那么同学们,我们简单的给大家进行一下代码的讲解和命令的实操,那么set b,假如说这个K1啊,第一位是好,那第二位也是一,没问题吧,第三位也是一,就代表啊假设这个K1。就是我假设一月份或者七月份,我这个月第一天七月7月1号7月2号7月3号来没来,那么假设啊,我7月3号我写个七怎么着错误了,所以说这个Y啊,用set,它只能是什么零和一,OK好,那假如我要把它改回。
10:11
没问题吧,所以这个叫that be,好,现在这个K一看一眼啊,以前我们大家都清楚K1它的类型是什么,是string,现在怎么着还是string,所以说set相当于我们什么string类型的类,OK,好,还是个string,那么这个就是我们的that be,那么get be,就set be,那么自然而然是不是有get be,那么来吧,现在我get beat k1,那么请问第零天有没有没有第一天来没来,来了,第二天来没来,来了第三天没来,第四天没来,那么假设啊,一年是365天,你看啊,它的默认题是多少?Offset是偏移辆,那你一个K是不是可以记一周,一个月,一年甚至十年这个数值,反正都是一些01010101的一些长位,一,一些长度位,那么假设现在第365天,一年365天。
11:09
对标我们的12月31号,来不来没来,就这么简单,OK,好,我们set get beat,那接下来啊。这个叫string lengths干嘛呢?统计这个字节数占用了多少啊?情况是这样的,那么同学们请听我讲,大家请看啊。现在我们呢,塞比K2第零天来了,第七天占用了一位也来了,那么这个时候我K2多少零到七是不是就是一个字节啊,OK,好,但是呢,第八天我也来了,那对不起,几个字节,两个字节它都是八位一组,八位一组这么说能跟上,所以不是字符串长度,比如说不是说呃,假设这个只应该占了三个啊,不是这样的,反正我给你的就是零到七,八位一组,八位一组它是按照什么字节来进行统计,那么超过八位以后,自己按照八位一组。
12:03
一个字节一个字节再扩容,好,那么同学们,我们sat be假设K2第零天来了,那么第七天我也来了,对吧?一次啊,就给八位,那么s tr lengths k2多少字节,一个字节,那再来K2的第八天我也来,哎。首乌啊,那么现在set be的第八天我也来了,那么好,这个时候我们的lengths是多少?大家看一下K2是不是占了两个字节,OK,那么以此类推,如果不管你就是没用,反正你每次申请就是一个字节八位,好那么这是我们的一个什么str,那么这个B,看它是什么东东呢?请看全部键里面含有一的有多少个,哎,那这个呢,就比较合拍了,是不是就是一种全是一的一种检索统计,OK,那么好啊,各位同学,我们简单的来看一下啊,假设set b啊,这个UID,那么这个就是什么罗个印假设啊,呃,这个UIUUID。
13:10
Log个IN123这个用户,那么假设第一天来了,第二天也来了,第三天也来了啊,那么比如说这个呢,是代表是单月它的登录次数,那么be countt,好u I idea log in123号用户,那么下面总共有多少啊,那么统计一下这个月啊,我们默认就代表这个用户他单月的登录次数,签到次数,用个bit看是不是明白哦,你这个月只来过三次,哎,某个影片你只点击,你只点击过三级,那么这样的话,每一个bit就反正占的很小,我这个每一个用户来一个千万级别的也不怕,那么这个时候干了就加个一,没干就标个零,OK好了,那么接下来这个时候我们B的看他。全是一的统计,OK,那么接下来比特就是比特位的运行操作,那下面啊,比如说这个是代表。
14:08
123这个用户,那么还没有,还有没有这个这个456这个用户呢,那比如说我想看看啊,连续两天签到的用户有多少,那么来吧,我们呢,类似于这样的一种诉求,先说我们的。需求请统计一下我们本网站连续两天或者连续十天都签到的用户,或者一周,那么假如说啊,我们某个网站,或者说某个视频网站,某连续三天都看了这个游戏直播的用户是哪一些?1000万的用户,我们做一个用户ID和位置的映射啊,比如说零号外,我们这个ID就是这样的,那么这这是什么意思呢?啊,比如说我们的h set啊,这时候这个K就是我们的。用ID map啊这个field,比如说。现在假如说啊,这个值。
15:04
它是零,我们呢,就是代表这个用户没问题吧,那么再来啊,假设现在一它呢,就是代表这么一个用户同学们。这么说能跟上。没问题吧,那么h get沃,那么假设啊,UID映射我全部拿下来,零就代表这个用户,一就代表这个用户,没问题吧,那这个时候我们先做他一张映射表,然后我们再这么干啊,Set bit,比如说。2020年8月8号,那么对标现在,比如说2023年1月1号。零登录过一登录过,二登录过,那么对标这是不是就是零登录过就代表UID这个用户流水用户号它登录过一有就代表这个用户登录过,这么说听不听得到,那么这呢,我们就简单了,那么假如说啊0123,那么这个就是我们的set be,然后呢,我们呢,直接20230101,那么假设1月1号这一天对吧,或者就说随便一个一月份都可以,那么搁到这儿,零号用户登录过,那现在一号用户也登录过,好。
16:26
我们呢,简单的来看一下,看了一下,我们看一下get be是不是2023年1月1号,那么这告诉我第零位有没有摇有这个一,那么对应的映射这个第零号用户是不是就是我们这个用户,哎,那么诸如此类啊,0123,那么同学们请看0123全部都来过,这么说能跟上好,这是我们的1月1号的,那么再来啊,那么同学们现在呢,我把它修改成了1月2号,只有零和二这两个登录过,这么说能跟上好同学们啊,零来过了,二来过了,那么大家请看现在我这个比特位是不是有两个,那这个时候我们想干什么呀?请给我统计一下。
17:13
那么现在连续两天都签到的用户啊,我们先各自单独统计,逼着看,20230101几个有四个,20230102几个两个,那么这个时候be o op大家请看。Operation这是啥东东啊,是不是就告诉我大哥,我们现在呢,这个beat operation,我们在照这个命令,它有什么and what not,有点类似于用的什么与或非,那么这个操作位的话,就这四个,那么下面我要求一个什么都有的,所以呢,我们在这儿用那个什么and,那么两天都来的,对吧,是不是要合并and,那么这个目的K,那么我们假设我们这个K啊,就叫K3,那么现在就是个合并统计的,那么你要统计哪两个,我要统计20230101和二零二三零一零二两天都同时登录签到的用户有几个,那么同学们漏眼,这个时候告诉我,我们这是不是只有一个,那么下面。
18:21
我抱歉口误,这个一代表是什么?呃,错,操作成功,那么这个时候be count k3几,所以说连续两天都登录的用户有几个,只有两个,哎,这样的统计非常快,而且也不占内存,确确实实实现在大厂商都在用的技能,那么到最后我们讲spring boot跟微服务整合了以后,那我会用Java操作一下命令,你是不是完全可以实时的统计,每天后面跑一个什么叉叉l job定时任务,天天是不是给你老大查询出现在我们某个视频某个广告的点击率分析啊。OK,好,那么搁到这里以后,我们就完成了我们的B套相关的说明,那么最终我们呢,来看一下在B套的案例假设啊,继续这是基本命令,下面呢说两个案例,按照天来统计,很简单了,那么这个呢,我就不再敲了,和前面的差不多啊,那么假如说啊,签到用户U1这个用户。
19:20
2021年六月份,那么第零天来了,第一天来了,第二天来了,那么噔噔噔噔。红框框是一个人,下面看看他第三天来没来,来了,那么下面再看看六月份第30天他来没来,没来,那么最后我想统计一下怎么着,我这个用户2021年六月份从第零天到第30天,他总共签到登录了几天?那么123456共计多少天,六天?那么请问如果你们公司要做个什么考勤系统啊或什么实时打卡呀,那么请告诉我用这个是不是就是最经典的,你记了几天,然后beat看一统计,马上给你查询出来呀。
20:05
OK,好了,那么同学们,这个就是我们bit map位图的基本操作,那么下面它的应用场景呢?我们来看一下啊,那么一年365天,假设我要想统计一下某个用户今年的活跃度,那么他全年,假设他天天都要登录。它要占用多少字节呢?那么来同学们请看一下啊,这贝塔假设就是记录某个用户他的登录的一个。天数,那么假设第零天来了,第一天来了,第15天来了,那么现在给他看他K2多少,是不是三天,那么诸如此类,我们再来K2364天,我从第零天开始,最后一天是不是364啊,他也来了,那么大家请看B的K2多少,就全年它是来了多少四天,那么来如果你写到了三百六十五一年的话,每个T才占用多少个字节46。
21:01
OK,所以说根本就不大,比起买CQ实惠多了,所以对于类类似于这样的钉钉打卡、影片点击广告点击率分析、登录签到用set bit几乎是现在是大厂的标配了,请同学们务必拿下,一定掌握好。那么最后给大家一个理论数据,我们刚才已经看到了,你统计一下一年来了多少天写到364,当然如果你从一开始就写到365,随便你,那么最后无非就是全是一的有多少,占用自己的数是多少,那按照一年我们来算算。按年去存储一个用户签到情况,一年按照365天算,咱们也别考虑,别不考虑什么闰年平年了啊,就平均一点,那么365除以八。约等于46个字节,那么1000万最多也就是44兆,那么假设每天你是用一个1亿位的bit map来存储,也只要占多少12兆比的内存,这么说能跟上好,那么下面十天差不多它呢,也就是120兆,那么最终我们假如说到2023年了,我们把两年前的数据delete塔给它删掉,这也是可以,那么可以进行一下示范,所以它就达到了我们既要又要还要的目的,既可以统计分析又快,而且不占太多内存,非常适合我们的打卡签到。好,那么同学们位图bit map这种数据类型就给大家介绍到这。
我来说两句