哈希算法是一种常见的时间复杂度为O(1)的算法，且不只存在于索引中，每个数据库应用中都存在该数据结构。

哈希表

哈希表（Hash Table）也称为散列表，由直接寻址表改进而来。

对于直接寻址表来说，关键字的全域为U，如果U比较小时，直接寻址技术就会显得简单而有效。
而当U很大，而计算机可用容量有限时，要在机器中存储大小为U的一张表T就有点不切实际，甚至是不可能的。
如果实际要存储的关键字集合K相对于全域U来说很小，那么分配给T的大部分空间都要浪费掉。

因此，哈希表出现了。在哈希方式下，元素处于h(k)中，h为哈希函数，h(k)的值是根据k值计算出的槽的位置。
函数h将关键字域U映射到哈希表T [0…m-1] 的槽位上。

哈希表虽然解决了直接寻址遇到的问题，但可能会发生哈希碰撞（collision），即两个关键字被映射到一个槽上。在数据库中一般采用最简单的碰撞解决技术，这种技术被称为链地址法。
在链地址法中，把散列到同一槽中的所有元素都放到一个链表中。而发生碰撞的槽存放一个指向链表头的指针，如果没有key被映射到槽中，则槽中的值为NULL。

最后要考虑的是哈希函数的均匀性，哈希函数h必须可以很好地进行散列，最好是能避免碰撞的发生。即使不能避免，也应该使碰撞的可能性尽可能地小。
一般来说，都将key转换成自然数，然后通过除法散列、乘法散列或者全域散列来实现。
数据库中一般采用除法散列的方法，比如h(k) = k mod m；

InnoDB存储引擎中的哈希算法

InnoDB使用哈希算法来对字典进行查找，其冲突机制采用链表方式，哈希函数采用除法散列方式。

对于缓冲池页的哈希表来说，在缓冲池中的Page页都有一个chain指针，它指向相同哈希函数值的页。

而对于除法散列，m（模）的取值为略大于2倍的缓冲池页数量的质数。
例如：当前参数innodb_buffer_pool_size的大小为10M，则共有640个16KB的页。对于缓冲池页内存的哈希表来说，需要分配640X2=1280个槽，但是由于1280不是质数，需要取比1280略大的一个质数，应该是1399，所以在启动时会分配1399个槽的哈希表，用来哈希查询所在缓冲池中的页。

那么InnoDB的缓冲池对于其中的页是怎么进行查找的呢？
其实简单，InnoDB的表空间都有一个space_id，用户所要查询的应该是某个表空间的某个连续16KB的页，即偏移量offset。
InnoDB存储引擎将space_id左移20位，然后加上这个space_id和offset，即关键字K=space_id<<20 + space_id + offset，然后通过除法散列到各个槽中。

自适应哈希索引

自适应哈希索引采用之前讨论到哈希表的方式实现。不同的是，这不仅是数据库自身创建并使用的，DBA本身并不能对其进行干预。
自适应哈希索引经哈希函数映射到一个哈希表中 ，因此对于字典类型的查找非常快速，如SELECT * FROM TABLE WHERE index_col=‘xxx’。
但是对于范围查找就无能为力了，通过SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况，如：

SHOW ENGINE INNODB STATUSG;

可以看到自适应哈希索引的使用信息，包括自适应哈希索引的大小、使用情况、每秒使用自适应哈希索引搜索的情况。
需要注意的是，哈希索引只能用来搜索等值的查询如：

SELECT * FROM table WHERE index_col='xxx';

而对于其他查找类型，如范围查找，是不能使用哈希索引的。因此会有non-hash searches/s的情况。通过hash searches:non-hash searches可以大概了解使用哈希索引后的效率。

由于自适应哈希索引是由InnoDB存储引擎自己控制的，因此这里的这些信息只供参考。不过可以通过参数innodb——adaptive_hash_index来禁用或启动此特性，默认为开启。