An implementation of hash table using linear probing algorithm.
More...
|
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 |
161 {
163 table[index].key = key;
164
165 if (++size / static_cast<double>(totalSize) >= 0.5) {
166 rehash();
167 }
168}
int linearProbe(int key, bool searching)
Definition linear_probing_hash_table.cpp:55
◆ addInfo()
void linear_probing::addInfo |
( |
int | key | ) |
|
Information about the adding process
- Parameters
-
key | key value to hash and add |
186 {
188 display();
190 std::cout <<
"hash of " << key <<
" is " << hashFxn(key) <<
" % "
191 << totalSize << " == " << hashFxn(key) % totalSize;
195 display();
196}
std::string add(const std::string &first, const std::string &second)
Adding two string.
Definition uint128_t.hpp:37
◆ display()
void linear_probing::display |
( |
| ) |
|
Function to displays the table
- Returns
- none
120 {
121 for (int i = 0; i < totalSize; i++) {
122 if (table[i].key == notPresent) {
124 } else if (table[i].key == tomb) {
126 } else {
130 }
131 }
133}
◆ 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
46 {
48 return hash(key);
49}
◆ linearProbe()
int linear_probing::linearProbe |
( |
int | key, |
|
|
bool | searching ) |
Performs linear probing to resolve collisions
- Parameters
-
- Returns
- hash value of the key
55 {
56 int hash = static_cast<int>(hashFxn(key));
57 int i = 0;
59 do {
60 int index = static_cast<int>((hash + i) % totalSize);
61 entry = table[index];
62 if (searching) {
63 if (entry.
key == notPresent) {
64 return notPresent;
65 }
66 if (searchingProber(entry, key)) {
68 return index;
69 }
70 std::cout <<
"Found tombstone or equal hash, checking next"
72 i++;
73 } else {
75 if (!rehashing) {
77 }
78 return index;
79 }
80 if (!rehashing) {
82 }
83 i++;
84 }
85 if (i == totalSize) {
87 return notPresent;
88 }
89 }
while (entry.
key != notPresent);
90 return notPresent;
91}
bool putProber(const Entry &entry, int key)
Definition double_hash_hash_table.cpp:120
Definition linear_probing_hash_table.cpp:35
int key
key value
Definition linear_probing_hash_table.cpp:37
◆ 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
98 {
99 if (entry.
key == notPresent || entry.
key == tomb) {
100 return true;
101 }
102 return false;
103}
◆ rehash()
void linear_probing::rehash |
( |
| ) |
|
Rehashes the table into a bigger table
- Returns
- None
138 {
139
140 rehashing = true;
141 int oldSize = totalSize;
143
144
145 totalSize *= 2;
147 for (int i = 0; i < oldSize; i++) {
148 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
149 size--;
150 add(oldTable[i].key);
151 }
152 }
153
154 rehashing = false;
156}
◆ removalInfo()
void linear_probing::removalInfo |
( |
int | key | ) |
|
Information about removal process
- Parameters
-
key | key value to hash and remove |
201 {
203 display();
205 std::cout <<
"hash of " << key <<
" is " << hashFxn(key) <<
" % "
206 << totalSize << " == " << hashFxn(key) % totalSize;
208 remove(key);
210 display();
211}
◆ remove()
void linear_probing::remove |
( |
int | key | ) |
|
Removes key. Leaves tombstone upon removal.
- Parameters
-
key | key value to hash and remove |
173 {
175 if (index == notPresent) {
177 }
179 table[index].key = tomb;
180 size--;
181}
◆ 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
110 {
111 if (entry.
key == key) {
112 return true;
113 }
114 return false;
115}