How can I count the number of collisions in a hash table?

Question

My insert function already handles conflicts correctly, but I want to be able to count the number of collisions in each of the different hashing methods (chaining, linear sounding and quadratic sounding). How can I do it?

This is my code:

#include <iostream> #include <fstream> #include <string> #include <vector> #include <iterator> #include <ctime> #include "Chaining.h" #include "QuadraticProbing.h" #include "LinearProbing.h" using namespace std; int main() { int collision_count = 0; float diff = 0.0; clock_t tStart, tStop; string ITEM_NOT_FOUND = "ITEM_NOT_FOUND"; std::vector<std::string> DataArray; std::copy(std::istream_iterator<std::string>(std::ifstream("OHenry.txt")),istream_iterator<string>(),back_inserter(DataArray)); std::vector<std::string> QueryArray; std::copy(std::istream_iterator<std::string>(std::ifstream("queries.txt")),istream_iterator<string>(),back_inserter(QueryArray)); cout << "Testing chaining probing...\n"; HashTable_chaining ChainingHT( ITEM_NOT_FOUND, 101 ); int i = 0; double average_c = 0.0; double total_c = 0.0; double temp_c = 0.0; while(i != DataArray.size()) { tStart = clock(); ChainingHT.insert(DataArray[i]); tStop = clock(); total_c = tStop - tStart; temp_c = total_c + temp_c; average_c = total_c / DataArray.size(); if(DataArray[i] != DataArray[NULL]) { collision_count++; } i++; } cout<<"The number of collisions using Chaining is: "<<collision_count<<endl; cout<<"The average time per insertion using Chaining is: "<<average_c<<endl; system("pause"); // Quadratic Probing cout << "Testing quadratic probing...\n"; HashTable_chaining QuadraticProbingHT( ITEM_NOT_FOUND, 101 ); int j = 0; int collision_count_quadratic = 0; double average_qp = 0; while(j != DataArray.size()) { clock_t tStartq = clock(); QuadraticProbingHT.insert(DataArray[j]); if(DataArray[j] != DataArray[NULL]) { collision_count_quadratic++; } j++; average_qp = (((double)(clock() - tStartq)/CLOCKS_PER_SEC) + average_qp) / DataArray.size(); } cout<<"The number of collisions using Quadratic is: "<<collision_count<<endl; cout<<"The average time per insertion using Quadratic is: "<<average_qp<<endl; 

Answer 1

Perhaps the hash table itself will report the number of detected collectors without exposing its internal implementation at all.

For hash tables using sensing (of any type), the number of columns is equal to the number of elements located at an index that does not match their hash code (that is, because the position in which they were usually stored was already taken).

For hash tables using a chain, the number of columns is equal to the number of elements in the hash table, minus the number of buckets occupied (in other words, count all inserted elements except the first in each bucket). It is also quite intuitive.

So, what would I do in your shoes is to give each hash table the count_colissions() method, which calculates the number of columns in O (n) time using the appropriate method and returns it.