'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