An implementation of hash table using quadratic probing algorithm.
More...
|
int | notPresent |
|
std::vector< Entry > | table |
|
int | totalSize |
|
int | tomb = -1 |
|
int | size |
|
bool | rehashing |
|
An implementation of hash table using quadratic probing algorithm.
◆ add()
void quadratic_probing::add |
( |
int | key | ) |
|
Checks for load factor here
- Parameters
-
key | key value to hash and add to table |
182 {
184 table[index].key = key;
185
186 if (++size / static_cast<double>(totalSize) >= 0.5) {
187 rehash();
188 }
189}
int quadraticProbe(int key, bool searching)
Definition quadratic_probing_hash_table.cpp:56
◆ addInfo()
void quadratic_probing::addInfo |
( |
int | key | ) |
|
Information about the adding process
- Parameters
-
key | key value to hash and add to table |
207 {
209 display();
211 std::cout <<
"hash of " << key <<
" is " << hashFxn(key) <<
" % "
212 << totalSize << " == " << hashFxn(key) % totalSize;
216 display();
217}
std::string add(const std::string &first, const std::string &second)
Adding two string.
Definition uint128_t.hpp:37
◆ display()
void quadratic_probing::display |
( |
| ) |
|
Displays the table
- Returns
- None
142 {
143 for (int i = 0; i < totalSize; i++) {
144 if (table[i].key == notPresent) {
146 } else if (table[i].key == tomb) {
148 } else {
152 }
153 }
155}
◆ find()
Entry quadratic_probing::find |
( |
int | key | ) |
|
Get the entry instance corresponding to a key
- Parameters
-
key | key value to search/probe |
- Returns
- if present, the entry instance
-
if not present, a new instance
131 {
133 if (index == notPresent) {
135 }
136 return table[index];
137}
Definition quadratic_probing_hash_table.cpp:37
◆ hashFxn()
size_t quadratic_probing::hashFxn |
( |
int | key | ) |
|
Hash a key
- Parameters
-
- Returns
- hash of the key
46 {
48 return hash(key);
49}
◆ putProber()
bool quadratic_probing::putProber |
( |
const Entry & | entry, |
|
|
int | key ) |
Finds empty spot
- Parameters
-
entry | Instance of table entry |
key | key value to search/probe |
- Returns
true
if key is present
-
false
if key is absent
106 {
107 if (entry.
key == notPresent || entry.
key == tomb) {
108 return true;
109 }
110 return false;
111}
int key
key value
Definition quadratic_probing_hash_table.cpp:39
◆ quadraticProbe()
int quadratic_probing::quadraticProbe |
( |
int | key, |
|
|
bool | searching ) |
Performs quadratic probing to resolve collisions
- Parameters
-
key | key value to search/probe |
searching | true if only searching, false1 if assigning @returns value of notPresent`. |
56 {
57 int hash = static_cast<int>(hashFxn(key));
58 int i = 0;
60 do {
61 size_t index =
63 totalSize;
64 entry = table[index];
65 if (searching) {
66 if (entry.
key == notPresent) {
67 return notPresent;
68 }
69 if (searchingProber(entry, key)) {
71 return index;
72 }
73 std::cout <<
"Found tombstone or equal hash, checking next"
75 i++;
76 } else {
78 if (!rehashing) {
80 }
81 return index;
82 }
83 if (!rehashing) {
84 std::cout <<
"Spot taken, looking at next (next index = "
85 << (
hash +
static_cast<size_t>(
87 totalSize
89 }
90 i++;
91 }
92 if (i == totalSize * 100) {
94 return notPresent;
95 }
96 }
while (entry.
key != notPresent);
97 return notPresent;
98}
void * hash(const std::string &message)
Converts the string to bytestring and calls the main algorithm.
Definition md5.cpp:287
bool putProber(const Entry &entry, int key)
Definition double_hash_hash_table.cpp:120
◆ rehash()
void quadratic_probing::rehash |
( |
| ) |
|
Rehashes the table into a bigger table
- Returns
- none
160 {
161
162 rehashing = true;
163 int oldSize = totalSize;
165
166 totalSize *= 2;
168 for (int i = 0; i < oldSize; i++) {
169 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
170 size--;
171 add(oldTable[i].key);
172 }
173 }
174
175 rehashing = false;
177}
◆ removalInfo()
void quadratic_probing::removalInfo |
( |
int | key | ) |
|
Information about removal process
- Parameters
-
key | key value to hash and remove from table |
222 {
224 display();
226 std::cout <<
"hash of " << key <<
" is " << hashFxn(key) <<
" % "
227 << totalSize << " == " << hashFxn(key) % totalSize;
229 remove(key);
231 display();
232}
◆ remove()
void quadratic_probing::remove |
( |
int | key | ) |
|
Removes key. Leaves tombstone upon removal.
- Parameters
-
key | key value to hash and remove from table |
194 {
196 if (index == notPresent) {
198 }
199 table[index].key = tomb;
201 size--;
202}
◆ searchingProber()
bool quadratic_probing::searchingProber |
( |
const Entry & | entry, |
|
|
int | key ) |
Looks for a matching key
- Parameters
-
entry | Instance of table entry |
key | key value to search/probe |
- Returns
true
if key matches the entry
-
false
if key does not match the entry
119 {
120 if (entry.
key == key) {
121 return true;
122 }
123 return false;
124}