An implementation of hash table using quadratic probing 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 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 |
184 table[index].key = key;
186 if (++size /
static_cast<double>(totalSize) >= 0.5) {
◆ addInfo()
void quadratic_probing::addInfo |
( |
int |
key | ) |
|
Information about the adding process
- Parameters
-
key | key value to hash and add to table |
212 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
◆ display()
void quadratic_probing::display |
( |
| ) |
|
Displays the table
- Returns
- None
143 for (
int i = 0; i < totalSize; i++) {
144 if (table[i].key == notPresent) {
146 }
else if (table[i].key == tomb) {
◆ 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
133 if (index == notPresent) {
◆ hashFxn()
size_t quadratic_probing::hashFxn |
( |
int |
key | ) |
|
Hash a key
- Parameters
-
- Returns
- hash of the key
◆ 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
107 if (entry.
key == notPresent || entry.
key == tomb) {
◆ 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`. |
57 int hash =
static_cast<int>(
hashFxn(key));
66 if (entry.
key == notPresent) {
73 std::cout <<
"Found tombstone or equal hash, checking next"
84 std::cout <<
"Spot taken, looking at next (next index = "
85 << (hash +
static_cast<size_t>(
92 if (i == totalSize * 100) {
96 }
while (entry.
key != notPresent);
◆ rehash()
void quadratic_probing::rehash |
( |
| ) |
|
Rehashes the table into a bigger table
- Returns
- none
163 int oldSize = totalSize;
168 for (
int i = 0; i < oldSize; i++) {
169 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
171 add(oldTable[i].key);
◆ removalInfo()
void quadratic_probing::removalInfo |
( |
int |
key | ) |
|
Information about removal process
- Parameters
-
key | key value to hash and remove from table |
227 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
◆ remove()
void quadratic_probing::remove |
( |
int |
key | ) |
|
Removes key. Leaves tombstone upon removal.
- Parameters
-
key | key value to hash and remove from table |
196 if (index == notPresent) {
199 table[index].key = tomb;
◆ 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
120 if (entry.
key == key) {