AcWing 840. 模拟散列表-golang

拉链法

package main
import (
    "fmt"
    "bufio"
    "os"
    "strings"
    "strconv"
    )

var n int
var idx int
var value, ne, index []int

const N = 100003


func main(){
    fmt.Scanf("%d", &n)
    value, ne, index = make([]int, N), make([]int, N), make([]int, N)

    for i := N-1; i >= 0; i--{
        index[i] = -1
     }

    scanner := bufio.NewScanner(os.Stdin)

    for i := n; i > 0; i--{
        scanner.Scan()
        op := strings.Split(scanner.Text(), " ")
        if op[0] == "I"{
            x, _ := strconv.Atoi(op[1])
            insert(x)
            continue
        }

        if op[0] == "Q"{
            x, _ := strconv.Atoi(op[1])
            if exist(x){
                fmt.Println("Yes")
            }else{
                fmt.Println("No")
            }
        }
    }
}

func insert(x int){
    k := (x%N+N)%N
    value[idx] = x
    ne[idx] = index[k]
    index[k] = idx
    idx++
}

func exist(x int)bool{
    k := (x%N+N)%N
    for i := index[k]; i != -1; i = ne[i]{
        if value[i] == x{
            return true
        }
    }

    return false
}