今天我们来介绍一个新的数据结构：散列表（Hash Table），平时也叫“哈希表”或“Hash表”。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

下面用个例子来介绍一下。

假如我们有89名选手参加学校运动会。为了方便记录成绩，每个选手都有一个参赛号码，依次是1到89。

其中，参赛选手的编号叫作键（key）或者关键字。把参赛编号转化为数组下标的映射方法叫作散列函数（或者“Hash函数”，“哈希函数”），而散列函数计算得到的值就叫作散列值（或“Hash值”，“哈希值”）

散列函数

散列函数

散列函数，顾名思意，它是一个函数。可以定义成hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。

该如何构造散列函数呢？有三个基本要求：

1. 散列函数计算得到的散列值是一个非负整数；
2. 如果key1 = key2，那hash(key1)==hash(key2)；
3. 如果key1 ≠ key2，那hash(key1) ≠ hash(key2)。

散列冲突

散列函数基本不可能做到不同的key对应的散列值都不一样，这种就叫作散列冲突。即便是MD5、SHA、CRC等哈希算法也无法避免。

常用的散列冲突解决方法有两类：开放寻址法（open addressing）和链表法（chaining）。

开放寻址法

开放寻址法的核心思想是，如果出现散列冲突，就重新找一个空间位置，将其插入。

开放寻址法

散列表跟数组一样，不仅支持插入、查找操作，还支持删除操作。对于使用线性探测法解决冲突的散列表，删除操作有些特别，要将删除的元素，标记为deleted。当线性探测查找的时候，遇到标记为deleted的空间，并不停下，而是继续往下探测。

开放寻址法

线性探测法存在很大问题，当散列表中插入的数据越来越多，散列冲突发生的可能性也越来越大，空闲位置越来越少，线性探测的时间也就越来越久。极端情况下，可能需要探测整个散列表，所以最坏情况的时间复杂度是O(n)。

对于开放寻址冲突解决方法，除了线性探测方法外，还有两种比较经典的探测方法：二次探测和双重散列。

为了尽可能保证散列表的操作效率，一般情况下会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）

链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，要更加简单。

在散列表中，每个“桶（bucket）”或“槽（slot）”对应一条链表，所有散列值相同的元素都放在相同的槽位对应的链表中。

链表法

插入：通过散列函数计算出对应的散列槽位，将其插入到对应的链表中。时间复杂度O(1)
查找、删除：同样通过散列函数找到对应的槽，然后遍历链表查找或者删除。时间复杂度跟链表的长度k成正比，也就是O(k)。

课后思考

1.假设我们有10万条URL访问日志，如何按照访问次数给URL排序？

• 遍历 10 万条数据，以 URL 为 key，访问次数为 value，存入散列表，同时记录下访问次数的最大值 K，时间复杂度 O(N)。
• 如果 K 不是很大，可以使用桶排序，时间复杂度 O(N)。
• 如果 K 非常大（比如大于 10 万），就使用快速排序，复杂度 O(NlogN)。

2.有两个字符串数组，每个数组大约有10万条字符串，如何快速找出两个数组中相同的字符串？

遍历两个字符串数组，以字符串为key，访问次数为value，存入散列表。然后遍历散列表找出value>1的字符串。