00:00
我们已经知道整体的利用布隆过布隆过滤器进行去重UV去重的一个思路，成整个的程序框架我们也已经搭起来了，我们这里边用到了一个自定义触发器，对吧？每来一条数据，直接把当前的状态清空，触发这里的这个计算操作，那关键就在于我们这里的计算操作怎么去做了，那当然这里边要做这个去重，我们用到了不能过滤器，那么应该自己定义一个，或者从已有的这个，呃，外边的这个库里边去引引入，对吧？啊，那这里边我们自己来定义一个布隆过滤器啊，自定义一个布隆过滤器，其实通过我们前面的介绍，大家会发现当前这个布隆过滤器啊，它主要的我们就叫做bloom吧，呃，因为如果叫bloom filter的话，呃，其实可能会跟本身flink里边啊，已经引入的一些布隆过滤器会有这个名称的冲突啊，我们为了防止它出现这个状况，我们直接就叫bloom，然后这里边呢，诶，可能会有大家想这个一个布。
01:00
通过滤器主要主要的这个要素是什么呢？我们说它本身底层就是一个位图对吧？哎，所以这里边其实关键就在于大家注意啊，主要的这个成分啊，主要就是主要就是一个位图，这是存储空间对吧，和一个，那就是里边的每一位到底怎么样去对应这个规则，就是我们说的哈希函数，所以它里边所谓的不能过滤器，就是这两个东西的一个一个整合，当然可能涉及到一些优化算法，对吧？哈希函数可以有多个，我怎么去选择位图，诶，我到底创建的那个位图大小怎么样去定义，那我们这里边就不做那么复杂的优化了啊，大家只要知道原理，我们就直接把这个位图的大小从外部传入就完事了，对吧？比方说这里边我们定义一个size啊，直接放在这儿长整形传进来，然后一个extend，呃，这个它应该是一个可可这个序列化的一个类型，对吧，S把它定义出来。
02:01
把它定义出来，然后接下来里边其实啊，那首先我们想到它就是一个位图和哈希函数嘛，那这这个位图我是不是要去你有开拓开开辟这么一块这个存储空间呢？定义这个位图呢？诶不能，因为我们这里边如果要你在这儿去定义的话，那就变成又成了我们内存里边去创建它的这个实例了，对吧？那这个位图又占用的是我们的内存了，所以这里边呢，我就只定义当前位图的大小，那具体的位图要放到red里面去，对吧？我我只要这里能控制它的那个大小就可以了啊，所以接下来我这里边就定义一个当前这个private的一个变量啊，定一个这个value啊，我就叫做cap它的容量，那我默认就是把这个外部的这个size传进来啊，那大家可能知道，就就是真实做优化的场景下，我们想要的那个size是什么呢？一般想要的是二的整次幂，对吧？哎，一要你要是二的整次幂的话，我们划分这个字节啊或者。
03:01
呃，做这个提取，做这个内存管理的时候也方便嘛，所以一般情况是要这个二的整次幂的啊，但是这里边我们就不做这个详细的这个算法调整了，对吧？传什么就是什么就完了，呃，然后这里边再做，接下来想要考虑的就是一个哈希函数了啊，哈希函数，那这个哈希函数我们dif抵DeFine一个哈希啊，本来我们这个底层就有这个哈希扣，这里面只是给大家举一个例子啊，看看这个哈希到底应该怎么做，比方说我应该有一个value，这是传进来的对吧？你要对谁做哈希，我们现在对那个user ID做哈希嘛，我这里边把这个定义成string，因为这个不一定是长整形对吧？呃，String string的话，这个涵盖的范围更广一点，然后另外我还可以传一个什么呢？传一个随机数种子来表示我后边要做的一些随机化的处理，对吧，把这个哈希能够打散，然后最后我返回的哈希求出来的是一个长整形的值，然后做一个。
04:02
啊，这样的返回好，先把它当前的这个，呃，就是整体的输入输出先定义好，然后接下来哈，接下来呢，在里边我先定义一个变量，这是我最后要返回的这个result啊，初始时先给一个是零，然后之后做什么操作呢？啊，其实非常简单，就是便利我们当前value里边的每一个字节把它摘出来啊那有同学说摘出来怎么做操作呢？难道是每个当前的每个字符对吧？每个叉去做一个加法吗？加起来就完事了吗？哎，当然不能那么简单，你如果要直接叠加的话，哎，那我们说这个你输入一个ID是ABC和输入一个CBA，那不就一样了吗？对吧？哎，这这就是很容易出现哈希碰撞对吧？所以这里面我们的函数一般这个哈希函数它怎么做呢？一般就是每一位去便利做某一种操作，然后这个做操作的过程当中呢，要结合这个随机数种子给它做一个包装和调整啊这个可能不太好理解，那这里边给大家。
05:02
直接写出来啊，比方说针对每一位啊，哎，这里边我们从零到当前，Until，当前这个value的less，便利我们里边的每一个字节，对吧？啊，把这个先定义出来，然后我们当前的result就做一个调整，基于之前的result，我干个什么事呢？先乘以这个C的随机数种子，然后接下来再加上当前value叉at当前这个艾的这个字符的这个值啊，大家看这个效果就是什么呢？我先做了一个变化调整，然后再加上这个值，得到了一个新的值，下一位就是下一个字符，对吧？在读进来的时候呢，我又在之前的这个基础上再乘一次，然后再加下一个，这就相当于每一位，每一个位置上的这个字符都有了一个不同的权重，对吧？啊，就是你越在靠越靠前的这个字符，这个权重就乘的越多，乘这个C的。
06:02
的这个次次次数就会越多啊，所以这是一个非常简单的一个经典实现啊，啊，那最后我们要返回一个返回啊哈希值对吧，要注意要在我们当前这个size size范围内对吧？哎，那有同学说这个怎么去做这个判断呢？哎，你可以做去去做这个取鱼的操作对吧？这是一个常见的，那另外还有一个我们说要要呃映射到映射到size范围内，或者说cap范围内容量对吧？我们这里面不用这个取鱼的方法，给大家用另外一种方式，什么方式呢？我直接用这个cap减一，这里大家要注意一下啊，我这里边哎，默认cap应该是二的整次幂对吧。整次幂，哎，所以什么叫二的整次幂呢？哎，就是那那不就是二的几次方嘛，对吧，写成二进制，它比较有特点，写成二进制就是我们最终在这个呃，内存空间里边存储的方式嘛，它如果是二的整次幂的话，那是不是就永远都是前面一个一，后边很多个零这样的状态啊，对吧？那大家知道如果要是一的话，这是二的零次幂，二就是一，零后面一个零二的一次幂，对吧？啊，那两后面两个零，二的二次就是4100就是四，那10002的三次幂就是八，哎，所以二的整次幂都有这个特点，一个一后面很多个零，那这里我如果减一的话，是不是就相当于全是一啊，对吧，后面的数就全是一了，然后我干个什么事情呢？做一个谓语操作，跟我当前的这个result做一个谓语操作，哎，那大。
07:57
他想我最后得到这个比方说啊，我当前这个cap，我要求二的四次幂，大家知道它肯定就是一后边四个零对吧？你如果写成一个字节的形式的话，就是0001000016嘛，写成这个，那那如果说这个容量只有这么大的话，我减一之后是不是就是00001111啊15对吧，后四位都是幺，前面都是零，然后你跟这个result做谓语，那是什么了之后与一个零是不是前面的都是零啊，与一个一后四位是不是相当于就都是自己本身的那个数对吧？本身你是零就是零，是幺就是幺，所以相当于我是对这个result做了一个截取对吧，就是截取它后面的几位，在我们当前范围内的几位。
08:48
啊啊，就是这这就是避免了什么呢？就避免了你做那个取鱼的时候，有时候很容易就出现一个一个就是相当于不同的数，取了余之后得到的那个结果一样，对吧？啊，你直接截取的话，其实行为也是类似的，这是一种不同的实践方式，做了一个谓语运算。
09:08
这是这个布隆过滤器的定义啊。
我来说两句