hash学习笔记

Mar 11, 2017 · 1 min read · hash

前言：

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

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

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

一个是哈希函数的构造：

构造散列函数

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
  1. [直接定址法](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)：取关键字或关键字的某个线性函数值为散列地址。即{\displaystyle hash(k)=k}![hash(k)=k](https://wikimedia.org/api/rest_v1/media/math/render/svg/92632e59ab25c8f6d526ea9fb9cf4e014912afe3)
或{ $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选择不好，容易产生冲突。

还有一个就是冲突的处理。。。?

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：
  * [开放定址法](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)（open addressing）：{\displaystyle hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}![hash_{i}=(hash(key)+d_{i})\,{\bmod  \,}m](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9f569136022671abb3e623da1828b31313fd254)
, {\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)](https://wikimedia.org/api/rest_v1/media/math/render/svg/7164de5dc3e5febaa66956083e959797e265f91c)
称为 线性探测(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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7497c2c6b8cbd6bade1f943ef7aa5a67f9fdf01)
{\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}=](https://wikimedia.org/api/rest_v1/media/math/render/svg/6dd62dbd7677fd8bef541db800f8ae6d68659062)
伪随机数序列，称为 伪随机探测。

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

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

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

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

  * [单独链表法](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)：将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用[栈](https://zh.wikipedia.org/wiki/)存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。


  * [双散列](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)。


  * [再散列](https://zh.wikipedia.org/w/index.php?title=&action=edit&redlink=1)：{\displaystyle hash_{i}=hash_{i}(key)}![hash_{i}=hash_{i}(key)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f134a19206b07cf80819456a4e6cdbc8d0b21094)

, {\displaystyle i=1,2...k} $i=1,2...k$ 。{\displaystyle hash_{i}} $hash_{i}$ 是一些散列函数。即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生“聚集”（Cluster），但增加了计算时间。

  * 建立一个公共溢出区