顺序存储的结构类型有顺序表、栈、队列等，但他们都需要一个一个地按顺序对元素进行访问，如果要访问的总量很大时候，并且当我们要访问的这一元素位于末尾时，则查找效率就会很低。
散列表是一种空间换时间的存储结构，就是牺牲了存储空间来换取了查找数据的效率，但是如果需要的存储空间太大时，也会让我们感到头疼，所以我们往往需要在空间和时间两者当中进行权衡。
1、什么是散列表
如果在图书馆里要找一本书，那我们应该不会从第 1 本书一直找下去，因为这样实在是太慢了。回想一下我们到图书馆找书是怎么找的呢？首先是不是应该先找到你要找的这本书属于什么类别，例如科幻类、古典文学、武侠类等等，然后再在这一个类别当中进行查找。
还有我们平常学英语应该也要查字典，那么要查找一个单词的时候，我们肯定不会从头翻到尾，而是首先通过这个单词的首字母，找到对应的那一页；再找第 2 个字母、第 3 个字母……这样可以快速跳到那个单词所在的页。
其实这些就是运用了散列表的思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不需要经过比较，一次读取就能够得到所查元素。
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表，由散列函数所得的存储地址称做散列地址。
从上图中，我们也可以看出散列表不仅仅只是一种查找技术，同时也是一种存储技术。另外，从散列表的定义，我们也可以发现，散列方法是不适用于范围查找的，换言之，在散列表中，我们不可能找到最大或最小关键码的记录，也不可能找到在某一范围内的记录。
那么散列表的关键值都要不同，这时我们会发现出现一个严重的问题，如果对于两个不同的数据 ，我们计算到了同样的键值，那么就会出现冲突，此时该如何处理呢？
所以构造一个好的散列表，最重要的是做好以下两个步骤：
- 设计一个”好”的散列函数来计算Key值。(好的哈希函数应尽可能避免冲突的出现，而且计算时应尽可能简洁快速)
- 出现了冲突时又该如何调整插入元素。
2、散列函数设计方法
1、直接寻址法
散列函数是关键码的线性函数，即：
$H(key)=a\times key + b $ 式中，a 和 b 是常数
例如：关键码集合为{10,20,30,40,60,80,90}，选取一个散列函数为：$H(key)=\frac{1}{10}key$ ,则散列表为：
适用情况：事先知道关键码，关键码集合不是很大并且连续性较好。
2、除留余数法
假设散列表长度为 n，取一个不大于 n 但近似接近或等于 m 的质数 p，利用除留余数法的散列函数把关键字转换成散列地址。
散列函数为：
$ H(key)=key\quad mod\quad p $
例如，数据元素集合为a={78,7,99,13,25,53,59,30}，哈希表长度n取11时，并不会产生哈希冲突；当n取9时，就会产生哈希冲突。p的选取并不是固定的，需要自己进行判断，以此来选择最合适的p值。
通常情况下，哈希表的长度n习惯选取质数。对p的选择也十分重要，一般取素数或m，这样可以有效减少哈希冲突的发生。
在来看一个例子：现在有一组关键码，我们取p=21，则会得到以下信息：
适用情况：除留余数法是一种最简单、也是最常见的构造散列函数的方法，并且不需要事先知道关键码的分布。
3、数字分析法
如果关键字是位数较多的数字（比如手机号和学号），且这些数字部分存在相同规律，则可以采用抽取剩余不同规律部分作为散列地址。
如下图所示，有80个记录，每一行为一个记录中的键，假设表长为100，则可取两位十进制数组成哈希地址。
通过对上图进行观察可以得出，第1,2列对应的数字都是相同的，而第3列和第8列存在着大量重复的数字（分别是3和2,7），因此不能选择它们成为哈希地址。而中间4位可以看作是随机的，所以可以从中任选两位作为哈希地址。
再来看一个更直白的应用，现在有一组学生的学号为：
这组学号的前7位取值相对比较集中，剩下的后两位取值较均匀，可以直接使用学号的最后两位作为哈希地址，所以这十个关键字的哈希地址分别为：
10、21、71、85、13、37、22、33、3、14。
适用情况：能预先估计出关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。
4、平方取中法
对关键码平方后，按散列表大小，取中间若干位作为散列地址（平方后截取）。
它弥补了数字分析法的一些缺陷，因为我们有时并不能知道键的全部情况，取其中几位也不一定合适，而一个数平方后的中间几个数和原数的每一位都相关，由此我们就能得到随机性更强的哈希地址取的位数由表长决定。
适用情况：事先不知道关键码的分布并且关键码的位数不是很大。
5、折叠法
将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
例如：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。
适用情况：关键码很多，事先不知道关键码的分布。
3、解决冲突的方法
我们在前面已经说过了，我们在构建散列表时，一个经常会碰到的问题是：不同的关键值经过散列函数的映射后，得到了一个同样的散列地址，这种现象就叫做冲突。那我们该如何解决冲突呢，方法总共有两类：开放定址法和拉链法。
用开放定址法处理冲突得到的散列表叫闭散列表；用拉链法处理冲突构造出的散列表叫开散列表。
1、开放定址法
当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。
基本公式为：$H(key) = (key+di)\quad mod\quad TableSize$。注意，这里是一个递归序列，其中$d_i$为增量序列，TableSize为散列表长。
根据$d_i$的不同我们又可以分为线性探测，平方（二次）探测，随机探测。
1、线性探测法
以增量序列 1，2，……，（TableSize -1）进行循环试探下一个存储地址，即$d_i$ = i。
例：关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为$H(key)=key\quad mod\quad 11 $，用线性探测法处理冲突，则散列表为：
通过上图，我们会发现计算散列地址时，较多的元素计算出散列地址为7，图中出现了堆积（在处理冲突的过程中会出现非同义词之间对同一个散列地址争夺的现象，这种现象就称为堆积现象。）的现象，明明还有空间，却都往一个地方挤。堆积地方的冲突会越来越多。
2、平方探测法
以增量序列$1^2$，$-1^2$，$2^2$，$-2^2$，……，$q^2$，$-q^2$ 且$q$ ≤ $\frac{TableSize}{2}$进行循环试探下一个存储地址。
同上一个例子相同，关键码集合、散列表和散列函数均不做改变，用平方探测法处理冲突，则散列表为：
我们可以发现平方探测法是跳着寻找位置的，那么就会存在一个问题，假设散列表中还有空间，平方探测(二次探测)就一定能找得到？举个例子说明一下：
散列函数为$H(key)=key\quad mod\quad 5$，用平方探测来处理冲突。
我们假设下一个插入11，则H(11)=1，探测序列：1+1=2, 1-1=0, (1+$2^2$) mod 5=0, (1-$2^2$) mod 5=2，(1+$3^2$) mod 5=0, (1-$3^2$) mod 5=2, (1+$4^2$) mod 5=2,$\cdots\cdots$我们可以看到，存放11元素的地址在地址0与地址2之间往复横跳，虽然地址3和地址4位置是有空位，但是却找不到这个空间。解决方法：有定理显示，如果散列表长度TableSize是某个$\color{red}{4k+3}$（k是正整数)形式的$\color{red}{素数}$时，平方探测法就可以探查到整个散列表空间。
3、随机探测法
以增量序列是伪随机数来进行循环试探下一个存储地址。
计算机产生随机数的方法通常采用线性同余法，
其中，d称为随机种子。当b、c和m的值确定后，给定一个随机种子，产生确定的随机数序列。
2、拉链法（链地址法）
对于不同的关键字可能会通过散列函数映射到同一地址，为避免非同义词发生冲突，把所有散列地址相同的记录，即所有同义词记录存储在一个线性链表中（称为同义词子表），在散列表中存储的是所有同义词子表的头指针。最开始我们已经说过了，用拉链法处理冲突构造出的散列表叫做开散列表。开散列表是不会出现堆积现象的。设n个记录存储在长度为m的散列表中，则同义词子表的平均长度为$\frac{n}{m}$。
关键字序列为 {15,16,29,37,48,12,25,56,67,47,22,34}，应用拉链法处理冲突的散列表如下图所示：
当单链表无法满足查找需求时，或者说单链表过长导致查找效率过低时，我们可以将单链表改成平衡二叉树或者红黑树进行数据的存储和查找，如下图所示：
4、散列查找的性能分析
- 由于冲突的存在，产生冲突后的查找仍然是给定值与关键码进行比较的过程。
- 在查找过程中，关键码的比较次数取决于产生冲突的概率。影响冲突产生的因素有：
（1）散列函数是否均匀
（2）处理冲突的方法
（3）散列表的装载因子
$\alpha= \frac{表中填入的记录数}{散列表的长度} $ - 几种处理冲突方法的平均查找长度（ASL）
散列表的平均查找长度是$\color{red}{装填因子\alpha的函数}$，而不是查找集合中记录个数n的函数。在很多情况下，散列表的空间都比查找集合大，此时虽然浪费了一定的空间，但换来的是查找效率。
