Foreword
记录2022 winter的CS106B Assignment7
Enumerations Warmup
熟悉一下枚举类型
Linear Probing Warmup
熟悉一下线性探测哈希
Implementing Linear Probing
实现LinearProbingHashTable.h
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
| #include "LinearProbingHashTable.h"
using namespace std;
LinearProbingHashTable::LinearProbingHashTable(HashFunction<string> hashFn) {
myHash = hashFn;
allocatedSize = hashFn.numSlots();
elems = new Slot[allocatedSize];
for (int i = 0; i < allocatedSize; ++i) {
elems[i].type = SlotType::EMPTY;
}
}
LinearProbingHashTable::~LinearProbingHashTable() {
delete[] elems;
}
int LinearProbingHashTable::size() const {
return logicalSize;
}
bool LinearProbingHashTable::isEmpty() const {
return logicalSize == 0;
}
bool LinearProbingHashTable::insert(const string& elem) {
int hash = myHash(elem) % allocatedSize;
while (true) {
if (logicalSize == allocatedSize) {
return false;
} else if (elems[hash].type == SlotType::EMPTY) {
elems[hash].value = elem;
elems[hash].type = SlotType::FILLED;
++logicalSize;
return true;
} else if (elems[hash].type == SlotType::FILLED) {
if (elems[hash].value == elem) {
return false;
}
} else if (elems[hash].type == SlotType::TOMBSTONE) {
if (!contains(elem)) {
elems[hash].value = elem;
elems[hash].type = SlotType::FILLED;
++logicalSize;
return true;
}
}
hash = (hash + 1) % allocatedSize;
}
}
bool LinearProbingHashTable::contains(const string& elem) const {
int hash = myHash(elem) % allocatedSize;
int T = logicalSize;
while (T) {
if (elems[hash].type == SlotType::FILLED && elems[hash].value == elem) {
return true;
} else if (elems[hash].type == SlotType::EMPTY) {
break;
} else if (elems[hash].type == SlotType::FILLED) {
--T;
}
hash = (hash + 1) % allocatedSize;
}
return false;
}
bool LinearProbingHashTable::remove(const string& elem) {
if (!contains(elem)) {
return false;
}
int hash = myHash(elem) % allocatedSize;
int T = logicalSize;
while (T) {
if (elems[hash].type == SlotType::EMPTY) {
return false;
} else if (elems[hash].type == SlotType::FILLED) {
if (elems[hash].value == elem) {
--logicalSize;
elems[hash].value.clear();
elems[hash].type = SlotType::TOMBSTONE;
return true;
}
--T;
}
hash = (hash + 1) % allocatedSize;
}
return false;
}
|
Robin Hood Warmup
熟悉一下Robin Hood哈希
主要思想是让每个key离它的home slot尽量近
Robin Hood Hashing
实现RobinHoodHashTable.h
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
| #include "RobinHoodHashTable.h"
using namespace std;
RobinHoodHashTable::RobinHoodHashTable(HashFunction<string> hashFn) {
myHash = hashFn;
allocatedSize = hashFn.numSlots();
elems = new Slot[allocatedSize];
for (int i = 0; i < allocatedSize; ++i) {
elems[i].distance = EMPTY_SLOT;
}
}
RobinHoodHashTable::~RobinHoodHashTable() {
delete[] elems;
}
int RobinHoodHashTable::size() const {
return logicalSize;
}
bool RobinHoodHashTable::isEmpty() const {
return logicalSize == 0;
}
bool RobinHoodHashTable::insert(const string& elem) {
if (contains(elem) || logicalSize == allocatedSize) {
return false;
}
int hash = myHash(elem) % allocatedSize;
int dis = 0;
while (true) {
if (elems[hash].distance == EMPTY_SLOT) {
++logicalSize;
elems[hash].value = elem;
elems[hash].distance = dis;
return true;
} else if (elems[hash].distance < dis) {
auto hostage = elems[hash].value;
elems[hash].value = elem;
elems[hash].distance = dis;
insert(hostage);
return true;
}
++dis;
hash = (hash + 1) % allocatedSize;
}
return false;
}
bool RobinHoodHashTable::contains(const string& elem) const {
if (logicalSize == 0) {
return false;
}
int hash = myHash(elem) % allocatedSize;
int dis = 0;
while (true) {
if (elems[hash].distance == EMPTY_SLOT) {
return false;
} else if (elems[hash].value == elem) {
return true;
} else if (elems[hash].distance < dis) {
return false;
}
++dis;
hash = (hash + 1) % allocatedSize;
}
}
bool RobinHoodHashTable::remove(const string& elem) {
if (!contains(elem) || logicalSize == 0) {
return false;
}
int hash = myHash(elem) % allocatedSize;
while (true) {
if (elems[hash].value == elem) {
elems[hash].distance = EMPTY_SLOT;
elems[hash].value.clear();
--logicalSize;
while (true) {
int nxt = (hash + 1) % allocatedSize;
if (elems[nxt].distance == EMPTY_SLOT || elems[nxt].distance == 0) {
elems[hash].distance = EMPTY_SLOT;
elems[hash].value.clear();
break;
}
elems[hash].value = elems[nxt].value;
elems[hash].distance = elems[nxt].distance - 1;
hash = nxt;
}
return true;
}
hash = (hash + 1) % allocatedSize;
}
return false;
}
|
效果
