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

Question

我想创建一个字典作为带有链接列表的哈希表来拼写检查文本文档。我读入文件“words.txt”来创建字典。此外，当我加载字典“words.txt”时，我必须计算/显示哈希表中每个槽的冲突次数

我得到了带有链接列表的 HashTable 类的源代码，如下所示:

hashtable.cpp(#include "listtools.cpp"因为它使用模板)

#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

我的 main.cpp 文件

#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());
}

有没有一种简单的方法来计算加载“words.txt”时每个插槽的碰撞次数？如果我在“put”函数中实现一个计数变量，我可以获得碰撞总数，但我不太确定如何计算/显示哈希表每个槽的碰撞次数。感谢您提供任何帮助/提示。

编辑: 听从了乔的建议，现在我想知道如何显示每个插槽的碰撞次数。我做了一个 void 函数来做到这一点，但它显示每个插槽的碰撞次数为 0。有人知道我应该做什么吗？

Answer 1

可能最简单的方法是在适当的地方声明一个数组

int collisionArray[SIZE]; 

在HashTable::HashTable()中将其初始化为0

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

然后在发现碰撞时增加适当的元素

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]++;
    }
}