GabWiki哈希
一般哈希
素数选取表：
| 下界 | 上界 | 素数 |
|---|---|---|
| 2^5 | 2^6 | 53 |
| 2^6 | 2^7 | 101 |
| 2^7 | 2^8 | 193 |
| 2^8 | 2^9 | 389 |
| 2^9 | 2^10 | 769 |
| 2^10 | 2^11 | 1531 |
| 2^11 | 2^12 | 3061 |
| 2^12 | 2^13 | 6113 |
| 2^13 | 2^14 | 12253 |
| 2^14 | 2^15 | 24379 |
| 2^15 | 2^16 | 48883 |
| 2^16 | 2^17 | 97787 |
| 2^17 | 2^18 | 195677 |
| 2^18 | 2^19 | 391627 |
| 2^19 | 2^20 | 783259 |
| 2^20 | 2^21 | 1566401 |
| 2^21 | 2^22 | 3133987 |
| 2^22 | 2^23 | 6269119 |
| 2^23 | 2^24 | 12538073 |
| 2^24 | 2^25 | 25082363 |
| 2^25 | 2^26 | 50170979 |
| 2^26 | 2^27 | 100353503 |
| 2^27 | 2^28 | 200730139 |
| 2^28 | 2^29 | 401498927 |
| 2^29 | 2^30 | 803081491 |
开放寻址法
C++
// 一般N取比数据范围大两倍的素数 INF取0x3f3f3f3f
int ht[N];
// 把ht中的值全部初始化为INF
memset(ht, 0x3f, sizeof(ht));
// 如果x在哈希表中就返回x的下标 否则返回x应该插入的位置
int find(int x) {
int y = (x % N + N) % N;
while (ht[y] != INF && ht[y] != x) {
if (++y == N) y = 0;
}
return y;
}// 一般N取比数据范围大两倍的素数 INF取0x3f3f3f3f
int ht[N];
// 把ht中的值全部初始化为INF
memset(ht, 0x3f, sizeof(ht));
// 如果x在哈希表中就返回x的下标 否则返回x应该插入的位置
int find(int x) {
int y = (x % N + N) % N;
while (ht[y] != INF && ht[y] != x) {
if (++y == N) y = 0;
}
return y;
}拉链法
拉链的方法与单链表向头节点前插入相同。
C++
// 一般N取两到三倍数据范围的素数
int ht[N], vals[N], nexts[N], idx;
// 初始化
void init() {
idx = 0;
memset(ht, -1, sizeof(ht));
}
// 向哈希表中插入一个数
void insert(int x) {
int y = (x % N + N) % N;
// 从单链表头插入
vals[idx] = x;
nexts[idx] = ht[y];
ht[y] = idx++;
}
// 在哈希表中查询某个数是否存在
bool find(int x) {
int y = (x % N + N) % N;
for (int i = ht[y]; i != -1; i = nexts[i]) {
if (vals[i] == x) return true;
}
return false;
}// 一般N取两到三倍数据范围的素数
int ht[N], vals[N], nexts[N], idx;
// 初始化
void init() {
idx = 0;
memset(ht, -1, sizeof(ht));
}
// 向哈希表中插入一个数
void insert(int x) {
int y = (x % N + N) % N;
// 从单链表头插入
vals[idx] = x;
nexts[idx] = ht[y];
ht[y] = idx++;
}
// 在哈希表中查询某个数是否存在
bool find(int x) {
int y = (x % N + N) % N;
for (int i = ht[y]; i != -1; i = nexts[i]) {
if (vals[i] == x) return true;
}
return false;
}字符串哈希
核心思想：将字符串看成P进制数，P的经验值是 unsigned long long （Java 用 long）存储，溢出的结果就是取模的结果，这样可以省去取模的代码和时间。
模板题：字符串哈希
C++
typedef unsigned long long ULL;
// h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
ULL h[N], p[N];
// 初始化
void init() {
// s是下标从0开始的字符串 n是其长度
p[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = h[i - 1] * P + str[i - 1];
p[i] = p[i - 1] * P;
}
}
// 计算子串 str[l...r] 的哈希值
ULL sub_hash(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}typedef unsigned long long ULL;
// h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
ULL h[N], p[N];
// 初始化
void init() {
// s是下标从0开始的字符串 n是其长度
p[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = h[i - 1] * P + str[i - 1];
p[i] = p[i - 1] * P;
}
}
// 计算子串 str[l...r] 的哈希值
ULL sub_hash(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}