哈希表
概念详解
哈希表解决的问题：把范围很大（如 -10⁹ ~ 10⁹）的数映射到一个小范围的数组下标上，从而实现 O(1) 的插入与查找。
冲突不可避免： 值域远大于数组大小，不同数可能映射到同一个下标，这就是”哈希冲突”。处理冲突有两种经典方法：
- 拉链法： 每个下标挂一条单链表，映射到该下标的所有数都插在链上。查询时先算下标，再沿链查找。
- 开放寻址法： 只用一个数组；冲突时从目标位置开始向后探测（线性探测），直到找到空位插入或找到目标。数组一般要开到数据量的 2~3 倍以降低堆积。
存储结构
开放寻址法
拉链法
字符串哈希方式
哈希函数细节： 取模的 N 通常选质数且离 2 的幂远一点（如 100003），能让下标分布更均匀；Java 中负数取模为负，所以用 (x % N + N) % N 把下标修正到非负。
拉链法
模拟散列表
题目描述
维护一个集合，支持如下几种操作：
I x：插入一个数 x；Q x：询问数 x 是否在集合中出现过。现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。 接下来 N 行，每行包含一个操作指令，操作指令为
"I x"或"Q x"中的一种。输出格式
对于每个询问指令
"Q x"，输出一个询问结果，如果 x 在集合中出现过，则输出"Yes"，否则输出"No"。 每个结果占一行。数据范围
- 1 ≤ N ≤ 10⁵
- -10⁹ ≤ x ≤ 10⁹
import java.util.*;import java.io.*;public class Main{ static int N = 100003; static int[] h = new int[N],e = new int[N],ne = new int[N]; static int idx = 0; public static void insert(int x){ int k = (x % N + N) % N; e[idx] = x; ne[idx] = h[k]; h[k] = idx++; } public static boolean find(int x ){ int k = (x % N + N ) % N; for(int i= h[k] ; i!= -1 ;i = ne[i]){ if(e[i] == x){ return true; } } return false; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine().trim()); Arrays.fill(h,-1); while(n -- >0){ String[] parts = br.readLine().trim().split("\\s+"); int x = Integer.parseInt(parts[1]); if (parts[0].equals("I")) { insert(x); } else { // Q bw.write(find(x) ? "Yes\n" : "No\n"); } } bw.flush(); }
}代码解析： h[k] 是第 k 条链的头结点下标（初始 -1）；插入采用头插法，把新节点插到链头；查询沿链遍历比较。数组 e、ne 模拟链表节点，与邻接表实现完全同构。
java中的做法
import java.io.*;import java.util.*;
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine().trim()); Set<Integer> set = new HashSet<>(N << 1); // 初始容量给大点，防止 rehash
while (N-- > 0) { String[] parts = br.readLine().trim().split("\\s+"); int x = Integer.parseInt(parts[1]); if (parts[0].equals("I")) { set.add(x); } else { // Q bw.write(set.contains(x) ? "Yes\n" : "No\n"); } } bw.flush(); }}开放寻址法
思路： 只用一个数组 h（大小取数据量 2~3 倍，如 N = 200003），初始全部填一个”空标记” EMPTY。find(x) 返回”x 应该在的位置”：从哈希起点开始线性探测，遇到 EMPTY 说明 x 不存在（返回该空位供插入），遇到 x 说明已存在（返回其位置）。插入即 h[find(x)] = x，查询即判断 h[find(x)] != EMPTY。
import java.io.*;
public class Main { static final int N = 200003; // 大于 2*1e5 的质数，降低堆积 static int[] h; // 哈希数组 static final int EMPTY = 0x3f3f3f3f; // 空标记（x 范围含 0，用超大值） static int n;
static int find(int x) { // 返回 x 应在的位置或插入位置 int k = (x % N + N) % N; // 保证非负 while (h[k] != EMPTY && h[k] != x) { k++; if (k == N) k = 0; } return k; }
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); n = Integer.parseInt(br.readLine().trim()); h = new int[N]; java.util.Arrays.fill(h, EMPTY); while (n-- > 0) { String[] sp = br.readLine().trim().split("\\s+"); int x = Integer.parseInt(sp[1]); int k = find(x); if (sp[0].equals("I")) h[k] = x; else bw.write(h[k] != EMPTY ? "Yes\n" : "No\n"); } bw.flush(); }}字符串哈希【字符串前缀哈希法】
1.将字符串看做p进制数，有十个字母就看做十位
2.将p进制的数转换为十进制的数
例如：ABCD 可以看做 p进制的（1234）p = 1 * p ^ 3 + 2 * p ^ 2 + 3 * p ^ 1 + 4 * p ^ 0
3.因为计算之后的数字可能很大，所以要将结果吗mod Q 使得计算结果在0 到 Q - 1之间
通过以上的方式就可以把任意一个字符串映射到0到Q-1之间的一个数，这就是字符串哈希的方式
注意，不要把某个字符映射成0
假如 “A” - > 0 那么 “A” 的p进制数对应的十进制数也为0，这也就会导致”AA”的p进制数对应的十进制数也为0
即”A”和”AA”两个不同的字符串会被映射到相同的0的位置
==这里保证字符串哈希值不冲突的方式就是假定自己狗运比较好，不存在冲突，即不考虑冲突的情况==
==p一般取131或者13331，Q = 2 ^ 64 这时出现冲突的概率微乎其微。（来自大佬的经验）==
==这种求哈希的方式以及求前缀字符串哈希值的方式的好处就是可以计算出所有子串的哈希值==
==计算前缀字符串哈希值的公式h[i] = h[i - 1] * p + str[i]==
==计算L到R的子串的哈希值只需要将短串哈希值*p ^ (R - L + 1) 即将短串高位与长串高位对齐==
==最后相减即可,h[R] - h[L] * p ^ (R - L + 1)==
==字符串哈希常用于快速判断两个字符串是否相等==
==相比于kmp算法，字符串哈希在处理一些较难的字符串题目的时候，kmp算法需要考虑很多，而字符串哈希可以简单粗暴地解决，但并不是kmp能做的字符串哈希都能做，像求循环节的时候就只能使用kmp算法来做==
本来比较两个字符串是需要一个字母一个字母地比较而使用字符串哈希就可以在O(1)的时间复杂度内完成
Java 实现技巧： 经验值 Q = 2^64 在 Java 中无需显式取模——用 long 类型存储哈希值，乘法溢出时自动对 2^64 取模（无符号溢出的效果），既快又符合经验参数。
字符串哈希
给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l₁, r₁, l₂, r₂，请你判断 [l₁, r₁] 和 [l₂, r₂] 这两个区间所包含的字符串子串是否完全相同。 字符串中只包含大小写英文字母和数字。
输入格式： 第一行包含整数 n 和 m，表示字符串长度和询问次数。 第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。 接下来 m 行，每行包含四个整数 l₁, r₁, l₂, r₂，表示一次询问所涉及的两个区间。 注意，字符串的位置从 1 开始编号。
输出格式： 对于每个询问输出一个结果，如果两个子串完全相同则输出 “Yes”，否则输出 “No”。 每个结果占一行。
数据范围： 1 ≤ n, m ≤ 10⁵
import java.io.*;
public class Main { static final int BASE = 131; static final int MAXN = 100010; static long[] h = new long[MAXN], p = new long[MAXN]; static char[] s;
// 计算子串 [l..r] 的哈希值 static long get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] nm = br.readLine().trim().split("\\s+"); int n = Integer.parseInt(nm[0]); int m = Integer.parseInt(nm[1]);
s = (" " + br.readLine()).toCharArray(); // 下标从 1 开始 p[0] = 1; for (int i = 1; i <= n; i++) { p[i] = p[i - 1] * BASE; h[i] = h[i - 1] * BASE + s[i]; }
while (m-- > 0) { String[] q = br.readLine().trim().split("\\s+"); int l1 = Integer.parseInt(q[0]); int r1 = Integer.parseInt(q[1]); int l2 = Integer.parseInt(q[2]); int r2 = Integer.parseInt(q[3]);
bw.write(get(l1, r1) == get(l2, r2) ? "Yes\n" : "No\n"); } bw.flush(); }}抽屉原理
抽屉原理
抽屉原理（又称 鸽巢原理 / Dirichlet 原理）一句话：
==把 n+1 只鸽子 放进 n 个鸽巢，至少有一个巢里 ≥2 只鸽子。==
看似平凡，却是离散数学、组合数学、算法设计里最常用、最强大的**“存在性”**工具之一。
==最原始形式（基本引理）==
==定理 1（基本抽屉原理） 若 |A| > |B|，则对任意映射 f : A → B，必存在 a₁ ≠ a₂ ∈ A，使得 f(a₁) = f(a₂)。 换句话说：元素比容器多 → 至少一个容器装 ≥2 个元素。==
例
- 367 个人里至少 2 人同一天生日（闰年 366 天）。
- 任意 3 个整数里必有 2 个奇偶性相同（奇/偶只有 2 个“抽屉”）。
抽屉原理在算法中的典型应用： 证明”某条路径上必存在环”（如 SPFA 判负环中 cnt ≥ n 必重复经过某点）、证明哈希冲突一定存在、任何长度为 n+1 的序列中必有两个数的差是 n 的倍数等。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时