面试题
现在有一个非常庞大的数据(亿级)，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)
分析
采用bloomFilters进行实现(时间&空间尽可能的有效)，bloomFilters也常常用在防止缓存穿透，即服务请求在发送到缓存之前，先查找下bloomFilters，检查对应的key是否存在，不存在直接返回；存在再进入到缓存进行查询->DB查询
实现思路:
实际实现采用多次HASH，查看对应数组内存储的值是否为1，多次hash结果均为1，则认为是存在；存在一定的误判率;hash算法尽可能采用一致性hash方式，确保数据分布较为均匀
package com.hero.cases; import com.beust.jcommander.internal.Lists;
import org.junit.Assert;
import org.junit.Test; import java.util.List; /**
* @Des:判断亿级元素是否存在
* @Auther: 飞狐
* @Date: 2019/3/29
*/
public class BloomFilters { /**
* 数组长度
*/
private int arraySize; private int[] array; public BloomFilters(int arraySize){
this.arraySize = arraySize;
array = new int[arraySize];
} /**
* 写入数据(经过3次Hash，把数组对应的位置标识为1)
* @param key
*/
public void add(String key){
int first = hashcode_1(key);
int second = hashcode_2(key);
int third = hashcode_3(key); array[first % arraySize] = 1;
array[second % arraySize] = 1;
array[third % arraySize] = 1;
} public int hashcode_1(String key){
int hash = 0;
int i ;
for(i = 0; i < key.length(); i++){
hash = 33 * hash + key.charAt(i);
}
return Math.abs(hash);
} /**
* FNV1_32_HASH算法
* @param data
* @return
*/
private int hashcode_2(String data){
final int p = 16777619;
int hash = (int) 2166136261L;
for(int i = 0; i < data.length(); i++){
hash = (hash ^ data.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5; return Math.abs(hash);
} private int hashcode_3(String key){
int hash,i;
for(hash = 0, i= 0; i < key.length();++i){
hash += key.charAt(i);
hash += (hash << 10);
hash ^= hash >> 6;
}
hash += hash << 3;
hash ^= hash >> 11;
hash += hash << 15;
return Math.abs(hash);
} /**
* 判断元素是否存在
* @param key
* @return
*/
public boolean check(String key){
int first = hashcode_1(key);
int second = hashcode_2(key);
int third = hashcode_3(key); if(array[first % arraySize] == 0){
return false;
} if(array[second % arraySize] == 0){
return false;
} if(array[third % arraySize] == 0){
return false;
}
return true;
} }
运行结果:
检查1: true
检查2: true
检查3: true
检查999999: true
检查400230340: false
执行时间:2261