处理大数据运算的利器 — 位图原理以及设计

迷南。 2022-06-05 02:53 139阅读 0赞

# 位图的原理以及设计 #

首先我们来写一道腾讯面试题-> 给40个亿不重复的无符号整数，没有排序过，每一个无符号的整数，快速的判断这个数在或者不在40亿

个 数? 有的人一看到这个题，很简单嘛最麻烦的就是从头遍历一遍的事情嘛. 不过要看清楚题！ 40亿个无符号整数. 我们生活中1G内存

占用的字节 数 1024\*1024\*1024为1073741824个字节.粗略就是10亿个字节. 而40亿个无符号整数是160亿个字节. 也就是这些数据存储下来

需要16G的内存.  那么问题来了，普通的工作电脑的内存都4G，好点的就是8G. (如果你是16G内存光速吃鸡那么当我没说)我们可以发现这

些数据的内存大于电 脑的内存所以存储不下. 这个时候就很头大了,内存都存不下那么你怎么读取呢？ 当然你说你直接去硬盘里面读.

好！ 没问题.从硬盘里面读 取数据的速度和从内存中读取的速度根本没得比的.如果你的时间多也可以.不过我们有一个更厉害的方法就

是我们的位图. 位图就是给定一段连续的空间然后让这个空间的每一位都为0，再然后让每一个位表示一个数字.再然后当你这个数字出现的

时候将它对应的那个 位->置为1.这样的话存储40亿个数据，也就是存储40亿个位.也就是5亿个字节.大概512MB的样子. 这样的话我们的内

存 存储这些数据也就是绰绰 有余了.所以位图对于大数据的问题有着显著的效果. 那我开始实现一个位图吧.

![20171116113620953][]

位图的实现,我们先思考一下它的内部结构.因为需要一段连续的空间那么它底层的实现原理一定是一个vector. 为了方便置位我将它的

类型置位char.然后它的构造函数是根据我们传入的数据来确定空间的大小. 因为一个字节8个位，所以我们需要的空间的大小就 :

数据总长度 / 8 + 1. 为什么加1？ 因为无符号整数做除运算完了后如果后面有小数点直接就会抹掉. 所以加个1防止数据不够存放.

class BitMap
    {
    public:
    	BitMap(size_t range)
    	{
    		_bitTable.resize((range >> 3) + 1);
    	}
    private:
    	vector<char> _bitTable;
    };

位图中标记一个位置的位 这个很容易思考我们首先需要定位到需要映射的位置,这个让数据的值直接整除8，获得的值就是在

第几个字节里面.现在我们定位到了字节. 接下来让数据模除一个8，那么现在我们就定位到了在这个字节里面的第几个位.好好地思考

一下. 这一块代码很简单，但是你需要了解整个过程的细节.最后只剩下标记了.

![20171116120100297][]

位图取消一个标记，定位到Num映射的过程跟上面一样，然后呢去除这个标记其实很简单.

//取消数字在位图当中的标识.
    	void RemoveBit(size_t x)
    	{
    		size_t index = x >> 3;
    		size_t num = x % 8;
    
    		_bitTable[index] &= ~(1 << num);
    	}

![20171116120958501][]

到最后只剩下检验一个位图当中该数剧是否存在，当然定位到该数据的位置很容易. 上面执行两遍了. 我们怎么判断这个位是否为1？

bool TestBit(size_t x)
    	{
    		size_t index = x >> 3;
    		size_t num = x % 8;
    		return _bitTable[index] & (1 << num);
    	}

这个自己顺着上面的图，理解理解就好啦.........位图做好了，那么对于上面那个问题我们就迎刃而解了. 当然如果有这样的问题

让你寻找出40亿个数据中出现过两次的数据? 用位图也可以解决，不过你就不能使用一个位来标记数据了，你就应该使用两个位了. 具体

实现你可以下去试一试~~~~~![大笑][laugh.gif] 我这里有一个现成的代码.

位图的简单实现:

//一位位图
    class BitMap
    {
    public:
    	BitMap(size_t range)
    	{
    		_bitTable.resize((range >> 3) + 1);
    	}
    
    	//标识一个数字在位图中的位置
    	void SetBit(size_t x)
    	{
    		size_t index = x >> 3;
    		size_t num = x % 8;
    
    		_bitTable[index] |= (1 << num);
    	}
    
    	//取消数字在位图当中的标识.
    	void RemoveBit(size_t x)
    	{
    		size_t index = x >> 3;
    		size_t num = x % 8;
    
    		_bitTable[index] &= ~(1 << num);
    	}
    
    
    	bool TestBit(size_t x)
    	{
    		size_t index = x >> 3;
    		size_t num = x % 8;
    
    		return _bitTable[index] & (1 << num);
    	}
    
    private:
    	vector<char> _bitTable;
    };

N位的位图实现:

class NBitMap
    {
    public:
    
    	NBitMap(int range)
    	{
    		_bitTable.reserve((range >> 2) + 1);
    	}
    
    	//位图中增加数据出现次数.
    	void Add(size_t x)
    	{
    		size_t index = x >> 2;
    		size_t num = x % 4;
    		num *= 2;
    
    		bool first = _bitTable[index] & (1 << num);
    		bool second = _bitTable[index] & (1 << (num + 1));
    
    		if (!(first && second))
    		{
    			_bitTable[index] += (1 << num);
    		}
    
    	}
    
    	//检验是否小于3
    	int Test(size_t x)
    	{
    		size_t index = x >> 2;
    		size_t num = x % 4;
    
    		num *= 2;
    		return (_bitTable[index] >> num) & 0x03;
    	}
    
    private:
    	vector<char> _bitTable;
    };

但是我现在画风一变，再问一个问题! 给两个文件，分别有100亿个queue，我们只有1G内存，如何找到文件交集? 有的人一看毫不犹豫！

这大数据莫用位图嘛！ 这还解释什么，快上车. 别别别，慢点. 注意我们的位图虽然强大，但是位图是有缺陷的.位图只能存储整数类型

数据. 当让它存储字符串什么的，位图就扛不住了. 但是生活中的问题总会有办法解决，这个时候就有大神提出了布隆过滤器这个操作.

现在我们知道这么个概念，下一个博客就会解释[布隆过滤器~][Link 1]

[20171116113620953]: /images/20220605/0d4dd574d90a4aa2b0888c03b2ee4699.png
[20171116120100297]: /images/20220605/40a9f9c620674436ac6496035d15376d.png
[20171116120958501]: /images/20220605/90b4faf200d74830ae0caf73bd51f68d.png
[laugh.gif]: /images/20220605/0aaff03db8d24c039ed7a41458344164.png
[Link 1]: http://blog.csdn.net/dawn_sf/article/details/78553999