五分钟速读：什么是散列表（哈希表）？

前言

假设你们班级100个同学每个人的学号是由院系-年级-班级和编号组成，例如学号为01100168表示是1系，10级1班的68号。为了快速查找到68号的成绩信息，可以建立一张表，但是不能用学号作为下标，学号的数值实在太大。因此将学号除以1100100取余，即得到编号作为该表的下标，那么，要查找学号为01100168的成绩的时候，只要直接访问表下标为68的数据即可。这就能够在O（1）时间复杂度内完成成绩查找。

实际上这里就用到了散列的思想。本文重在介绍散列的思想以及散列需要考虑的问题。

散列表（哈希表）

理想散列表（哈希表）是一个包含关键字的具有固定大小的数组，它能够 以常数时间执行插入，删除和查找操作 。

• 每个关键字被映射到0到数组大小N-1范围，并且放到合适的位置，这个 映射规则就叫散列函数

• 理想情况下，两个不同的关键字映射到不同的单元，然而由于数组单元有限，关键字范围可能远超数组单元，因此就会出现两个关键字散列到同一个值得时候，这就是 散列冲突

实例演示

通过前面的描述，我们已经了解了一些基本概念，现在来看一个实例。
假设有一个大小为7的表，现在，要将13,18,19，50，20散列到表中。

• 选择散列函数，例如使用hash(x)=x%7作为散列函数

• 计算数据散列值，并放到合适的位置

计算13 % 7得到6，因此将13放到下标为6的位置：

计算18 % 7得到4，因此将18放到下标为4的位置：

计算19 % 7得到5，因此将19放到下标为5的位置：

计算50 % 7得到1，因此将50放到下标为1的位置：

计算20 % 7得到6，因此将20放到下标为6的位置，但是此时6的位置已经被占用了，因此就产生了 散列冲突 ，关于散列冲突的解决，我们后面再介绍。

将数据散列之后，如何从表中查找呢？例如，查找数值为50的数据位置，只需要计算50 % 7，得到下标1，访问下标1的位置即可。但是如果考虑散列冲突，就没有那么简单了。

通过这个实例，了解了以下几个概念：

• 散列函数，散列函数的选择非常重要

• 散列冲突，涉及散列表时，因尽量避免散列冲突，对于冲突也要有好的解决方案

• 快速从散列表中查找数据

冲突解决

解决散列冲突通常有以下几种方法：

• 拉链法

• 开放定址法

• 再散列

• …

拉链法

分离链接法的做法是将同一个值的关键字保存在同一个表中 。例如，对于前面：

如果再要插入元素20，则在下标为6的位置存储表头，而表的内容是13和20。

这种方法的特点是需要另外分配新的单元来存储散列到同一个位置的数据。

查找的时候，除了根据计算出来的散列值找到对应位置外，还需要在链表上进行搜索。而在 单链表上的查找速度是很慢 的。另外 散列函数如果设计得好，冲突的概率其实也会很小 。

开放定址法

而开放定址法的思想是， 如果冲突发生，就选择另外一个可用的位置 。

而开放定址法中也有常见的几种策略。

• 线性探测法

还是以前面的为例：

如果此时再要插入20，则20 % 7 = 6，但是6的位置已有元素，因此探测下一个位置（6+1）%7，在这里就是下标为0的位置。因此20的存储位置如下：