Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
quadratic_probing Namespace Reference

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

Classes

struct  Entry
 

Typedefs

using Entry = 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)
 
int quadraticProbe (int key, bool searching)
 
Entry find (int key)
 
void display ()
 
void rehash ()
 
void remove (int key)
 
void addInfo (int key)
 
void removalInfo (int key)
 

Variables

int notPresent
 
std::vector< Entrytable
 
int totalSize
 
int tomb = -1
 
int size
 
bool rehashing
 

Detailed Description

An implementation of hash table using quadratic probing algorithm.

Function Documentation

◆ add()

void quadratic_probing::add ( int  key)

Checks for load factor here

Parameters
keykey value to hash and add to table
182  {
183  int index = quadraticProbe(key, false);
184  table[index].key = key;
185  // Load factor greater than 0.5 causes resizing
186  if (++size / static_cast<double>(totalSize) >= 0.5) {
187  rehash();
188  }
189 }
Here is the call graph for this function:

◆ addInfo()

void quadratic_probing::addInfo ( int  key)

Information about the adding process

Parameters
keykey value to hash and add to table
207  {
208  std::cout << "Initial table: ";
209  display();
210  std::cout << std::endl;
211  std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
212  << totalSize << " == " << hashFxn(key) % totalSize;
213  std::cout << std::endl;
214  add(key);
215  std::cout << "New table: ";
216  display();
217 }
Here is the call graph for this function:

◆ 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) {
145  std::cout << " Empty ";
146  } else if (table[i].key == tomb) {
147  std::cout << " Tomb ";
148  } else {
149  std::cout << " ";
150  std::cout << table[i].key;
151  std::cout << " ";
152  }
153  }
154  std::cout << std::endl;
155 }
Here is the call graph for this function:

◆ find()

Entry quadratic_probing::find ( int  key)

Get the entry instance corresponding to a key

Parameters
keykey value to search/probe
Returns
if present, the entry instance
if not present, a new instance
131  {
132  int index = quadraticProbe(key, true);
133  if (index == notPresent) {
134  return Entry();
135  }
136  return table[index];
137 }
Here is the call graph for this function:

◆ hashFxn()

size_t quadratic_probing::hashFxn ( int  key)

Hash a key

Parameters
keykey value to hash
Returns
hash of the key
46  {
47  std::hash<int> hash;
48  return hash(key);
49 }

◆ putProber()

bool quadratic_probing::putProber ( const Entry entry,
int  key 
)

Finds empty spot

Parameters
entryInstance of table entry
keykey 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 }

◆ quadraticProbe()

int quadratic_probing::quadraticProbe ( int  key,
bool  searching 
)

Performs quadratic probing to resolve collisions

Parameters
keykey value to search/probe
searchingtrue if only searching, false1 if assigning @returns value ofnotPresent`.
56  {
57  int hash = static_cast<int>(hashFxn(key));
58  int i = 0;
59  Entry entry;
60  do {
61  size_t index =
62  (hash + static_cast<size_t>(std::round(std::pow(i, 2)))) %
63  totalSize;
64  entry = table[index];
65  if (searching) {
66  if (entry.key == notPresent) {
67  return notPresent;
68  }
69  if (searchingProber(entry, key)) {
70  std::cout << "Found key!" << std::endl;
71  return index;
72  }
73  std::cout << "Found tombstone or equal hash, checking next"
74  << std::endl;
75  i++;
76  } else {
77  if (putProber(entry, key)) {
78  if (!rehashing) {
79  std::cout << "Spot found!" << std::endl;
80  }
81  return index;
82  }
83  if (!rehashing) {
84  std::cout << "Spot taken, looking at next (next index = "
85  << (hash + static_cast<size_t>(
86  std::round(std::pow(i + 1, 2)))) %
87  totalSize
88  << std::endl;
89  }
90  i++;
91  }
92  if (i == totalSize * 100) {
93  std::cout << "Quadratic probe failed (infinite loop)" << std::endl;
94  return notPresent;
95  }
96  } while (entry.key != notPresent);
97  return notPresent;
98 }
Here is the call graph for this function:

◆ rehash()

void quadratic_probing::rehash ( )

Rehashes the table into a bigger table

Returns
none
160  {
161  // Necessary so wall of add info isn't printed all at once
162  rehashing = true;
163  int oldSize = totalSize;
164  std::vector<Entry> oldTable(table);
165  // Really this should use the next prime number greater than totalSize * 2
166  totalSize *= 2;
167  table = std::vector<Entry>(totalSize);
168  for (int i = 0; i < oldSize; i++) {
169  if (oldTable[i].key != -1 && oldTable[i].key != notPresent) {
170  size--; // Size stays the same (add increments size)
171  add(oldTable[i].key);
172  }
173  }
174  // delete[] oldTable;
175  rehashing = false;
176  std::cout << "Table was rehashed, new size is: " << totalSize << std::endl;
177 }
Here is the call graph for this function:

◆ removalInfo()

void quadratic_probing::removalInfo ( int  key)

Information about removal process

Parameters
keykey value to hash and remove from table
222  {
223  std::cout << "Initial table: ";
224  display();
225  std::cout << std::endl;
226  std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
227  << totalSize << " == " << hashFxn(key) % totalSize;
228  std::cout << std::endl;
229  remove(key);
230  std::cout << "New table: ";
231  display();
232 }
Here is the call graph for this function:

◆ remove()

void quadratic_probing::remove ( int  key)

Removes key. Leaves tombstone upon removal.

Parameters
keykey value to hash and remove from table
194  {
195  int index = quadraticProbe(key, true);
196  if (index == notPresent) {
197  std::cout << "key not found" << std::endl;
198  }
199  table[index].key = tomb;
200  std::cout << "Removal successful, leaving tombstone" << std::endl;
201  size--;
202 }
Here is the call graph for this function:

◆ searchingProber()

bool quadratic_probing::searchingProber ( const Entry entry,
int  key 
)

Looks for a matching key

Parameters
entryInstance of table entry
keykey 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 }
std::vector
STL class.
quadratic_probing::putProber
bool putProber(const Entry &entry, int key)
Definition: quadratic_probing_hash_table.cpp:106
quadratic_probing::display
void display()
Definition: quadratic_probing_hash_table.cpp:142
quadratic_probing::Entry
Definition: quadratic_probing_hash_table.cpp:37
quadratic_probing::remove
void remove(int key)
Definition: quadratic_probing_hash_table.cpp:194
quadratic_probing::Entry::key
int key
key value
Definition: quadratic_probing_hash_table.cpp:39
std::cout
quadratic_probing::rehash
void rehash()
Definition: quadratic_probing_hash_table.cpp:160
std::round
T round(T... args)
std::endl
T endl(T... args)
add
std::string add(std::string a, std::string b)
Definition: string_fibonacci.cpp:24
quadratic_probing::hashFxn
size_t hashFxn(int key)
Definition: quadratic_probing_hash_table.cpp:46
quadratic_probing::quadraticProbe
int quadraticProbe(int key, bool searching)
Definition: quadratic_probing_hash_table.cpp:56
quadratic_probing::searchingProber
bool searchingProber(const Entry &entry, int key)
Definition: quadratic_probing_hash_table.cpp:119
std::hash
std::pow
T pow(T... args)