1

我第一次使用哈希表，我想我对它们的工作原理有了基本的了解。我正在使用哈希表来检查文件中是否存在单词。该程序接收一个“字典”文件和一个单词检查文件。当我有一本小字典时，该程序运行良好，但当我使用非常大的字典时，单词会被覆盖。我希望能对原因有所了解。这是我的代码：

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <pthread.h>
#include <tgmath.h>
#include <ctype.h>
#include "hashtable_constants.h"


#define HASH_SIZE 500
#define MAX_WORD_SIZE 50

struct hashTable {
    int collisions;
    char** words;
};

struct hashTable hashTables[HASH_SIZE];

int hashKey(char * str)
{
    int key = 0;
    for(int j = 0; j <= 51; j++)
    {
        if(str[j] == '\0')
            break;

        key += (int)str[j];
    }
    key = key % HASH_SIZE;
    return key;
}

int main(int argc, char** argv)
{   

    if(argc > 3)
    {
        fprintf(stderr, "Too many arguments!\n");
        return -1;
    }
    else if(argc < 3)
    {
        fprintf(stderr, "Not enough arguments!\n");
        return -1;
    }

    FILE *dictionary = fopen(argv[1], "r");
    FILE *wordCheck = fopen(argv[2], "r");

    if(dictionary == NULL || wordCheck == NULL ) //ensure input file exists
    {
        fprintf(stderr, "Error accessing input files\n");
        return -1;
    }

    for(int i = 0; i < HASH_SIZE; i++)
    {
        hashTables[i].collisions = 0;
        hashTables[i].words = malloc(HASH_SIZE * MAX_WORD_SIZE);
    }

    struct stat fileStat1;
    struct stat fileStat2;

    stat(argv[1], &fileStat1);
    stat(argv[2], &fileStat2);

    char* dictBuffer = (char*)malloc(fileStat1.st_size + 1);
    char* wordCheckBuff = (char*)malloc(fileStat2.st_size + 1);

    if (dictBuffer == NULL || wordCheckBuff == NULL) 
    {
        fprintf (stderr, "Memory error");
        return -1;
    }

    fread(dictBuffer, 1, (int)fileStat1.st_size, dictionary);
    fread(wordCheckBuff, 1, (int)fileStat2.st_size, wordCheck);

    char* word = malloc(MAX_WORD_SIZE + 1);
    int count = 0;

    for(int i = 0; i < (int)fileStat1.st_size; i++)
    {
        char c = dictBuffer[i];
        if(isspace(c))
        {
            word[count] = '\0';
            char* wordToAdd = word;
            int key = hashKey(wordToAdd);
            int collisionIndex = hashTables[key].collisions; 
            hashTables[key].words[collisionIndex] = wordToAdd;
            hashTables[key].collisions++;   
            count = 0;

            free(word);
            word = malloc(MAX_WORD_SIZE + 1);

            //printf("Added: %s to hashtable at key: %d\n",word,key);
        }
        else
        {
            word[count] = c;
            count++;
        }
    }

    count = 0;

    for(int i = 0; i < (int)fileStat2.st_size; i++)
    {
        char c = wordCheckBuff[i];
        if(isspace(c))
        {
            word[count] = '\0';
            char* wordToCheck = word;
            int key = hashKey(wordToCheck);
            int collisionIndex = hashTables[key].collisions;
            int foundWord = 0;

            for(int j = 0; j < collisionIndex; j++)
            {
                if(hashTables[key].words[j] == wordToCheck)
                {
                    printf("%s == %s\n",hashTables[key].words[j], wordToCheck);
                    foundWord = 1;
                    break;
                }
            }

            if(foundWord == 0)
                printf("Not a word: %s\n", wordToCheck);
            /*else
                printf("Key: %d -- Is a word: %s\n",key, word);*/

            free(word);
            word = malloc(MAX_WORD_SIZE + 1);
            count = 0;
        }
        else
        {
            word[count] = c;
            count++;
        }
    }

    for(int i = 0; i < HASH_SIZE; i++)
        free(hashTables[i].words);

    free(word);
    fclose(dictionary);
    fclose(wordCheck);      

    printf("done\n");

    return 0;   
}
4

1 回答 1

2

问题在于：

hashTables[key].words[collisionIndex] = wordToAdd;

您将“wordToAdd”添加到表中。

但是 wordToAdd 等于 word。几行之后你打电话

free(word);

所以哈希表现在拥有一个指向已释放内存的指针。

这将导致程序中出现各种未定义的行为，也很可能是段错误。而且很可能由于内存现在是“空闲的”，随后对 malloc 的调用可能会再次返回相同的指针 - 然后您将用另一个单词填充该指针。因此，您会看到字符串的覆盖。

你需要回顾一下你在程序中一般是如何使用“malloc”/“free”的。如果您希望指针指向有效字符串，则不能在该字符串的预期生命周期内对该指针调用“free”。

您要做的是 malloc 每个字符串，并将指针添加到哈希表。然后，当您完成哈希表并且不再需要字符串数据时，对其中包含的所有指针调用“free”。在您的情况下，这可能需要在程序执行结束时出现在您的清理代码中。

于 2013-10-31T02:46:47.157 回答