散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 哈希算法 - 图1 到首字母 哈希算法 - 图2 的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 哈希算法 - 图3 ，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

哈希算法通常有以下几个特点：

  • 正像快速：原始数据可以快速计算出哈希值
  • 逆向困难：通过哈希值基本不可能推导出原始数据
  • 输入敏感：原始数据只要有一点变动，得到的哈希值差别很大

  • 冲突避免：很难找到不同的原始数据得到相同的哈希值

    基本概念

  • 若关键字为 哈希算法 - 图4 ，则其值存放在{\displaystyle f(k)}的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 哈希算法 - 图5 为散列函数，按这个思想建立的表为散列表。

  • 对不同的关键字可能得到同一散列地址，即 哈希算法 - 图6 ，而 哈希算法 - 图7 ，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数 哈希算法 - 图8 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
  • 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

    构造散列函数

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

处理冲突

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：

  • 开放定址法（open addressing）： 哈希算法 - 图13, 哈希算法 - 图14，其中 哈希算法 - 图15为散列函数， 哈希算法 - 图16 为散列表长， 哈希算法 - 图17 为增量序列，哈希算法 - 图18 为已发生冲突的次数。增量序列可有下列取法：

哈希算法 - 图19称为 线性探测(Linear Probing)；即 哈希算法 - 图20 ，或者为其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。哈希算法 - 图21 哈希算法 - 图22称为 平方探测(Quadratic Probing)。相对线性探测，相当于发生冲突时探测间隔 哈希算法 - 图23 个单元的位置是否为空，如果为空，将地址存放进去。哈希算法 - 图24伪随机数序列，称为 伪随机探测。
显示线性探测填装一个散列表的过程：
关键字为 {89,18,49,58,69} 插入到一个散列表中的情况。此时线性探测的方法是取 哈希算法 - 图25 。并假定取关键字除以10的余数为散列函数法则。

散列地址 空表 插入89 插入18 插入49 插入58 插入69
0 49 49 49
1 58 58
2 69
3
4
5
6
7
8 18 18 18 18
9 89 89 89 89 89

第一次冲突发生在填装49的时候。地址为9的单元已经填装了89这个关键字，所以取 哈希算法 - 图26 ，往下查找一个单位，发现为空，所以将49填装在地址为0的空单元。第二次冲突则发生在58上，取 哈希算法 - 图27 ，往下查找3个单位，将58填装在地址为1的空单元。69同理。
表的大小选取至关重要，此处选取10作为大小，发生冲突的几率就比选择质数11作为大小的可能性大。越是质数，mod取余就越可能均匀分布在表的各处。
聚集（Cluster，也翻译做“堆积”）的意思是，在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

  • 单独链表法：将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
  • 双散列。
  • 再散列：哈希算法 - 图28, 哈希算法 - 图29 。哈希算法 - 图30 是一些散列函数。即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生“聚集”（Cluster），但增加了计算时间。
  • 建立一个公共溢出区

哈希算法主要用来保障数据真实性(即完整性)，即发信人将原始消息和哈希值一起发送，收信人通过相同的哈希函数来校验原始数据是否真实。

注：以上不能保证数据被恶意篡改，原始数据和哈希值都可能被恶意篡改，要保证不被篡改，可以使用RSA公钥私钥方案，再配合哈希值。 哈希算法主要用来防止计算机传输过程中的错误，早期计算机通过前7位数据第8位奇偶校验码来保障（12.5%的浪费效率低），对于一段数据或文件，通过哈希算法生成128bit或者256bit的哈希值，如果校验有问题要求重传。 哈希算法主要有MD4、MD5、SHA。

查找性能

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

  1. 散列函数是否均匀；
  2. 处理冲突的方法；
  3. 散列表的装填因子。

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度。α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

了解了hash基本定义，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢？这里简单说一下：
（1）MD4
MD4(RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现—它是基于 32 位操作数的位操作来实现的。
（2） MD5
MD5(RFC 1321）是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好
（3） SHA-1 及其他
SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举（brute-force）性更好。SHA-1 设计时基于和MD4相同原理，并且模仿了该算法。
那么这些Hash算法到底有什么用呢?

Hash算法在信息安全方面的应用主要体现在以下的3个方面：
（1）文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。
MD5 Hash算法的”数字指纹”特性，使它成为目前应用最广泛的一种文件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。
（2）数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称”数字摘要”进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
（3） 鉴权协议
如下的鉴权协议又被称作挑战—认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。
MD5、SHA1的破解

2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。2005年2月宣布破解SHA-1密码。

几种哈希算法的安全性对比：

  • MD4 1990年 输出128位 （已经不安全）
  • MD5 1991年 输出128位 （已经不安全）
  • SHA-0 1993年 输出160位 （发布之后很快就被NSA撤回，是SHA-1的前身）
  • SHA-1 1995年 输出160位 （已经不安全）
  • SHA-2包括SHA-224、SHA-256、SHA-384，和 SHA-512，分别输出224、256、384、512位。 (目前安全)

2的128次方为340282366920938463463374607431768211456，也就是10的39次方级别
2的160次方为1.4615016373309029182036848327163e+48，也就是10的48次方级别
2的256次方为1.1579208923731619542357098500869 × 10的77次方，也就是10的77次方
宇宙中原子数大约在10的60次方到80次方之间，所以2的256次方有足够的空间容纳所有的可能，算法好的情况下冲突碰撞的概率很低。

拓展工具