首页 > 其他分享 >哈希

哈希

时间:2024-04-16 17:37:24浏览次数:28  
标签:int res ll base 哈希 MOD

简介

哈希是一种能把字符串(实际上数组也行,不过本文都会以字符串为例)映射成一个数的算法,哈希就是把一个字符串转成一个 \(K\) 进制数,但由于得到的数可能会非常大,所以其中会用到取模,因此哈希也有些玄学(建议 CF 有赛后 hack 的比赛不要使用哈希,或提高哈希的安全度)。

普通哈希

可以将 a b c ... z 分别映射为 \(1,2,3,\dots,26\) (本文默认只包含小写英文字母,如果有其它字符再进行映射即可)。

注意不能将 a 映射为 \(0\),因为这样哈希就会认为 ab \(=\) b

单次时间复杂度 \(O(|S|)\)。

代码

const int base = 27, MOD = int(1e9) + 7;

int Hash(const string &s) {
  int res = 0;
  for(int i = 0; i < int(s.size()); ++i) {
    res = (1ll * res * base % MOD + s[i] - 'a' + 1) % MOD;
  }
  return res;
}

Hash(s);

前缀哈希

令 \(sum_i\) 表示前 \(i\) 个字符的哈希值,那么可以得到 \(sum_i=(sum_{i-1}\cdot base+mp_{s_i})\bmod m\),其中 \(base\) 指进制,\(mp_c\) 指字符 \(c\) 映射出的值,\(m\) 指模数。

我们还可以得到 \([l,r]\) 的哈希值是 \((sum_r - sum_{l-1}\cdot base^{r-l+1})\bmod m\)。

预处理时间复杂度 \(O(|S|)\),单次时间复杂度 \(O(1)\)(因为可以预处理出 \(base^k\) 的值)。

代码

const int base = 27, MOD = int(1e9) + 7;

int Calc(int l, int r) {
  return ((sum[r] - 1ll * sum[l - 1] * Pow[r - l + 1] % MOD) % MOD + MOD) % MOD;
}

s = ' ' + s, Pow[0] = 1;
for(int i = 1; i <= n; ++i) {
  sum[i] = (1ll * sum[i - 1] * base % MOD + s[i] - 'a' + 1) % MOD;
  Pow[i] = 1ll * Pow[i - 1] * base % MOD;
}

Calc(l, r)

哈希的安全性

因为哈希使用了取模,所以就有可能不同的字符串会被当做是相同的。这种情况被称为哈希冲突

生日悖论

生日悖论是说:你有 \(30\) 个朋友,一年有 \(365\) 天(不考虑闰年),那么有朋友的生日在同一天的概率是多少?

可以先算出每个朋友都不相同的概率,然后用 \(1\) 减,可以得到:

\(1-\frac{365}{365}\cdot \frac{364}{365}\cdot\frac{363}{365}\cdot\dots\cdot\frac{336}{365}=1-\frac{365!}{335!\cdot365^{30}}\approx 70\%\)。

这个故事告诉我们,哈希冲突的概率比你想得可能要大的多。

大质数

一种最简单的方法就是:让你的模数更大!(并且使用质数)

比如说你可以把模数设为:\(10^{18}+3,10^{18}+9,10^{18}+31\)(注意!\(10^{18}+7\) 不是质数!)。

或者把你的进制也改为质数,比如:\(131,133,13331,1145141\)。

大质数表

代码

using ll = long long;

const ll base = 1145141, MOD = (ll)(1e18) + 3;

多重哈希

还有一种方法,就是多用几个模数(进制也可以用多个),只有在所有结果下都相同我们才认为两个字符串相同,这样也可以大大提升哈希的安全性。

建议在使用双重哈希时可以使用孪生素数(差为 \(2\) 的一对质数,如:\(10^9 + 7,10^9+9\))。

代码

using ll = long long;

const ll base[2] = {131, 1145141}, MOD[2] = {(ll)(1e18) + 3, (ll)(1e18) + 9};

int Hash(const string &s, int op) {
  int res = 0;
  for(int i = 0; i < int(s.size()); ++i) {
    res = ((__int128)res * base[op] % MOD[op] + s[i] - 'a' + 1) % MOD[op];
  }
  return res;
}

Hash(s, 0), Hash(s, 1);

标签:int,res,ll,base,哈希,MOD
From: https://www.cnblogs.com/yaosicheng124/p/18138749

相关文章

  • MD5哈希长度延展攻击(选做)
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......
  • MD5哈希长度延展攻击(选做)
    MD5哈希长度延展攻击(选做)任务任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行......
  • MD5哈希长度延展攻击
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......
  • MD5哈希长度延展攻击(选做)
    一、理解长度扩展攻击(lengthextensionattack),是指针对某些允许包含额外信息的加密散列函数的攻击手段。对于满足以下条件的散列函数,都可以作为攻击对象:①加密前将待加密的明文按一定规则填充到固定长度(例如512或1024比特)的倍数;②按照该固定长度,将明文分块加密,并用前一个......
  • MD5哈希长度延展攻击
    1.哈希长度延展攻击的机制哈希长度延展攻击利用的是哈希函数如MD5和SHA-1的特性。当计算哈希时,如果攻击者知道原始数据的哈希值但不知道原始数据内容,他们仍然可以在原始数据后添加一些数据,并且能计算出新数据串的哈希值,而不需要知道原始数据是什么。对于MD5哈希函数,攻击者利用......
  • MD5哈希长度延展攻击
    任务详情任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文......
  • 代码随想录算法训练营第7天 | 哈希表 454.四数相加II 383. 赎金信 15. 三数之和 18.
    leetcode454.四数相加II题目454.四数相加II解题思路实现代码leetcode383.赎金信题目383.赎金信解题思路实现代码leetcode15.三数之和题目15.三数之和解题思路实现代码leetcode454.四数相加II题目18.四数之和解题思路实现代码......
  • 20211128李杰—— MD5哈希长度延展攻击
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......
  • 数据结构-哈希表
    数据结构-哈希表1.定义:哈希表(也称为散列表)是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。它通过将键映射到表中一个位置来访问记录,从而加快访问速度。#创建一个空字典hash_table={}#向哈希表中添加键-值对hash_table['apple']=10hash_table['banana'......
  • MD5哈希长度延展攻击
    1.哈希长度延展攻击的机制哈希长度延展攻击利用的是哈希函数如MD5和SHA-1的特性。当计算哈希时,如果攻击者知道原始数据的哈希值但不知道原始数据内容,他们仍然可以在原始数据后添加一些数据,并且能计算出新数据串的哈希值,而不需要知道原始数据是什么。对于MD5哈希函数,攻击者利用......