c - 仅当在 c 中重新散列哈希表时，大小为 8 的无效读取

Question

无效读取发生在我的代码中的 HTSize 函数中，但它也发生在其他函数中。仅当哈希表重新散列时才会出现此问题。它可能与我的 HTCreate 函数有关，但我不太确定。

我试过使用 malloc 和 calloc 但没有任何效果。

typedef char* KeyType;
typedef int HTItem;
typedef struct node{
    KeyType key;
    HTItem item;
    struct node *next;
}List;
typedef struct {
    List *head;
}TableEntry;
typedef TableEntry *HTHash;


int TABLESIZE = 10;

HTHash HTCreate(void)
{
//malloc
//      int i;
//      HTHash table = (HTHash)malloc(TABLESIZE*sizeof(TableEntry));
//      for(i=0;i<TABLESIZE;i++)
//          table[i].head = NULL;
//      return table;
//calloc    
        return calloc(TABLESIZE, sizeof(TableEntry));
}

int HTSize(HTHash hash)
{
    int i,count=0;
    List *temp; 
    for(i=0;i<TABLESIZE;i++)
    {
        if(hash[i].head != NULL)
        {
            count++;
            temp = hash[i].head->next;
            while(temp != NULL)
           {
                count++;
                temp = temp->next;
           }
        }   
    }
    return count;   
}

void HTInsert(HTHash hash, KeyType key, HTItem item)
{
    float a = 0.0;
    int index = h(key);
    int i;
    List *NewNode = (List*)malloc(sizeof(List));
    NewNode->key = key;
    NewNode->item = item;
    NewNode->next = NULL;
    if(hash[index].head == NULL)
        hash[index].head = NewNode;
    else
    {
        if(!strcmp(hash[index].head->key,key))
            hash[index].head->item = item;
        else
        {
            while(hash[index].head->next != NULL)
            {
                if(!strcmp(hash[index].head->next->key,key))
                {
                    hash[index].head->next->item = 
item;
                    break;
                }
                hash[index].head->next = hash[index].head- 
>next->next;
            }
            if(hash[index].head->next == NULL)
                hash[index].head->next = NewNode;
        }
    }
    a = (1.0 * HTSize(hash))/ TABLESIZE;
    if(a>=0.9)
    {
        printf("hash table is rehashing!\n");
        HTRehash(hash); 
    }
}

void HTRehash(HTHash hash)
{
    int i;
    HTHash temp = hash;
    int n = TABLESIZE;
    TABLESIZE = 2 * TABLESIZE;
    hash = HTCreate();
    for(i=0;i<n;i++)
    {
        List* list = temp[i].head;
        while(list!=NULL)
        {
            HTInsert(hash,list->key,list->item);
            list = list->next;
        }
    }
}

在使用 valgrind 运行它的 HTSize 中，它给了我 3 次“大小 8 的无效读取”。

Answer 1

您的问题似乎是您使用单个指针调用 HTRehash。然后你重新分配哈希表，但现在你不能返回这个新内存。

您必须使用双指针调用它，以便调用者可以使用新内存，或者您必须返回新指针。后者更简单，大纲:

HTHash HTRehash(HTHash hash)
{
    //...
    hash = HTCreate();
    //...
    return hash;
}

我还注意到您没有释放旧的哈希表。