大话高并发高可用一致性|网站架构发展|网络编程缓存|C 语言实现布隆过滤器 Bloom Filter 编程练习 | GTest 教程

两个部分分为本文章，一部分是布隆过滤器的实现指引。

一个提供的前置知识，包括：

哈希表及引用，基本网络应用程序结构，计算机科学中的缓存，数据库分离网站结构，数据库缓存，布隆过滤器及其应用，

基本网络应用程序结构

学习计算机，必须了解实际从业者工作的时候到底在干什么。

最好学习各部分专业课程之前就能以系统的观点去看每个模块，了解学的东西到底在整个系统中哪一个小块，能够知道学的东西哪一部分是实际应用中尤为重要的，哪一部分是旁支末节。到具体学习的时候，用分层隔离的思想把当前模块搞清楚。

首先是现在的网络编程到底在编什么的问题，我们首先知道有网络，网络上有各种节点，比如电脑手机等客户端终端设备和各种网络服务供应商的服务器设备在进行通信，这些通信中就是传输着各种数据。

所以编程要么是编电脑手机上的软件（客户端开发）或网页（网页前端开发），要么是编服务器上运行的各种服务（服务器后端开发）。

主要还是学习怎么编服务器上运行的各种服务从而从事后端开发的工作。。

服务器提供服务响应请求回复应答，客户端进行请求，标准的网络服务就是简单的C/S 结构，客服端服务器结构。我们为了把布隆过滤器讲清楚，下面都只分析服务器，即网站结构。

一个网站的架构，一开始都是最简单的，就是一台服务器，客户端通过某些方法（请抽象这个过程）经过网络向这个服务器发一个请求，服务器得到请求后进行一些计算然后返回一个结果给客户端。

比如一个不会算加法的客户端发 1 和 1 给服务端，服务端算出 1 + 1 等于什么，于是他就会返回 2 给客户端。

所以我们最简单的程序就是编一个算 1 + 1 的程序，然后写一个循环，然后就月薪过万了，为了方便理解，假如我们有一些抽象变量（他们实际可能是文件），可以设想以下的伪代码：

variables: has_request, client, server, a, b, sumdef server: while(True):if(has_request == True):sum = a + bhas_request = Falsedef client_1:a = 1b = 1has_request = Trueprint sumdef client_2:a = 2b = 3has_request = Trueprint sum

接下来让我们进行亿点跳跃（就像从1 + 1 = 2到微积分习题），实际上我们并不会写一个在服务器上帮数学天才算加法的程序，我们要做的远比这要复杂得多。

想象我们需要做一个买卖人口的网站，我们要做什么？从基本的访问开始分析：

提供能注册和登录的功能，从而记录买家和卖家的信息，如地址，电话号码。

我们要保存买家和卖家的信息，而且不能保存在内存里（比如用数组或者链表），因为内存里的数据在服务器关机后就全部没有了，这个过程叫做持久化。

我们要提供查询买家和卖家信息的功能。

我们要登记在买卖的人口信息，比如买家 A 希望从美国买家手中购买美国 年的人口总数信息，我们要让买家 A 搜索到这个信息，从而进行订单。

还有很多。

总之上面这些只是为了引入数据持久化的概念，以及数据查询的概念。

如果想要完成我说的持久化，就用fopen打开一个文件，然后拿一个指针指向我的结构体数组，然后调用write函数嗯写就行了，要读进内存，也就malloc一块指针，然后调用read嗯读就行了。

但是实际上这种方法不够抽象，第一个是没有兼容性，不同的软件调用write和read的方式不一样，也就不能方便地迁移服务，比如网站供应商用 Java ，但是他不想干了，于是要卖给公司 B，但是公司 B 用 C++ 开发，他们必须找人研究原来的 Java 代码是怎么读取写入数据的，然后翻译一遍。

而且不符合抽象分层的思想。而且还要处理各种奇怪的情况，这里先讲解第一种情况，如果服务器突然断电了，如何保证程序能够不破坏硬盘中的数据，下次开机的时候怎么知道哪些数据没有写入成功从而不能读取（试想write到一半停电了，可能还是有一点点数据写入到硬盘中了）。

基于各种原因，人们自然想到做一种标准化的软件基础设施（infrastructure）（提一下实际后端开发也分为做基础设施的和做业务的，我们这里主要是以做业务的来讲解）提供数据的保存和查询功能，其中最著名的是关系型数据库SQL 。基于调用抽象 API，而不关心底层实现的思想，我们只需要知道数据库是一种标准化的提供数据管理功能的东西，也常叫他做DBMS，即数据库管理系统。

接下来也请总是进行像上面分析为什么我们要做数据库的思想实验来想清楚这些东西到底在解决什么问题，庞大的互联网泡沫行业平时到底在做什么要这么多人力物力，以及学计算机到底要做些什么重复性或原创性工作。但是思想实验不一定总是完全正确的，但是一开始的理解我们只需要一些自洽的逻辑即可。

缓存是什么

这里推荐一本理解计算机到底是怎么构建的轻松读物《编码》，程序员必读属于是，系统学组成原理之前用这个构建一个符合逻辑的大致映像很有帮助。

缓存是现代计算机里尤其重要的一个思想方法，也分层思想属于是。

首先提一下 CPU 里面的缓存，最基本的门电路来存一个比特，他的访问速度肯定是类似光速的，但是我们不可能做一个 1TB 的 CPU，具体来说甚至我们做不了一个 32MB 的 CPU 中的运算单元，运算单元（ALU）即完成运算的电路，这些电路不可能支持很多数据（寄存器），因为每算一个 32 位数的加法都有好多好多条线要布。所以妥协的方案是每次运算的时候从内存里读取一些加载到寄存器上，然后进行计算。

但是内存太慢了，这里有一份十年前的 Latency Numbers Every Programmer Should Know 就给出了内存访问时间大概是 CPU L1缓存的 200 倍。

CPU 缓存（SRAM制作）即是作为内存（DRAM制作）和 CPU 中的寄存器（SRAM）之间的一个妥协，他做在 CPU 内部，但是不与 ALU 直接连接（即不用布一堆运算用的线。后来补充：我的意思应该是指不用布置与 ALU 的数据通路，不过实际现代 CPU 是有巨多物理寄存器的用上了重命名算法，具体都是后话了），CPU 要读取数据的时候总是先读取缓存的数据，如果缓存没有，就去把内存的数据拖到缓存一份再读缓存（这里其实只是其中一种方案，具体的方案比如 write through 和 write back 是不同的选择）。

硬盘更慢，这也是为什么必须先读取硬盘的东西到内存，到 CPU 缓存，再到 CPU 中的 ALU 的原因。这种层次存储结构利用了局部性原理。即总的最外层的 CPU 缓存 L3 缓存也就 32MB，为什么程序还能能快速运行呢，就是因为每个程序运行的时间片（通常是几百个CPU时钟周期，谁是1除以CPU主频）里一般都不会涉及太大范围的存储访问（指操纵的数据机构和跑的代码，几KB已经能容纳大量代码）。

缓存的思想就讲到这里。对于上面的latency.txt请注意最后一条，从美国加州发一个网络数据包到荷兰再回到美国加州的时间是 150ms，和 L1 Cache 的访问速度 0.5纳秒 比起来，大到不得了。

数据库分离网站结构

前面我们讲了数据库，现在我们继续跳跃，现在把我们的网站架构升级到多台服务器，那么为什么要这样做呢？有很多原因，思想实验就认同以下说的就行了。

有了多台服务器之后，几亿个（高并发）用户要买卖美国 人口信息的时候我们都能响应了，因为我们有很多的硬件。

然后就可能要分离我们的数据库和服务了，原来说的服务器只有一台，响应买卖人口网页访问的服务和保存各种人口信息和买家卖家信息的数据库都在同一个服务器上，压力很大。考虑是服务器所在机器要处理大量请求，耗用大内存和占用大量资源，数据库也要占用大量资源，避免机器抗不住也要分离数据库和应用服务器。

现在我们可能有很多服务器，所以甚至我们可以把数据库也单独拿到别的服务器上去。这样的考虑又保证了安全性，应用服务器（买卖人口网站）挂了数据库不一定挂，现在我们有很多应用服务器，挂了一台马上可以另一台补上，这个叫高可用。

当然，我们可以更加激进，我们把数据库服务器也做个几百台，哪台倒了马上换一台上来。

这么多服务器，怎么保证他们的内容是一样的呢，比如数据库，如果内容不一样就麻烦了。这个就叫一致性。这三个黑体字是后端 infrastructure（基础架构） 开发的主要研究内容。我们这里就不继续深入了。

而后端程序员基本要做的事情就是，通过调用基础架构提供的各种 API，来完成业务上的开发，包括编写各种数据库事务增加删除修改查询的语句，利用各种框架完成任务的工作。

框架基本是把各种脏活累活（前面说的 infrastructure 开发）都做好，让上层负责业务的程序员专注于业务逻辑，比如算 1 + 1 ，你只需要在main函数里面写好，不用去关心程序是怎么被操作系统调度执行的（为什么main函数要return 0? 实际是 CRT 的某些约定！），需要用argc和argv也传进来了，自己不用关心他怎么传进来的。

但是这样也带来了一些负担，程序员必须学习多一个东西，就是这个main函数的约定，你不用main函数也不做脏活，程序就不能运行起来。

框架就是像main函数一样的东西，他做好了各种网络底层的脏活累活（main外面的程序启动的活），但是你必须根据他的规定来。

这里再多几句，讲一下库和框架的区别，库是别人写好的逻辑，是封装好的一些操作，比如printf是一个库函数，是一个 API，你给他输入他给你结果，而框架是像main函数的东西，是一个脚手架，你只需要做完形填空，做好最关键的东西，他帮你运行，而不用写完整的文章。

这些内容都很重要。而学习网络编程，很多时间都要去学习框架如何使用（虽然有点本末倒置但是如果不用框架会更加本末倒置）和框架的规定，再到业务逻辑代码。而业务逻辑代码只是基本功，会不会使用工具是人和动物的根本区别。

数据库的缓存

前面讲了这么多，其实都是为了讲布隆过滤器，在此之前我们先讲服务器缓存。读到这里你已经具备缓存的知识和当前基本的网站架构的主要内容了。

所以接下来进行更大的跳跃。

对于数据库服务器而言，我们上文说过了网络的速度到底有多慢，所以不到万不得已，我们都不会去查数据库。

最基本的想法就是手机电脑上（客户端）缓存一些内容，网站的服务器也缓存一些内容，这样根据局部性原理（前文也提到了），很多时候就不用去查数据库了。

我们不讲客户端，就讲服务端的，前面讲到 SQL 关系型数据库模型是广泛应用的数据库，他是一个硬盘数据库。他能进行关系查询，什么是关系查询？比如我有一个学生表，一个选课表，一个课程表，就能通过三者之间的一些关系用课程查到选了课的学生（当前先把表抽象成一个大数组吧）。

硬盘数据库肯定是慢的（实际DBMS内部也有内存缓存的），现在考虑我们在内存建一个内存，如果在缓存里的话我们就不用查询硬盘数据库了（应当把硬盘数据库里面的数据当成上千万甚至亿条, 而缓存则是最常用的几百条到几万条），如果命中缓存，就直接返回结果。回想上面讲过的内容，有什么适合这个操作呢？

很容易想到上面说过的哈希表（哈希表我说得可能不太清楚，最好还是百度一下加深理解）。同样的，要处理各种琐碎的问题，所以同样做成一个基础设施。

我们可以同一台服务器硬件运行一个这种内存数据库做缓存，甚至可以另外开一个服务器放这个哈希表。

哈希表的本质其实是一个 K-V pair 存储结构，所以这种数据库就叫做 KV 数据库。SQL 的广为人知软件是 MySQL （后端开发）和 SQLite（主要是客户端开发），而 KV 数据库的广为人知软件则是 Redis（remote dictionary server），因为 KV 表就像一个字典（在 Python 中 哈希表就是用字典指代）。

又有一个新的问题了，对于不在缓存里的数据？我们是不是必须要去查询数据库了呢？并没有，还有优化手段，我们必须注意到，绝大多的查询，可能他根本就不存在！不存在还查关系数据库（关系数据库的查询并没有 KV 数据库快）肯定浪费（这种情况成为缓存击穿，即因为缓存中没有就要去查数据库）。

于是就到今天我们要实现的布隆过滤器了。

布隆过滤器介绍

维基百科中有详细的介绍 Wikipedia: Bloom Filter，由于潜在的网络问题，另外提供一个针对实现过程中涉及的计算的内容的链接：布隆过滤器。还记得独立无关事件叠加原理即乘法定理以及关于自然对数 e 定义的重要极限的读者可以自己进行错误概率上的推理加强理解，但是这不是必要的。

布隆过滤器的基本介绍在吴军的 数学之美系列 里面有介绍，同样由于潜在的网络问题，这里引用一部分：

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。

比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；

在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。

最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。但是当集合巨大时，哈希表存储效率低的问题就显现出来了。

比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。

一个办法就是记录下那些发垃圾邮件的 email 地址。全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。

布隆过滤器的数学工具只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。

对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, …,F8） 产生八个信息指纹（f1, f2, …, f8）。

再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, …,g8。

现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。

现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。

我们用相同的八个随机数产生器（F1, F2, …, F8）对这个地址产生八个信息指纹 s1,s2,…,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,…,t8。

如果 Y 在黑名单中，显然，t1,t2,…,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。

但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率(False Positive Possibility)。

实验提要

这是一个简单的数小时可以完成的 C 语言学习编程练习，读者将学习编写一个布隆过滤器 (Bloom Filter), 谁是当前网络应用中广泛应用的一环。本文假定读者是对网络编程零基础的。厄，我编写这个只是为了学习 TDD 和 CMake，不要吐槽这个东西太简单了，下面的东西语法可能有些错乱但是用来机翻成英语很好用。

/rzbdz/bloomfilter/tree/lab 读者可以 git clone 这个仓库进行学习。

参与者应当具备良好的 C 语言编程基本知识，包括但不仅限于以下知识点：

基本的编程（分支循环等）整数数据类型位运算结构体指针堆上内存分配 (malloc和free)

下文将提供足够丰富的必要前置知识（不够清楚的地方可以在网络进行信息检索）关于布隆过滤器帮助完成练习。本文所有的黑体字都是计算机从业的重要知识点。

基本要求：

在 Linux x64 系统下完成本项目。（如果不是 Ubuntu 发行版则需要自己安装编译工具链而不是直接运行我们提供的脚本安装）。完成 utils 子目录中的 bitset 源码文件的函数实现，函数原型已经在各自的头文件中给出，其中 hash 已经提供了一种实现。利用 utils 中的模块提供的函数接口调用实现 filter 子目录中的布隆过滤器编写。在对应的测试源代码文件中添加自定义测试（源码中有帮助说明），更多详情：gtest通过所有非自定义测试。

扩展：

+限制布隆过滤器位的个数为 2 的整数幂从而优化哈希取模运算为a % capacity=>a & (capacity - 1)。如果不知道怎么做可以在 Rounding up to next power of 2 找答案。+阅读论文 Less Hashing, Same Performance:

Building a Better Bloom Filter 中的两个哈希函数实现多个哈希函数的方法，并修改布隆过滤器中求哈希码的实现。（实际不用真的阅读，直接拿公式用）+在 2 的基础上扩展哈希函数的数量，优化布隆过滤器的构造策略，在给定的期望 fpp 和限制的可用空间下改进 k 的选取策略（当限制可用空间时 m 会比实际公式最优解偏小，如果用 m 带入公式计算 k 会引发 fpp 增加）。*利用 mutex 等工具将布隆过滤器改写为线程安全的。（不做要求）

文件目录

目录结构：

├── CMakeLists.txt# CMake configure file├── build_support# googletest CMake configure file│ └── googletest├── src│ ├── filter │ │ └── ## Bloom Filter implementation│ ├── include │ │ ├── filter │ │ │ └── bloom_filter.h│ │ └── utils│ │ ├── bitset.h │ │ ├── fileio.h│ │ └── hash.h│ └── utils│ ├── ## Bit String implementation│ ├── # File i/o│ └──# implemented hash function└── tests # googletest folder├── ##├── ##└── ##

上面的目录中，进行本 lab 需要进行工作的文件有标识为两个 # 号。

下面为如何进行本作业的下载安装，如果 CMake 进行 googletest 安装时阻塞时间过长请到build_support/googletest/CMakeLists.txt.in文件中将 github 仓库源修改为 gitee 镜像。

$ git clone .....$ sudo ./build_support/packages.sh$ cd bloom_filter$ mkdir build$ cd build$ cmake ..

具体的代码编写见源码中的注释要求。

关于如何编译本项目，见 README.md, 做 lab 应当完全在 lab 分支下进行，而不是 master 分支。

如果编写完全正确，你将能够通过所有的 gtest 测试。

任务点

Task 0: File IO

在这个部分，你将通过阅读 的源码学习 Linux 下的文件与 IO 知识 (这部分知识常常不会在 C 语言编程课上涉及因为他们大多是一些规定上的东西，需要用时查手册即可)，并且你可以根据需要自己学习mmap的原理。

但是上面这些不是必要的，什么是必要的是你必须阅读 fileio.h 所提供的接口的文件中的注释，以保证在接下来的编程练习中不直接调用标准库的fread和fwrite函数完成编程。

这是为了练习抽象分层思想以及运用已有的 API 与库解决问题的能力。

你还需要通过观察 源文件学习怎么使用 fileio.h 提供的接口来进行读写文件，

以及学习基本的 gtest 测试函数编写。这是为了学习TDD 测试驱动开发的思想。

其中如EXPECT_EQ的函数可以在上文提供的链接中找到说明，

最基本的 gtest 测试函数就像这样：

TEST(TestSuitName, TestCaseName){...// won't stop at FailureEXPECT_EQ(1+1, 2);...for(int i = 0;i<100;i++){// do stop at FailureASSERT_EQ(i&1, 1);}...}

注意如果TestCaseName前面如果有DISABLED_前缀时他不会运行，可以把这个认为是一种快捷注释。下面列出 gtest 常用的断言：

// true or falseEXPECT_TRUE(ret)：ret == trueEXPECT_FALSE(ret)：ret == false// equal or notEXPECT_EQ(expected, actual)：expected == actualEXPECT_NE(expected, actual)：expected != actual// compare floatsEXPECT_FLOAT_EQ(expected, actual)：(float)expected == actualEXPECT_DOUBLE_EQ(expected, actual)：(double)expected == actualEXPECT_NEAR(var1, var2, tol)：abs(var1 - var2) <= tol// compare stringsEXPECT_STREQ(s1, s2)：s1 == s2EXPECT_STRNE(s1, s2)：s1 != s2EXPECT_STRCASEEQ(s1, s2)：s1 == s2EXPECT_STRCASENE(s1, s2)：s1 != s2

对于更多有关单元测试的内容你将会在后续学习（如学习 Java 语言中的 JUnit 单元测试）。

下面将简要介绍怎么运行测试，由于假定读者不需要具备 C/C++ 项目构建的知识，所以 CMake 文件已经编辑好，不需要修改。

CMake 是一个通过编写类似脚本的东西管理 C/C++ 项目的程序（称为项目构建），在前面安装的时候已经使用过 cmake 命令。这里之后基本不涉及 cmake 命令。

CMake 基本上就是管理各种文件之间的依赖关系，头文件的位置，同一个项目多个可执行文件生成的大概。使用 CMake 不需要用户再编写复杂的编译链接命令，可以认为他是用代码在命令行下做 GUI IDE 所做工作的一个工具（实际上也作为通用的项目构建方案被各种 GUI IDE 所支持）。

由于项目安装的时候已经安装好了所有的编译用的命令集合的 Makefile 文件，需要编译的时候（等价于点击 IDE 的编译菜单）只需要这样（以下命令在项目目录下的 build 子文件夹中执行）：

$ make tests # 编译所有测试（共 3 套测试）$ make bitset_test # 编译位串相关的测试，即 $ make fileio_test # 同理$ make filter_test # 同理

执行则是执行可执行文件，这一点即 Linux 系统下的./可执行文件名称，如输入./tests即执行所有的测试。

Task 1: Bit Set

在这个部分，你将要编写一个管理布隆过滤器中位数组数据结构的组件。基本的结构体为bitset_, 他有两个成员，其中 length_ 记录的是位串的长度，零长数组的用法详细见这里：Zero-Length , 这个将帮助方便直接构建在内存硬盘上数据结构。

基于各组件独立的原则，bitset 实现不能够依赖 fileio，bitset 本身也不提供序列化读写文件的接口但是提供了从内存（buffer）中识别一个 biset 结构体的方法。为了继续独立，我们提供支持其他内存分配器的接口，这将有助于调用 fileio 直接在 mmap 的内存上构建 bitset 结构体。

你需要在中完成定义在bitset.h的所有函数，你不能够修改结构体的定义，但是你可以自由地添加辅助函数，但是不要暴露在头文件中。

Task 2: Bloom Filter

在这个部分，你将调用 Task 0 和 Task 1 的接口，实现一个布隆过滤器。你需要理解布隆过滤器的参数的数学计算公式，以便于在函数optimal_hash_function_count和optimal_bitset_length中实现他们，你可以自由的删除这两个标记为static访问标识的帮助函数，只要你的实现是正确的。

布隆过滤器的结构体中有一个File结构体，这个内嵌结构体只是为了能够方便地管理，实际不会参与布隆过滤器持久化的部分，你必须覆写他们当你初始化一个布隆过滤器无论你新建还是从内存或是文件中读入一个时。

我们规定标识一个布隆过滤器的标识符为一个const char *, 即文件名。保证你调用remove函数删除他们在你需要测试的时候，否则你可能会创建过多的垃圾文件。

布隆过滤器的关键部分在于Insert函数和ContainsKey函数，实现他们正如头文件中的注释所提示的那样。这两个函数将要调用哈希函数来完成哈希码计算。

你可以随意地增加宏定义，但是你不能修改现有的宏定义为了测试需要，当然你也可以修改测试，这决定于你。

一切完成的时候，你将在运行 gtest 后看到一篇绿色，这说明你完成了，恭喜，如果悠闲地可以尝试完成挑战性的扩展要求。

上面和下面都是完成本作业需要的所有前置知识。这是一篇完全自洽的文章（当然本身编程练习需要参考一些文外资料）！

基本位运算

对于一个uint32_t（C99 中定义在头文件

#includestdint.h中）而言，他是一个 32 位宽度的整数类型，即意味着他有 4 个字节。

对于一个uint32_t, 如果需要把四个字符（char，一个字节宽度）转换为一个32 位整数，有两种方案，一是大端（Big Endian）一种是小端（Little Endian），同样，本练习实际上也可以认为不涉及大端和小端。

如果我们需要操作一个 32 位整数的第 3 位（从低位到高位 0~31 编号），可以用num & (1<<3)选取，用num |= (1 << 3)置位。

哈希表

对于计算机而言，内存是随机访问友好的。

相比顺序查找，一种更快的方法是用哈希表，我们通过某种函数（哈希函数）建立一种键（即查找的依据）和值的位置之间的映射关系，就只需要计算一次键的哈希码就能定位到我们需要的数据。这里假定理想的哈希函数是没有冲突的，但是实际会有冲突，本练习不会涉及哈希冲突的问题。

设想一个长度为10,000的数组，假设我们有5,000个数据（简单原因认为是整数），他们在数组中无论是乱序存放还是有序，如果想知道一个特定的数在不再数组中，都需要扫描整个数组才能知道（有序时可以使用二分查找加速）。

使用哈希表存储，我们对每个插入的整数先用哈希函数映射到某个值，比如对于插入250，hash(250) = 123456789, 于是我们只需要把250放到数组的第123456789个位置。正如这个例子，对于哈希函数而言，其计算出来的数值并不一定符合数组的范围（这里是10,000个），有必要通过模运算来截断过大的值，为了避免冲突，我们总是希望使用质数作为模数，因为不同数能被同一个数整除的时候，同时这个公因子也是合数的因子的时候，很容易模出相同的结果，而质数只有两个因数较难冲突。