目录

问题描述

方案1-使用C语言的链表

分析

源码

测试效果

方案2-使用C++的list容器

源码

测试效果

方案3-使用布隆过滤器

源码

测试效果

 布隆过滤器的原理​

布隆过滤器的优点

布隆过滤器的缺点

 布隆过滤器的使用场景

问题总结

问题描述

最近，一道笔试题“火”了：

已有一亿个数据（或对象），设计一个算法，判定指定的数据是否已经存在？

要求占用内存小于1G。

这道题，怎么说，都是很简单的，大不了线性遍历啊，难不成，还有坑吗？

确实有很点坑！这个题，语言不限，已经被很多JAVA大佬分析过了，不过还没有人用C++分析过。现在我们用C语言和C++拆解一下，体会一下剖解大厂笔试题的快感。

方案1-使用C语言的链表

分析

如果直接使用数组，显然是不成立的，内存明显不够。所以我们考虑使用链表试探一下。

这个问题，用非IT术语说，就是海量数据筛选，和当年湖南卫视的超级女生有的类似，不过综艺海选，是“选优”。这里的筛选，是判定指定的数据是否存在。

在“人海”中，确定指定人，是否在里面？

 

 

 为了描述方便，我们直接使用爬虫工具作为应用场景。因为在爬取数据时，需要判断待爬取的链接URL是否已经爬取过了。

源码

#include 
#include 
#include 
#include 

//使用timeGetTime
#include 
#pragma comment( lib,"winmm.lib" )

#define MAX_COUNT  10000000

struct node {
	char url[128];
	struct node* next;
};

struct node* createList() {
	struct node* list = (struct node*)malloc(sizeof(struct node));
	list->next = NULL;
	return list;
}

void loadData(struct node* list, int count) {
	struct node* p = list;
	int n = 0;
	for (int i = 0; i < count; i++) {
		struct node* newNode = (struct node*)malloc(sizeof(struct node));
		if (newNode == NULL) {
			printf("no memory!n");
			exit(1);
		}
		sprintf_s(newNode->url, sizeof(newNode->url), "https://www.github.com/%d.html", i + 1);
		newNode->next = NULL;
		p->next = newNode;
		p = p->next;

		if ((i+1) % 1000000 == 0) {
			printf("had loaded %d Wn", ++n * 100);
		}
	}
}

void listPushBack(struct node* list, struct node* user) {
	struct node* p;
	for (p = list; p->next; p = p->next);
	p->next = user;
	user->next = NULL;
}

bool findData(struct node* list, const char *url) {
	for (struct node* p = list->next; p; p = p->next) {
		if (strcmp(p->url,url)) {
			return true;
		}
	}
	return false;
}

int main(void) {
	unsigned long time0 = timeGetTime();

	struct node* dataList = createList();
	loadData(dataList, MAX_COUNT); 
	
	// 在尾部添加我们想要找的数据，放在最后，是为了测试最坏情况
	struct node findObject = { "https://www.github.com/100000001.html", 0 };
	listPushBack(dataList, &findObject);

	unsigned long time1 = timeGetTime();
	printf("数据已经加载完成, 耗时 %d ms.n", time1-time0);

	
	printf("开始搜索...n");
	bool ret = findData(dataList, findObject.url);
	unsigned long time2 = timeGetTime();
	printf("搜索结束.耗时 %d ms.n", time2 - time1);

	if (ret) {
		printf("Found!n");
	} else {
		printf("Not Found!n");
	}

	return 0;
}

测试效果

通过修改宏 MAX_COUNT ，调整数据总量。

加载500万数据，小试牛刀！ 

加载1000万数据，不减锋芒！

加载一亿数据，直接GG!

 

 当加载到一亿数据量时，内存消耗预计为：（128+4）* 100000000 = 12.29G 

实际上，当加载到1100万数据量时，已经消耗1.35G内存，导致程序直接崩溃！

方案2-使用C++的list容器

如果使用C++的标准容器list，最大加载量会不会增长呢？

源码

#include 
#include 
#include 
#include 
using namespace std;

//使用timeGetTime
#include 
#pragma comment( lib,"winmm.lib" )

#define MAX_COUNT  5000000

void loadData(list* list, int count) {
	int n = 0;
	for (int i = 0; i < count; i++) {
		string url = "https://www.github.com/"  + to_string(i+1) +  "html";
		list->push_back(url);

		if ((i+1) % 1000000 == 0) {
			cout << "had loaded " << (++n * 100) << "W" << endl;
		}
	}
}

bool findData(list*list, string *url) {
	for (auto it = list->begin(); it != list->end(); it++) {
		if (*it == *url) {
			return true;
		}
	}
	return false;
}

int main(void) {
	unsigned long time0 = timeGetTime();

	list dataList;
	loadData(&dataList, MAX_COUNT);

	// 在尾部添加我们想要找的数据，放在最后，是为了测试最坏情况
	string findObject = "https://www.github.com/100000001.html";
	dataList.push_back(findObject);

	unsigned long time1 = timeGetTime();
	printf("数据已经加载完成, 耗时 %d ms.n", time1 - time0);

	printf("开始搜索...n");
	bool ret = findData(&dataList, &findObject);
	unsigned long time2 = timeGetTime();
	printf("搜索结束.耗时 %d ms.n", time2 - time1);

	if (ret) {
		printf("Found!n");
	}
	else {
		printf("Not Found!n");
	}

	return 0;
}

测试效果

500W应该没有问题吧？

 为什么list容器比自己写的C语言链表更慢？其实这个很好理解，list容器本省就是为了更方便使用，做了很多封装，加上使用string类型字符串，导致性能更不上方案一的纯C链表。

1000W, 再加码！

还没有加载到800万就GG了！

此时已经消耗内存：1.7G, 如下图所示：

 一亿数据，已经没有机会挑战了！这里，也可以看出使用list容器的开销。其实，在一般场合，list足够用了，只是在这个极限挑战中，没有超过1000万的数据量！

方案3-使用布隆过滤器

布隆过滤器，很多人没有听说过，不是因为你孤陋寡闻，而是这个算法，一般人不用它。在很多经典教材中，都没有留下名号。所以，不了解它，实属正常。

但是，在特殊的场合，比如现在这个亿万级数量的筛查，这个布隆过滤器，就能产生神效！先上源码，再看效果。

源码

代码的具体原理，稍后我们再分析。

#include "bloomfilter.h"
#include 
#include 

#define MAX_ITEMS 	100000000      // 设置最大元素
#define P_ERROR 	0.0000001       // 设置误差


int main(int argc, char** argv)
{
    // 1. 定义BaseBloomFilter
    static BaseBloomFilter filter = { 0 };

    // 2. 初始化filter，调用时传入hash种子，存储容量，以及允许的误判率
    InitBloomFilter(&filter, 0, MAX_ITEMS, P_ERROR);

    // 3. 向BloomFilter中新增数值
    unsigned long time0 = time(NULL);
    printf("开始加载...n");
    char url[128] = "";
	int n = 0;
    for (int i = 0; i < MAX_ITEMS; i++) {
        sprintf(url, "https://www.github.com/%d.html", i+1);
        if (BloomFilter_Add(&filter, (const void*)url, strlen(url))) {
            printf("add %s failedn", url);
        }
		
        if ((i+1) % 1000000 == 0) {
			printf("had loaded %d Wn", ++n * 100);
		}
    }
	
    unsigned long time1 = time(NULL);
    printf("数据已经加载完成, 耗时 %d s.n", time1-time0);

    printf("开始搜索...n");
	char* str = "https://www.github.com/100000000.html";
    if (BloomFilter_Check(&filter, (const void*)str, strlen(str))) {
        printf("没有找到：%sn", str);
    } else {
		 printf("找到：%sn", str);
	}

    unsigned long time2 = time(NULL);
	printf("搜索结束.耗时 %d s.n", time2 - time1);
  
    // free bloomfilter
    FreeBloomFilter(&filter);
    getchar();
    return 0;
}

这个算法中使用的头文件“bloomfilter.h”，私信我，直接发送。 

注意，这个源码，需要使用gcc或者g++编译器。编译命令如下：

 gcc  fileName.cpp  -lsupc++ 

注意，需要使用库文件 libsupc++（是libstdc++里面的一个库）。

测试效果

直接挑战1000万的负荷！ 

16秒加载完1000万数据，仅消耗39.99MB内存！表现还可以。再来挑战一个亿，试一下!

......

 157秒加载完一亿条数据，不到一秒即查询结束，内存消耗不到400M。

 布隆过滤器的原理

布隆过滤器，本质上就是一个非常大的位图，以及多个哈希函数。例如对于数据1，分别使用三个哈希函数hash1/hash2/hash3, 得到三个不同的值（哈希值），用哈希指对位图的大小进行取余运算，得到三个位图序号，然后把这些序号设置为1。即，一个数据（或者数据的关键值），对应位图中的3个位，这3个位都被设置为1. 当要判断某条数据是否存在在这个数据集合中时，只要使用这三个哈希函数，得到3个哈希值，进而判断位图中的3个位是否为1。如果这三个位，全部都是1，那么表示，这个数据，可能在这个数据集合中。否则表示这个数据一定不在这个集合中。

因为多个数据的哈希值，可能出现部分重叠，所以可能存在“假阳性”，即数据没有存在集合中，但是判断为存在于这个集合中。

假阳性的解决方案：不能100%消除假阳性，但是可以通过合理配置，把假阳性降到可以接受的范围。

布隆算法的关键因数：

1. 最大多少个数据 (n)
2. 错误率或假阳率(p)，例如0.0000001
3. 哈希函数的个数(k)
4. 位图的内存大小（m）

 具体计算工具：Bloom filter calculator

布隆过滤器的优点

• 速度快，时间复杂度为O(N). N为哈希函数的个数，不是数据个数。
• 安全性高，因为不需要存储数据本身
• 内存消耗低。因为并不存储数据本身，消耗的只是位图空间。

布隆过滤器的缺点

• 存在误判的可能性(假阳性），可以通过参数来降低，但是不能完全消除。
• 添加元素容易，删除元素困难。
• 不能获取已添加元素的具体信息。

 布隆过滤器的使用场景

• 网络爬虫，爬取海量数据，已经爬取过的，就不需要再次爬取了。
• 实现邮件的黑名单过滤。收到邮件后，先判断是否已经在黑名单中。
• 解决Redis数据库的缓存穿透。如果客户请求查询一个不存在的数据时，先去查缓冲，结果查找失败，然后又去查数据库，还是失败，浪费性能。使用布隆过滤器就可以先进行筛选，已经判定不存在，那就没有必要去查缓冲更不用去查数据库。

问题总结

使用链表或者list等数据结构，查询速度其实并不慢，但是面对亿万级的数据筛选，最大的问题，是内存消耗。因为布隆过滤器，并不存储数据本身，而且查询的速度也与数据量无关，仅和哈希函数的个数有关。