哈希表与哈希算法

哈希表又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key ，则可以在 O1 时间内获取对应的值 value 。除哈希表外，数组和链表也可以实现查询功能,但效率都没有哈希表效率高。
我们可以用一个数组来简单实现哈希表，我们将数组中每个空位称为桶，每个桶可存储一个键值对。查询操作就是找到对应key的桶，并在桶中获取value。如何通过key获取对应的桶呢，这是通过哈希函数实现的，哈希函数计算过程分两步，第一步通过哈希算法计算得到哈希值，然后将哈希值对桶数量取模，从而获得该桶的数组索引。index = hash(key) % capacity，通过得到的index在哈希表中访问对应的桶，从而获得value。理论上存在多个输入对应同一个输出，这就是哈希冲突，我们可以通过扩容进行解决，但扩容需要将所有键值对从原哈希表迁移至新的哈希表非常耗时，所以要预留足够的容量，防止频繁扩容。扩容这种方式简单但效率低，我们可以采用改良哈希表结构，采用拉链法，将单一桶转换成一个链表，链表很长的时候查询效率很差，所以达到一定长度就转成树的结构提高效率。
在哈希表中，我们希望哈希算法具有确定性、高效率和均匀分布的特点。常见的哈希算法包括 MD5、SHA-1、SHA-2 和 SHA-3 等。MD5 常用于校验文件完整性，SHA-2 常用于安全应用与协议。
哈希表的底层实现是数组，链表，与二叉树，但为什么效率比他们高呢？那是因为它的空间效率变低了，相当于有一部分空间未使用，而且如果一个功能在相同的时间复杂度下使用数组或者链表实现，那么通常比哈希表更快，因为哈希函数计算需要时间。如果key是小范围的整数，一般直接采用数组。