哈希表

哈希表又称为散列表，是一种key-value表结构。由哈希函数和数组组成，它的原理是通过哈希函数将传入的key值计算出索引，最后从数组中通过索引快速获取数据。

哈希表结构图

一般情况下它的时间复杂度为O(1)，相比较于有序列表，它的时间复杂度为O(logn)。

哈希表与列表最大的区别在于哈希表需要通过哈希函数中的算法来将key值换算成列表的索引，并且同一个key只能指向与同一个索引，也就是说一旦某个key换算成了一个索引后任何其他key都无法换算成该索引。如果出现重复的索引就称之为哈希碰撞。

在常用的语言中，哈希表通常以字典（dict）的形式表现。

哈希函数

构造哈希函数有多种方式，比如直接寻址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法。

由于哈希函数有可能会出现不同的输入值会输出相同的输出值的情况，这种情况称为碰撞。
所以一个好的哈希算法需要具备以下几点：

• 抗碰撞性，尽量避免冲突。
• 抗篡改性，只要改动一个字节，其哈希值也会很大不同。
• 查找效率

碰撞处理

再好的哈希算法都有可能会有碰撞的可能，越好的算法碰撞几率越小，如x1!=x2,结果输出：f(x1)=f(x2)这种情况出现，所以我们必须得处理碰撞的情况。
常用的碰撞处理方式有以下几种：

• 线性探测（Linear probing） 如果有冲突就找下一个位置直到找到空位为止。线性探测是以x+1,x+2…x+n的方式进行查找
• 二次探测 二次探测是以x+1^2, x+2^2以这种方程进行查找
• 链表法 在每个索引出都指向一个链表，把碰撞的数据存储在链表中
• 双重散列 如果出现碰撞会用第二个散列函数重新计算以此类推

小结

• 哈希表的核心就是哈希函数，哈希函数写的好就是个好的哈希表
• 哈希表最怕的就是冲突，一旦遇到冲突最坏情况会造成时间复杂度为O(n)
• 哈希表的查找，插入和删除都很快
• 哈希表中有一个填装因子，如果该系数超过了一定量就需要对数组进行扩容了，系数调整的低也是一种避免冲突的方式，但是会牺牲空间
• 哈希表可用于缓存数据，Redis的数据格式就是哈希表
• 哈希表非常适合用于避免重复