'FInd colisions in a integer hash table
In my assignment, I need to to count the number of collisions in my hash table. Also I need to find the mean size of the list. But I'm bit unsure if my implementation is correct.
The assignment:
[...]
"Add a collision counter to the original file (HashTable.cpp). Remember that a collision is when a data is mapped occurs to a position in the hash table that is already occupied."
"Write a function that calculates and returns the average of the lengths of the lists. Also print this value at the end of program execution: "
[...]
My code so far (HashTable.cpp):
//https://www.cplusplus.com/reference/list/list/
//list documentation
#include <iostream>
#include <list>
#include<vector>
#include<cassert>
namespace data_structure{
class HashTable{
private:
std::list<int> *table;
int total_elements;
std::vector<int> positions;
// Hash function to calculate hash for a value:
int getHash(int key){
return key % total_elements;
}
public:
// Constructor to create a hash table with 'n' indices:
HashTable(int n){
total_elements = n;
table = new std::list<int>[total_elements];
}
std::list<int> *get_table()
{
return table;
}
std::vector<int> get_vector()
{
return positions;
}
// Insert data in the hash table:
void insertElement(int key){
table[getHash(key)].push_back(key); //Add element at the end
positions.push_back(getHash(key));
}
// Remove data from the hash table:
void removeElement(int key){
int x = getHash(key);
std::list<int>::iterator i;
for (i = table[x].begin(); i != table[x].end(); i++) {
// Check if the iterator points to the required item:
if (*i == key)
break;
}
// If the item was found in the list, then delete it:
if (i != table[x].end())
table[x].erase(i); //Erase elements
}
void printAll(){
// Traverse each index:
for(int i = 0; i < total_elements; i++){
std::cout << "Index " << i << ": ";
// Traverse the list at current index:
for(int j : table[i])
std::cout << j << " => ";
std::cout << std::endl;
}
}
size_t find_total_colisions(std::vector<int> &v)
{
size_t amount_of_colisions{0};
for(size_t i = 0;i<v.size();i++)
{
for(size_t j = i+1;j<v.size();j++)
{
if(v[i] == v[j])
{
amount_of_colisions++;
}
}
}
return amount_of_colisions;
}
double mean_of_lists(std::list<int> *list)
{
double mean{0};
auto total{0};
for(auto i = 0;i<total_elements;i++)
{
for(auto &element : table[i])
{
total++;
mean += element;
}
}
return static_cast<double>(mean/total);
}
};
}
std::ostream & operator<<(std::ostream &cout , std::vector<int> &v)
{
for(auto element : v )
{
std::cout << element << " ";
}
return cout;
}
int main() {
// Create a hash table with x indices:
data_structure::HashTable ht(9);
// Declare the data to be stored in the hash table:
int array[] = {2, 4, 6, 8, 10, 1, 21, 13, 15, 9, 12, 30, 7, 17, 24, 45, 41, 32, 38, 39, 35, 26, 27, 50, 55, 52};
// Insert the whole data into the hash table:
for(size_t i = 0; i < sizeof(array)/sizeof(array[0]); i++)
ht.insertElement(array[i]);
std::cout << "\n..:: Hash Table ::.." << std::endl;
ht.printAll();
ht.removeElement(1);
std::vector<int> positions = ht.get_vector();
std::cout << std::endl << "..:: After deleting element 1 ::.." << std::endl;
ht.printAll();
std::cout << "Table of positions\n";
std::cout << positions << "\n";
size_t colisions{0};
colisions = ht.find_total_colisions(positions);
std::cout << "Number of colisions = " << colisions << "\n";
std::cout << "Mean of the list = " << ht.mean_of_lists(ht.get_table()) << "\n";
return 0;
}
Are those functions right? If no, how could I implement it? Give an example because I'm confused about it.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|