调整散列表大小有问题

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键控引用变量，否则，它将指向已删除的无效哈希表。尝试以下修改：

...
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
}
...

另外，请注意我对代码中存在的两个内存泄漏所作的评论，我还将考虑到@ list指出，没有必要在喜欢列表的末尾插入代码，简化代码并使其更快。