1 | const LinkedList = require("./LinkedList");
|
2 |
|
3 |
|
4 | const defaultHashTableSize = 32;
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 | class HashTable {
|
11 | constructor(hashTableSize = defaultHashTableSize) {
|
12 | this.buckets = Array(hashTableSize)
|
13 | .fill(null)
|
14 | .map(() => new LinkedList());
|
15 |
|
16 |
|
17 | this.keys = {};
|
18 | }
|
19 |
|
20 |
|
21 | hash(key) {
|
22 | const hash = Array.from(key).reduce((acc, cur) => {
|
23 | return acc + cur.charCodeAt(0);
|
24 | }, 0);
|
25 | return hash % this.buckets.length;
|
26 | }
|
27 |
|
28 | set(key, value) {
|
29 | const hash = this.hash(key);
|
30 | this.keys[key] = hash;
|
31 | const bucket = this.buckets[hash];
|
32 | const node = bucket.find({ callback: item => item.key === key });
|
33 | if (!node) {
|
34 | bucket.append({ key, value });
|
35 | } else {
|
36 | node.value.value = value;
|
37 | }
|
38 | }
|
39 |
|
40 | delete(key) {
|
41 | const hash = this.hash(key);
|
42 | delete this.keys[hash];
|
43 | const bucket = this.buckets[hash];
|
44 | const node = bucket.find({ callback: item => item.key === key });
|
45 | if (node) {
|
46 | return bucket.delete(node.value);
|
47 | }
|
48 | return null;
|
49 | }
|
50 |
|
51 | get(key) {
|
52 | const hash = this.hash(key);
|
53 | const bucket = this.buckets[hash];
|
54 | const node = bucket.find({ callback: item => item.key === key });
|
55 | return node ? node.value.value : undefined;
|
56 | }
|
57 |
|
58 | has(key) {
|
59 | return Object.hasOwnProperty.call(this.keys, key);
|
60 | }
|
61 |
|
62 | getKeys() {
|
63 | return Object.keys(this.keys);
|
64 | }
|
65 | }
|
66 |
|
67 | export default HashTable;
|