JavaScriptAlgorithms/Other data structures/HashTable.html at master · biaodigit/JavaScriptAlgorithms · GitHub

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
    const capacity = [53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
        12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741];
    const upperTol = 10;
    const lowerTol = 2;
    let capacityIndex = 0;

    class HashTable {
        constructor() {
            this.hashTable = Array(M);
            this.M = capacity[capacityIndex];
            this.size = 0;
            for (let i = 0; i < M; i++) {
                this.hashTable[i] = new Map()
            }
        }

        add(key, value) {
            let map = this.hashTable[this.hash(key)];
            if (map.has(key)) {
                map.set(key, value)
            } else {
                map.set(key, value);
                this.size++;
            }

            if (this.size >= upperTol * this.M && capacityIndex + 1 < capacity.length) {
                capacityIndex++;
                this.resize(capacity[capacityIndex])
            }
        }

        search(key) {
            let map = this.hashTable[this.hash(key)];

            if(!map.has(key)) {
                throw new Error(`${key} is doesn't exist`)
            }

            return map.get(key)
        }

        remove(key) {
            let map = this.hashTable[this.hash(key)],
                ret = null;

            if (map.has(key)) {
                ret = map.delete(key);
                this.size--
            }

            if (this.size < lowerTol * this.M && capacityIndex - 1 >= 0) {
                capacityIndex--;
                this.resize(capacity[capacityIndex])
            }
            return ret
        }

        set(key, value) {
            let map = this.hashTable[this.hash(key)];
            if (!map.has(key)) {
                throw new Error(`${key} doesn't exist!`)
            }
            map.set(key, value)
        }

        //链地址法
        hash(key) {
            let str = null;
            switch (this._type(key)) {
                case 'string':
                    str = key;
                    break;
                case 'null':
                case 'undefined':
                case 'number':
                case 'boolean':
                    str = key + ''
            }

            return (this._hashCode(str) & 0x7fffffff) % this.M   //十六进制表示法，一个f表示四个1，共有28个1，一个7在2进制表示3个1，因此一共有31个1，结果是把hashCode(str)对应的整形对应的二进制最高位的1给抹去，对计算机而言是一个符号位，符号位为0表示负数，1为正数
        }

        contains(key) {
            return this.hashTable[this.hash(key)].has(key)
        }

        get(key) {
            return this.hashTable[this.hash(key)].get(key)
        }

        _type(key) {
            let str = Object.prototype.toString.call(key),
                type = str.slice(8, -1).toLowerCase();

            return type
        }

        resize(newM) {
            let newHashTable = Array(newM);
            for (let i = 0; i < newM; i++) {
                newHashTable[i] = new Map()
            }

            let oldM = this.M;
            this.M = newM;
            for (let i = 0; i < oldM; i++) {
                let map = this.hashTable[i];
                for (let key of map.keys()) {
                    newHashTable[this.hash[key]].set(key, map.get(key))
                }
            }

            this.hashTable = newHashTable
        }

        //辅助函数
        _hashCode(str) {
            let h = 0, off = 0;
            let len = str.length;
            for (let i = 0; i < len; i++) {
                h = 31 * h + str.charCodeAt(off++);
            }
            let t = -2147483648 * 2;
            while (h > 2147483647) {
                h += t
            }
            return h
        }
    }
</script>
</body>
</html>