Hash,一般翻译做”散列”,也有直接音译为”哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

字符串算法之hash

我还是觉得hash好神奇。这到底是什么鬼东西啊喂!

首先推荐三篇入门博客,我觉得写的十分精妙~

hash入门

hash进阶:使用字符串hash乱搞的姿势

字符串hash入门

这三篇博客已经基本把hash的前世今生交代清楚了。我再补充一点自己对hash的浅薄认识好了。一千个读者心中有一千个hash。众所周知,hash就是乱搞。hash是一种加密解密规则,类似于破译密码的一个过程。

我们对于子字符串每位进行一波操作,并不断累加。其关键步骤就是

h[i]=h[i-1]*base+s[i]

由此我们可以得到每个字符串对应的值。但是,hash冲突的产生就是这个值可能不是一一对应的,一个值也许对应了多个字符串。

尽量避免hash冲突的关键就在于对base这个进制以及模数的选择上,base一般选择大于字符串中的最大的字符且不含模数的值因子的数。

比如说,如果你是对一串小写字母做字符串hash,那么131这个进制就是不错的选择。

而模数的选取方式一般分为三种:

  • 选择两个模数,判断的时候只有两个hash值都相同才算相同
  • 选择一个大质数,像11111111111111111111111或者212370440130137957
  • 用unsigned long long 自然溢出

那么区间hash值如何计算呢?

因为hash实质上是将字符串进行进制转换的过程,所以对于区间内的hash值就是整体值去左去右分别对应的转换好的进制值。用公式表达就是这样子:

ll get_hash(int l,int r)

{

  return h[r]-h[l-1]*p[r-l+1];

}

p[n]代表base的n次方。

最后更新: 2019年08月07日 09:27

原始链接: http://yisin.top/2019/08/05/字符串算法之hash/

× 请我吃糖~
打赏二维码