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

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

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

Go 代码 - 拉链法

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

const N = 100003

var (
    h  [N]int
    e  [N]int
    ne [N]int
    idx int
)

func main() {
//  file, _ := os.Open("./1.txt")
//  defer file.Close()
    new(os.Stdin)

    for i := 0; i < len(h); i++ {
        h[i] = -1 // 初始化为 -1
    }

    x := readLine()
    n, _ := strconv.Atoi(x[0]) // 操作数量
    for i := 0; i < n; i++ {
        x = readLine()
        switch x[0] {
        case "I": // 插入一个数 v
            v, _ := strconv.Atoi(x[1])
            insert(v)
        case "Q": // 询问数 v 是否在集合中出现过
            v, _ := strconv.Atoi(x[1])
            if find(v) {
                fmt.Println("Yes")
            } else {
                fmt.Println("No")
            }
        }
    }
}

// 插入把 x 插入到下标为 k 的位置上单链表
func insert(x int) {
    k := (x%N + N) % N // 再 +N、 莫N，目的是确保余数是正数，这就是哈希值
    e[idx] = x
    ne[idx] = h[k]
    h[k] = idx
    idx++
}

// 查询操作
func find(x int) bool {
    k := (x%N + N) % N                  // 再 +N、 莫N，目的是确保余数是正数，这就是哈希值
    for i := h[k]; i != -1; i = ne[i] { // h[k]存的是k位置上单链表第一个位置下标
        if e[i] == x { // 当前节点的值是多少，ne[i]就是下一个节点的下标
            return true
        }
    }
    return false
}

var scanner *bufio.Scanner

func new(reader io.Reader) {
    scanner = bufio.NewScanner(reader)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
}
func readLine() []string {
    scanner.Scan()
    return strings.Split(scanner.Text(), " ")
}

Go 代码 - 开放寻址法

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

const N = 200003
const null = 0x3f3f3f3f // 大于10^9的数

var (
    h   [N]int
    e   [N]int
    ne  [N]int
    idx int
)

func main() {
//  file, _ := os.Open("./1.txt")
//  defer file.Close()
    new(os.Stdin)

    for i := 0; i < len(h); i++ {
        h[i] = null // 初始化为 大于10^9的数，表示这个位置没有被占用
    }

    x := readLine()
    n, _ := strconv.Atoi(x[0]) // 操作数量
    for i := 0; i < n; i++ {
        x = readLine()
        v, _ := strconv.Atoi(x[1])
        k := find(v)
        switch x[0] {
        case "I": // 插入一个数 v
            h[k] = v
        case "Q": // 询问数 v 是否在集合中出现过
            if h[k] != null {
                fmt.Println("Yes")
            } else {
                fmt.Println("No")
            }
        }
    }
}

// 查询操作,存在就返回找到的位置，不存在就返回它应该存储的位置
func find(x int) int {
    k := (x%N + N) % N              // 再 +N、 莫N，目的是确保余数是正数，这就是哈希值
    for h[k] != null && h[k] != x { // 该位置k被占用，并且不等于查找的 x
        k++
        if k == N { // 看完最后有一个位置
            k = 0 // 循环看第一个位置
        }
    }
    return k // 如果 x 在 h 中，就返回 x 所在的位置，如果不在就返回应该存储的位置
}

var scanner *bufio.Scanner

func new(reader io.Reader) {
    scanner = bufio.NewScanner(reader)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))
}
func readLine() []string {
    scanner.Scan()
    return strings.Split(scanner.Text(), " ")
}