TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
Classes | Functions | Variables
linear_probing Namespace Reference
Open Addressing

An implementation of hash table using linear probing algorithm. More...

Classes

struct  Entry
 

Functions

bool putProber (const Entry &entry, int key)
 
bool searchingProber (const Entry &entry, int key)
 
void add (int key)
 
size_t hashFxn (int key)
 Hash a key. Uses the STL library's std::hash() function.
 
int linearProbe (int key, bool searching)
 
void display ()
 
void rehash ()
 
void remove (int key)
 
void addInfo (int key)
 
void removalInfo (int key)
 

Variables

int notPresent
 
std::vector< Entry > table
 
int totalSize
 
int tomb = -1
 
int size
 
bool rehashing
 

Detailed Description

An implementation of hash table using linear probing algorithm.

Function Documentation

◆ add()

void linear_probing::add ( int key)

Adds entry using linear probing. Checks for load factor here

Parameters
keykey value to hash and add

Definition at line 161 of file linear_probing_hash_table.cpp.

161 {
162 int index = linearProbe(key, false);
163 table[index].key = key;
164 // Load factor greater than 0.5 causes resizing
165 if (++size / static_cast<double>(totalSize) >= 0.5) {
166 rehash();
167 }
168}
linear_probing::linearProbe
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
keykey value to hash and add

Definition at line 186 of file linear_probing_hash_table.cpp.

186 {
187 std::cout << "Initial table: ";
188 display();
189 std::cout << std::endl;
190 std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
191 << totalSize << " == " << hashFxn(key) % totalSize;
192 std::cout << std::endl;
193 add(key);
194 std::cout << "New table: ";
195 display();
196}
add
std::string add(const std::string &first, const std::string &second)
Adding two string.
Definition uint128_t.hpp:38

◆ display()

void linear_probing::display ( )

Function to displays the table

Returns
none

Definition at line 120 of file linear_probing_hash_table.cpp.

120 {
121 for (int i = 0; i < totalSize; i++) {
122 if (table[i].key == notPresent) {
123 std::cout << " Empty ";
124 } else if (table[i].key == tomb) {
125 std::cout << " Tomb ";
126 } else {
127 std::cout << " ";
128 std::cout << table[i].key;
129 std::cout << " ";
130 }
131 }
132 std::cout << std::endl;
133}

◆ hashFxn()

size_t linear_probing::hashFxn ( int key)

Hash a key. Uses the STL library's std::hash() function.

Parameters
keyvalue to hash
Returns
hash value of the key

Definition at line 46 of file linear_probing_hash_table.cpp.

46 {
47 std::hash<int> hash;
48 return hash(key);
49}

◆ linearProbe()

int linear_probing::linearProbe ( int key,
bool searching )

Performs linear probing to resolve collisions

Parameters
keykey value to hash
Returns
hash value of the key

Definition at line 55 of file linear_probing_hash_table.cpp.

55 {
56 int hash = static_cast<int>(hashFxn(key));
57 int i = 0;
58 Entry entry;
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)) {
67 std::cout << "Found key!" << std::endl;
68 return index;
69 }
70 std::cout << "Found tombstone or equal hash, checking next"
71 << std::endl;
72 i++;
73 } else {
74 if (putProber(entry, key)) {
75 if (!rehashing) {
76 std::cout << "Spot found!" << std::endl;
77 }
78 return index;
79 }
80 if (!rehashing) {
81 std::cout << "Spot taken, looking at next" << std::endl;
82 }
83 i++;
84 }
85 if (i == totalSize) {
86 std::cout << "Linear probe failed" << std::endl;
87 return notPresent;
88 }
89 } while (entry.key != notPresent);
90 return notPresent;
91}
double_hashing::putProber
bool putProber(const Entry &entry, int key)
Definition double_hash_hash_table.cpp:120
linear_probing::Entry
Definition linear_probing_hash_table.cpp:35
linear_probing::Entry::key
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
entryinstance to check in
keykey value to hash
Returns
hash value of the key

Definition at line 98 of file linear_probing_hash_table.cpp.

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

Definition at line 138 of file linear_probing_hash_table.cpp.

138 {
139 // Necessary so wall of add info isn't printed all at once
140 rehashing = true;
141 int oldSize = totalSize;
142 std::vector<Entry> oldTable(table);
143 // Really this should use the next prime number greater than totalSize *
144 // 2
145 totalSize *= 2;
146 table = std::vector<Entry>(totalSize);
147 for (int i = 0; i < oldSize; i++) {
148 if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
149 size--; // Size stays the same (add increments size)
150 add(oldTable[i].key);
151 }
152 }
153 // delete[] oldTable;
154 rehashing = false;
155 std::cout << "Table was rehashed, new size is: " << totalSize << std::endl;
156}

◆ removalInfo()

void linear_probing::removalInfo ( int key)

Information about removal process

Parameters
keykey value to hash and remove

Definition at line 201 of file linear_probing_hash_table.cpp.

201 {
202 std::cout << "Initial table: ";
203 display();
204 std::cout << std::endl;
205 std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
206 << totalSize << " == " << hashFxn(key) % totalSize;
207 std::cout << std::endl;
208 remove(key);
209 std::cout << "New table: ";
210 display();
211}

◆ remove()

void linear_probing::remove ( int key)

Removes key. Leaves tombstone upon removal.

Parameters
keykey value to hash and remove

Definition at line 173 of file linear_probing_hash_table.cpp.

173 {
174 int index = linearProbe(key, true);
175 if (index == notPresent) {
176 std::cout << "key not found" << std::endl;
177 }
178 std::cout << "Removal Successful, leaving tomb" << std::endl;
179 table[index].key = tomb;
180 size--;
181}

◆ searchingProber()

bool linear_probing::searchingProber ( const Entry & entry,
int key )

Looks for a matching key

Parameters
entryinstance to check in
keykey value to hash
Returns
hash value of the key

Definition at line 110 of file linear_probing_hash_table.cpp.

110 {
111 if (entry.key == key) {
112 return true;
113 }
114 return false;
115}

Variable Documentation

◆ notPresent

int linear_probing::notPresent

Definition at line 27 of file linear_probing_hash_table.cpp.

◆ rehashing

bool linear_probing::rehashing

Definition at line 32 of file linear_probing_hash_table.cpp.

◆ size

int linear_probing::size

Definition at line 31 of file linear_probing_hash_table.cpp.

◆ table

std::vector<Entry> linear_probing::table

Definition at line 28 of file linear_probing_hash_table.cpp.

◆ tomb

int linear_probing::tomb = -1

Definition at line 30 of file linear_probing_hash_table.cpp.

◆ totalSize

int linear_probing::totalSize

Definition at line 29 of file linear_probing_hash_table.cpp.