# JudgeGirl 50054

## A Hash Table

實作一個hash table，給予 $N$ 個字串並存進hash table，再來給予 $Q$ 個字串queries，如果字串在table內，輸出他的hash，不然輸出`-1`

一個字串的hash是所有字的ascii值加起來，如果是數字的話直接加數值，然後mod $S$（hash table的大小），如一個大小100的table，`ABC123`就是 $((65+66+67)+(1+2+3)) % 100 = 4$

一個hash對應一個bucket，bucket中可以有多個字串

$$
\begin{align}
& 3≤S≤1000 \\
& 1≤N≤10000 \\
& 1≤Q≤20000 \\
& 1≤\text{string length}≤100
\end{align}
$$

## Keys

首先寫hash function

int hash(char word[128], int len) {
    int ret = 0;
    for (int i = 0; i < len; i++) {
        if (word[i] >= '0' && word[i] <= '9') ret += word[i] - '0';
        else ret += word[i];
    }
    return ret % S;
}

再來我們維護一個`table[1024]`來記錄各個bucket已有幾個字串，和table本身`bucket[1024][10000][128]`，接下來就是很簡單的搜尋

唯一要注意的是陣列要開大一點，因為 $N$ 最大會是10000

#include <stdio.h>
#include <string.h>

int table[1024] = {0};
char buckets[1024][10000][128];
int S, N, Q;

int hash(char word[128], int len) {
    int ret = 0;
    for (int i = 0; i < len; i++) {
        if (word[i] >= '0' && word[i] <= '9') ret += word[i] - '0';
        else ret += word[i];
    }
    return ret % S;
}

int main() {
    scanf("%d %d %d", &S, &N, &Q);

    int h;
    char word[128];
    for (int n = 0; n < N; n++) {
        scanf(" %s", word);
        h = hash(word, strlen(word));
        strcpy(buckets[h][table[h]++], word);
    }

    for (int q = 0; q < Q; q++) {
        scanf(" %s", word);
        h = hash(word, strlen(word));
        int found = 0;
        for (int i = 0; i < table[h]; i++) {
            if (strcmp(word, buckets[h][i]) == 0) {
                printf("%d\n", h);  
                found = 1;
                break;
            }
        }
        if (!found) printf("-1\n");
    }

    return 0;
}