存储结构

  1. 开放寻址法（又名“蹲坑法”）
  2. 拉链法

操作类型

  1. 添加
  2. 查找
  3. 删除（很少有，而且删除不是严格意义上的删除，只是打一个标记）

作用

将大的数据范围映射到小的值域

如何实现

  1. 哈希函数，一般用取模运算
  2. 冲突处理
    1. 拉链法
    2. 开放寻址法
      1. 线性探查法（即当前坑位被占，向后挪一位继续探测）
      2. 二次探查法（即当前坑位被占，向后挪 i*i 位，注意取模，i从0开始递增）

840. 模拟散列表

维护一个集合，支持如下几种操作：

  1. I x，插入一个数 x；
  2. Q x，询问数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N，表示操作数量。
接下来 N行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。
输出格式
对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
输入样例：

  1. 5
  2. I 1
  3. I 2
  4. I 3
  5. Q 2
  6. Q 5

输出样例：

  1. Yes
  2. No

拉链法

插入：用一个数组存储链表的头指针，根据元素的哈希值找到对应位置的链表，然后采用头插法插入即可。
查询：查询时也是一样的哈希操作，找到该元素对应的应该被存储的链表，遍历链表找该节点，存在返回true，不存在返回false
数组的长度与具体问题有关。一般来讲输入的规模与数组的长度差不多
这里数组长度取质数

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static final int N = 100003;
  6.     static ListNode[] list = new ListNode[N];
  7.     public static void main(String[] sss) throws IOException{
  8.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  9.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  11.         int n = Integer.parseInt(br.readLine());
  13.         while (n-- > 0) {
  14.             String[] str = br.readLine().split(" ");
  15.             int x = Integer.parseInt(str[1]);
  17.             if (str[0].equals("I")) insert(x);
  18.             else {
  19.                 if (query(x)) bw.write("Yes\n");
  20.                 else bw.write("No\n");
  21.             }
  22.         }
  24.         br.close();
  25.         bw.close();
  27.     }
  29.     static void insert(int x) {
  30.         //找到应该插入的链表
  31.         int k = ((x % N) + N) % N;
  32.         if (list[k] == null) {
  33.             list[k] = new ListNode(x);
  34.         }
  35.         else {
  36.             ListNode node = new ListNode(x, list[k].next);
  37.             list[k].next = node;
  38.         }
  39.     }
  41.     static boolean query(int x) {
  42.         int k = ((x % N) + N) % N;
  44.         ListNode cur = list[k];
  45.         while (cur != null) {
  46.             if (cur.val == x) return true;
  47.             cur = cur.next;
  48.         }
  49.         return false;
  50.     }
  51. }
  53. class ListNode {
  54.     int val;
  55.     ListNode next;
  57.     ListNode(int x) {
  58.         this.val = x;
  59.     }
  60.     ListNode(int x, ListNode next) {
  61.         this.val = x;
  62.         this.next  = next;
  63.     }
  64. }

蹲坑法

开辟一个输入规模两到三倍的数组存储输入元素，用一个输入中不存在的元素NONE作为空的记录
插入和查找用一个函数 find() 完成，find返回数组的下标
将元素哈希，找到对应坑位，如果该坑已经有元素，继续向后寻找直至找到一个空位置或者某个坑位的元素值与该元素相同，返回对应的数组下标
如果是插入：h[find(x)] = x
如果是查询：h[find(x)] == NONE，如果相等说明该元素不存在。

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     static final int N = 200003, NONE = 0x3f3f3f3f;
  6.     static int[] h = new int[N];
  7.     static {
  8.         //用NONE初始化h
  9.         Arrays.fill(h, NONE);
  10.     }
  11.     public static void main(String[] sss) throws IOException{
  12.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  15.         int n = Integer.parseInt(br.readLine());
  17.         while (n-- > 0) {
  18.             String[] str = br.readLine().split(" ");
  19.             int x = Integer.parseInt(str[1]);
  21.             if (str[0].equals("I")) h[find(x)] = x;
  22.             else {
  23.                 if (h[find(x)] == NONE) bw.write("No\n");
  24.                 else bw.write("Yes\n");
  25.             }
  27.         }
  29.         br.close();
  30.         bw.close();
  32.     }
  34.     //线性探查法
  35.     static int find(int x) {
  36.         int k = ((x % N) + N) % N;
  37.         for (int i = k; ; i++) {
  38.             if (i == N) i = 0;
  39.             if (h[i] == NONE || h[i] == x) return i;
  40.         }
  41.     }
  42. }

开放地址法解决冲突采用二次探测法的例题：
1564. 哈希