111qqz的小窝

老年咸鱼冲锋!

hash学习笔记

前言:

hash这种东西人人都会用的东西还有必要说?

起因是…本问了hash中的一个细节…然后…我知道怎么做… 结果描述的不够清楚?如果知道那个做法的名字也许就不用费劲描述了呢。。。所以来复习一下吧2333

hash函数_维基百科

 

说起来其实哈希只有两个东西比较重要吧。。。

一个是哈希函数的构造:

构造散列函数

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

  1. 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即{\displaystyle hash(k)=k}hash(k)=k{hash(k)=a\cdot k+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):{\displaystyle hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}hash_{i}=(hash(key)+d_{i})\,{\bmod  \,}m, {\displaystyle i=1,2…k\,(k\leq m-1)}i=1,2...k\,(k\leq m-1),其中{\displaystyle hash(key)}hash(key)为散列函数,{\displaystyle m}m为散列表长,{\displaystyle d_{i}}d_{i}为增量序列,{\displaystyle i}i为已发生冲突的次数。增量序列可有下列取法:
{\displaystyle d_{i}=1,2,3…(m-1)}d_{i}=1,2,3...(m-1)称为 线性探测(Linear Probing);即{\displaystyle d_{i}=i}d_{i}=i,或者为其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,把散列地址存放在该空单元。
{\displaystyle d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}…\pm k^{2}}d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} {\displaystyle (k\leq m/2)}(k\leq m/2)称为 平方探测(Quadratic Probing)。相对线性探测,相当于发生冲突时探测间隔{\displaystyle d_{i}=i^{2}}d_{i}=i^{2}个单元的位置是否为空,如果为空,将地址存放进去。
{\displaystyle d_{i}=}d_{i}=伪随机数序列,称为 伪随机探测

看起来蛮厉害。。其实我们熟悉的线性探测(当前位置冲突了顺序找下一个)和平方探测都是开放地址的一种。。。

但是这东西。。。不管怎么设计。。都存在爆炸的可能。。。术语叫【聚集】

聚集(Cluster,也翻译做“堆积”)的意思是,在函数地址的表中,散列函数的结果不均匀地占据表的单元,形成区块,造成线性探测产生一次聚集(primary clustering)和平方探测的二次聚集(secondary clustering),散列到区块中的任何关键字需要查找多次试选单元才能插入表中,解决冲突,造成时间浪费。对于开放定址法,聚集会造成性能的灾难性损失,是必须避免的。

于是有一下解决聚集的方法:

  • 单独链表法:将散列到同一个存储位置的所有元素保存在一个链表中。实现时,一种策略是散列表同一位置的所有冲突结果都是用存放的,新元素被插入到表的前端还是后端完全取决于怎样方便。
  • 再散列{\displaystyle hash_{i}=hash_{i}(key)}hash_{i}=hash_{i}(key), {\displaystyle i=1,2…k}i=1,2...k{\displaystyle hash_{i}}hash_{i}是一些散列函数。即在上次散列计算发生冲突时,利用该次冲突的散列函数地址产生新的散列函数地址,直到冲突不再发生。这种方法不易产生“聚集”(Cluster),但增加了计算时间。
  • 建立一个公共溢出区

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz