数据结构与算法散列表（HashTable）

　　你是否注意到
　　当我们在word中编辑英文单词
　　如果拼写错误则会出现红色浪线提示
　　那么这个功能是如何实现的呢？
　　带着这个疑问，我们开始今天的内容：散列表（Hash Table）
　　何为散列
　　散列表其实就是我们俗称的‘哈希表’或‘Hash表’，通常在面试中会作为集合类hashMap的延申问题出现。
　　散列表是一种由数组演变而来的一种数据结构，利用数组下标随机访问的特性实现快速访问。
　　我们通过例子来理解一下＂散列＂思想
　　假设某饭店现在有五桌客人点餐吃饭，我们通过数组来存放每桌客人的点餐信息，数组下标为桌号1~5，这样就实现了根据桌号获取点餐信息。
　　由于饭店生意好，现在饭店扩建为两层，每层五桌，于是桌号的记录规则就变成了两位数，第一位代表楼层，第二位代表桌号，如‘21’，即二楼一号桌。
　　这样一来就无法直接根据桌号对应数组下标来获取点餐信息了，我们需要做一个中间处理，将二位数的桌号转换为数组下标，然后获取信息：
　　整理一下上面的思路：像这种，将编号（键）通过中间处理（散列函数）转换为数组下标（散列值value），进而快速获取数组信息的思想即散列思想。
　　散列函数
　　散列函数通常只做一件事：将键（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; }
　　散列冲突
　　试想一下这样一种情况，这个饭店无限扩建至上百层，每层上百张餐桌，那么是否会出现key不同，但value相同的情况呢？
　　实际上在真实的应用情景中，这种情况几乎无法避免，叫做‘散列冲突’。
　　像目前流行的MD5、SHA等哈希算法也都无法避免散列冲突。
　　那么是否有办法解决散列冲突问题呢？
　　开放寻址
　　开放寻址的思路是：往散列表中插入数据时，如果某个key经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，直到找到空闲位置然后将其插入：
　　需要注意的是，如果到散列表底部依然没有空位，那么会从散列表顶部继续查找，直到找到空闲位置。
　　散列表的查询逻辑和上面的插入逻辑相同。
　　链表法
　　相比于开放寻址，链表法则更简单直接，数组的每一个元素对应条链表，所有散列值相同的元素都放入元素对应的链表中即可。
　　问题回顾
　　在了解了散列表的基本内容之后，我们可以回看一下开篇提到的word错词提示功能。
　　可以通过散列表来实现：将英文单词库存入散列表中，每次输入单词之后，查询该词是否存在于散列表中。如果不存在则提示拼写错误即可。