散列(哈希)表 及应用-python字典,布隆过滤器

450px-hash_table_5_0_1_1_1_1_1_ll-svg

散列表/哈希表

散列表Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名{\displaystyle x}x到首字母{\displaystyle F(x)}F(x)的一个函数关系),在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字“取首字母”是这个例子中散列函数的函数法则{\displaystyle F()}F()存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

 

基本概念

  • 若关键字为{\displaystyle k}k,则其值存放在{\displaystyle f(k)}f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系{\displaystyle f}f散列函数,按这个思想建立的表为散列表
  • 对不同的关键字可能得到同一散列地址,即{\displaystyle k_{1}\neq k_{2}}k_{1}\neq k_{2},而{\displaystyle f(k_{1})=f(k_{2})}f(k_{1})=f(k_{2}),这种现象称为冲突英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数{\displaystyle f(k)}f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

 

散列函数

散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快定位。

  1. 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即{\displaystyle hash(k)=k}hash(k)=k{\displaystyle hash(k)=a\cdot k+b}hash(k)=a\cdot k+b,其中{\displaystyle a\,b}a\,b为常数(这种散列函数叫做自身函数)
  2. 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
  3. 平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
  4. 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
  5. 随机数法
  6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即{\displaystyle hash(k)=k\,{\bmod {\,}}p}hash(k)=k\,{\bmod \,}p, {\displaystyle p\leq m}p\leq m。不仅可以对关键字直接取模,也可在折叠法平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

 

处理冲突

开放地(定)址法(open addressing):

将所有节点均存储在散列表中。

当冲突发生时,使用某种探测技术在散列表中形成一个探测序列,沿此序列逐个单元地查找,直到找到给的的关键字或者碰到一个开放的地址(即改地址单元为空)为止。

 Hi = (H(key)+di) mod m      i=1,2, …, k(k<=m-1)

其中:H(key)为HASH函数,m为散列表长;di为增量序列,可以有下列三种取法:

  • di=1,2,3, …, m-1 , 称为线性探测再散列
  • di=12, -12, 22, -22, …, +-k^2(k<=m/2), 称为二次探测再散列
  • 双重散列法—探测序列:hi = (h(key)+i * hl(key)) % m     0<=i<=m-1

 

拉链法

将互为同义词的节点链成一个单链表,只将链表的头指针存放在散列表数组中。

用拉链法处理碰撞时,散列表的每一个结点增加一个链接结点字段,用来连接同义词字表。

 

开放地址法和拉链法比较:

todo

 

插值法

处理原则:以现在的数据地址加上一个固定的差值,当数据地址超出数组大小时,让数据地址采用循环的方式处理,即新数据地址对数组大小取余数。

 

应用

 

python字典

Python内部大量使用dict这种结构(比如字符串对象的intese机制),效率要求很高,采用哈希表实现,最低能在O(1)时间内完成搜索。使用hash就必须解决冲突的问题,dict采用的是开放寻址法。

python字典中的一个key-value键值对元素称为entry(也叫做slots),对应到python内部时PyDictEntry,PyDictObject就是 PyDictEntry的集合。 PyDictEntry的定义是:

详见: http://foofish.net/python_dict_implements.html

 

布隆过滤器

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

 

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢,上述三种结构的检索时间复杂度分别为{\displaystyle O(n),O(\log n),O(n/k)}O(n),O(\log n),O(n/k)

布隆过滤器的原理是,当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

2011010219003441

优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数({\displaystyle O(k)}O(k))。另外,散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

布隆过滤器可以表示全集,其它任何数据结构都不能;

{\displaystyle k}k{\displaystyle m}m相同,使用同一组散列函数的两个布隆过滤器的交并差运算可以使用位操作进行。

 

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

在降低误算率方面,有不少工作,使得出现了很多布隆过滤器的变种。

 

References:

wikipedia

《数据结构与算法》

google图片

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注