封面
Bloom Filter
BloomFilter是一种空间效率很高的随机数据结构，可以回答“集合中是否存在某一个特定元素”这样问题，最近也在补习算法，在集合中排序搜索都是一个问题。当然在 javascript 中可以通过遍历数组中每个元素，进行比较找出集合中是否有元素。利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter 不适合那些零错误的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。
这里我们想象一下，有一百万个 object，要进行查找，需要遍历每一个 object，这一定是件耗时费力的事，使用 bloom filter 只需进行一次操作。我教你怎么做。bloom filters 的通常是给出两种类型的答案：yes 或 no，这里答案 no 并没有什么特别，表示元素确定不在集合中。
但得到 Yes 的答案时，实际上不是“是”，而是“可能”，是一种概率的是，有关这个概率问题，通过机器学习我对这句话有一定理解。
因此，这种数据结构被称为概率结构，所以返回值表示有可能，虽然这个很有趣，而且是不会错的答案。但是谁需要一个不确定性的答案呢? 这样数据结构适合一种情况，就是在大多数情况下你预期的答案都是“不”的情况。现在就通过例子来介绍一下这种情况。
首先展示这个数据结构是如何工作的，集合中的每个元素都被编码为一个 bitfil。下面是一个哈希函数，使用这个函数将输入文字生成数字。
例如，输入 John 函数返回数字 2，这样使用首字母的编码，字母编码用二进制或运算符来设置第二个位。
["John","Anna","Tom"]
let calculateBit1Value = (value)=> value.charCodeAt(0)%8
const bitNumber = calculateBit1Value("John")
bloomFilter = bloomFilter | bitNumber
//Check bits for "John"
const bitNumber = calculateBit1Value("John")
const isInTheSet = (bloomFilter & bitNumber) !== 0
稍后，可以使用相同的函数来获取 John 的号码来检查 John 是否存在。你可以想象，如果set 中没有该 bit，也就是返回值是 0，这意味着 John 不在集合里。现在问题是为什么返回“真”时，还是不能保证的 john 是存在的呢。原因在于冲突。
图
如果使用相同的散列函数，通过首字母来计算数字，当输入 John和Jane 到函数内，因为具有相同的首字母。这就发生冲突，对于 John 在 set 中，而 Jane 不在set中，散列函数会输出相同的值，得到错误的结果。不知道通过这个小示例大家清楚了吗。
那么 Angular 在哪里用这个 bloom filter 呢？答案是在依赖注入系统中使用。所以依赖注入系统的基础是一个注入器。在学习 angularjs 时候我就花不少时间才理解了什么是依赖注入。
图
依赖注入是一个服务，也是一个容器，通过可以计算服务(service)之间的依赖关系，然后由负责将需要注入的服务(service)实例化后注入到程序中。
图
大多数框架只有一个称为全局注入器的注入器，而 Angular 有一个层级结构依赖注入器，根据对于组件的层次结构，创建一个注入器。
图
对于每个组件都会得到一个的注入器，所以如图会得到层次结构的注入器，如果 widget manager 是由最顶层的注入器中提供的，在最底层的 widget 上面的注入器能够提供所需的服务。
图
这样 Angular 必须通过每一个注入器来确定所需服务的具体位置，也就是由哪个组件所提供的，只有当到达最底层的注入器时，才能得到想要服务，进行解析。
这样做可能需要相当长的一段时间，例如，如果每个注入器都有十个依赖项，十个服务，将需要遍历其中的每一个服务并进行比较，这是一个很长的时间。
图
那么 Angular 是怎么来处理这个问题的呢，为每个注入器都引入了一个 bloom filter，而使用 bloom filter ，正如之前所介绍的，bloom filter 就是一个检测 service 是否在集合中的操作。根据我们之前对 bloom filter 所了解，其答案多数情况下可能都是否定的，所以存在，不存在，返回到顶层是答案可能有(maybe)。如果得到的答案是可能有，那么就可以进行实际比较，找到服务，这就是 bloom filter 在 Angular 中应用。
最后希望大家关注我们微信公众号
wechat.jpeg
网友评论