Hash Table:
Create a hash table class/struct.
Define an array that holds 27 elements.
Define a function called Hash(int)
- This function returns the
... [Show More] modulo of that int by the size of
the table (array).
Define an add function that takes an integer.
- This function takes the integer, determines the hash of that
number by calling the above hash function,
then adds it to the table using linear probing for collision
resolution.
Define a function that looks up a value, it takes an integer,
return -1 if the value is not in the table.
Create a main that allows the user to add and lookup items in
the table.
*/
#include
#include
using namespace std;
const int SIZE = 27; // a good strong prime number
const int EMPTY = -1; // -1 indicates that the cell is empty
#define DISPLAY true // remove to disable debugging output
struct hashrecord
{
int id; //to hold a unique id for each element
int data; //the data for each element, I used a simple int
};
class HashTable
{
private:
hashrecord table[SIZE]; // where our data will be held
public:
HashTable();
int Hash(int data);
bool Add(int data);
bool Probe(int data);
int Lookup(int data);
void Print();
};
HashTable::HashTable()
{
#ifdef DISPLAY
cout << "Building hash table.\n";
#endif
for (int i = 0; i < SIZE; i++) // table[i] = EMPTY;
{
table[i].id = -1; //set all ids to -1 to show they're
empty
table[i].data = EMPTY; //set all data values to default
}
}
//This function returns the modulo of that int by the size of the table (array).
int HashTable::Hash(int data)
{
return data % SIZE;
}
/* add items in the table.
- This function takes the integer, determines the hash of that number by calling
the above
hash function, then adds it to the table using linear probing for collision
resolution. */
bool HashTable::Add(int data)
This study source was downloaded by 100000823950634 from CourseHero.com on 04-22-2021 08:45:59 GMT -05:00
https://www.coursehero.com/file/63195728/Lab-hash-2nd-revisedcpp/
This study resource was
shared via CourseHero.com
{
#ifdef DISPLAY
cout << " :adding " << data << " at ";
#endif
if (table[Hash(data)].data == EMPTY) // apply the hash function first
{
#ifdef DISPLAY
cout << "at " << Hash(data) << endl;
#endif
table[Hash(data)].data = data;
table[Hash(data)].id = Hash(data);
return true;
}
else //otherwise we need to probe
return Probe(data);
}
// linear probing function for collision resolution
bool HashTable::Probe(int data)
{
int index = Hash(data); //data % SIZE;
int probeFcn = Hash(index+1); //(index + 1) % SIZE; // start of the linear
probing [Show Less]