面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?

最近小林在求职面试中被询问了这么一个有趣的面试题:

假设当我们需要在一千万个整数(整数的范围在1-1亿之间)里面快速查找某个整数是否存在于其中的话,如何快速查找进行判断会比较方便呢?

ps: int 类型的数据存储的时候是会占用四个字节空间,假设存储的数据范围在1-1亿之间,那么数据存储的时候大概占用空间为:100 * 100 * 1000 * 4 byte 大概存储空间大小消耗为 :40000 kb 40mb左右。

1.散列表结构方案

通过散列表来实现该功能当然是可以的,但是散列表里面除了需要存储对应的数字以外,还需要存储对应的链表指针,每个数字都采用int类型来进行存储的话,光是数字占用的内存大小大概是40mb左右,如果是加上了指针的存储空间的话,那么存储的内存大小大概是80mb左右了。

2.布尔数组结构方案

通过使用布尔类型的数组来进行存储。首先创建一个一千万长度的布尔类型数组,然后根据整数,定位到相应的下标赋值true,那么以后在遍历的时候,根据相应的下标查找到指定的变量,如果该变量的值是true的话,那么就证明该数字存在。

布尔类型变量在存储的时候只有true和false存在,但是在数组中存储的时候实际上是占用了1个字节,该类型的变量在被编译之后实际上是以int类型的数据0000 0000和0000 0001存储的,因此还是占用了较多的内存空间。

3.使用bitmap来进行存储

例如说一个长度是10的bitmap,每一个bit位都存储着对应的0到9的十个整形数字,此时每个bitmap所对应的位都是0。当我们存入的数字是3的时候,位于3的位置会变为1。

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

当我们存储了多个数字的时候,例如说存储了4,3,2,1的时候,那么位图结构就会如下所示:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

那么这个时候你可能就会疑惑了,到底在代码上边该如何通过计算来获取一个数字的索引定位呢?

首先我们将核心思路的代码先贴上来:

 public void set(int number) {
        //相当于对一个数字进行右移动3位,相当于除以8
        int index = number >> 3;
 
        //相当于 number % 8 获取到byte[index]的位置
        int position = number & 0x07;
 
        //进行|或运算  参加运算的两个对象只要有一个为1,其值为1。
        bytes[index] |= 1 << position;
    }

为了方便理解核心思想,所以还是通过图例来理解会比较好:

例如说往bitmap里面存储一个数字11,那么首先需要通过向右移位(因为一个byte相当于8个bit),计算出所存储的byte[]数组的索引定位,这里计算出index是1。由于一个byte里面存储了八个bit位,所以通过求余的运算来计算postion,算出来为3。

这里假设原有的bitmap里面存储了4和12这2个数字,那么它的结构如下所示:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

这个时候,我们需要存储11进来,那么就需要进行或运算了:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

同理,当我们判断数字是否存在的时候,也需要进行相应的判断,代码如下:

  public boolean contain(int number) {
        int index = number >> 3;
        int position = number & 0x07
        return (bytes[index] & (1<<position)) !=0;
    }
面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

整合一下,简单版的一个bitmap代码如下:

public class MyBitMap {
 
    private byte[] bytes;
    private int initSize;
 
    public MyBitMap(int size) {
        if (size <= 0) {
            return;
        }
        initSize = size / (8) + 1;
        bytes = new byte[initSize];
    }
 
    public void set(int number) {
        //相当于对一个数字进行右移动3位,相当于除以8
        int index = number >> 3;
        //相当于 number % 8 获取到byte[index]的位置
        int position = number & 0x07;
        //进行|或运算  参加运算的两个对象只要有一个为1,其值为1。
        bytes[index] |= 1 << position;
    }
 
 
    public boolean contain(int number) {
        int index = number >> 3;
        int position = number & 0x07;
        return (bytes[index] & (1 << position)) != 0;
    }
 
    public static void main(String[] args) {
        MyBitMap myBitMap = new MyBitMap(32);
        myBitMap.set(30);
        myBitMap.set(13);
        myBitMap.set(24);
        System.out.println(myBitMap.contain(2));
    }
 
}

从刚刚位图结构的讲解中,你应该可以发现,位图通过数组下标来定位数据,所以,访问效率非常高。而且,每个数字用一个二进制位来表示,在数字范围不大的情况下,所需要的内存空间非常节省。

比如刚刚那个例子,如果用散列表存储这 1 千万的数据,数据是 32 位的整型数,也就是需要 4 个字节的存储空间,那总共至少需要 40MB 的存储空间。如果我们通过位图的话,数字范围在 1 到 1 亿之间,只需要 1 亿个二进制位,也就是 12MB 左右的存储空间就够了。

但是实际应用中,却并非如我们所想象的那么简单,假设我们的实际场景进行改变一下:

还是刚刚的那个情况:

还是一千万个数字,但是数字范围不是 1 到 1 亿,而是 1 到 10 亿,那位图的大小就是 10 亿个二进制位,也就是 120MB 的大小,消耗的内存空间反而更加大了,而且在bitmap里面还会有部分空间浪费的情况存在。

假设我们对每一个数字都进行一次hash计算,然后通过hash将计算后的结果范围限制在1千万里面,那么就不需要再定义10亿个二进制位了。

但是这样子还是会有相应的弊端,例如说hash冲突。那么这个时候如果我们采用多个hash函数来进行处理的话,理论上是可以大大降低冲突的概率的。于是就有了下边所说的布隆过滤器一说。

布隆过滤器

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

布隆过滤器通过使用多次的hash计算来进行数值是否存在的判断,虽然大大降低了hash冲突的情况,但是还是存在一定的缺陷,那就是容易会有误判的情况。例如说如下如所示:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

布隆过滤器的误判有一个特点,那就是,它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在,那说明这个数字真的不存在,不会发生误判;如果某个数字经过布隆过滤器判断存在,这个时候才会有可能误判,有可能并不存在。

不过,只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例,那就可以将这种误判的概率降到非常低。

那么该怎么调整这个位图大小和存储数字之间的比例呢?

这里可能就需要用到一些数学公式来进行计算了。

在位数组长度m的BF中插入一个元素,相应的位可能会被标志为1。所以说,在插入元素后,该比特仍然为0的概率是:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

现有k个哈希函数,并插入n个元素,自然就可以得到该比特仍然为0的概率是:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

反过来讲,它已经被置为1的概率就是:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

也就是说,如果在插入n个元素后,我们用一个不在集合中的元素来检测,那么被误报为存在于集合中的概率(也就是所有哈希函数对应的比特都为1的概率)为:

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

当n比较大时,在查询了相关资料之后,可以近似得出误判率的公式大致如下:(本人数学不是太好,这段公式是请教其他大佬得出的)

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?
图片

所以,在哈希函数的个数k一定的情况下:

  • 位数组长度m越大,误判率越低;
  • 已插入元素的个数n越大,误判率越高。

尽管说布隆过滤器在使用的时候会有误判的情况发生,但是在对于数据的准确性有一定容忍度的情况下,使用布隆过滤器还是会比较推荐的。

在实际的项目应用中,布隆过滤器经常会被用在一些大规模去重,但又允许有小概率误差的场景中,例如说我们对一组爬虫网页地址的去重操作,或者统计某些大型网站每天的用户访问数量(需要对相同用户的多次访问进行去重)。

实际上,关于bitmap和布隆过滤器这类工具在大型互联网企业上已经受到了广泛使用,例如说java里面提供了BitSet类,Redis也提供了相应的位图类,Google里面的guava工具包中的BloomFilter也已经实现类布隆过滤器,所以在实际应用的时候只需要直接使用这些现有的组件即可,避免重复造轮子的情况发生。

4.Redis提供的BitMap

在redis里有一个叫做bitmap的数据结构,使用技巧如下:

setbit指令

语法:setbit key offset value
127.0.0.1:6379> setbit bitmap-01 999 0
(integer) 0
127.0.0.1:6379> setbit bitmap-01 999 1
(integer) 0
127.0.0.1:6379> setbit bitmap-01 1003 1
(integer) 0
127.0.0.1:6379> setbit bitmap-01 1003 0
(integer) 1
127.0.0.1:6379> setbit bitmap-01 1004 0
(integer) 0

注意:

1.offset 参数必须大于或等于 0 ,小于 2^32 (bit 映射被限制在 512 MB 之内)。

2.因为 Redis 字符串的大小被限制在 512 兆(megabytes)以内, 所以用户能够使用的最大偏移量为 2^29-1(536870911) , 如果你需要使用比这更大的空间, 请使用多个 key。

3.当生成一个很长的字符串时, Redis 需要分配内存空间, 该操作有时候可能会造成服务器阻塞(block)。在2010年出产的Macbook Pro上, 设置偏移量为 536870911(512MB 内存分配)将耗费约 300 毫秒, 设置偏移量为 134217728(128MB 内存分配)将耗费约 80 毫秒, 设置偏移量 33554432(32MB 内存分配)将耗费约 30 毫秒, 设置偏移量为 8388608(8MB 内存分配)将耗费约 8 毫秒。

getbit指令

语法:getbit key offset

返回值:

127.0.0.1:6379> setbit bm 0 1
(integer) 0
127.0.0.1:6379> getbit bm 0
(integer) 1

bitcount指令

语法:bitcount key [start] [end]  ,这里的start和end值为可选项

返回值:被设置为 1 的位的数量

127.0.0.1:6379> bitcount user18 
(integer) 4

bitop指令

语法:bitop operation destkey key [key ...]

operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种:

BITOP AND destkey key [key ...] ,对一个或多个 key 求逻辑并,并将结果保存到 destkey 。
BITOP OR destkey key [key ...] ,对一个或多个 key 求逻辑或,并将结果保存到 destkey 。
BITOP XOR destkey key [key ...] ,对一个或多个 key 求逻辑异或,并将结果保存到 destkey 。
BITOP NOT destkey key ,对给定 key 求逻辑非,并将结果保存到 destkey 。

实战案例

统计某个用户在xx论坛的签到次数,这里假设用户的id为u18

127.0.0.1:6379> setbit user18 1 1
(integer) 0
127.0.0.1:6379> setbit user18 2 1
(integer) 0
127.0.0.1:6379> setbit user18 5 1
(integer) 0
127.0.0.1:6379> setbit user18 15 1
(integer) 0
127.0.0.1:6379> bitcount user18 
(integer) 4

通过使用bitcount指令可以快速从redis中计算出user18的签到天数。

( ps:但是如果要计算出连续签到的天数,或者记录更多的签到信息,并且考虑上数据存储的可靠稳定性,那么此时bitmap就不太适用了,这里我只是模拟了一个案例供大家学习这条指令的使用。)

按天统计网站活跃用户

设计思路,用天来作为统计的key,然后以用户ID作为Offset,一旦用户登录访问网站,则根据其用户id计算出对应的offset并且将其设置为1。

//2020年10月21日 用户11034访问网站
127.0.0.1:6379> setbit 20201021 11034 1
(integer) 0
//2020年10月21日 用户11089访问网站
127.0.0.1:6379> setbit 20201021 11089 1
(integer) 0
//2020年10月21日 用户11034访问网站
127.0.0.1:6379> setbit 20201022 11034 1
(integer) 0
//2020年10月21日 用户11032访问网站
127.0.0.1:6379> setbit 20201023 11032 1
(integer) 0
//通过使用bitop or 做多个集合的交集运算,计算出2020年10月21日 至2020年10月22日
//内连续登录的用户id,并且将其放入到名为active_user的bitmap中
127.0.0.1:6379> bitop or active_user 20201021 20201022
(integer) 1387
//提取活跃用户信息
127.0.0.1:6379> bitcount active_user
(integer) 2
127.0.0.1:6379>

用户在线状态、在线人数统计

//模拟用户98321访问系统
127.0.0.1:6379> setbit online_member 98321 1
(integer) 0
127.0.0.1:6379> setbit online_member 13284 1
(integer) 0
127.0.0.1:6379> setbit online_member 834521 1
(integer) 0
127.0.0.1:6379> bitcount online_member
(integer) 3
//模拟用户13284离开系统,在线人数减1
127.0.0.1:6379> setbit online_member 13284 0
(integer) 1
127.0.0.1:6379> bitcount online_member
(integer) 2
127.0.0.1:6379> 

这段指令案例将会员id作为来offset位置,存入到来bitmap中,通过设置相应到bitmap,当有对应会员登录访问的时候,对应offset位置则置为1,最后通过bitcount来统计该bitmap中有多少个项为1,从而计算出用户在线的人数。

Guava提供的布隆过滤器

对应的依赖:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

引入相关的依赖之后,可以通过编写一个简单的案例来理解guava里面提供的布隆过滤器组件:

packageorg.idea.guava.filter;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
/**
@author idea
@date created in 11:05 上午 2020/10/25
*/

public class GuavaBloomFilter {
public static void main(String[] args) {
//创建布隆过滤器时要传入期望处理的元素数量,及最期望的误报的概率。
    BloomFilter<Integer> bloomFilter = BloomFilter.create(
Funnels.integerFunnel(),
100,  //希望存储的元素个数
0.01  //希望误报的概率
);
bloomFilter.put(1);
bloomFilter.put(2);
bloomFilter.put(3);
bloomFilter.put(4);
bloomFilter.put(5);
        //判断过滤器内部是否存在对应的元素
System.out.println(bloomFilter.mightContain(1));
System.out.println(bloomFilter.mightContain(2));
System.out.println(bloomFilter.mightContain(1000));
}
}

这段代码中你可能会疑惑,为什么是mightContain而不是contain呢?

这一点其实和布隆过滤器本身的误判机制有关。

布隆过滤器常用的场景为:

对于一些缓存穿透的场景可以用于做为预防手段。

本身的优点:

存储空间消耗较少。

时间效率高,查询和插入的时间复杂度均为O(h)。(h为hash函数的个数)

缺点:

查询元素是否存在的概率不能保证100%准确,会有部分误判的情况存在。

只能插入和查询元素,不允许进行删除操作。

END

推荐好文

强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

为什么MySQL不推荐使用uuid或者雪花id作为主键?

为什么建议大家使用 Linux 开发?爽(外加七个感叹号)

IntelliJ IDEA 15款 神级超级牛逼插件推荐(自用,真的超级牛逼)

炫酷,SpringBoot+Echarts实现用户访问地图可视化(附源码)

记一次由Redis分布式锁造成的重大事故,避免以后踩坑!

十分钟学会使用 Elasticsearch 优雅搭建自己的搜索系统(附源码)

面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?

原文始发于微信公众号(Java知音):面试被问,一千万个整数里面快速查找某个整数,你会怎么去做?