Durk944 Durk944 - 1 month ago 6
C++ Question

C++ "Count the number of collisions at each slot in the hash table"

I'm suppose to create a Dictionary as a Hash Table with Linked List to spell check a text document. I read in the file "words.txt" to create the dictionary. Also, I have to count/display the number of collisions at each slot in the hash table when I load in the dictionary "words.txt"

I'm given the source code for the HashTable Class with Linked List as followed :

hashtable.cpp (#include "listtools.cpp" since its using templates)

#include <iostream>
#include <string>
#include "listtools.h"
#include "listtools.cpp"
#include "hashtable.h"

using LinkedListSavitch::Node;
using LinkedListSavitch::search;
using LinkedListSavitch::headInsert;
using namespace std;

#define HASH_WEIGHT 31

namespace HashTableSavitch
{
HashTable::HashTable()
{
for (int i = 0; i < SIZE; i++)
{
hashArray[i] = NULL;
//array for collisons
collisionArray[i] = 0;
}
}

HashTable::~HashTable()
{
for (int i=0; i<SIZE; i++)
{
Node<string> *next = hashArray[i];
while (next != NULL)
{
Node<string> *discard = next;
next = next->getLink( );
delete discard;
}
}
}

unsigned int HashTable::computeHash(string s) const
{
unsigned int hash = 0;
for (unsigned int i = 0; i < s.length( ); i++)
{
hash = HASH_WEIGHT * hash + s[i];
}
return hash % SIZE;
}

bool HashTable::containsString(string target) const
{
int hash = this->computeHash(target);
Node<string>* result = search(hashArray[hash], target);
if (result == NULL)
return false;
else
return true;
}

void HashTable::put(string s)
{
int count = 0;
int hash = computeHash(s);
if (search(hashArray[hash], s) == NULL)
{
// Only add the target if it's not in the list
headInsert(hashArray[hash], s);
}
else
{
collisionArray[hash]++;
}
void HashTable::printArray()
{
int number;
for(int i = 0; i < SIZE; i++)
{
number = collisionArray[i];
cout << "----------------\n";
cout << "index = " << i << endl;
cout << "Collisions = " << number << endl;
cout << "----------------\n";
}
}
} // HashTableSavitch


my main.cpp file

#include <iostream>
#include <fstream>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <string>
#include "hashtable.h"
using namespace std;
using HashTableSavitch::HashTable;

void upToLow(string & str);
void removePunct(string & str);

int main()
{
HashTable h;
string currWord;
string word;
int countMisspelled = 0;
int countCorrect = 0;

//Get input from words.rtf
ifstream dictionary("words.txt");

//File checking
if (dictionary.fail())
{
cout << "File does not exist" << endl;
cout << "Exit program" << endl;
}

//Create the dictionary as a hash table
while(dictionary >> currWord)
{
h.put(currWord);
}
dictionary.close();

//display collisions
h.printArray();

//Get input from gettysburg_address.txt
ifstream input("gettysburg_address.txt");

//File checking
if (input.fail())
{
cout << "File does not exist" << endl;
cout << "Exit program" << endl;
}

//Spell check gettysburg_address.txt
cout << "Misspelled words : " << endl;
cout << endl;

//If a word is not in the dictionary assume misspelled
while(input >> word)
{
removePunct(word);
upToLow(word);
if(h.containsString(word) == false)
{
countMisspelled++; // Increment misspelled words count
cout << word << " ";
if(countMisspelled % 20 == 0) // Display misspelled words 20 per line
{
cout << endl;
}
}
else
{
countCorrect++; // Increment correct words count
}
}
input.close();

cout << endl;
cout << endl;

cout << "Number of misspelled words : " << countMisspelled << endl;
cout << "Number of correct words : " << countCorrect << endl;

return 0;
}


/*Function to convert uppercase letters to lowercase*/
void upToLow(string & str)
{
for (unsigned int i = 0; i < strlen(str.c_str()); i++)
if (str[i] >= 0x41 && str[i] <= 0x5A)
str[i] = str[i] + 0x20;
}


/*Function to remove punctuation from string*/
void removePunct(string & str)
{
str.erase(remove_if(str.begin(), str.end(), static_cast<int(*)(int)>(&ispunct)),str.end());
}


Is there a simple way to count the number of collisions at each slot when loading in "words.txt" ? If I implement a count variable in the "put" function I can get the total number of collisions, but I'm not quite sure how to count/display the number of collisions at each slot of the hash table. Any help/tips is appreciated.

EDIT :
Followed Joe's advice and now I'm wondering how I could display the number of collisions at each slot. I made a void function to do just that but it displays the number of collisions at each slot to be 0. Anyone know what I should do?

Joe Joe
Answer

Probably the simplest way is declare an array in an appropriate place

int collisionArray[SIZE]; 

initialize it to 0 in HashTable::HashTable()

HashTable::HashTable()
{
 for (int i = 0; i < SIZE; i++)
 {
  hashArray[i] = NULL;
  collisionArray[i] = 0;
 }
}

then increment the appropriate element when a collision is found

void HashTable::put(string s)
{
    int count = 0;
    int hash = computeHash(s);
    if (search(hashArray[hash], s) == NULL)
    {
        // Only add the target if it's not in the list
        headInsert(hashArray[hash], s);
        collisionArray[hash]++;
    }
}