An implementation of hash table using double hashing algorithm.
More...
|
using | Entry = struct Entry |
|
|
int | notPresent |
|
std::vector< Entry > | table |
|
int | totalSize |
|
int | tomb = -1 |
|
int | size |
|
bool | rehashing |
|
An implementation of hash table using double hashing algorithm.
◆ add()
void double_hashing::add |
( |
int | key | ) |
|
Checks for load factor here
- Parameters
-
key | key value to add to the table |
185 {
186
187
189 table[index].key = key;
190
191 if (++size / static_cast<double>(totalSize) >= 0.5) {
193 }
194}
int doubleHash(int key, bool searching)
Performs double hashing to resolve collisions.
Definition double_hash_hash_table.cpp:71
void rehash()
Definition double_hash_hash_table.cpp:161
◆ addInfo()
void double_hashing::addInfo |
( |
int | key | ) |
|
Information about the adding process
- Parameters
-
key | key value to add to table |
212 {
214 display();
217 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
221 display();
222}
size_t hashFxn(int key)
Hash a key. Uses the STL library's std::hash() function.
Definition double_hash_hash_table.cpp:47
std::string add(const std::string &first, const std::string &second)
Adding two string.
Definition uint128_t.hpp:37
◆ display()
void double_hashing::display |
( |
| ) |
|
Displays the table
- Returns
- None
143 {
144 for (int i = 0; i < totalSize; i++) {
145 if (table[i].key == notPresent) {
147 } else if (table[i].key == tomb) {
149 } else {
153 }
154 }
156}
◆ doubleHash()
int double_hashing::doubleHash |
( |
int | key, |
|
|
bool | searching ) |
Performs double hashing to resolve collisions.
- Parameters
-
key | key value to apply double-hash on |
searching | true to check for conflicts |
- Returns
- Index of key when found
-
new hash if no conflicts present
71 {
72 int hash =
static_cast<int>(
hashFxn(key));
73 int i = 0;
75 do {
76 int index =
77 static_cast<int>(hash + (i *
otherHashFxn(key))) % totalSize;
78 entry = table[index];
79 if (searching) {
80 if (entry.
key == notPresent) {
81 return notPresent;
82 }
83 if (searchingProber(entry, key)) {
85 return index;
86 }
87 std::cout <<
"Found tombstone or equal hash, checking next"
89 i++;
90 } else {
92 if (!rehashing) {
94 }
95 return index;
96 }
97 if (!rehashing) {
98 std::cout <<
"Spot taken, looking at next (next index:"
99 << " "
101 totalSize
103 }
104 i++;
105 }
106 if (i == totalSize * 100) {
108 return notPresent;
109 }
110 }
while (entry.
key != notPresent);
111 return notPresent;
112}
void * hash(const std::string &message)
Converts the string to bytestring and calls the main algorithm.
Definition md5.cpp:287
size_t otherHashFxn(int key)
Used for second hash function.
Definition double_hash_hash_table.cpp:58
bool putProber(const Entry &entry, int key)
Definition double_hash_hash_table.cpp:120
Definition double_hash_hash_table.cpp:36
int key
key value
Definition double_hash_hash_table.cpp:38
◆ hashFxn()
size_t double_hashing::hashFxn |
( |
int | key | ) |
|
Hash a key. Uses the STL library's std::hash()
function.
- Parameters
-
- Returns
- hash value of the key
47 {
49 return hash(key);
50}
◆ otherHashFxn()
size_t double_hashing::otherHashFxn |
( |
int | key | ) |
|
Used for second hash function.
- Parameters
-
- Returns
- hash value of the key
58 {
60 return 1 + (7 - (hash(key) % 7));
61}
◆ putProber()
bool double_hashing::putProber |
( |
const Entry & | entry, |
|
|
int | key ) |
Finds empty spot in a vector
- Parameters
-
entry | vector to search in |
key | key to search for |
- Returns
true
if key is not present or is a toumb
-
false
is already occupied
120 {
121 if (entry.
key == notPresent || entry.
key == tomb) {
122 return true;
123 }
124 return false;
125}
◆ rehash()
void double_hashing::rehash |
( |
| ) |
|
Rehashes the table into a bigger table
- Returns
- None
161 {
162
163 rehashing = true;
164 int oldSize = totalSize;
166
168 totalSize *= 2;
169 for (int i = 0; i < oldSize; i++) {
170 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
171 size--;
172 add(oldTable[i].key);
173 }
174 }
175
176
177
178 rehashing = false;
180}
◆ removalInfo()
void double_hashing::removalInfo |
( |
int | key | ) |
|
Information about removal process
- Parameters
-
key | key value to remove from table |
227 {
229 display();
232 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
234 remove(key);
236 display();
237}
◆ remove()
void double_hashing::remove |
( |
int | key | ) |
|
Removes key. Leaves tombstone upon removal.
- Parameters
-
199 {
201 if (index == notPresent) {
203 }
204 table[index].key = tomb;
206 size--;
207}
◆ searchingProber()
bool double_hashing::searchingProber |
( |
const Entry & | entry, |
|
|
int | key ) |
Looks for a matching key
- Parameters
-
entry | vector to search in |
key | key value to search |
- Returns
true
if found
-
false
if not found
133 {
134 if (entry.
key == key) {
135 return true;
136 }
137 return false;
138}