布隆过滤器解决"面试题:
- 如何建立一个十亿级别的哈希表,限制内存空间"
- "如何快速查询一个10亿大小的集合中的元素是否存在"
如题
布隆过滤器确实很神奇, 简单来说就是通过多次hash将key存进一个集合中,可以灰常快速地在数亿级的数据中快速查找!
实现布隆过滤器需要用bit位存储的数组, 千万别用int[] ,毕竟一个int整形占32位,一个int = 32 bit!
但是Java没有bit, 那用byte吧,一个byte(8位)当做8位的bit来算吧,每一位代表一个具体的值来进行hash; 解析hash和设置hsah值的时候, 需要位运算提取出每位上的值(每位上的0或1)!
但是java的byte还需要分正负,默认一个byte的范围为[-128,127] !
部分学习借鉴搬运的博客原文链接
https://www.cnblogs.com/liyulong1982/p/6013002.html
https://baike.baidu.com/item/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8/5384697?fr=aladdin
笔记整理
算法核心
- 首先需要k个hash函数，每个函数可以把key散列成为1个整数
- 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
- 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
- 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
优点：
不需要存储key，使用节省空间
缺点：
- 算法判断key在集合中时，有一定(通过优化算法可以降到很低)的概率key其实不在集合中
- 无法删除
典型的应用场景：
- 某些存储系统的设计中，会存在空查询缺陷：当查询一个不存在的key时，需要访问慢设备，导致效率低下。
- 比如一个前端页面的缓存系统，可能这样设计：先查询某个页面在本地是否存在，如果存在就直接返回，如果不存在，就从后端获取。但是当频繁从缓存系统查询一个页面时，缓存系统将会频繁请求后端，把压力导入后端。
- 这是只要增加一个bloom算法的服务，后端插入一个key时，在这个服务中设置一次
需要查询后端时，先判断key在后端是否存在，这样就能避免后端的压力. - 最近还学到, 布隆过滤器还可以防止缓存雪崩, 原理同上.
黑客通过大量请求数据库中不存在的key, 导致遍历整个缓存和数据路进行查询, 每次都无法让前端的缓存发挥效果,缓存系统将会频繁请求后端数据库,很快就会造成系统雪崩.
因此可以利用布隆过滤器进行解决这个问题.
- 解决思路: 将数据库中的key全部建立到布隆过滤器中, 每次请求先查询布隆过滤器; 如果存在,则放行, 毕竟布隆过滤器会有很少部分key会误算!
- 注意: 通过布隆过滤器的值,极大地概率存在着这个key;不通过的key, 那么一定不存在.
模拟布隆过滤器; 先挖坑,扔在这里
一个byte分为8位用,故1250万的byte数组就可以了.
该数组大小为: .
package com.szs.test;
public class myBloomFilter {
//一个boolean只占一个字节, 一个字节是八位,把每个字节拆成八位来用
//一个byte分为8位用,故可哈希出10亿个具体的数据,1.250亿的byte数组就可以了,但是需要125M更多的内存.
// 但是具体题目一般都有内存的限制(比如100M 以内), 还有其他的情况需要考虑!
//10^9 == 10亿 , 故int就够了.( int的取值范围为: -2^31——2^31-1,即-2147483648——2147483647 , 大概最高值为2*10^9)
//如下数组为1.25*10^7大小.
private static byte[] array01 = new byte[12500000];
private static byte[] array02 = new byte[12500000];
private static byte[] array03 = new byte[12500000];
/** 简单的布隆过滤器的main测试类
* @param args
*/
public static void main(String[] args) {
}
/**
* 查找一个key,判断是否存在;若存在返回true,否则返回false
* @param x
*/
public static boolean findKey(long x) {
return true;
}
/**
*
* @param x
*/
public static void insertKey(long x) {
}
/**
* 删除一个key, 暴力for循环进行删除
* @param x
*/
public static void deleteKey(long x) {
}
/**
* 尝试hash后,返回对应的hash值,
*/
public static void hashKeyThreeTimes(long x) {
}
/**
* 存储hash值到数组中的index下标
* @param x
*/
public static void storeHashCode(long hashCode) {
}
}
其他思路
- 量子计算, 一个量子有八种状态,其实就是八进制,两个量子就可以枚举64种状态; 依次类推,十亿级别数据量的时间复杂度为: log810^9= 9 .故时间复杂度为O(1).
- 并行计算: 多处理进行处理.
- 增加系统内存,增加JVM虚拟机的可分配内存.
