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 に答える