此篇承接上篇CSS和html5标签。写一些CSS3的新特性，flex布局和JS的基础知识。

CSS3

CSS3是较新的层叠样式表的规范，其中的一些特性并未得到现行浏览器的支持。需要在样式前面加上-ms-, -moz-或是-webkit-，才可获得最好的浏览器支持。

边框：CSS3支持设置圆角矩形（border-radius），边框阴影（box-shadow）甚至边框图片（border-image）.

背景：设置背景大小和重复方式（background-size，background-repeat），设置背景所属范围和绘制区域（background-origin，background-clip）

文本效果：文本阴影（text-shadow），断词方式（word-wrap），断句方式（word-break）

字体：支持从外部导入字体（font-face）

2D，3D变换：transform，有rotate，translate，scale，skew，translateX，translateY，rotateX，rotateY等属性。

渐变：transition，选择属性，时间和变换函数。一般结合伪类（如:hover）使用。

动画：keyframe（设置关键帧）+animation（决定动画的名称，持续时间，周期，方向等等）

多列：column-count，column-gap，column-rule，column-span等属性

用户界面：resize支持用户自己调整元素大小等等。

更多内容可以参考W3scool的CSS3讲解。

Flex布局

Flex是一种十分方面的布局方式，可以轻松实现居中对其等需求和响应式布局。目前在较新的浏览器中有支持。Flex需要在display属性中指定为flex。从而使得这个容器有了flex的特点。

flex-direction：指定伸缩容器的主轴方向，即子元素伸缩的方向。有row，row-reverse，column，column-reverse等值。其中row是常用且默认的。

flex-wrap：控制伸缩容器是单行或是多行，即侧轴新行的堆放方向。有no-wrap，wrap，wrap-reverse等值。默认值为no-wrap。

flex-flow：通常将flex-direction和flex-wrap结合起来用flex-flow统一表示。

align-items：控制容器内伸缩项目的侧轴对齐方式。有flex-start，flex-end，center，stretch，baseline等值。

justify-content：主轴上伸缩项目的对齐方式。有flex-start，flex-end，center，space-between，space-around等值。

align-content：多行间在伸缩容器里的对齐方式，有flex-start，flex-end，center，space-between，space-around，stretch等值。

order：通过css动态更改子元素的排列顺序。默认为0，值越大顺序越靠前，可以取负值。

flex-grow，flex-basis，flex-shrink等是更加复杂的用法。这里从略。结合@media screen and (max-width: xxxpx or min-width: xxxpx){ css code}会有很好的响应式布局效果。

更多内容和展示效果，可以在w3plus的flex讲解中找到。

JS与html经验小结

不成篇幅，这里用列表的形式给出。

1. alert()弹出对话框，无返回值；confirm()弹出确认框，返回boolean；prompt()弹出信息框，返回用户输入。
2. document，window，element等是html的js接口中的常用对象，具体可以MDN的技术文档。
3. element代表了页面DOM结构的节点，有文本节点和元素节点的区别。
4. document中的常用函数包括getElementById，getElementsByTagName， getElementsByClassName，createElement等，element中有innerHtml，style，classname等属性值。
5. 添加元素，appendChild，insertBefore，都需要父元素调用，通过parentNode获得。反之，可以通过firstChild，lastChild，nextSibling等获知子元素情况。删除元素使用removeChild。
6. parseInt()是JS的内建函数，用来将字符串转换为整型数，须开头为数字且遇到非数字为止。JS默认均用浮点数存储所有数据，通过isNaN判断是否为数字，isFinite判断是否为无穷。
7. array是JS的基础数据类型之一，以键值对的形式存储，和hashtable很像，有push, reverse, sort, shift, unshift, push, pop, join，reduce等用法。
8. 有foreach的用法
9. 函数也是对象，有诸如arguments，length等属性。可以作为返回值或是输入值。甚至有制造函数的函数。

更多内容可见MDN的技术文档。

前言：与实验室同学参加百度前端学院，做了几个任务，做小小的总结如下。

html5标签

html5标签增加了标签的语义化，更有助于爬虫爬取，代码阅读。对比无意义的div span等标签，article aside section等新标签的语义化更有助于文档结构化。

• article：独立的个体，可以是文章，博客等等。语义上article和article间是独立不相关的。
• section：彼此互补的部分，section间是有共同联系，互补的。section间共同构成一个整体。
• header：article的标题部分，可以是标题，作者，时间等等。
• hgroup：当标题部分的标题很多时，用hgroup包起来。只用h标签就能完成就不需要hgroup。
• aside：侧边栏，与article的主体部分相隔离，可以是额外介绍，可以是用户注册等。
• nav：导航栏，放置网站logo，导航列表等等。
• footer：尾注，可以是版权声明，帮助等等。
• caption：表题。可有可无。
• figure：放置图片，内设img标签。
• figcaption：图片标题
• cite/var/code/samp/kbd：引用、变量、代码、范例、键盘输入域
• datalist：输入列表
• time：时间，放置时间等，内有datetime属性

使用html5标签，格式化文档，将大大增加代码可读性。

css布局

block代表块级元素，有宽和高独占一行；inline代表内联元素，无宽和高，不独占；inline-block内联块元素，不独占一行，有宽和高。

position的取值有4中。static：默认，在文档流中；relative：相对于原位置位移，不移出文档流；absolute：相对于父容器位移，移出文档流；fixed，相当于屏幕位移，移出文档流；sticky，综合relative和fixed设置阈值。

完成多栏设置时，可用inline-block,position:absolute,float。其中float适用性最广，inline-block最简洁，position最笨。使用float时，注意清除浮动。

师兄给了一个虚网映射的仿真（cpp），和之前的embed-detail的C语言仿真工具很像，经过一周左右的学习，挖掘出了其中虚网映射部分的内容，在此整理，以作日后学习。鉴于之前embed-detail的学习总结很繁琐，这里的总结只做精要的介绍。

数据结构

这一部分在Utility.h中完成，是对映射种种数据容器的整理。

节点：

编号，CPU，带宽和，优先度

最短路：

跳数，带宽，路径列表，下一跳

映射结果（单节点）：

物理节点对象，虚拟节点编号，所属根节点，到根节点跳数，Node_list中序号，Node_list总数

（类）物理拓扑：

节点总数，边总数，资源，节点资源，边资源；

节点群（一维向量），边群（二维向量），最短路群（二维结构向量）；

方法：

• 初始化，
• 节点排序算法，
• Floyd算法,
• 找到节点序号对应的下标，
• 计算网络资源

（类）虚拟拓扑（继承物理拓扑）：

//同物理拓扑

允许最大跳数，分割率，拓扑类型，起始时间，映射时间，存活时间，消耗，节点消耗，链路消耗，收入，收入支出比，是否匹配成功，是否起请求截止，是否delay过，是否失败

满足约束条件的节点群（二维向量），结果群（结果向量），最短路群（二维链表向量）

方法：

• 读入拓扑，
• 初始化，
• 计算最短路径和，
• 查找结点是否已经映射，
• 匹配节点（包含匹配边），
• 匹配边，
• 匹配过程（包含匹配节点），
• 分配或释放资源（匹配过程中完成），
• 打印结果，
• 计算收入支出，
• 计算收入，
• 释放虚网的所有资源

核心方法分析

这一部分在Utility.cpp中完成，是对映射种种方法的实现。

（物理网络）

1. 初始化：开辟最短路群空间，计算链路CPU/带宽和/PR值

2. 计算资源：节点，链路资源相加。

（虚拟网络）

1. 读入文件：读入节点数，链路数，开始时间，存活时间等。

2. 初始化：填充Node_list

3. 查找结点是否已被映射：for 循环遍历暴力查找

4. 匹配节点：读入物理网络和参照物理网络，当前结点所属根节点，已映射节点数。

（1）打印

（2）从可行最短跳（虚拟网络中的跳数）到最大允许跳开始循环

（2.1）从可行节点（Node_list）中查找满足CPU要求的节点

（2.2）查找匹配边（Match_Edge），若有打印信息并返回

（3）打印失败信息返回

5. 匹配链路：读入物理网络预期参照，当前结点编号和下标，已映射节点数。

（1）循环寻找所有与该节点关联的节点

（1.1）若有关联，清空并循环更新最短路向量

（1.2）循环检测带宽是否满足要求

（2）循环还原减少的带宽资源

（3）返回成功标记

6. 匹配：读入物理拓扑，完成一个虚网的匹配

（1）建立物理拓扑最短路矩阵

（2）初始化最短路群，root, chosen_num（已选中节点数）

（3）初始化根节点result类实例，若无备选节点，返回 0

（4）循环寻找可行的根节点直到遍历完成

（4.1）以当前父节点为基础开始匹配子节点，循环

（4.1.1）循环寻找父节点的关联的子节点

（4.1.1.1）若某节点无匹配物理节点，循环释放资源，返回 0

（4.1.1.2）若找到，更新result群向量，调用匹配节点，找到对应物理节点序号

（4.1.1.2.1）若成功返回，继续更新result，最短路矩阵，更新底层资源

（4.1.1.2.2）若不成功，回退chosen_num，释放资源，更新root，最短路

（4.1.2）若未回退到根节点，不用调整根节点，继续从下个父节点开始匹配，直到匹配完成

（4.2）若匹配未完成，释放根节点和其余资源

（5）若匹配成功计算收入支出返回回退次数，否则释放资源，返回 0；

7. 资源管理：通过标记值区分占用或是释放，循环更新节点和链路资源

8. 打印，计算收入支出

9. 释放虚网资源：循环释放，返回释放资源值

主程序

这一部分在VNM.cpp中完成，是时间窗模型下虚网映射的实现。步骤如下：

1. 初始化临时变量，

2. 从文件中读入底层物理网络，虚网请求

3.  打印初始信息，计算物理资源

4. 循环到所有请求都被处理完成或是有finish标记

4.1 循环计算该窗口内待映射请求数

4.2 循环这些请求

4.2.1 挑出未延迟且未成功的

4.2.1.1 初始化虚网，打印信息

4.2.1.2 开始匹配，计算时间

4.2.1.3 计算收入，更改标记为映射完成或延迟

4.2.1.4 计算当前物理资源，写入到文件

4.2.2 挑出匹配成功且到期的请求

4.2.2.1 更新它们的R/S和完成数目

4.2.2.2 释放它们的资源

4.2.3 挑出delay过久的请求，置为失败，更新资源和计数器

4.3 计算该时间窗内的支出，收入等数据，更新finish和计数器

4.4 打印该时间窗测试数据到文件

4.5 更新时间窗时间

5. 关闭文件，打印当前时间

前言：在北邮人论坛里看到了对多态，继承，多重继承等的讨论，遂对比较陌生的鸭子类型和反射做了些学习。实际上这两个概念属于编程范式的范畴，在语法层面之上。对之的了解，相信对于以后语言的学习，多少也有些触类旁通的帮助。

鸭子类型

静态语言和动态语言

编程语言按照数据类型大体可以分为两类，一类是静态类型语言，另一类是动态类型语言。

静态类型语言在编译时便已确定变量的类型，而动态类型语言的变量类型要到程序运行的时候，待变量被赋予某个值之后，才会具有某种类型。

静态类型语言的优点首先是在编译时就能发现类型不匹配的错误，编辑器可以帮助我们提前避免程序在运行期间有可能发生的一些错误。其次，如果在程序中明确地规定了数据类型，编译器还可以针对这些信息对程序进行一些优化工作，提高程序执行速度。

静态类型语言的缺点首先是迫使程序员依照强契约来编写程序，为每个变量规定数据类型，归根结底只是辅助我们编写可靠性高程序的一种手段，而不是编写程序的目的，毕竟大部分人编写程序的目的是为了完成需求交付生产。其次，类型的声明也会增加更多的代码，在程序编写过程中，这些细节会让程序员的精力从思考业务逻辑上分散开来。

动态类型语言的优点是编写的代码数量更少，看起来也更加简洁，程序员可以把精力更多地放在业务逻辑上面。虽然不区分类型在某些情况下会让程序变得难以理解，但整体而言，代码量越少，越专注于逻辑表达，对阅读程序是越有帮助的。

动态类型语言的缺点是无法保证变量的类型，从而在程序的运行期有可能发生跟类型相关的错误。这好像在商店买了一包牛肉辣条，但是要真正吃到嘴里才知道是不是牛肉味。

如在Ruby，Python，JavaScript等语言中，当我们对一个变量赋值时，显然不需要考虑它的类型，因此，JavaScript是一门典型的动态类型语言。

是什么

动态类型语言对变量类型的宽容给实际编码带来了很大的灵活性。由于无需进行类型检测，我们可以尝试调用任何对象的任意方法，而无需去考虑它原本是否被设计为拥有该方法。

这一切都建立在鸭子类型（duck typing）的概念上，鸭子类型的通俗说法是：“如果它走起路来像鸭子，叫起来也是鸭子，那么它就是鸭子。”

我们可以通过一个小故事来更深刻地了解鸭子类型。

从前有一个国王，他觉得世界上最美妙的声音就是鸭子的叫声，于是国王召集大臣，要组建一个1000只鸭子组成的合唱团。大臣们找遍了全国，终于找到999只鸭子，但是始终还差一只，最后大臣发现有一只非常特别的鸡，它的叫声跟鸭子一模一样，于是这只鸡就成为了合唱团的最后一员。

这个故事告诉我们，国王要听的只是鸭子的叫声，这个声音的主人到底是鸡还是鸭并不重要。鸭子类型指导我们只关注对象的行为，而不关注对象本身。

下面用代码来模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var duck = {
    duckSinging: function(){
    console.log( '嘎嘎嘎' );
    }
};

var chicken = {
    duckSinging: function(){
    console.log( '嘎嘎嘎' );
    }
};

var choir = [];    // 合唱团

var joinChoir = function( animal ){
    if ( animal && typeof animal.duckSinging === 'function' ){
    choir.push( animal );
    console.log( '恭喜加入合唱团' )
    console.log( '合唱团已有成员数量:' + choir.length );
    }
};

joinChoir( duck );       // 恭喜加入合唱团
joinChoir( chicken );    // 恭喜加入合唱团

我们看到，对于加入合唱团的动物，大臣们根本无需检查它们的类型，而是只需要保证它们拥有duckSinging方法。

在动态类型语言的面向对象设计中，鸭子类型的概念至关重要。利用鸭子类型的思想，我们不必借助超类型的帮助，就能轻松地在动态类型语言中实现一个原则：“面向接口编程，而不是面向实现编程”。

为什么

那么，为什么要有鸭子出现？

一、组合

C++等语言实现面向对象的主要方法是继承，而鸭子类型实现面向对象的方式是组合。而我们所熟知的，甚至被奉为面向对象编程原则的”多组合，少继承“的思想也说明了组合要比继承更加灵活方便。

C++中的多继承特性从一定层面反映了开发这想通过更多的父类获得特性；优先组合的思想也反应出我们希望能够使用更多对象的特性并隐藏细节；接口的出现反映出我们不希望通过多继承这样庞大的机制就能够实现更为复杂的对象关系；这些原本都是继承机制的面向对象思想或原则。

在日常的面向对象编程过程中，通常会为了做一个相对完美的抽象，关注了更多的类之间的关系，而不能把主要精力集中在业务逻辑代码中。

鸭子类型提供了大道至简的编程思想和模式

二、复用

静态类型中最关键的一点是面向契约编程，即双方定下调用契约，然后你实现，我调用。这避免了许多运行中问题。可是，正因为此，复用被弱化很多。

这里再次提到C++，多重继承的提出也有复用的目的。因为，人们不满足于只能仅仅复用简单的个体，很希望能够吸取多种对象的功能。这和现实是很相近的。一个业务实体往往能够兼备多种实体的功能。

尽管后来其他语言都是采用接口的机制取代多重继承，来实现业务实体的多个功能面的契约定义。可是，接口只是解决的契约的定义。另外，对于契约，其实有时候是很不公平的事。微软的认证是一个例子：

微软的认证是有阶梯约束的。过了初级才能考中级，而不管你是否已经拥有了初级的能力。对于没有参与考试的人，这是件不公平的事。如果有一项任务，必须拥有某种资格认证的人才能做，你是看资质证书呢？还是看能力表现？

这是个非常有意思的问题。如果是你，你会选择哪个呢？静态语言选择了前者，动态语言选择了后者。鸭子类型就是充分想利用这些没有获得契约的资源。在不改变这些对象的前提下，对之复用。

总结

鸭子类型是一种多态的表现形式，是一些动态语言具有的特征。它能够避免一些类的重写，无需大量复制相同的代码，但是也需要良好的文档支持，和严谨的代码，否则代码调试起来会多处许多麻烦，谁知道你的鸭子是不是我的鹅呢？

反射

反射同样是个抽象的、在语法之上的概念，是一些语言具有的特征，它牺牲了语言的封装性来实现代码的重用和灵活性，有利有弊。在Java，Ruby，C++，C#，Scheme诸多语言，甚至C中都有体现。

是什么

从**元编程（Metaprogramming）的角度来看，一门语言同时也是自身的元语言的能力称之为反射（Reflection）。按照 Toby Davies 论文 Homoiconicity, Lazyness and First-Class Macros 的说法，反射（Reflection）其实是通过允许在运行时存取程序数据，以改变程序行为的程序设计技术。他认为，反射其实是一种“语义同像（Semantic Homoiconicity）”。具有语义同像性的语言必须把程序中的一些内部状态，比如符号表、指令指针，暴露**给程序员。这样，程序员就可以把这些东西当作 First-Class-Value 而很容易地操作它们。

提供反射这种特性，无外乎是出于为了提高生产力、提高编程时的灵活性等考量。

下面以Ruby为例。

1
2
3
4
5
6
7
8

irb> require 'what_methods'
=> true irb>[1, 2, 3, 4].what? 4 
[1, 2, 3, 4].last == 4  
[1, 2, 3, 4].pop == 4 
[1, 2, 3, 4].lenght == 4
[1, 2, 3, 4].size == 4
[1, 2, 3, 4].count == 4
=>[:last, :pop, :length, :size, :count, :max]

又是一个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

module M; end
class A; include M; end
class B < A; end
class C < B; end

b = B.new
b.instance_of? A  #=> false
b.instance_of? B  #=> true
b.instance_of? C  #=> false
b.instance_of? M  #=> false

b.kind_of? A      #=> true
b.kind_of? B      #=> true
b.kind_of? C      #=> false
b.kind_of? M      #=> true

Scheme中甚至有指令指针级别的反射。例子略。

作用

解释究竟反射机制能够带来什么好处之前，先来看看具体的Reflection机制，以明白透过常见的Reflection支持，在程序中究竟能做到那些事情。这里以Java为例介绍，目的不在介绍Java完整的Reflection API，而是透过Java，帮助大家了解Reflection的一般性概念。

在Java中反射机制的源头，就是一个叫“Class”的class(在C#中有一个相似的类别，则叫做Type)。这个类别有点特殊，原因在于此类别的每一个对象都用来表示系统中的每一个类别。

具体来说，每个Class对象都描述了每个类别的相关信息，也提供你透过它可以进行的一些操作。想要开始Reflection的动作，就必须先取得Class类别的对象。最常被运用到的两个途径，一个便是Object(所有对象皆继承的类别)所提供的getClass()函数，另一个则是Class类别所提供的forName()静态函数。

前者让你得以取得一个对象(尤其是类型未知的对象)所属的类别，而后者则让你得以指定一个类别的名称后，直接得到该类别对应的Class对象。

有了Class对象之后，便能“审视”自身的特性，这些特性包括了它隶属于那个Package、类别本身究竟是Public还是Private、继承自那一类别、实作了那些接口等。更重要的是，你可以得知它究竟有那些成员变量以及成员函数(包括建构式)

透过这个自我审视的过程，程序便能够了解它所要处理的对象(尤其是类型未知的对象)，究竟具备了什么特质。对运用反射机制的程序而言，所了解到的这些特质，便会影响到该程序的运作行为。

取得了某类别的成员变量后(在Java中是以Field类别的对象表示)，便可以取得该类别对象的成员变量值，也可以设定其值。同样的，取得了某类别的成员函数后(在Java中是以Method类别的对象表示)，便可取得该成员函数的回传类型、传入的自变量列表类型，当然更重要的是，Method类别的对象，可被用以呼叫类别对象的相对应成员函数。

有了反射，程序代码在撰写及编译的时间点，毋需明白实际在运行时，究竟会涉及那些类别以及它们各自的行为。你所写下的程序代码，可以完全是对要处理的类别一无所知，也可以是对他们有一点基本的假设(例如要处理的类别都具有相同名称的函数，却没有实作相同的接口，或是继承同样的类别)，一切都可以等到执行时期，透过自我审视的能力，了解要面对的对象究竟具备什么特性，再依据相对应的逻辑，动态利用程序代码控制。 当程序毋需将行为写死，便消除了相依性

有了如此动态的能力，程序代码在撰写时毋需将行为写死，包括要处理的类别、要存取的成员变量、要呼叫的函数等。这大大增加了程序弹性，同时也增加了程序的扩充性。

举例来说，一个连接数据库的Java系统而言，在编译时期是不需要知道究竟运作时会使用那一个JDBC驱动程序，系统只需要透过某种方式，例如在设定档中指定类别名称，那么程序便可以依据这类别名称，加载相对应的JDBC驱动程序，程序代码中完全可以不涉及具体的JDBC驱动程序究竟为何。

总结

本来应该对程序员透明的机制，现在却暴露给了程序员，使得我们有能力去操纵它，让它能够更灵活地完成我们的工作。

所以说，反射这种东西，确实破坏了封装的初衷，但他们两者之间并不是绝对的对立。想一想，我们封装、隐藏细节、建立抽象屏障，无外乎都是为了降低程序的复杂度——这是工程上的折衷。但是在大量的实践中我们发现，我们抽象出来的通用模式并不是银弹，很多问题在它构建的框架之下解决起来就非常麻烦。

所以有了反射这么一手，把很多难以预测的问题留到运行时，动态地去考虑去解决。这也就使得我们在走投无路时，还可以有一道后门开着让我们大摇大摆地进入。

同时。

计算机程序在执行完一系列语句指令后，它知道自己执行的是啥么？它知道它自己是在干什么么？反射，就是试图在语言层面提供一种这样的能力：让代码有自省能力，让代码知道自己在干什么，尽管目前的实现还很初级、很浅薄。

结语

对于编程模式的研究，在我看来有点类似一把砍柴刀，磨刀不误砍柴工，这方面的研究学习在不同的语言和语法实现上，会有着催化剂般的作用。就像数学基础之于计算机算法。

参考资料

1. 动态类型语言和鸭子类型
2. 鸭子类型:一切都是为了复用
3. 初识go语言以及鸭子类型
4. 编程语言中的 鸭子模型(duck typing)
5. 动态与弹性 细看编程语言的反射机制
6. 为什么语言里要提供“反射”功能？
7. 语言的反射为什么比较慢，反射存在的意义是什么？为什么C++没有反射？
8. 元编程的魅力——反射机制

海量字符串检索是很考验算法效率的工作。Trie树和PAT树常用，但是内存占用严重。在垃圾邮件过滤或网络爬虫这种不要求检索结果完全正确的场景下，布隆过滤器是个很好的选择。

Hash函数

Hash（中译为哈希，或者散列）函数在计算机领域，尤其是数据快速查找领域，加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面（这些小的数据集叫做哈希值，或者散列值）。Hash table（散列表，也叫哈希表），是根据哈希值(Key value)而直接进行访问的数据结构。也就是说，它通过把哈希值映射到表中一个位置来访问记录，以加快查找的速度。时间复杂度只有O(1).

哈希函数有以下两个特点：

• 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
• 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的。但也可能不同，这种情况称为“散列碰撞”（或者“散列冲突”）。
  解决冲突的方法有许多，如向左或向右移位，拉链法等等。在数据量不大的情况下，Hash函数作为查找的解决方法看上去是很美好的。然而，数据量大了之后呢。不妨设想下面的应用场景。

假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。给一个URL，怎样知道蜘蛛是否已经访问过呢？稍微想想，就会有如下几种方案：

1. 将访问过的URL保存到数据库。
2. 用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
3. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
4. Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。

以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。

方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？

方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。

方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。

方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。还记得数据结构课上学过的Hash表冲突的各种解决方法么？若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍

实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

上面所举的爬虫只是一个例子，在允许少量错误的情况下，布隆过滤器将是最好的选择。

布隆过滤器（Bloom Filter）

布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。

基本思想

如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit Array）中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

优缺点

• 优点——相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
• 缺点——误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。

误算率（False Positive）分析

一个Bloom Filter有以下参数：

m | bit数组的宽度（bit数）
n | 加入其中的key的数量
k | 使用的hash函数的个数
f | False Positive的比率

假设 Hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 Hash 函数的个数，那么位数组中某一特定的位在进行元素插入时的 Hash 操作中没有被置位的概率是：1 - 1/m

那么在所有 k 次 Hash 操作后该位都没有被置 “1” 的概率是：(1 - 1 / m)^k

如果我们插入了 n 个元素，那么某一位仍然为 “0” 的概率是：(1 - 1 / m) ^ k*n

因而该位为 “1”的概率是：1 - (1 - 1 / m) ^ k*n

现在检测某一元素是否在该集合中。标明某个元素是否在集合中所需的 k 个位置都按照如上的方法设置为 “1”，但是该方法可能会使算法错误的认为某一原本不在集合中的元素却被检测为在该集合中（False Positives），该概率由以下公式确定：

1 - (1 - 1 / m) ^ k*n ≈ (1 - e ^ (-k * n / m)) ^ k

其实上述结果是在假定由每个 Hash 计算出需要设置的位（bit） 的位置是相互独立为前提计算出来的，不难看出，随着 m （位数组大小）的增加，假正例（False Positives）的概率会下降，同时随着插入元素个数 n 的增加，False Positives的概率又会上升，对于给定的m，n，如何选择Hash函数个数 k 由以下公式确定：

m / n * ln2 ≈ 0.7 * m / n

此时False Positives的概率为：2 ^ -k ≈ 0.6185 ^ (m / n)

而对于给定的False Positives概率 p，如何选择最优的位数组大小 m 呢，

m = -n * lnp / (ln2) ^ 2

上式表明，位数组的大小最好与插入元素的个数成线性关系，对于给定的 m，n，k，假正例概率最大为：(1 - e ^ (-k * (n + 0.5)/(m - 1))) ^ k

值得注意的是，k值并非越大越好。可以证明，当 k = ln(2) * m/n 时出错的概率是最小的。

操作

1.加入字符串

为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。

当我们往Bloom Filter中增加任意一个元素x时候，我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。即第i个哈希函数映射的位置hash_i(x)就会被置为1（1≤i≤k）。

注意：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个”1”处）。

2. 检查字符串是否在集合中

在判断y是否属于这个集合时，我们只需要对y使用k个哈希函数得到k个哈希值，如果所有hash_i(y)的位置都是1（1≤i≤k），即k个位置都被设置为1了，那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y₁就不是集合中的元素（因为y1有一处指向了“0”位）。y₂或者属于这个集合，或者刚好是一个false positive。

3. 删除字符串

通常，字符串加入了就被不能删除了，因为删除会影响到其他字符串，且无法判断删除字符串是否真在集合内。实在需要删除字符串的可以使用Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。

实现

C语言内，并没有定义Bitmap这个容器，所以需要自己实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 268435456

/*init bitmap*/
unsigned char * bitmap_init(int size){
	int bytes;
	unsigned char * p = NULL;
	if(size % 8 == 0) 
		bytes = size / 8;
	else 
		bytes = size / 8 + 1;
	p = (unsigned char *)malloc(bytes);
	if(NULL == p)
		return NULL;
	memset(p, 0, bytes);
	return p;
}

/*set flag on a certain index bit*/
int bitmap_set(unsigned char * bitmap, int index, int flag){
//index range should have been checked outside!
	int seg = index / 8;
	int off = index % 8;
	unsigned char p =  0x1<< off;
	if(flag == 1)
		bitmap[seg] |= p;
	else if(flag == 0)
		bitmap[seg] &= ~p;
	else
		return 0;
	return 1;
}

/*get flag on a certain index bit*/
int bitmap_get(unsigned char * bitmap, int index){
///check index range outside first!
	int seg = index / 8;
	int off = index % 8;
	unsigned char p = 0x1 << off; 	int tmp = bitmap[seg] & p; 	return tmp > 0 ? 1 :0;
}
/*free bitmap*/
void bitmap_free(unsigned char * bitmap){
	free(bitmap);
	*bitmap = NULL;
}

之后，通过位图的置位和取位即可完成Bloom Filter的插入和检测操作。Hash函数选取如下（实际上，可以通过一个函数生成k个独立的哈希函数，存在优化空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

unsigned int RSHash(char* str, unsigned int len)
{
   unsigned int b    = 378551;
   unsigned int a    = 63689;
   unsigned int hash = 0;
   unsigned int i    = 0;

   for (i = 0; i < len; str++, i++)
   {
      hash = hash * a + (*str);
      a = a * b;
   }

   return hash;
}
/* End Of RS Hash Function */

unsigned int JSHash(char* str, unsigned int len)
{
   unsigned int hash = 1315423911;
   unsigned int i    = 0;

   fo r(i = 0; i < len; str++, i++)
   {
      hash ^= ((hash << 5) + (*str) + (hash >> 2));
   }

   return hash;
}
/* End Of JS Hash Function */

unsigned int PJWHash(char* str, unsigned int len)
{
   const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
   const unsigned int ThreeQuarters     = (unsigned int)((BitsInUnsignedInt  * 3) / 4);
   const unsigned int OneEighth         = (unsigned int)(BitsInUnsignedInt / 8);
   const unsigned int HighBits          = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
   unsigned int hash = 0;
   unsigned int test = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = (hash << OneEighth) + (*str);
      if((test = hash & HighBits) != 0) {
         hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
      }
   }

   return hash;
}
/* End Of  P. J. Weinberger Hash Function */

unsigned int ELFHash(char* str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int x    = 0;
   unsigned int i    = 0;

   for (i = 0; i < len; str++, i++) {
      hash = (hash << 4) + (*str);
      if ((x = hash & 0xF0000000L) != 0) {
         hash ^= (x >> 24);
      }
      hash &= ~x;
   }

   return hash;
}
/* End Of ELF Hash Function */

unsigned int BKDRHash(char* str, unsigned int len)
{
   unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = (hash * seed) + (*str);
   }

   return hash;
}
/* End Of BKDR Hash Function */

unsigned int SDBMHash(char* str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++) {
      hash = (*str) + (hash << 6) + (hash << 16) - hash;
   }

   return hash;
}
/* End Of SDBM Hash Function */

unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash;
}
/* End Of DJB Hash Function */

unsigned int DEKHash(char* str, unsigned int len)
{
   unsigned int hash = len;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
   }
   return hash;
}
/* End Of DEK Hash Function */

unsigned int BPHash(char* str, unsigned int len)
{
   unsigned int hash = 0;
   unsigned int i    = 0;
   for(i = 0; i < len; str++, i++)
   {
      hash = hash << 7 ^ (*str);
   }

   return hash;
}
/* End Of BP Hash Function */

unsigned int FNVHash(char* str, unsigned int len)
{
   const unsigned int fnv_prime = 0x811C9DC5;
   unsigned int hash      = 0;
   unsigned int i         = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash *= fnv_prime;
      hash ^= (*str);
   }

   return hash;
}
/* End Of FNV Hash Function */

unsigned int APHash(char* str, unsigned int len)
{
   unsigned int hash = 0xAAAAAAAA;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash ^= ((i & 1) == 0)
         ? (  (hash <<  7) ^ (*str) * (hash >> 3))
         : (~((hash << 11) + ((*str) ^ (hash >> 5))));
   }

   return hash;
}
/* End Of AP Hash Function */

/*Hash string with 11 different hash function(flag = 0)
Or Search string in a maked bloom filter(flag = 1)
*/
int bloomfilter_insert(unsigned char * bitmap, char* emailstring, int flag){
	unsigned int index;

	index = RSHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = JSHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = PJWHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = ELFHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = BKDRHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = SDBMHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = DJBHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = DEKHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = BPHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = FNVHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	index = APHash(emailstring,strlen(emailstring)) % MAX;
	if(flag == 1){if(bitmap_get(bitmap,index) == 0) return 0;}
	else bitmap_set(bitmap,index,1);

	return 1;
}

测试部分略。

结语

实际操作中，Bloom Filter达到了和Trie一样的效果，且时间短，占用内存少。可见其效率。实际上，Bloom Filter已有诸多应用：

• Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。
• Squid 网页代理缓存服务器在 cache digests中使用了也布隆过滤器。
• Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
• SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
• Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

参考资料

1. 维基百科：布隆过滤器
2. 数学之美二十一：布隆过滤器（Bloom Filter）
3. 布隆过滤器(Bloom Filter)详解 - Haippy - 博客园
4. 海量数据处理算法—Bloom Filter
5. 那些优雅的数据结构(1) : BloomFilter——大规模数据处理利器
6. Bloom Filter算法详解及实例
7. bitmap应用及C语言实现
8. bitmap C语言实现
9. General Purpose Hash Function Algorithms