Hash魔法:哈希表的工作原理与常用操作

一种高效的数据结构
服务器君一共花费了336.053 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

哈希表(Hash Table)的应用近两年才在NOI中出现,作为一种高效的数据结构,它正在竞赛中发挥着越来越重要的作用。 

哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。 

哈希表又叫做散列表,分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构,本文中的“哈希表”仅指“闭散列”,关于其他方面读者可参阅其他书籍。

基础操作 

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素。也可以简单的理解为,按照关键字为每一 个元素“分类”,然后将这个元素存储在相应“类”所对应的地方。

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 

总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。 

函数构造:构造函数的常用方法(下面为了叙述简洁,设 h(k) 表示关键字为 k 的元素所对应的函数值): 

  • 除余法: 选择一个适当的正整数 p ,令 h(k ) = k mod p ,这里, p 如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的方法。 
  • 数字选择法: 如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的若干位,所组成的新的值作为关键字或者直接作为函数值。 

冲突处理:线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ,则当 h(k) 已经存储了元素的时候,依次探查 (h(k)+i) mod S , i=1,2,3…… ,直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发现空单元,这就是哈希表已经满了,发生了错误。当然这是可以通过扩大数组范围避免的)。 

支持运算:哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。 设插入的元素的关键字为 x ,A 为存储的数组。 初始化比较容易,例如 :

const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素  
p=9997; // 表的大小  
procedure makenull;  
var i:integer;  
begin  
for i:=0 to p-1 do  
A[i]:=empty;  
End;   

哈希函数值的运算根据函数的不同而变化,例如除余法的一个例子:

function h(x:longint):Integer;  
begin  
h:= x mod p;  
end;  

我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数 locate。

function locate(x:longint):integer;  
var orig,i:integer;  
begin  
orig:=h(x);  
i:=0;  
while (i < S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do  
inc(i);  
//当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元  
//素存储的单元,要么表已经满了  
locate:=(orig+i) mod S;  
end;   

插入元素:

procedure insert(x:longint);  
var posi:integer;  
begin  
posi:=locate(x); //定位函数的返回值  
if A[posi]=empty then A[posi]:=x  
else error; //error 即为发生了错误,当然这是可以避免的  
end;   

查找元素是否已经在表中:

procedure member(x:longint):boolean;  
var posi:integer;  
begin  
posi:=locate(x);  
if A[posi]=x then member:=true  
else member:=false;  
end;  

这些就是建立在哈希表上的常用基本运算。

当数据规模接近哈希表上界或者下界的时候,哈希表完全不能够体现高效的特点,甚至还不如一般算法。但是如果规模在中央,它高效的特点可以充分体现。试验表明当元素充满哈希表的 90% 的时候,效率就已经开始明显下降。这就给了我们提示:如果确定使用哈希表,应该尽量使数组开大,但对最太大的数组进行操作也比较费时间,需要找到一个平衡点。通常使它的容量至少是题目最大需求的 120% ,效果比较好(这个仅仅是经验,没有严格证明)。

应用举例

什么时候适合应用哈希表呢?如果发现解决这个问题时经常要询问:“某个元素是否在已知集合中?”,也就是需要高效的数据存储和查找,则使用哈希表是最好不过的了!那么,在应用哈希表的过程中,值得注意的是什么呢? 

哈希函数的设计很重要。一个不好的哈希函数,就是指造成很多冲突的情况,从前面的例子已经可以看出来,解决冲突会浪费掉大量时间,因此我们的目标就是尽力避免冲突。前面提到,在使用“除余法”的时候,h(k)=k mod p ,p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢?假设 p=1000 ,则哈希函数分类的标准实际上就变成了按照末三位数分类,这样最多1000类,冲突会很多。一般地说,如果 p 的约数越多,那么冲突的几率就越大。 

简单的证明:假设 p 是一个有较多约数的数,同时在数据中存在 q 满足 gcd(p,q)=d >1 ,即有 p=a*d , q=b*d, 则有 q mod p= q – p* [q div p] =q – p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0,b] 的正整数。也就是说, [b div a] 的值只有 b+1 种可能,而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样,虽然mod 运算之后的余数仍然在 [0,p-1] 内,但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出, p 的约数越多,发生这种余数分布不均匀的情况就越频繁,冲突的几率越高。而素数的约数是最少的,因此我们选用大素数。记住“素数是我们的得力助手”。 

另一方面,一味的追求低冲突率也不好。理论上,是可以设计出一个几乎完美,几乎没有冲突的函数的。然而,这样做显然不值得,因为这样的函数设计 很浪费时间而且编码一定很复杂,与其花费这么大的精力去设计函数,还不如用一个虽然冲突多一些但是编码简单的函数。因此,函数还需要易于编码,即易于实现。 

综上所述,设计一个好的哈希函数是很关键的。而“好”的标准,就是较低的冲突率和易于实现。 

另外,使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候,需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。 

这些只是一般原则,真正遇到试题的时候实际情况千变万化,需要具体问题具体分析才行。

延伸阅读

此文章所在专题列表如下:

  1. Hash魔法:哈希表的原理与实现
  2. Hash魔法:一致性 hash 算法
  3. Hash魔法:分布式哈希算法
  4. Hash魔法:哈希表的工作原理与常用操作

本文地址:http://www.nowamagic.net/librarys/veda/detail/1343,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1343

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《算法导论(原书第2版)》 科曼(Cormen T.H.) (作者), 等 (作者, 译者), 潘金贵 (译者)

《算法导论(原书第2版)》一书深入浅出,全面地介绍了计算机算法。对每一个算法的分析既易于理解又十分有趣,并保持了数学严谨性。本书的设计目标全面,适用于多种用途。涵盖的内容有:算法在计算中的作用,概率分析和随机算法的介绍。本书专门讨论了线性规划,介绍了动态规划的两个应用,随机化和线性规划技术的近似算法等,还有有关递归求解、快速排序中用到的划分方法与期望线性时间顺序统计算法,以及对贪心算法元素的讨论。本书还介绍了对强连通子图算法正确性的证明,对哈密顿回路和子集求和问题的NP完全性的证明等内容。全书提供了900多个练习题和思考题以及叙述较为详细的实例研究。

更多计算机宝库...