一亿个对象去重，要求内存占用小于1G
source link: https://blog.csdn.net/qq_33709582/article/details/122046773
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
老生常谈的大集合去重问题，很多大厂面试都喜欢问，其实吼，实现很简单，难在优化
优化点：
- 如何提高效率
- 如何减少内存占用
既然如此，那咱先实现，后面再逐步优化
一亿个对象，直接放list，然后判断对象是否存在行不行？
但一亿个对象装进一个list，有亿点点难啊
要不我们先试试100w个？
试试就逝世
我们先准备些工具用来生成对象
1、新建个对象，就叫person吧
public class Person {
private Long id;
private String name;//姓名
private Long phone;//电话
private BigDecimal salary;//薪水
private String company;//公司
private Integer ifSingle;//是否单身
private Integer sex;//性别
private String address;//住址
private LocalDateTime createTime;
private String createUser;
}
2、为了模拟真实数据，我们要用到一些枚举值和随机算法
private static Random random = new Random();
private static String[] names = {"黄某人", "负债程序猿", "谭sir", "郭德纲", "李狗蛋", "铁蛋", "赵铁柱", "蔡徐鸡", "蔡徐母鸡"};
private static String[] addrs = {"二仙桥", "成华大道", "春熙路", "锦里", "宽窄巷子", "双子塔", "天府大道", "软件园", "熊猫大道", "交子大道"};
private static String[] companys = {"京东", "腾讯", "百度", "小米", "米哈游", "网易", "字节跳动", "美团", "蚂蚁", "完美世界"};
private static LocalDateTime now = LocalDateTime.now();
//获取指定数量person
private static ArrayList<Person> getPersonList(int count) {
ArrayList<Person> persons = new ArrayList<>(count);
for (int i = 0; i < count; i++) {
persons.add(getPerson());
}
return persons;
}
//随机生成person
private static Person getPerson() {
Person person = Person.builder()
.name(names[random.nextInt(names.length)])
.phone(18800000000L + random.nextInt(88888888))
.salary(new BigDecimal(random.nextInt(99999)))
.company(companys[random.nextInt(companys.length)])
.ifSingle(random.nextInt(2))
.sex(random.nextInt(2))
.address("四川省成都市" + addrs[random.nextInt(addrs.length)])
.createTime(LocalDateTime.now())
.createUser(names[random.nextInt(names.length)]).build();
return person;
}
这个算法生成的对象重复率很低很低（几乎不会有重复的）
来看下效果
但全是随机的也不行，我们需要有个确定的对象，因为我们后面要判断某个对象是否存在，所有要有个方法用来生成确定对象
//获得一个确定的person，需传入一个date，什么作用这里先别管，后面一看就懂
private static Person getFixedPerson(LocalDateTime date) {
Person person = Person.builder()
.name("薇娅")
.phone(18966666666L)
.salary(new BigDecimal(99999))
.company("天猫")
.ifSingle(0)
.sex(0)
.address("上海市徐家汇某栋写字楼")
.createTime(date)
.createUser("老马").build();
return person;
}
开始测试（ 终于开始了，好鸡冻 ）
一次装100w有点多，我们分开装，一次装50w
public static void main(String[] args) {
ArrayList<Person> arrayList = new ArrayList<>();
for (int i = 0; i < 2; i++) {
arrayList.addAll(getPersonList(500000));
}
//add一个确定的person
arrayList.add(getFixedPerson(now));
long start = System.currentTimeMillis();
System.out.println(arrayList.contains(getFixedPerson(now)));
System.out.println("arrayList内对象数量" + arrayList.size());
long end = System.currentTimeMillis() - start;
System.out.println("耗时(ms)：" + end + ",消耗内存(m)：" + (ObjectSizeCalculator.getObjectSize(arrayList) / (1024 * 1024)));
}
害行，100w效率害行，内存也还顶得住
超级加倍，试试1000w
//其它代码跟上面一样
for (int i = 0; i < 20; i++) {
arrayList.addAll(getPersonList(500000));
}
效率也害行，不过内存，好家伙，用了2.5G，有点拉跨，那以此类推，1个亿得25G内存，这怕是有点顶不住啊
list一个亿我就不测了 0.0
list方案以失败告终
其实吼，非要用list也不是不行，装不了一个亿就分批次呗，酱紫解决了内存的问题，但是耗时解决不了，就按照上面的1000w0.3s来计算，一个亿至少也得3s，还是有点拉跨
有没有一种容器，能够容纳一亿个对象，并且占用内存还少？
布隆过滤器：你直接念我身份证得了
是的，今天的主题是布隆过滤器（BloomFilter）
前面都是为了引出BloomFilter，有对比你才知道这玩意儿多牛逼
下面是一个低配版BloomFilter，原理最后说
public class MyBloomFilter {
//后面hash函数会用到，用来生成不同的hash值，可以随便给，但别给奇数
private final int[] ints = {6, 8, 16, 38, 58, 68};
//统计当前对象数量
private Integer currentBeanCount = 0;
//你的布隆过滤器容量
private int DEFAULT_SIZE = Integer.MAX_VALUE;
//bit数组，用来存放结果
private final BitSet bitSet = new BitSet(DEFAULT_SIZE);
public MyBloomFilter() {
}
public MyBloomFilter(int size) {
if (size > Integer.MAX_VALUE) throw new RuntimeException("size is too large");
if (size <= (2 << 8)) throw new RuntimeException("size is too small");
DEFAULT_SIZE = size;
}
//获取当前过滤器的对象数量
public Integer getCurrentBeanCount() {
return currentBeanCount;
}
//计算出key的hash值，并将对应下标置为1
public void push(Object key) {
Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
currentBeanCount++;
}
//判断key是否存在，true不一定说明key存在，但是false一定说明不存在
public boolean contain(Object key) {
boolean result = true;
for (int i : ints) {
result = result && bitSet.get(hash(key, i));
}
return result;
}
//hash算法，借鉴了hashmap的算法，利用i对同个key生成一组不同的hash值
private int hash(Object key, int i) {
int h;
int index = key == null ? 0 : (DEFAULT_SIZE - 1 - i) & ((h = key.hashCode()) ^ (h >>> 16));
return index > 0 ? index : -index;
}
}
1000w
public static void main(String[] args) {
//实例化
MyBloomFilter filter = new MyBloomFilter();
for (int i = 0; i < 20; i++) {
//push到BloomFilter
getPersonList(500000).forEach(person -> filter.push(person));
}
//push一个确定的对象
filter.push(getFixedPerson(now));
//判断这个对象是否存在
long start = System.currentTimeMillis();
System.out.println(filter.contain(getFixedPerson(now)));
long end = System.currentTimeMillis() - start;
System.out.println("bloomFilter内对象数量：" + filter.getCurrentBeanCount());
System.out.println("耗时(ms)：" + end + ",消耗内存(m)：" + (ObjectSizeCalculator.getObjectSize(filter) / (1024 * 1024)));
}
嗷嗷快是不是，而且只要是内存只用了256m，并且吼，这个内存不会随着对象的增多而变大，不信我们来试试
//其他代码全一样
for (int i = 0; i < 200; i++) {
//push到BloomFilter
getPersonList(500000).forEach(person -> filter.push(person));
}
即使是一个亿，性能也能嘎嘎快，而且内存依然是256m，得不得劲儿
当然，自古好事两难全，BloomFilter虽然性能猛，但是也有缺点
它在用作判断对象 是否存在 时有误判率，误判率随着对象数量增加而增加
但是用作判断对象 是否不存在 时，没有误判率
这个特性让它经常用作应对缓存穿透（判断key是否合法）
看累了吧，奖励一张嗨丝
简单说下原理
就是通过对比hash算法计算出来的下标，但注意，是对比一组，而不是一次，一次hash结果只对应一个下标
把同一个key进行多次hash运算，将hash出来的下标放入数组，数组默认全为0，放入元素后该下标就为1，后面判断是否存在元素的时候也是进行同样次数的hash运算，看下结果对应的所有下标是否全为1，若全为1，则代表该key可能存在，若存在不为1的，则说明该key一定不存在；
默认bit数组：[0，0，0，0，0，0]
比方说有个key计算出的一组hash下标是0，2，5
对应位bit数组：[1，0，1，0，0，1]
判断某个未知key是否存在时候，假设我们计算出来的下标是0，2，4
对应位数组：[1，0，1，0，1，0]
此时位数组内5对应下标值为0，而已知key位数组的5对应下标位1，说明这两个key一定不同
相反，如果某个key计算出来的下标为[1，0，1，0，0，1]，只能说这个key可能存在，因为这几个位置可能是其它key计算出来的
ok我话说完
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK