散列表
散列表就是根据关键字不需比较便可直接取得所查记录在内存存储位置的数据结构。
一般来说对于一个关键字k，使用一个对应关系f(k)将其映射到表中一个位置，因此下次再拿关键字k来查询时，可以使用对应关系f(x)直接到指定位置去获取其存储值而无需进行比较。这个对应关系f(x)就是散列函数。
散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来重新创建一个叫做散列值的指纹。 对于散列函数有几个性质：
- 对于一个散列函数，如果散列值是不相同的，那么这散列值的原始输入也是不相同的
- 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为哈希碰撞。
- 散列函数是不可逆的，也就是说对于给定的散列值，没有实用的方法可以计算出一个原始输入
典型的散列函数都有非常大的定义域，比如SHA-2最高接受(2^64-1)/8长度的字节字符串。
先介绍一下填充因子的概念：
其定义为：a = 填入表中的元素个数 / 散列表的长度
a是散列表装满程度的标志因子。由于表长是定值，a与“填入表中的元素个数”成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，a越小，标明填入表中的元素越少，产生冲突的可能性就越小。(摘自wiki)
对不同的关键字可能得到同一散列地址现象称为冲突，也就是碰撞。把每个关键字映射到唯一的索引上的理想散列函数几乎是不存在的，我们需要对碰撞做处理，这里介绍两个常用的方法：
- 开放定址法，其中心思想就是如果根据散列函数f(x)得到的散列值发生碰撞，那么就在此值的基础上根据一定算法再计算得到一个新的位置，如果新的位置也碰撞就再根据上面的算法再计算知道找到可用的散列值为止。根据探测的策略不同有如下分类
- 线性探测法，就相当于逐个的探测表中地址，知道找到可用的地址，如果探测一遍都找不到可用地址则此次插入失败，这种做法实现简单但相对的容易产生数据的堆聚现象
- 平方探测法，将线性探测的步长改为冲突次数的平方数进行探测
- 随机探测法，将线性探测的步长改为随机数，这样能使不同的关键字具有不同的探测次序，从而可以减少堆聚现象
- 拉链法，其中心思想是将所有散列值相等的关键字值存到一个单链表中，然后散列表中结点存储一个指向该链表的指针。
Hash索引
Hash索引是基于Hash表（散列表）实现的，只有精确匹配索引的所有列的查询才是有效的。因为实现基于散列表，存储引擎会对每个索引值计算一个散列值，索引结构中最终存储其散列值以及指向数据行的指针。
我们知道Hash查找速度是很快的，但是也有其缺点：
- 不能利用覆盖索引，由于Hash索引只存储散列值和索引，而不存储字段的真实值，也就没有办法只通过检索索引结构就得到返回值，必须进行行读取操作才能拿到目标值。
- Hash索引也不支持部分索引列匹配查找，因为Hash索引是用全部索引列作为关键字来计算散列值的。单单只使用部分索引列的查询是无法通过散列函数计算出正确的目的值。
- Hash索引只支持等值比较，不支持任何范围查询
- Hash索引无法用于排序，因为Hash索引数据并不是有序的
- 在有很多Hash碰撞的情况下，一些索引维护操作的代价将会很高。
- 在有很多Hash碰撞的情况下，查询效率也会有所降低
以MySQL的Memory引擎为例，Memory引擎默认索引类型就是Hash索引，同时也是支持B-Tree索引的，它在处理碰撞的时候，使用的是拉链法，它会把散列值相同的索引以链表的形式挂在Hash表条目后。
** 我们回忆下链表的结构 **
链表是一种线性表，但不是按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。相对于顺序表而言，链表对于插入删除操作有着非常高的效率，其时间复杂度为O(1)的复杂度，缺点是查找操作需要O(n)的时间。顺序表的插入更新删除时间复杂度是O(logn)，但是每次插入更新删除操作都会涉及到大量元素的移动。
接着来看Memory引擎的Hash索引，它使用拉链法处理碰撞。当碰撞很多时，其后挂链表就会变得很长，而链表对于查找的时间复杂为O(n)，也就是说随着碰撞的增多，其查询效率会显著降低。
也有算法实现采用把后挂链表改为挂载一颗平衡二叉查找树来提高其查询效率，有兴趣的可以去看看具体思想和实现。