近似 O(1)的时间复杂度
哈希表一般算法中处理的问题
- 插入一个数
- 查找一个数
- 删除一个数
实现哈希表的两种做法
拉链法
首先选择拉链法来解决问题,拉链法用通俗的话来说,就是数组+单链表的实现
选择 hash 函数 将大整数 x 映射成为小整数的
1 |
|
开放寻址法
开放寻址法本质也是从前往后插入,比拉链法更简单的是它只需要开一个数组,操作和理解起来相对容易一点。开放寻址法从前往后找找到空的地方插入,如果已经有了就让当前这个位置的加一
1 |
|
字符串哈希
(字符串哈希) O(n)+O(m)
全称字符串前缀哈希法,把字符串变成一个 p 进制数字(哈希值),实现不同的字符串映射到不同的数字。
对形如 X1X2X3⋯Xn−1Xn
的字符串,采用字符的 ascii 码乘上 P 的次方来计算哈希值。
映射公式 (X1×Pn−1+X2×Pn−2+⋯+Xn−1×P1+Xn×P0)modQ
注意点:
- 任意字符不可以映射成 0,否则会出现不同的字符串都映射成 0 的情况,比如 A,AA,AAA 皆为 0
- 冲突问题:通过巧妙设置 P (131 或 13331) , Q (264)
的值,一般可以理解为不产生冲突。
问题是比较不同区间的子串是否相同,就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和,求一个字符串的子串哈希值就相当于求部分和。
前缀和公式 h[i+1]=h[i]×P+s[i]
i∈[0,n−1]
h 为前缀和数组,s 为字符串数组
区间和公式 h[l,r]=h[r]−h[l−1]×Pr−l+1
区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样,只差两位,
乘上 P2
把 ABC 变为 ABC00,再用 ABCDE - ABC00 得到 DE 的哈希值。
作者:chocolate-emperor
链接:https://www.acwing.com/solution/content/24738/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1 |
|