An implementation of hash table using linear 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 linear probing algorithm.
◆ add()
void linear_probing::add |
( |
int |
key | ) |
|
Adds entry using linear probing. Checks for load factor here
- Parameters
-
key | key value to hash and add |
163 table[index].key = key;
165 if (++size /
static_cast<double>(totalSize) >= 0.5) {
◆ addInfo()
void linear_probing::addInfo |
( |
int |
key | ) |
|
Information about the adding process
- Parameters
-
key | key value to hash and add |
191 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
◆ display()
void linear_probing::display |
( |
| ) |
|
Function to displays the table
- Returns
- none
121 for (
int i = 0; i < totalSize; i++) {
122 if (table[i].key == notPresent) {
124 }
else if (table[i].key == tomb) {
◆ hashFxn()
size_t linear_probing::hashFxn |
( |
int |
key | ) |
|
Hash a key. Uses the STL library's std::hash()
function.
- Parameters
-
- Returns
- hash value of the key
◆ linearProbe()
int linear_probing::linearProbe |
( |
int |
key, |
|
|
bool |
searching |
|
) |
| |
Performs linear probing to resolve collisions
- Parameters
-
- Returns
- hash value of the key
56 int hash =
static_cast<int>(
hashFxn(key));
60 int index =
static_cast<int>((hash + i) % totalSize);
63 if (entry.
key == notPresent) {
70 std::cout <<
"Found tombstone or equal hash, checking next"
89 }
while (entry.
key != notPresent);
◆ putProber()
bool linear_probing::putProber |
( |
const Entry & |
entry, |
|
|
int |
key |
|
) |
| |
Finds empty spot
- Parameters
-
entry | instance to check in |
key | key value to hash |
- Returns
- hash value of the key
99 if (entry.
key == notPresent || entry.
key == tomb) {
◆ rehash()
void linear_probing::rehash |
( |
| ) |
|
Rehashes the table into a bigger table
- Returns
- None
141 int oldSize = totalSize;
147 for (
int i = 0; i < oldSize; i++) {
148 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
150 add(oldTable[i].key);
◆ removalInfo()
void linear_probing::removalInfo |
( |
int |
key | ) |
|
Information about removal process
- Parameters
-
key | key value to hash and remove |
206 << totalSize <<
" == " <<
hashFxn(key) % totalSize;
◆ remove()
void linear_probing::remove |
( |
int |
key | ) |
|
Removes key. Leaves tombstone upon removal.
- Parameters
-
key | key value to hash and remove |
175 if (index == notPresent) {
179 table[index].key = tomb;
◆ searchingProber()
bool linear_probing::searchingProber |
( |
const Entry & |
entry, |
|
|
int |
key |
|
) |
| |
Looks for a matching key
- Parameters
-
entry | instance to check in |
key | key value to hash |
- Returns
- hash value of the key
111 if (entry.
key == key) {