字符串_哈希
字符串哈希就是把不同的字符串映射成不同的整数
对于一个字符串s,他的哈希函数这样定义:
例如字符串abc,其哈希函数数值为
当两个字符串不同但是其哈希函数值一样的现象称为哈希碰撞,一般来说巧妙设置P和M的值,即让他们两个互质,通常可以避免哈希碰撞。P通常取质数131或13331,M通常取最大整数2的64次方,把哈希数值h定义为ULL,超过则自动溢出,等价于取模;
求一个字符串的哈希值相当于求前缀和;
求一个字符串的子串的哈希值相当于求区间值
字符串哈希就是把不同的字符串映射成不同的整数
对于一个字符串s,他的哈希函数这样定义:
例如字符串abc,其哈希函数数值为
当两个字符串不同但是其哈希函数值一样的现象称为哈希碰撞,一般来说巧妙设置P和M的值,即让他们两个互质,通常可以避免哈希碰撞。P通常取质数131或13331,M通常取最大整数2的64次方,把哈希数值h定义为ULL,超过则自动溢出,等价于取模;
求一个字符串的哈希值相当于求前缀和;
求一个字符串的子串的哈希值相当于求区间值
相关推荐