-
Notifications
You must be signed in to change notification settings - Fork 0
/
simple-hashtable.ts
83 lines (67 loc) · 1.88 KB
/
simple-hashtable.ts
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
export { Hashtable, Pair, _DEFAULT_INIT_SIZE, _DEFAULT_LOAD_FACTOR };
const _DEFAULT_INIT_SIZE = 64;
const _DEFAULT_LOAD_FACTOR = 8;
const _PRIME_MULTIPLIER = 314159;
interface Pair {
key: string;
value: any;
}
class Hashtable {
private size: number;
private count: number;
private bucket: Array<Array<Pair>>;
constructor(size: number = _DEFAULT_INIT_SIZE) {
this.size = size;
this.count = 0;
this.bucket = [];
}
insert(key: string, value: any): void {
let index = this.simpleHash(key);
if (this.bucket[index] === undefined)
this.bucket[index] = [];
this.bucket[index].push({ key: key, value: value });
this.count++;
if (this.count >= this.size * _DEFAULT_LOAD_FACTOR)
this.grow();
}
search(key: string): Pair {
let index = this.simpleHash(key);
if (this.bucket[index] !== undefined) {
for (const pair of this.bucket[index]) {
if (pair.key === key)
return pair;
}
}
return null;
}
delete(key: string): void {
let index = this.simpleHash(key);
this.bucket[index] = this.bucket[index].filter(pair => pair.key !== key);
}
private simpleHash(key: string): number {
let sum = 0;
let shift = 0;
[...key].forEach(ch => {
sum ^= ch.charCodeAt(0) << shift;
shift = (shift % 57) + 4;
});
sum += sum >> 33;
sum *= _PRIME_MULTIPLIER;
sum += sum >> 33;
return ((sum % this.size) + this.size) % this.size;
}
private grow(): void {
let auxTable = new Hashtable(this.size * _DEFAULT_LOAD_FACTOR);
console.log(this);
for (let index = 0; index < this.size; index++) {
if (this.bucket[index] !== undefined) {
for (const pair of this.bucket[index]) {
auxTable.insert(pair.key, pair.value);
}
}
}
this.size = auxTable.size;
this.count = auxTable.count;
this.bucket = auxTable.bucket;
}
}