I wanted to get some input on a very basic simple Closed HashTable program I wrote as we just started to study the very basics of them in class. Because of this I decided I'd go ahead and try to implement a very basic one.
I got it and I am getting the output that I would get when I worked it out on pen and paper so it seems I did get it to work. Though before I expand on this program more to make the HashTable an actual class that I could use (yes I know their are ones already out there that I could use, but it is just for practice and make sure I understand the bare bone basics of them).
So here are the basics of what I wanted. I wanted a Closed HashTable that used a basic hash function. I then wanted it to hash the set and then display the hash table set. Nothing fancy, nor it is even using classes yet. Though how is the code so far for it? Anything that I should watch out for?
Here's the code, it's bare bones basic just enough to get theory into code
#include <iostream>
// Method Prototypes
int* CreateSet(int buckets, int defaultValue = -1);
void GetSet(int* set, int buckets);
void DisplaySet(int* set, int buckets);
void DeleteSet(int* set);
int HashFunction(int* set, int x, int buckets);
int* ClosedHashSet(int* set, const int buckets);
int main()
{
int buckets;
int* set;
int* hashSet;
// ask the user how big the set is
std::cout << "Please enter the size of the set: ";
std::cin >> buckets;
set = CreateSet(buckets);
GetSet(set, buckets);
std::cout<< "\nOrinal Set..." <<std::endl;
DisplaySet(set, buckets);
hashSet = ClosedHashSet(set, buckets);
std::cout << "\nClosed Hashing Set..." << std::endl;
DisplaySet(hashSet, buckets);
DeleteSet(set);
DeleteSet(hashSet);
return 0;
}
// Creates a set with the desired default value
// defaults to -1 for the defalt value
int* CreateSet(int buckets, int defaultValue)
{
int* set = new int[buckets];
for(int i = 0; i<buckets; i++)
{
set[i] = defaultValue;
}
std::cout << std::endl;
return set;
}
// Gets input from the user on what value to give each index in the set
// sets each index in the set to that value
void GetSet(int* set, int buckets)
{
for(int i = 0; i<buckets; i++)
{
std::cout << "Index " << i << ": ";
std::cin >> set[i];
}
}
// Takes in a set and displays the set
void DisplaySet(int* set, int buckets)
{
for(int i = 0; i<buckets; i++)
{
std::cout << i << ": " << set[i] << std::endl;
}
}
// Takes in a set and frees the memory that was created of that set
void DeleteSet(int* set)
{
delete[] set;
set = nullptr;
}
// Takes in the set you're hashing from, element to hash and how many buckets in the hash function
// returns the index using the hash function
int HashFunction(int* set, int x, int buckets)
{
// the index of the hash function
int result = (x*x)%buckets;
// what index of the hash function we are on
int hashedIndex = 1;
// while the element we are hashing has already been hashed
while(set[result] != -1)
{
// try to get another index using closed hashing
result = ( ((x*x)%buckets)+hashedIndex) %buckets;
// increase the hashedIndex
hashedIndex++;
}
return result;
}
// Takes in the set to hash from and the number of buckets and returns the set hashed
int* ClosedHashSet(int* set, const int buckets)
{
int* hashSet = CreateSet(buckets);
int result = 0;
for(int i = 0; i<buckets; i++)
{
result = HashFunction(hashSet, set[i], buckets);
hashSet[result] = set[i];
}
return hashSet;
}
Here is the hash function that i am using for this program
h(x)=x2 % b
where b is the number of buckets wanted for the set
Anything to watch out for code wise? Should had been implemented better (though note it will be put in a class and template it later on)?
Again this is just to try to implement the bare bone basics. I am not trying to do something better than what the professionals have already done for it. Just practice and would not try this for an actual project.
Thanks!