Hash 哈希的神奇之处

Published: 23 Sep 2015 Category: algorithm

一、Hash散列为什么能提高检索速度?

众所周知, 有序数组存储数据,对数据的检索效率会很高,但是,插入和删除会有瓶颈产生。 链表存储数据,通常只能采用逐个比较的方法来检索数据(查找数据),但是,插入和删除的效率很高。

于是,将两者结合,取长补短,优势互补一下,就产生哈希散列这种存储方式。

具体是怎么样的呢? 我们可以理解成,在链表存储的基础上,对链表结构进行的一项改进。 我们将一个大的链表,拆散成几个或者几十个小的链表。 每个链表的表头,存放到一个数组里面。

采用Hash散列进行存储,主要就是为了提高检索速度。

二、HashCode

我们按照什么规则来将一个大链表中的数据,分散存放到不同的链表中呢?

在计算机当中,肯定是要将规则数量化的,也就是说,这个规则,一定要是个数字,这样才比较好操作。

比如,按照存放时间,每5分钟一个时间段,将相同时间段存放的数据,放到同一个链表里面;
或者,将数据排序,每5个数据形成一个链表; 等等,还有好多可以想象得到的方法。

但是,这些方法都会存在一些不足之处。

如果存放的数据,都是整数就好了。 这样,我可以创建一个固定大小的数组,比如50个大小,然后,让数据(整数)对50进行取余运算, 然后,这些数据,自然就会被分成50个链表了,每个链表可以是无序的,反正链表要逐个比较进行查询。

如果,我一个有200个数据,分组后,平均每组也就4个数据,那么,链表比较,平均也就比较4次就好了。

但是,实际上,我们存放的数据,通常都不是整数。

所以,我们需要将数据对象映射成整数的一个算法。

HashCode方法,应运而生了。

每个数据对象,都会对应一个HashCode值,通过HashCode我们可以将对象分组存放到不同的队列里。 这样,在检索的时候,就可以减少比较次数。

三、与Hashtable检索性能相关的因素

三方面的因素:HashCode方法、数组的大小 以及 数据对象的数量。

  1. 如果数组大小为1,那和链表存储没有什么区别了, 而且,还多了一步计算HashCode的时间,所以,数组不能太小,太小查询费时间。

  2. 如果我只存放1个数据对象,数组又非常大,那么,数组所占的内存空间,就比数据对象占的空间还大, 这样,少量数据对象,巨大的数组,虽然能够使检索速度,但是,浪费了很多内存空间。

  3. 如果所有对象的HashCode值都是相同的数, 那么,无论数组有多大,这些数据都会保存到同一个链表里面,

一个好的HashCode算法,可以使存放的数据,有较好的分散性, 在实际的实现当中,HashSet和HashMap都对数据对象产生的HashCode进行了二次散列处理, 使得数据对象具有更好的分散性。

四、Hash算法冲突解决方法分析(click me)

当关键字值域远大于哈希表的长度,而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外,当关键字的实际取值大于哈希表的长度时,而且表中已装满了记录,如果插入一个新记录,不仅发生冲突,而且还会发生溢出。因此,处理冲突和溢出是哈希技术中的两个重要问题。

1、开放定址法

用开放定址法解决冲突的做法是:当冲突发生时,使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探查到开放的 地址则表明表中无待查的关键字,即查找失败。

注意:
①用开放定址法建立散列表时,建表前须将表中所有单元(更严格地说,是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。

按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。

(1)线性探查法(Linear Probing)
该方法的基本思想是:
将散列表T[0..m-1]看成是一个循环向量,若初始探查的地址为d(即h(key)=d),则最长的探查序列为:

    d,d+l,d+2,…,m-1,0,1,…,d-1

即:探查时从地址d开始,首先探查T[d],然后依次探查T[d+1],…,直到T[m-1],此后又循环到T[0],T[1],…,直到探查到T[d-1]为止。

探查过程终止于三种情况:
(1)若当前探查的单元为空,则表示查找失败(若是插入则将key写入其中);
(2)若当前探查的单元中含有key,则查找成功,但对于插入意味着失败;
(3)若探查到T[d-1]时仍未发现空单元也未找到key,则无论是查找还是插入均意味着失败(此时表满)。

利用开放地址法的一般形式,线性探查法的探查序列为:

    hi=(h(key)+i)%m 0≤i≤m-1 //即di=i

用线性探测法处理冲突,思路清晰,算法简单,但存在下列缺点:
① 处理溢出需另编程序。一般可另外设立一个溢出表,专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表,查找方法可用顺序查找。

② 按上述算法建立起来的哈希表,删除工作非常困难。假如要从哈希表 HT 中删除一个记录,按理应将这个记录所在位置置为空,但我们不能这样做,而只能标上已被删除的标记,否则,将会影响以后的查找。

③ 线性探测法很容易产生堆聚现象。所谓堆聚现象,就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突,如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ,则当新的记录加入该表时,与这个序列发生冲突的可能性愈大。因此,哈希地址的较长连续序列比较短连续序列生长得快,这就意味着,一旦出现堆聚 ( 伴随着冲突 ) ,就将引起进一步的堆聚。

(2)线性补偿探测法

线性补偿探测法的基本思想是: 将线性探测的步长从 1 改为 Q ,即将上述算法中的 j = (j + 1) % m 改为: j = (j + Q) % m ,而且要求 Q 与 m 是互质的,以便能探测到哈希表中的所有单元。

【例】 PDP-11 小型计算机中的汇编程序所用的符合表,就采用此方法来解决冲突,所用表长 m = 1321 ,选用 Q = 25 。

(3)随机探测

随机探测的基本思想是: 将线性探测的步长从常数改为随机数,即令: j = (j + RN) % m ,其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列,将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序,从而可以避 免或减少堆聚。基于与线性探测法相同的理由,在线性补偿探测法和随机探测法中,删除一个记录后也要打上删除标记。

2、拉链法

(1)拉链法解决冲突的方法
 拉链法解决冲突的做法是:将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于 1,但一般均取α≤1。

【例】设有 m = 5 , H(K) = K mod 5 ,关键字值序例 5 , 21 , 17 , 9 , 15 , 36 , 41 , 24 ,按外链地址法所建立的哈希表如下图所示:
hash

(2)拉链法的优点
与开放定址法相比,拉链法有如下几个优点:
①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结 点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

(3)拉链法的缺点
 拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

ConcurrentHashMap的实现, 使用的是拉链法.

3.总结

与开放定址法相比,拉链法主要的优点有:

  • 1。拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
  • 2。由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况。
  • 3。节省空间;(但是指针需要额外空间)
  • 4。在用拉链法构造的散列表中,删除结点的操作易于实现。