C 在调整哈希表大小时遇到​​问题

Question

我将在此处发布(我认为)与问题相关的代码片段，但如有必要，我可以使用 pastebin。可能已经发布了足够多的代码:P

我的程序包含一个哈希表，当某个哈希桶达到 20 个条目时，该哈希表需要加倍。虽然我相信逻辑是好的，而且它编译得很好，但它抛出了一个段错误。代码在不调整大小时运行起来很顺畅，但调整大小时会把事情搞砸。

感谢您的帮助:)

错误

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401012 in ml_add (ml=0x7fffffffe528, me=0x75a5a0) at mlist.c:74
74          while((cursorNode->next) != NULL){
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.80.el6_3.5.x86_64
(gdb) backtrace
#0  0x0000000000401012 in ml_add (ml=0x7fffffffe528, me=0x75a5a0) at mlist.c:74
#1  0x0000000000401554 in main (argc=1, argv=0x7fffffffe638) at finddupl.c:39

哈希表的结构

typedef struct bN { //linked list node containing data and next
    MEntry *nestedEntry;
    struct bN *next;
} bucketNode;

typedef struct bL { // bucket as linked list
    struct bN *first;
    int bucketSize;
} bucket;

struct mlist {
    struct bL *currentTable; //bucket array
};

添加函数

int ml_add(MList **ml, MEntry *me){

    MList *tempList;
    tempList = *ml;

    bucketNode *tempNode = (bucketNode *)malloc(sizeof(bucketNode));
    tempNode->nestedEntry = me;
    tempNode->next = NULL;

    unsigned long currentHash = me_hash(me, tableSize);

    if((tempList->currentTable[currentHash].bucketSize) == 0)   {
        tempList->currentTable[currentHash].first = tempNode;
        tempList->currentTable[currentHash].bucketSize = (tempList->currentTable[currentHash].bucketSize) + 1;
    }
    else if((tempList->currentTable[currentHash].bucketSize) == 20){
        printf("About to resize");
        printf("About to resize");
        tempList = ml_resize(&tempList, (tableSize * 2));
        tableSize = tableSize * 2;
        ml_add(&tempList,me);
    }
    else{
        bucketNode *cursorNode;
        cursorNode = tempList->currentTable[currentHash].first;
        while((cursorNode->next) != NULL){
            cursorNode = cursorNode->next;
        }
        cursorNode->next = tempNode;
        tempList->currentTable[currentHash].bucketSize = (tempList->currentTable[currentHash].bucketSize) + 1;
        return 1;
    }

    return 1;

}

调整大小函数

MList *ml_resize(MList **ml, int newSize){
    MList *oldList;
    oldList = *ml;

    MList *newList;

    if ((newList = (MList *)malloc(sizeof(MList))) != NULL){
        newList->currentTable = (bucket *)malloc(newSize * sizeof(bucket));
        int i;
        for(i = 0; i < newSize; i++){
            newList->currentTable[i].first = NULL;
            newList->currentTable[i].bucketSize = 0;
        }
    }

    int j;
    for(j = 0; j < tableSize; j++){
        bucketNode *cursorNode = oldList->currentTable[j].first;
        bucketNode *nextNode;
        while(cursorNode != NULL){
            nextNode = cursorNode->next;
            ml_transfer(&newList, cursorNode, newSize); 
            cursorNode = nextNode;  
        }
    }

    free(oldList);

    return newList;
}

转移到新的列表函数

void ml_transfer(MList **ml, bucketNode *insertNode, int newSize){

    MList *newList;
    newList = *ml;

    bucketNode *tempNode = insertNode;

    tempNode->next = NULL;

    unsigned long currentHash = me_hash((tempNode->nestedEntry), newSize);

    if((newList->currentTable[currentHash].bucketSize) == 0)    {
        newList->currentTable[currentHash].first = tempNode;
        newList->currentTable[currentHash].bucketSize = (newList->currentTable[currentHash].bucketSize) + 1;
    }
    else{
        bucketNode *cursorNode;
        cursorNode = newList->currentTable[currentHash].first;
        while((cursorNode->next) != NULL){
            cursorNode = cursorNode->next;
        }
        cursorNode->next = tempNode;
        newList->currentTable[currentHash].bucketSize = (newList->currentTable[currentHash].bucketSize) + 1;
    }

}

Answer 1

问题很可能在于 ml_add() 函数无法在哈希表调整大小时更新 MList** ml 参数节点。

当哈希表调整大小时，旧哈希表被销毁(在 ml_resize() 内部)，但指向调整大小的新哈希表的指针仅在 tempList 变量中更新，这只是 *ml 的本地副本。您还应该更新 *ml 以修改在函数外部保持 hashTable 引用的变量，否则，它将指向已删除的无效 Hashtable。尝试以下修改:

...
else if((tempList->currentTable[currentHash].bucketSize) == 20){
        printf("About to resize");
        printf("About to resize");
        tempList = ml_resize(&tempList, (tableSize * 2));
        tableSize = tableSize * 2;
        ml_add(&tempList,me);
        *ml = tempList;   // this is necesary to fix the pointer outside the
                           // function, that still points to the hashtable 
                           // memory freed by the resize function
}
...

另外请注意我对你的代码中存在的两个内存泄漏所做的评论，我也会考虑@hexist 指出的没有必要在头部的喜欢列表的末尾插入，简化代码并使其更快。