数据结构::由一道面试题进入位图的世界

时间:2021-05-20 10:28:57

【引言】:

我们先来看一道腾讯的面试题:

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

那么拿到这道题的时,我们怎么做呢?

首先我们肯定会想到各种不同的办法:比如:     查找数是否在,我们肯定首先会想到哈希,因为简单快速,它的效率虽然快,但是如果使用它的话,如何将这么大的数放到内存中,数已经放不下了,还要进行存储指针或者数据结构等,这些也是要消耗内存的。     这道题其实是大数据问题中海量数据的查找问题,为什么说是海量数据呢,因为它给定的是40亿个数,40亿个数大概是多大呢,就是16G,这么大的数,现在的32位或者是64位机,内存在4G-8G,内存肯定放不下,那么这里我们就提供一种方法,不仅省了内存而且可以进行快速查找,就是我们接下来要认识的位图。

【位图】:

1、概念:

位图主要用于(大数据)快速检索关键字状态,通常要求关键字是一个连续的序列(或者关键字是一个连续序列中的大部分), 最基本的情况,使用1bit标示一个关键字的状态(可标示两种状态),但根据需要也可以使用2bit(标示4种状态),3bit(标示8种状态),当一个状态标示需要的位数达到32bit时,就演变成来一个整型数组了。

2、位图的结构

位图就是用每一位的0,1来表示一个数的状态

【位图的算法实现】:

说明:一个整数是4个字节,我们现在使用位图,就是用位图的一个位来表示整数的32个位

1、置位的实现

A:说明

1)我们用vector来进行存储这些数,那么这些数就在不同的数组下标中,如果我们要进行置位这个数,首先肯定得先找到这个数在哪

2)我们先用要开的位大小进行 “/32”,得到要查找的数在那个下标中,然后进行%32得到这个数的具体位置。

3)找到了这个数,就将这个数置为1:那么如何置为1,先将此数进行右移%出来的数值位,然后和1进行或运算

我来画图举个例子:

数据结构::由一道面试题进入位图的世界

B:代码实现:

void SetMap(size_t v)
{
//通过除得到此数在哪一个下标中存储中
size_t index = v>>5;
//通过模得到此数的具体位置
size_t num = v%32;
//将此数存在的位置置为1
_bm[index] |= (1<<num);

}

2、复位的实现:

A:说明:

1)复位就是要恢复,所以这里我们要这样进行置位

2)依然同理置位,求出此数所在的位置,将1移位%出来的数值位后,取反然后和此位置的数再进行&运算。

B:代码实现:

void RetsetMap(size_t v)
{
size_t index = v>>5;
size_t num = v%32;

_bm[index] &= ~(1<<num);
}

3、测试一个数是否在的函数实现

A:说明:

1)依然同理上面的求出此数的具体位置,然后1移位%出来的数值位,暂时记为p

2)用数组中原本这个位置的数和p进行&运算,结果为1的话,就在,不为1的话就不在

B:代码实现:

bool TestMap(size_t v)
{
size_t index = v>>5;
size_t num = v%32;

return _bm[index] & (1<<num);
}

【位图的应用】:

位图一般用来解决海量数据的问题,需要注意的是,位图限定了解决正整数的问题。 

1)使用位图法判断整形数组是否存在重复 

遍历数组,一个一个放入bitmap,并且检查其是否在bitmap中出现过,如果没出现放入,否则即为重复的元素。 

2)使用位图法进行整形数组排序 

首先遍历数组,得到数组的最大最小值,然后根据这个最大最小值来缩小bitmap的范围。这里需要注意对于int的负数,都要转化为unsigned int来处理,而且取位的时候,数字要减去最小值。

3)磁盘空闲块的管理

Ext3文件系统中使用位图来管理磁盘空闲块(空闲inode节点)。文件系统创建后,该文件系统拥有的块数以及inode节点数都是确定的,数据块区包含一系列连续的块(块号是连续的),于是可以用位图来标示数据块的分配状态(分配、未分配两种状态,1bit即可标示)。
如下图,假设ext3的数据块从128开始,一直到1024,则需要1024-128 = 996bit = 128字节的位图空间。如下图,第1bit标示128号块已经被分配,第2bit标示129号块未被分配,依次类推。使用位图的高效性在于:1bit标示状态,节省存储空间,通过关键字来定位位图(偏移是固定的),效率高。
1
0
1
1
….
 

4)区域服务器路由

腾讯的QQ号用一个数字标示,范围从0到20亿,每个QQ号都有可能出现,所有的QQ号被分散的存储北京、上海、深圳、武汉四个城市的服务器中,现在需要一个路由服务器快速的将登陆的QQ路由到正确的服务器,路由服务器可以读取四个QQ服务器的数据,并构建路由表(需全部存在内存中,内存限制1G),路由表该如何存储?
关键:QQ号从0-20亿,每个号码都有可能出现;服务器通过0、1、2、3标示,这四种状态可以用2bit来标示,于是可以考虑使用位图来描述路由表。
解法:从0~20亿,为每个QQ号分配2bit,路由服务器从QQ服务器中获取信息,并设置QQ于服务器号的对应关系。当QQ登录时,路由服务器根据QQ号定位到其对应的状态,并返回对应的服务器号。总的内存大小20亿 * 2 /8 = 5亿字节(约为0.5G)。
 

5)高效排序

数据库里存了很多800电话号码,数量特别大,以至于内存放不下,如何排序,时间比空间更重要?电话号码类似于800-810-5555。
关键:去掉电话号码的800后面就是7位的十进制整数,每个整数都有可能出现而且不会重复出现,可以采用各种排序算法对这些数据进行排序,但时间复杂度都在O(NlogN)及以上。
解法:因每个七位以内的整数都有可能出现,可以用1bit来标示电话号是否出现,遍历整个电话号序列,设置相应的位,遍历位图收集位被设置的号码即可。
扩展:对于上述问题,每个电话号码最多出现一次,如果关键字可能多次重复出现,但关键字范围比较确定且很集中的情况下,也可使用位图(根据关键字最多可能出现的次数确定每个关键字需要的位数),但此时的位图通常会是一个整型数组,数组内容为对应位置关键字出现的次数,在执行收集过程时,对于每个关键字要收集多次(根据数组的值确定)。如有一大批职工的年龄信息,需要对这些职工按照年龄信息进行排序,则只需要建立一个长度为100的数组,每个数组为对应年龄人的个数,扫描一遍数组,收集年龄信息即可。

【附源代码】:


#include<iostream>
#include<vector>
#pragma once
using namespace std;
class BitMap
{
public:
//位图的构造
BitMap(size_t N = 1024) //
{
_bm.resize((N/32)+1); //注意此处的运算符优先级
}
//按照位图的方式进行数值的置位
void SetMap(size_t v)
{
//通过除得到此数在哪一个下标中存储中
size_t index = v>>5;
//通过模得到此数的具体位置
size_t num = v%32;
//将此数存在的位置置为1
_bm[index] |= (1<<num);

}
//进行数值的复位
void RetsetMap(size_t v)
{
size_t index = v>>5;
size_t num = v%32;

_bm[index] &= ~(1<<num);
}
//给定一个数,测试这个数是否在
bool TestMap(size_t v)
{
size_t index = v>>5;
size_t num = v%32;

return _bm[index] & (1<<num);
}
protected:
vector<size_t> _bm;
};

void TestBitMap()
{
//此处要开无符号整型大小的空间
BitMap bm((size_t)-1);
bm.SetMap(50);
bm.SetMap(10);
bm.SetMap(20);
bm.SetMap(40);
bm.SetMap(7);

cout<<bm.TestMap(8)<<endl;
cout<<bm.TestMap(7)<<endl;

}