一、什么是哈希值

哈希值是通过一个计算函数把难以比较的字符串或者其他类型的数据映射成一个整数，最常用的就是映射a～z的hash值，变成hash[(str(i)-‘a’]这个数是一个十进制数，这个十进制数把它映射到0-25，也就是数组下标。

但通常来说是映射成1-26，因为方便计算，这是最简单的哈希值，然后这个哈希值映射成下标，这在算法题里面经常会出现，或者说可以将一个数据看成一个P进制数，还是说上一个例子，如果是字符串对比的话，我们可以把这26个字母看成一个26进制的数，一般的话任意子串的哈希我们一般使用前缀和的方式，这里暂时不展开了。那么这个数怎么映射呢？就是把字符串出现的字母都取一遍然后去当成一个26进制算，这样得到的哈希值发生冲突的概率就比较低，因为转换为的数一定是一个少数值，比如要计算abc的值，那就是（123）26=1*26^2+2*26^1+3这个计算出来的数就是hash值。

现在下结论：hash值是通过一个f(hash)计算出一个整数，然后当查找一个数据或者字符串的时候就将计算出来的整数进行对比，只用看整数相不相等就可以，而不用去暴力O(n)(如果是要对比n个数那就是O(n^2)了，所以，hash值就是为查找算法，提供一个优异的O(1)复杂度的解决方案（哈希的开销主要是对函数进行计算）另外hash值在加密问题里也很重要，通过一种不可知的hash算法将hash值计算出来然后校验也是一种应用方式。

延伸阅读：

二、Hash 算法碰撞

稍微想一下就可以发现，既然输入数据长度不固定，而输出的哈希值却是固定长度的，这意味着哈希值是一个有限集合，而输入数据则可以是无穷多个，那么建立一对一关系明显是不现实的。所以“碰撞”是必然会发生的，所以一个成熟的哈希算法会有较好的抗冲突性，同时在实现哈希表的结构时也要考虑到哈希冲突的问题。

比如“666”经过 Hash 后是“fae0b27c451c728867a567e8c1bb4e53”，相同 Hash 算法得到的值是一样的。比如 WiFi 密码如果是 8 位纯数字的话，顶多就是 99999999 种可能性，破解这个密码需要做的就是提前生成好 0 到 1 亿数字的 Hash 值，然后做 1 亿次布尔运算（就是 Bool 值判断，0 或者 1），而现在普通 I5 四核 CPU 每秒能到达 200 亿次浮点数计算，做 1 亿次布尔运算也就是秒级别的时间就破解了。

上一篇

怎么推进项目?

下一篇

制作线路图哪款软件好用?