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

An implementation of hash table using double hashing 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)
 Hash a key. Uses the STL library's std::hash() function. More...
 
size_t otherHashFxn (int key)
 Used for second hash function. More...
 
int doubleHash (int key, bool searching)
 Performs double hashing to resolve collisions. More...
 
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 double hashing algorithm.

Function Documentation

◆ add()

void double_hashing::add ( int  key)

Checks for load factor here

Parameters
keykey value to add to the table
185  {
186  // auto* entry = new Entry();
187  // entry->key = key;
188  int index = doubleHash(key, false);
189  table[index].key = key;
190  // Load factor greater than 0.5 causes resizing
191  if (++size / static_cast<double>(totalSize) >= 0.5) {
192  rehash();
193  }
194 }
Here is the call graph for this function:

◆ addInfo()

void double_hashing::addInfo ( int  key)

Information about the adding process

Parameters
keykey value to add to table
212  {
213  std::cout << "Initial table: ";
214  display();
215  std::cout << std::endl;
216  std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
217  << totalSize << " == " << hashFxn(key) % totalSize;
218  std::cout << std::endl;
219  add(key);
220  std::cout << "New table: ";
221  display();
222 }
Here is the call graph for this function:

◆ display()

void double_hashing::display ( )

Displays the table

Returns
None
143  {
144  for (int i = 0; i < totalSize; i++) {
145  if (table[i].key == notPresent) {
146  std::cout << " Empty ";
147  } else if (table[i].key == tomb) {
148  std::cout << " Tomb ";
149  } else {
150  std::cout << " ";
151  std::cout << table[i].key;
152  std::cout << " ";
153  }
154  }
155  std::cout << std::endl;
156 }
Here is the call graph for this function:

◆ doubleHash()

int double_hashing::doubleHash ( int  key,
bool  searching 
)

Performs double hashing to resolve collisions.

Parameters
keykey value to apply double-hash on
searchingtrue to check for conflicts
Returns
Index of key when found
new hash if no conflicts present
71  {
72  int hash = static_cast<int>(hashFxn(key));
73  int i = 0;
74  Entry entry;
75  do {
76  int index =
77  static_cast<int>(hash + (i * otherHashFxn(key))) % totalSize;
78  entry = table[index];
79  if (searching) {
80  if (entry.key == notPresent) {
81  return notPresent;
82  }
83  if (searchingProber(entry, key)) {
84  std::cout << "Found key!" << std::endl;
85  return index;
86  }
87  std::cout << "Found tombstone or equal hash, checking next"
88  << std::endl;
89  i++;
90  } else {
91  if (putProber(entry, key)) {
92  if (!rehashing) {
93  std::cout << "Spot found!" << std::endl;
94  }
95  return index;
96  }
97  if (!rehashing) {
98  std::cout << "Spot taken, looking at next (next index:"
99  << " "
100  << static_cast<int>(hash + (i * otherHashFxn(key))) %
101  totalSize
102  << ")" << std::endl;
103  }
104  i++;
105  }
106  if (i == totalSize * 100) {
107  std::cout << "DoubleHash probe failed" << std::endl;
108  return notPresent;
109  }
110  } while (entry.key != notPresent);
111  return notPresent;
112 }
Here is the call graph for this function:

◆ hashFxn()

size_t double_hashing::hashFxn ( int  key)

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

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

◆ otherHashFxn()

size_t double_hashing::otherHashFxn ( int  key)

Used for second hash function.

Parameters
keykey value to hash
Returns
hash value of the key
58  {
59  std::hash<int> hash;
60  return 1 + (7 - (hash(key) % 7));
61 }

◆ putProber()

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

Finds empty spot in a vector

Parameters
entryvector to search in
keykey to search for
Returns
true if key is not present or is a toumb
false is already occupied
120  {
121  if (entry.key == notPresent || entry.key == tomb) {
122  return true;
123  }
124  return false;
125 }

◆ rehash()

void double_hashing::rehash ( )

Rehashes the table into a bigger table

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

◆ removalInfo()

void double_hashing::removalInfo ( int  key)

Information about removal process

Parameters
keykey value to remove from table
227  {
228  std::cout << "Initial table: ";
229  display();
230  std::cout << std::endl;
231  std::cout << "hash of " << key << " is " << hashFxn(key) << " % "
232  << totalSize << " == " << hashFxn(key) % totalSize;
233  std::cout << std::endl;
234  remove(key);
235  std::cout << "New table: ";
236  display();
237 }
Here is the call graph for this function:

◆ remove()

void double_hashing::remove ( int  key)

Removes key. Leaves tombstone upon removal.

Parameters
keykey value to remove
199  {
200  int index = doubleHash(key, true);
201  if (index == notPresent) {
202  std::cout << "key not found" << std::endl;
203  }
204  table[index].key = tomb;
205  std::cout << "Removal successful, leaving tombstone" << std::endl;
206  size--;
207 }
Here is the call graph for this function:

◆ searchingProber()

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

Looks for a matching key

Parameters
entryvector to search in
keykey value to search
Returns
true if found
false if not found
133  {
134  if (entry.key == key) {
135  return true;
136  }
137  return false;
138 }
double_hashing::Entry
Definition: double_hash_hash_table.cpp:36
double_hashing::otherHashFxn
size_t otherHashFxn(int key)
Used for second hash function.
Definition: double_hash_hash_table.cpp:58
std::vector
STL class.
double_hashing::putProber
bool putProber(const Entry &entry, int key)
Definition: double_hash_hash_table.cpp:120
std::cout
double_hashing::hashFxn
size_t hashFxn(int key)
Hash a key. Uses the STL library's std::hash() function.
Definition: double_hash_hash_table.cpp:47
double_hashing::rehash
void rehash()
Definition: double_hash_hash_table.cpp:161
double_hashing::display
void display()
Definition: double_hash_hash_table.cpp:143
double_hashing::remove
void remove(int key)
Definition: double_hash_hash_table.cpp:199
std::endl
T endl(T... args)
double_hashing::searchingProber
bool searchingProber(const Entry &entry, int key)
Definition: double_hash_hash_table.cpp:133
double_hashing::doubleHash
int doubleHash(int key, bool searching)
Performs double hashing to resolve collisions.
Definition: double_hash_hash_table.cpp:71
add
std::string add(std::string a, std::string b)
Definition: string_fibonacci.cpp:24
double_hashing::Entry::key
int key
key value
Definition: double_hash_hash_table.cpp:38
std::hash