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 |
189 table[index].key = key;
191 if (++size /
static_cast<double>(totalSize) >= 0.5) {
◆ addInfo()
void double_hashing::addInfo |
( |
int |
key | ) |
|
Information about the adding process
- Parameters
-
key | key value to add to table |
217 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
◆ display()
void double_hashing::display |
( |
| ) |
|
Displays the table
- Returns
- None
144 for (
int i = 0; i < totalSize; i++) {
145 if (table[i].key == notPresent) {
147 }
else if (table[i].key == tomb) {
◆ 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
72 int hash =
static_cast<int>(
hashFxn(key));
77 static_cast<int>(hash + (i *
otherHashFxn(key))) % totalSize;
80 if (entry.
key == notPresent) {
87 std::cout <<
"Found tombstone or equal hash, checking next"
98 std::cout <<
"Spot taken, looking at next (next index:"
106 if (i == totalSize * 100) {
110 }
while (entry.
key != notPresent);
◆ 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
◆ otherHashFxn()
size_t double_hashing::otherHashFxn |
( |
int |
key | ) |
|
Used for second hash function.
- Parameters
-
- Returns
- hash value of the key
60 return 1 + (7 - (hash(key) % 7));
◆ 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
121 if (entry.
key == notPresent || entry.
key == tomb) {
◆ rehash()
void double_hashing::rehash |
( |
| ) |
|
Rehashes the table into a bigger table
- Returns
- None
164 int oldSize = totalSize;
169 for (
int i = 0; i < oldSize; i++) {
170 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
172 add(oldTable[i].key);
◆ removalInfo()
void double_hashing::removalInfo |
( |
int |
key | ) |
|
Information about removal process
- Parameters
-
key | key value to remove from table |
232 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
◆ remove()
void double_hashing::remove |
( |
int |
key | ) |
|
Removes key. Leaves tombstone upon removal.
- Parameters
-
201 if (index == notPresent) {
204 table[index].key = tomb;
◆ 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
134 if (entry.
key == key) {