哈希算法，蓝桥杯java备战中

哈希表的实现

核心思路

目标：实现一个基于开放寻址法（线性探测）的哈希表，支持插入元素 I x 和查询元素 Q x 两种操作。 核心逻辑：

1. 哈希函数：将元素映射到固定范围的索引（哈希值）。
2. 冲突解决：通过线性探测寻找可用槽位（插入）或目标槽位（查询）。
3. 状态管理：用数组标记槽位是否为空（-1 表示空）。

详细步骤

1. 哈希函数设计

• 哈希值计算：hash(x) = x % prime，其中 prime 是一个大质数（略小于哈希表容量）。
• 目的：将任意整数映射到 [0, prime-1] 范围内，作为初始插入/查询位置。

  static int hash(int x) {return x % prime; // 确保结果在 [0, prime-1] 之间
  }

  2. 插入元素（I x）

• 步骤：
  1. 计算哈希值 h = hash(x)。
  2. 线性探测：
     • 若 mp[h] == -1（空槽位），直接插入。
     • 若 mp[h] == x（已存在相同元素），无需插入。
     • 若 mp[h] 被其他元素占用，则 h++ 继续探测，直到找到可用位置。
  3. 越界处理：探测时对 h 取模，确保不越界。

• // 插入逻辑
  int x = in.nextInt();
  int pos = find(x);
  mp[pos] = x;

  3. 查询元素（Q x）

• 步骤：
  1. 计算哈希值 h = hash(x)。
  2. 线性探测：
     • 若 mp[h] == x，返回存在（Yes）。
     • 若 mp[h] == -1，返回不存在（No）。
     • 若 mp[h] 被其他元素占用，则 h++ 继续探测。// 查询逻辑 int x = in.nextInt(); int pos = find(x); if (mp[pos] == x) { System.out.println("Yes"); } else { System.out.println("No"); }

• // 查询逻辑
  int x = in.nextInt();
  int pos = find(x);
  if (mp[pos] == x) {System.out.println("Yes");
  } else {System.out.println("No");
  }

  4. find(x) 方法的核心逻辑

• 目标：找到元素 x 的可用槽位（插入）或目标槽位（查询）。
• 循环条件： while (mp[h] != -1 && mp[h] != x)
  • 必须同时满足：
    1. 槽位被占用（mp[h] != -1）。
    2. 槽位存储的不是目标元素（mp[h] != x）。

  • static int find(int x) {int h = hash(x);int initialH = h;while (mp[h] != -1 && mp[h] != x) {h = (h + 1) % prime; // 取模防止越界if (h == initialH) {return -1; // 哈希表已满}}return h;
    }

    若条件不满足：返回当前 h（要么是空槽位，要么是目标槽位）。

🌰 示例演示

假设 prime = 7，哈希表初始化为 [-1, -1, -1, -1, -1, -1, -1]：

操作	插入元素	哈希值	最终哈希表状态
I 5	5	5%7=5	[ -1, -1, -1, -1, -1, 5, -1 ]
I 12	12	12%7=5	冲突！探测到索引 6 → 插入
Q 12	查询 12	12%7=5	在索引 6 找到 → 返回 Yes

⚠️ 注意事项

1. 质数选择：哈希表容量应选大质数（如 prime = 100009），减少冲突概率。
2. 越界处理：线性探测时需对索引取模（h = (h + 1) % prime）。
3. 哈希表满处理：若遍历完所有槽位仍未找到位置，需抛出异常或扩容。
4. 不可变键：若键是对象，需确保插入后哈希值不变（避免修改字段）。

📝 完整代码

package Lanqiao;import java.util.Arrays;
import java.util.Scanner;public class L19870 {static int prime = 100009; // 大质数static int[] mp = new int[prime]; // 哈希表容量=primestatic Scanner in = new Scanner(System.in);public static void main(String[] args) {solve();in.close();}// 哈希函数static int hash(int x) {return x % prime;}// 寻找可用槽位或目标槽位static int find(int x) {int h = hash(x);int initialH = h;while (mp[h] != -1 && mp[h] != x) {h = (h + 1) % prime; // 防止越界if (h == initialH) {return -1; // 哈希表已满}}return h;}// 处理操作static void solve() {Arrays.fill(mp, -1); // 初始化空槽位int q = in.nextInt();while (q-- > 0) {String op = in.next();if (op.equals("I")) {int x = in.nextInt();int pos = find(x);if (pos != -1) mp[pos] = x;} else if (op.equals("Q")) {int x = in.nextInt();int pos = find(x);System.out.println(pos != -1 && mp[pos] == x ? "Yes" : "No");}}}
}