哈希表:
作用: 将一个常用庞大的数据或数据结构映射为0~N
存储结构
开放寻址法
约定一个不在数据范围的数表示当前坑位没人
仅需开一个数组,经验将此数组长度开到题目数字范围的2-3倍
上厕所法找空的坑位
拉链法
原数 % N : N一般要取质数且要离2的整次幂最小 - 使冲突的可能性最小 - ((x % N) + N) % N (使负数模运算后为正)
开一堆槽,给每个槽拉拉链(单链表)
(删除:不真的删,而是给当前元素打标记)
字符串哈希方法
有很多字符串题都可用字符串哈希方法做,不一定要kmp
字符串前缀哈希
https://www.acwing.com/video/44/
如何定义某个前缀的哈希值:将字符串看为p进制的数, 再将此p进制数转为10进制数后%Q =》 将某个字符串映射为0~q-1
注意:
一般不要将某个数字映射为0(A AA AAAA),从1开始比较好
经验值p取131或13331, Q =2^64(cpp里直接用unassigned long long(溢出即%2^64),其他%大数) 则认为不存在冲突
作用: 可利用所有前缀哈希求出所有子串的哈希
comment: 由于h[r]与h[l-1]位数对不上,因此需要将l - 1串左移至最高位比较
(图中h[l]应为h[l-1])