哈希表
之前学的离散化是特殊的哈希,是要求保序的。这里要讲的是一般的哈希
- 比如我们要在一个10^9值域内插入和查找10^5个数
- 我们可以将每一个数映射到(0,10^5)的范围
-
这种映射关系就叫哈希函数
-
常用的哈希函数是直接取模,如x mod 10^5。注意:一般用一个质数
- 多个数映射到同一个数,即叫冲突。按照冲突的处理方式的不同,我们把哈希表分为开放寻址法和拉链法。
拉链法
- 开一个一位数组。每个元素是一个槽,当我们比如把11映射到3,就把11加到3拉出的链上,若另一个数也映射到3,则也把这个数加到这个3所拉出来的链表上。
开放寻址法
-
只开一个一位数组,不用开链表,但是数组的范围要比N大个2到3倍
-
和上厕所原理一样,如果通过哈希函数映射到k,那就从k开始从前往后找,如果第k个坑没人占就用,如果有人占就逐个往后找直到找到第一个空位。
- 添加方式就是如上所述
- 查找:找到k,然后从k开始找,在碰到第一个空位之前如果没找到x,就是没找到。否则就是找到
字符串哈希
-
当我们要快速判断两个字符串想不想等的时候,就可以用这个做法
-
把一个字符串看做一个p进制的数,如果字符串有10个字母,就把这个数看做10位,每位是字符的ASCII码
- 把p进制数转换成10进制数。最后把结果mod 一个Q
- 最后我们就可以实现把任何一个字符串映射到【0,Q-1】的一个数了
注意;
1. 不映射成数字0
2. 字符串哈希是假定不存在冲突的
3. 经验值:P = 131或13331。 Q = 2^64。这样基本上是不会冲突的
h[i]
代表前i个字符的哈希值
- 例如 str = “acwing”
- h[0] = 0
- h[1] = “a” 的哈希值
- h[2] = “ac” 的哈希值
- ……
- h[5] = “acwin” 的哈希值
h[R] - h[L-1]*p^R-L+1
代表第L个字符到第R个字符这个子串的哈希值