BitMap的简单实现 & 布隆过滤器介绍数据结构与算法

BitMap 【BitMap的简单实现 & 布隆过滤器介绍】BitMap是一种用时间换空间的思想, 用一个bit位标志int值是否存在, 这样, 40亿int值判重的情况下, 需要申请的内存为 4^9 / 8 * 10 ^9 = 500MB

private byte[] bits; private int cap; public BitMap(int cap) { this.cap = cap; bits = new byte[cap / 8 + 1]; }public void set(int k) { if (k > cap) return; int byteIndex = k / 8; int bitIndex = k % 8; bits[byteIndex] |= (1 << bitIndex); }public boolean get(int k) { if (k > cap) return false; int byteIndex = k / 8; int bitIndex = k % 8; return (bits[byteIndex] & (1 << bitIndex)) == 1; }

应用

ip判重, ipv4地址可以一一映射到int值, 故可以通过BitMap判重
海量数据排序, set到BitMap, 从低到高遍历每位. 如果有重复, 需要救助hash表维护数量(只维护出现次数 > 1的值, 节省空间)

布隆过滤器布隆过滤器是对bitmap的一种优化, 牺牲一丟准确度来节省空间.
如果数值的范围是[0, 40亿], 但是数量只有1亿, 用BitMap就会浪费过多内存. 布隆过滤器的做法是申请大概10亿的空间, 通过hash函数让值落到这个空间内.
如何处理哈希冲突?
定义k个哈希函数, 对于一个值, 会将bit[k1], bit[k2], …的位置设置为1. 判重时, 只要有一个bit位为0, 则表示不重复