导航菜单
首页 >  天富APP >  » 正文

天富APP登入关于使用java string的contains方法与布隆过滤


天富手机客户端


这个过程中,天富APP登入内存会把所有数据加载到内存里面,相信如果数据比较多肯定会造成内存溢出的。这个是contains方法的弊端。
但是如果我们不想要这种太消耗性能的方法,我们应该如何做呢?

首先我们看一个名字叫布隆过滤,看看百度百科:

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的[二进制]向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难
如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,天富APP登录检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表(又叫哈希表,Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的。