1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
interface MyHashMap {    contains(key: number): boolean;    put(key: number, value: number): void;
    get(key: number): number;
    remove(key: number): void;}function MyHashMap(): MyHashMap {    //由于我们使用整数除法作为哈希函数，为了尽可能避免冲突，应当将 \textit{base}base 取为一个质数。    const BASE = 1009;    type Value = Array<[number, number]>;    const storage: Record<number, Value> = Object.create(null);
    function getsub(key: number): Value {        const hash = key % BASE;        const sub = storage[hash];        if (sub) {            return sub;        } else {            const res: Value = [];            storage[hash] = res;            return res;        }    }    function put(key: number, value: number): void {        const sub = getsub(key);        const pair = sub.find((v) => v[0] === key);        if (pair) {            pair[1] = value;            return;        } else {            sub.push([key, value]);        }        // Reflect.set(sub, key, true)    }
    function remove(key: number): void {        const sub = getsub(key);        const index = sub.findIndex((v) => v[0] === key);        if (index >= 0) {            sub.splice(index, 1);        }        // Reflect.set(sub, key, false)    }
    function contains(key: number): boolean {        const sub = getsub(key);        return sub.findIndex((v) => v[0] === key) >= 0;        // return !!Reflect.get(sub, key,)    }    function get(key: number): number {        //  if(!contains(key)){return -1}        const sub = getsub(key);        const pair = sub.find((v) => v[0] === key);        if (pair) {            return pair[1];        }        return -1;    }    return { put, get, remove, contains };}export default MyHashMap;