//-----------------------------------------------------------
// Purpose: Implementation of HashTable class.
// Author: John Gauch
//-----------------------------------------------------------
#include "main.h"
int collisions;
int insertion_count;
//-----------------------------------------------------------
// Constructor
//-----------------------------------------------------------
HashTable::HashTable(int size)
{
Size = size;
Value = new int[Size];
Key = new int[Size];
for (int index=0; index < Size; index++)
{
Value[index] = NONE;
Key[index] = EMPTY;
}
}
//-----------------------------------------------------------
// Copy constructor
//-----------------------------------------------------------
HashTable::HashTable(const HashTable & ht)
{
Size = ht.Size;
Value = new int[Size];
Key = new int[Size];
for (int index=0; index < Size; index++)
{
Value[index] = ht.Value[index];
Key[index] = ht.Key[index];
}
}
//-----------------------------------------------------------
// Destructor
//-----------------------------------------------------------
HashTable::~HashTable()
{
delete []Value;
delete []Key;
}
//-----------------------------------------------------------
// Insert method
//-----------------------------------------------------------
bool HashTable::Insert(int key, int value, int size)
{
if (insertion_count >= size) {
return false;
}
// Find desired key
int index = Hash(key);
while ((Key[index] != key) && (Key[index] != EMPTY))
index = Hash2(index);
// Insert value into hash table
Value[index] = value;
Key[index] = key;
insertion_count++;
return true;
}
//-----------------------------------------------------------
// Search method
//-----------------------------------------------------------
bool HashTable::Search(int key, int &value)
{
// Find desired key
int index = Hash(key);
while ((Key[index] != key) && (Key[index] != EMPTY))
index = Hash2(index);
// Return value from hash table
if (Key[index] == key)
value = Value[index];
return (Key[index] == key);
}
//-----------------------------------------------------------
// Delete method
//-----------------------------------------------------------
bool HashTable::Delete(int key)
{
// Find desired key
int index = Hash(key);
while ((Key[index] != key) && (Key[index] != EMPTY))
index = Hash2(index);
// Delete value from hash table
if (Key[index] == key)
{
Value[index] = NONE;
Key[index] = DELETED;
return true;
}
return false;
}
//-----------------------------------------------------------
// Primary hash function
//-----------------------------------------------------------
int HashTable::Hash(int key)
{
return key % Size;
}
//-----------------------------------------------------------
// Secondary hash function
//-----------------------------------------------------------
int HashTable::Hash2(int index)
{
collisions++;
cout << "Collision Detected" << endl;
return (index+1) % Size;
}
//-----------------------------------------------------------
// Print function for debugging
//-----------------------------------------------------------
void HashTable::Print()
{
cout << "Index\t" << "Value\t" << "Key\n";
for (int index=0; index < Size; index++)
cout << index << "\t"
<< Value[index] << "\t"
<< Key[index] << "\n";
}
//-----------------------------------------------------------
// Main program.
//-----------------------------------------------------------
int main()
{
// Initialize random number generator
srandom(time(NULL));
int SIZE;
int COUNT;
int MAX;
cout << "Enter SIZE: ";
cin >> SIZE;
cout << "Enter COUNT: ";
cin >> COUNT;
cout << "Enter MAX: ";
cin >> MAX;
HashTable hash (SIZE);
int key;
int value;
for(int i = 0; i < COUNT; i++) {
key = random() % MAX;
value = random() % MAX;
hash.Insert(key, value, SIZE);
}
hash.Print();
cout << "Collisions: " << collisions;
}