数据结构与算法：散列表（Hash Table）

你是否注意到

当我们在word中编辑英文单词

如果拼写错误则会出现红色浪线提示

那么这个功能是如何实现的呢？

带着这个疑问，我们开始今天的内容：散列表（Hash Table）

01

何为散列

散列表其实就是我们俗称的‘哈希表’或‘Hash表’，通常在面试中会作为集合类hashMap的延申问题出现。

散列表是一种由数组演变而来的一种数据结构，利用数组下标随机访问的特性实现快速访问。

我们通过例子来理解一下“散列”思想

假设某饭店现在有五桌客人点餐吃饭，我们通过数组来存放每桌客人的点餐信息，数组下标为桌号1~5，这样就实现了根据桌号获取点餐信息。

由于饭店生意好，现在饭店扩建为两层，每层五桌，于是桌号的记录规则就变成了两位数，第一位代表楼层，第二位代表桌号，如‘21’，即二楼一号桌。

这样一来就无法直接根据桌号对应数组下标来获取点餐信息了，我们需要做一个中间处理，将二位数的桌号转换为数组下标，然后获取信息：

整理一下上面的思路：像这种，将编号（键）通过中间处理（散列函数）转换为数组下标（散列值value），进而快速获取数组信息的思想即散列思想。

02

散列函数

散列函数通常只做一件事：将键（key）转换为散列值（value）,需要注意的是，这里的散列值是指数组下标，而并非数组所存储的数据。

我们来实现一下上文例子中的散列函数：

//两层，每层五桌，对应我们的数组下标可以是1~10
//那么‘21’应该对应下标为6
//得出散列函数算法：（第一位 - 1）* 5 + 第二位 
int hash(String key){
  String  first = num.substring(0,1);
  int firstafter = Integer.parseInt(first) - 1;
  int value = 5 * firstafter  +  num.substring(1);
  return value;
}

03

散列冲突

试想一下这样一种情况，这个饭店无限扩建至上百层，每层上百张餐桌，那么是否会出现key不同，但value相同的情况呢？

实际上在真实的应用情景中，这种情况几乎无法避免，叫做‘散列冲突’。

像目前流行的MD5、SHA等哈希算法也都无法避免散列冲突。

那么是否有办法解决散列冲突问题呢？

04

开放寻址

开放寻址的思路是：往散列表中插入数据时，如果某个key经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，直到找到空闲位置然后将其插入：

需要注意的是，如果到散列表底部依然没有空位，那么会从散列表顶部继续查找，直到找到空闲位置。

散列表的查询逻辑和上面的插入逻辑相同。

05

链表法

相比于开放寻址，链表法则更简单直接，数组的每一个元素对应条链表，所有散列值相同的元素都放入元素对应的链表中即可。

问题回顾

在了解了散列表的基本内容之后，我们可以回看一下开篇提到的word错词提示功能。

可以通过散列表来实现：将英文单词库存入散列表中，每次输入单词之后，查询该词是否存在于散列表中。如果不存在则提示拼写错误即可。