【本人秃顶程序员】用Redis快速实现BloomFilter！

太过爱你忘了你带给我的痛 2022-04-23 00:38 298阅读 0赞

←←←←←←←←←←←← 快！点关注

## 背景 ##

最近工作上有个类似需求是： 现有约3亿条数据词典存在于一个csv文件A中，作为数据源。对于 用户输入的任意单词M，需要快速的在A中匹配M单词是否存在。（A文件约3G大小左右，总行数三亿）

拿到这个需求，你的第一想法怎么做呢？

正常思路可能是：

1.  将csv文件A导入某关系型数据库。
2.  sql查询按M匹配。

上面的方式有个明显的缺点是：慢！

3亿多行的数据，即便是建好索引进行检索，匹配到也得话不少时间（笔者没亲自试过，感兴趣的朋友可以自行测试测试，理论上快不起来的）。

目前能 在时间复杂度和空间复杂度上达到最佳的方案，恐怕就是Bloom Filter了， 维基地址：Bloom Filter

> 此处给不太了解Bloom Filter的读者看，熟悉的朋友直接看下一节。

> 本文场景Bloom Filter 使用思路解释：  
> 假设申请了一段bit位大数组（即数组中的元素只能是一个bit位，1或0，默认元素值都为0）  
> 将csv文件A中的每个单词，经过多个hash函数进行hash运算之后得到在大数组中对应的多个下标位置  
> 将步骤2中得到的多个下标位置的bit位都置为1.  
> 对于用户输入的任意单词M，按照2的步骤得到多个下标位置，其对应大数组中的值全部为1则存在，否则不存在。

## 方案选型 ##

实现`Bloom Filter`的方法很多，有各种语言版本的，这里为了真切感受一下算法的魅力，笔者这里决定用java 代码徒手撸了！

另一方面，考虑到分布式应用的需要，显然在单机内存上构建`Bloom Filter`存储是不太合适的。 这里选择`redis`。

redis有以下为操作，可以用于实现bloomfilter：

redis> SETBIT bit 10086 1
    (integer) 0
    redis> GETBIT bit 10086
    (integer) 1
    redis> GETBIT bit 100   # bit 默认被初始化为 0
    (integer) 0

## 实现细节 ##

实现bloom filter的关键是hash函数，一般为了降低误报率、减少hash碰撞的影响，会选择多个hash函数。

那么，怎么写一个hash函数呢？

不要方，我们要的hash是 input: String --> output: int , jdk里面的String类不是恰好也有一个hashCode 方法吗？ 翻出来看一看！

> 欢迎大家加入粉丝群：963944895，群内免费分享Spring框架、Mybatis框架SpringBoot框架、SpringMVC框架、SpringCloud微服务、Dubbo框架、Redis缓存、RabbitMq消息、JVM调优、Tomcat容器、MySQL数据库教学视频及架构学习思维导图

/**
         * Returns a hash code for this string. The hash code for a
         * {@code String} object is computed as
         * <blockquote><pre>
         * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
         * </pre></blockquote>
         * using {@code int} arithmetic, where {@code s[i]} is the
         * <i>i</i>th character of the string, {@code n} is the length of
         * the string, and {@code ^} indicates exponentiation.
         * (The hash value of the empty string is zero.)
         *
         * @return  a hash code value for this object.
         */
        public int hashCode() {
            int h = hash;
            if (h == 0 && value.length > 0) {
                char val[] = value;
    
                for (int i = 0; i < value.length; i++) {
                    h = 31 * h + val[i];
                }
                hash = h;
            }
            return h;
        }

看到这一行`h = 31 * h + val[i];`，貌似原理其实也很简单，每个字符对应的ascii码，经过一个公式计算依次加起来。这里有个系数`31`, 稍微变一下， 不就可以有多个hash函数了吗。

以下是稍加修改后的hash函数：

//总的bitmap大小  64M
        private static final int cap = 1 << 29;
        /*
         * 不同哈希函数的种子，一般取质数
         * seeds数组共有8个值，则代表采用8种不同的哈希函数
         */
        private int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};
        private int hash(String value, int seed) {
            int result = 0;
            int length = value.length();
            for (int i = 0; i < length; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }

剩下的事情便很简单了，对每个词典A中的单词，依次调seeds 中对应的hash函数（这里一共是8个），用redis的setbit操作，将下标值置为1.

redis代码 (这里用pipeline 包装了下。)

@Service
    public class RedisService {
        @Autowired
        private StringRedisTemplate template;
        public void multiSetBit(String name, boolean value, long... offsets) {
            template.executePipelined((RedisCallback<Object>) connection -> {
                for (long offset : offsets) {
                    connection.setBit(name.getBytes(), offset, value);
                }
                return null;
            });
        }
        public List<Boolean> multiGetBit(String name, long... offsets) {
            List<Object> results = template.executePipelined((RedisCallback<Object>) connection -> {
                for (long offset : offsets) {
                    connection.getBit(name.getBytes(), offset);
                }
                return null;
            });
            List<Boolean> list = new ArrayList<>();
            results.forEach(obj -> {
                list.add((Boolean) obj);
            });
            return list;
        }
    }

最后，代码串起来大概长这个样子：

FileInputStream inputStream = new FileInputStream("/XXXX.csv");
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            HashSet<Long> totalSet=new HashSet<>();
            String word=null;
            while((word = bufferedReader.readLine()) != null){
                for (int seed : seeds) {
                    int hash = hash(word, seed);
                    totalSet.add((long) hash);
                }
                long[] offsets = new long[totalSet.size()];
                int i=0;
                for(Long l:totalSet){
                    offsets[i++]=l;
                }
                redisService.multiSetBit("BLOOM_FILTER_WORDS_DICTIONARY", true, offsets);
            }

查的时候也类似：

String word = "XXXX"; //实际输入
            long[] offsets = new long[seeds.length];
            for (int i = 0; i < seeds.length; i++) {
                int hash = hash(mobile, seeds[i]);
                offsets[i] = hash;
            }
            List<Boolean> results = redisService.multiGetBit("BLOOM_FILTER_WORDS_DICTIONARY", offsets);
            //判断是否都为true （则存在)
            boolean isExisted=true;
            for(Boolean result:results){
                if(!result){
                    isExisted=false;
                    break;
                }
            }

## 注意事项 ##

> setbit的offset是用大小限制的，在0到 232（最大使用512M内存）之间，即0~4294967296之前，超过这个数会自动将offset转化为0，因此使用的时候一定要注意。

--------------------

# 读者福利： #

**分享免费学习资料**

**针对于还会准备免费的Java架构学习资料（里面有高可用、高并发、高性能及分布式、Jvm性能调优、MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料）  
为什么某些人会一直比你优秀，是因为他本身就很优秀还一直在持续努力变得更优秀，而你是不是还在满足于现状内心在窃喜！希望读到这的您能点个小赞和关注下我，以后还会更新技术干货，谢谢您的支持！**

**资料领取方式：加入粉丝群`963944895`，私信管理员即可免费领取**