面试题:40亿个QQ号,限制1G内存,如何去重?

2024-01-20 11:28

本文主要是介绍面试题:40亿个QQ号,限制1G内存,如何去重?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 概要
  • 什么是BitMap?有什么用?
  • 什么是布隆过滤器,实现原理是什么?
  • 应用场景
    • 如何使用

概要

40亿个unsigned int,如果直接用内存存储的话,需要:

4*4000000000 /1024/1024/1024 = 14.9G ,考虑到其中有一些重复的话,那1G的空间也基本上是不够用的。

想要实现这个功能,可以借助位图。

使用位图的话,一个数字只需要占用1个bit,那么40亿个数字也就是:

4000000000 * 1 /8 /1024/1024 = 476M

相比于之前的14.9G来说,大大的节省了很多空间。

比如要把我的QQ号"907607222"放到Bitmap中,就需要找到第907607222这个位置,然后把他设置成1就可以了。

图片

这样,把40亿个数字都放到Bitmap之后,所有位置上是1的表示存在,不为1的表示不存在,相同的QQ号只需要设置一次1就可以了,那么,最终就把所有是1的数字遍历出来就行了。

什么是BitMap?有什么用?

位图(BitMap),基本思想就是用一个bit来标记元素,bit是计算机中最小的单位,也就是我们常说的计算机中的0和1,这种就是用一个位来表示的。

所谓位图,其实就是一个bit数组,即每一个位置都是一个bit,其中的取值可以是0或者1

图片

像上面的这个位图,可以用来表示1,4,6:

图片

如果不用位图的话,我们想要记录1,4,6 这三个整型的话,就需要用三个unsigned int,已知每个unsigned int占4个字节,那么就是34 = 12个字节,一个字节有8 bit,那么就是 128 = 96 个bit。

所以,位图最大的好处就是节省空间。

位图有很多种用途,特别适合用在去重、排序等场景中,著名的布隆过滤器就是基于位图实现的。

但是位图也有着一定的限制,那就是他只能表示0和1,无法存储其他的数字。所以他只适合这种能表示ture or false的场景。

什么是布隆过滤器,实现原理是什么?

布隆过滤器是一种数据结构,用于快速检索一个元素是否可能存在于一个集合(bit 数组)中。

它的基本原理是利用多个哈希函数,将一个元素映射成多个位,然后将这些位设置为 1。当查询一个元素时,如果这些位都被设置为 1,则认为元素可能存在于集合中,否则肯定不存在

所以,布隆过滤器可以准确的判断一个元素是否一定不存在,但是因为哈希冲突的存在,所以他没办法判断一个元素一定存在。只能判断可能存在。

图片

所以,布隆过滤器是存在误判的可能的,也就是当一个不存在的Hero元素,经过hash1、hash2和hash3之后,刚好和其他的值的哈希结果冲突了。那么就会被误判为存在,但是其实他并不存在。

图片

想要降低这种误判的概率,主要的办法就是降低哈希冲突的概率及引入更多的哈希算法。

下面是布隆过滤器的工作过程:

1、初始化布隆过滤器

在初始化布隆过滤器时,需要指定集合的大小和误判率。布隆过滤器内部包含一个bit数组和多个哈希函数,每个哈希函数都会生成一个索引值。

2、添加元素到布隆过滤器

要将一个元素添加到布隆过滤器中,首先需要将该元素通过多个哈希函数生成多个索引值,然后将这些索引值对应的位设置为 1。如果这些索引值已经被设置为 1,则不需要再次设置。

3、查询元素是否存在于布隆过滤器中

要查询一个元素是否存在于布隆过滤器中,需要将该元素通过多个哈希函数生成多个索引值,并判断这些索引值对应的位是否都被设置为 1。如果这些位都被设置为 1,则认为元素可能存在于集合中,否则肯定不存在。

布隆过滤器的主要优点是可以快速判断一个元素是否属于某个集合,并且可以在空间和时间上实现较高的效率。但是,它也存在一些缺点,例如:

  1. 布隆过滤器在判断元素是否存在时,有一定的误判率。
  2. 布隆过滤器删除元素比较困难,因为删除一个元素需要将其对应的多个位设置为 0,但这些位可能被其他元素共享。

应用场景

布隆过滤器因为他的效率非常高,所以被广泛的使用,比较典型的场景有以下几个:

1、网页爬虫: 爬虫程序可以使用布隆过滤器来过滤掉已经爬取过的网页,避免重复爬取和浪费资源。

2、缓存系统: 缓存系统可以使用布隆过滤器来判断一个查询是否可能存在于缓存中,从而减少查询缓存的次数,提高查询效率。布隆过滤器也经常用来解决缓存穿透的问题。

3、分布式系统: 在分布式系统中,可以使用布隆过滤器来判断一个元素是否存在于分布式缓存中,避免在所有节点上进行查询,减少网络负载。

4、垃圾邮件过滤: 布隆过滤器可以用于判断一个邮件地址是否在垃圾邮件列表中,从而过滤掉垃圾邮件。

5、黑名单过滤: 布隆过滤器可以用于判断一个IP地址或手机号码是否在黑名单中,从而阻止恶意请求。

如何使用

Java中可以使用第三方库来实现布隆过滤器,常见的有Google Guava库和Apache Commons库以及Redis。

如Guava:

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterExample {public static void main(String[] args) {// 创建布隆过滤器,预计插入100个元素,误判率为0.01BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), 100, 0.01);// 插入元素bloomFilter.put("Lynn");bloomFilter.put("666");bloomFilter.put("八股文");// 判断元素是否存在System.out.println(bloomFilter.mightContain("Lynn")); // trueSystem.out.println(bloomFilter.mightContain("张三"));  // false}
}

Apache Commons:

import org.apache.commons.lang3.StringUtils;
import org.apache.commons.collections4.BloomFilter;
import org.apache.commons.collections4.functors.HashFunctionIdentity;
public class BloomFilterExample {public static void main(String[] args) {// 创建布隆过滤器,预计插入100个元素,误判率为0.01BloomFilter<String> bloomFilter = new BloomFilter<>(HashFunctionIdentity.hashFunction(StringUtils::hashCode), 100, 0.01);// 插入元素bloomFilter.put("Lynn");bloomFilter.put("666");bloomFilter.put("八股文");// 判断元素是否存在System.out.println(bloomFilter.mightContain("Lynn")); // trueSystem.out.println(bloomFilter.mightContain("张三"));  // false}
}

Redis中可以通过Bloom模块来使用,使用Redisson可以:

Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myfilter");
bloomFilter.tryInit(100, 0.01);
bloomFilter.add("Lynn");
bloomFilter.add("666");
bloomFilter.add("八股文");
System.out.println(bloomFilter.contains("Lynn"));
System.out.println(bloomFilter.contains("张三"));
redisson.shutdown();

首先创建一个RedissonClient对象,然后通过该对象获取一个RBloomFilter对象,使用tryInit方法来初始化布隆过滤器,指定了最多能添加的元素数量为100,误判率为0.01。

然后,使用add方法将元素"Hollis"、"666"和"八股文"添加到布隆过滤器中,使用contains方法来检查元素是否存在于布隆过滤器中。

或者Jedis也可以:

Jedis jedis = new Jedis("localhost");
jedis.bfCreate("myfilter", 100, 0.01);
jedis.bfAdd("myfilter", "Lynn");
jedis.bfAdd("myfilter", "666");
jedis.bfAdd("myfilter", "八股文");
System.out.println(jedis.bfExists("myfilter", "Lynn"));
System.out.println(jedis.bfExists("myfilter", "张三"));
jedis.close();

这篇关于面试题:40亿个QQ号,限制1G内存,如何去重?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/625855

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

使用Java发送邮件到QQ邮箱的完整指南

《使用Java发送邮件到QQ邮箱的完整指南》在现代软件开发中,邮件发送功能是一个常见的需求,无论是用户注册验证、密码重置,还是系统通知,邮件都是一种重要的通信方式,本文将详细介绍如何使用Java编写程... 目录引言1. 准备工作1.1 获取QQ邮箱的SMTP授权码1.2 添加JavaMail依赖2. 实现

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C

golang内存对齐的项目实践

《golang内存对齐的项目实践》本文主要介绍了golang内存对齐的项目实践,内存对齐不仅有助于提高内存访问效率,还确保了与硬件接口的兼容性,是Go语言编程中不可忽视的重要优化手段,下面就来介绍一下... 目录一、结构体中的字段顺序与内存对齐二、内存对齐的原理与规则三、调整结构体字段顺序优化内存对齐四、内

Linux内存泄露的原因排查和解决方案(内存管理方法)

《Linux内存泄露的原因排查和解决方案(内存管理方法)》文章主要介绍了运维团队在Linux处理LB服务内存暴涨、内存报警问题的过程,从发现问题、排查原因到制定解决方案,并从中学习了Linux内存管理... 目录一、问题二、排查过程三、解决方案四、内存管理方法1)linux内存寻址2)Linux分页机制3)

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常