II_项目_电商用户行为分析/060_尚硅谷_电商用户行为分析_布隆过滤器实现UV统计（中）

然后接下来我们是不是就要去做这个process操作了啊，这里边我们要用一个不容过滤器去对它进行这个查重，对吧，然后相当于过滤出来这里边。自然大家就会想到，我首先是不是得定义一个布隆过滤器啊，这里边定义一个布隆过滤器。Class就叫做bloom，呃，这里边可以有一个参数啊，因为大家知道布隆过滤器，我们可以定义一个默认大小对不对，Size啊，当然这是一个可以是一个long类型的啊，当然这个就是大家也可以给一个int类型，因为大家知道int类型的话，呃，这个就是有有32位，那那其实正负20亿对吧。20亿的话，这个呃，代表应该是代表多少呢。

已经代表的这个大小是，呃，20亿的话就是。两两两个G对不对，就相当于我们的这个布隆过滤器本身，它的那个未存储，未存储这个位图占的大小最多可以定义两个G的大小了，那这个其实一般情况是足够用了，前面我们算过那个几十个亿的数据，如果要过滤就是对吧，每个对应一位的话，其实是不是只占几十兆啊，对吧？呃，就是几十个G的数据，其实最后压缩下来只占几十兆，你这里边最大要是这个几个G的话，那其实int类型已经够了，这里边我们还是定义成long吧，就是更大一点啊，就是没上限。呃，这里边它需要去继承一个s lizable，好，然后接下来这里边关键我们是要它里边有什么东西呢？一个就是这个大小，有了这个大小我们就知道位图到底多大了，对吧，好，这个。

位图的总大小。呃呃，当然这里边主要限制的就是胃的数量，对不对，我们这里边在定义一个private。Cap，呃，它其实代表的是什么呢？那大家想这个传进来是是size，那那那不就行了吗？我们还可以给一个默认值对不对，对吧，如果要是size大于零的话，那么我们就用size。Else的话，我们可以给一个默认值，比方说大家觉得多大差不多就就够用了呢，前面我们说大概几十兆就够了，对吧，那我们最小可能给个十几兆吧，比方说这个，呃，这个16兆，16兆应该是一个二的多少次，大家想一想，20 24。

16兆的字节的话，那是。1024是二的十次，二的六次应该是。呃，二的四次是16对吧，所以，所以16兆应该是二的十，呃兆的话，那应该是20对吧？那应该是24对不对，那如果要是字节的话，那具体到win，那是不是应该还要再乘以八对，所以是27对吧？二的27次，所以我们默认的这个大小用这个啊。大家看一未运算对吧，左移27位，那是不是一后边27个零啊，所以按照这个大小去存，是不是基本上就是呃，至少就是就是16兆对不对，相当于能存16兆大小的一个位图，一个bitmap，好，这是我们先给定义好这个啊，然后大家前面说了那个布隆过滤器的核心啊，最重要的应该是一个什么东西呢？

是不是一个哈希函数啊，对吧？定义哈希函数，呃，这里我们就自定义一个简单的哈希函数了，但大家可以用掉一些库，里边实现的更加复杂，更加就是随机性更强的哈希函数，防止碰撞啊。我们这里给大家举一个例子，你既然要计算哈希，是不是得把value传进来，我们的value是K，那就是应应该当成一个字符了啊，就是一个string，然后。是不是还应该有一个随机输入种子啊，给一个int啊类型的种子，这里边返回一个浪类型的哈希计算结果。那这里首先我定义一个result等于零，对吧。

好，呃，哎，这里边。我们定义一个浪类型啊，好，然后接下来。怎么了？诶，这个这个错一直在报啊，呃呃，没关系，我们先把后面先写完，看看他是不是因为这个。返回哦，因为现在没有返回值嘛，对吧？当然当然它会它会报一个错，好我们先先继续往下写啊，然后大家会想到接下来是不是就要算这个哈希位呀，对吧？算这个哈希，那怎么去算呢？其实最简单，对于一个string来讲，是不是一位一位去判断它每一位是什么，对不对，然后根据位每一个字符的那一个那个编码值，然后叠加，按照某种随机计算的一个一个方式，一个算法，然后叠加得到这个result，比方说这里边给大家举一个例子啊，这里边就是I从我们这个零到多少呢？N to一个。

呃，就是value它的。哎，这里边我我觉得这里边应该是有点问题的啊。行，这个我们我们先看一下那个，后边面对我们直接返回一个0L，这里好像还是在报错是吧。

看一眼啊。刚才他那个在提示什么。应该是上面等，哎诶诶，这里边我们应该是这个浪，这里边得有一个等号对吧？哎，这个这个诶正常来讲，我们应该是直接它应该把这个自动给我们补全的啊，但是它这里边没有补全好了，我们先不管它啊。好，这里边。好，这里我们把这一个for啊，这这个这个还是还是从头给大家捋一遍啊，就是这里边定义一个哈希函数，然后我们要返回一个long类型的结果，对不对？呃，这里边定义首先定义一个结果啊，保存结果result等于0L对吧？然后接下来是不是一个for循环，可以去遍历当前的这个value啊，每一位对吧？把这个每一位遍历出来，然后应用一定的算法在这个result原有的result上面去做叠加，一次一次每一位去叠加，那这里边就定义一下这个。

从0UNTIL，呃，这里边是不是到value.length啊，就是这样对吧？呃，从从这个每一位开始去叠加，这里边我们的计算的方式就直接result，最后还要付给result。用result干什么呢？首先我们可以让它乘以C的，这是我们那个随随机数总种子，对吧？我们把它作为一个变量控制进来，然后随机去程取，然后接下来要加一个什么呢？当然要加它当前的那个位，对不对？因为它本来是string，我们char at。一个爱这个位置是不是拿到的，就是对应的呃，那样的那个结果啊，对吧，所以这里边我们可以直接把这一部分要拿到啊，当然当然这里边这个这个result得用一个va类型啊，这个不能resign，所以这里边我们其实就可以把每一位按按照这种方式一位一位去迭代去处理，最后是不是。

每一个字符串都能得到一个很特殊的值啊，而且大家会想到即使是稍微差一点点，是不是因为这个随机数种子选取的不一样，是不是最后它分布也会差很大，这就是一个哈希函数的一个特点对不对啊，往往就是你稍微改一点点，最后的结果分布就差很大，你根本没有办法去碰撞，呃，就是用一种轮旋的方式去去碰撞它啊，这是这个for循环，那最后我们是不是要返回一个具体的结果啊，最后是直接把这个result返回就可以了吗？

再想想是不是这样？也可以，但是大家注意，Result是一个。是一个long类型，一个长整型，我们最后其实要返回的是不是只取它的多少位啊。是不是只取它的27位就可以了呀？啊，所以我们想要的就是他最后的那27位的最后的那个那个效果，那个结果，所以我们这里边可以让他做一个按按位的与运算，跟谁做一个与运算呢？跟前面我们定义好的cap减一，大家想想cap减一是什么？呃，默认的时候cap是一左一二十七位，那应该就是一，后面27个零对不对，那现在减一就应该是前边都是零是不是后边是27个一啊，所以跟它做一个与运算，是不是它得到的结果就一定在。

零到那个27个一之间对不对，哎，所以这就是完全的把它匹配到了我们对应的这个位图能表示的这个位置上去啊，这就是我们的这个布隆过滤器啊。