-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
hash-table.spice
62 lines (54 loc) · 1.63 KB
/
hash-table.spice
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
import "std/data/vector";
import "std/data/linked-list";
import "std/data/optional";
import "std/math/hash";
// Generic types for key and value
type K dyn;
type V dyn;
type HashEntry<K, V> struct {
K key
V value
}
public type HashTable<K, V> struct {
Vector<LinkedList<HashEntry<K, V>>> table
}
public p HashTable.ctor(unsigned long bucketCount = 100l) {
this.table = Vector<LinkedList<HashEntry<K, V>>>(bucketCount);
for unsigned long i = 0l; i < bucketCount; i++ {
this.table.pushBack(LinkedList<HashEntry<K, V>>());
}
}
public p HashTable.upsert(const K& key, const V& value) {
const unsigned long index = this.hash(key);
const LinkedList<HashEntry<K, V>>& list = this.table.get(index);
foreach const HashEntry<K, V>& entry : list {
if (entry.key == key) {
entry.value = value;
return;
}
}
}
public f<Optional<V>> HashTable.get(const K& key) {
const unsigned long index = this.hash(key);
const LinkedList<HashEntry<K, V>>& list = this.table.get(index);
foreach const HashEntry<K, V>& entry : list {
if (entry.key == key) {
return Optional<V>(entry.value);
}
}
return Optional<V>();
}
public p HashTable.remove(const K& key) {
const unsigned long index = this.hash(key);
LinkedList<HashEntry<K, V>>& list = this.table.get(index);
for (unsigned long i = 0l; i < list.getSize(); i++) {
if (list.get(i).key == key) {
list.remove(i);
return;
}
}
}
inline f<unsigned long> HashTable.hash(const K& key) {
K keyCopy = key;
return hash(keyCopy) % this.table.getSize();
}