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

An implementation of hash table using linear 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)
 Hash a key. Uses the STL library's std::hash() function. More...
 
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< Entrytable
 
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
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 }
Here is the call graph for this function:

◆ addInfo()

void linear_probing::addInfo ( int  key)

Information about the adding process

Parameters
keykey value to hash and add
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 }
Here is the call graph for this function:

◆ 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) {
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 }
Here is the call graph for this function:

◆ 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
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
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 }
Here is the call graph for this function:

◆ 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
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  // 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 }
Here is the call graph for this function:

◆ removalInfo()

void linear_probing::removalInfo ( int  key)

Information about removal process

Parameters
keykey value to hash and remove
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 }
Here is the call graph for this function:

◆ remove()

void linear_probing::remove ( int  key)

Removes key. Leaves tombstone upon removal.

Parameters
keykey value to hash and remove
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 }
Here is the call graph for this function:

◆ 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
110  {
111  if (entry.key == key) {
112  return true;
113  }
114  return false;
115 }
linear_probing::Entry::key
int key
key value
Definition: linear_probing_hash_table.cpp:37
linear_probing::putProber
bool putProber(const Entry &entry, int key)
Definition: linear_probing_hash_table.cpp:98
linear_probing::Entry
Definition: linear_probing_hash_table.cpp:35
linear_probing::rehash
void rehash()
Definition: linear_probing_hash_table.cpp:138
std::vector
STL class.
linear_probing::searchingProber
bool searchingProber(const Entry &entry, int key)
Definition: linear_probing_hash_table.cpp:110
linear_probing::hashFxn
size_t hashFxn(int key)
Hash a key. Uses the STL library's std::hash() function.
Definition: linear_probing_hash_table.cpp:46
linear_probing::remove
void remove(int key)
Definition: linear_probing_hash_table.cpp:173
linear_probing::linearProbe
int linearProbe(int key, bool searching)
Definition: linear_probing_hash_table.cpp:55
std::cout
std::endl
T endl(T... args)
add
std::string add(std::string a, std::string b)
Definition: string_fibonacci.cpp:24
linear_probing::display
void display()
Definition: linear_probing_hash_table.cpp:120
std::hash