c - C 中指向链表的数组加倍

Question

我正在用 C 实现一个哈希集，其中我的数组指向一个链接列表

这是链接列表:

typedef struct hashnode hashnode;

struct hashnode {
    char *word;
    // will hold our word as a string

    hashnode *link;
    //will be used only if chaining
};

这是哈希集:

struct hashset {
    size_t size;
    //size of entire array

    size_t load;
    //number of words total

    hashnode **chains;
    //linked list (if words have same index);
};

现在我的双数组代码遇到问题 我相信某处有一个悬空指针 这是代码:

void dbl_array(hashset *this) {
    size_t newlen = this->size +1;
    newlen *= 2;
    //double siz
    hashnode **new_array = malloc(newlen * sizeof(hashnode*));
    //new array
    int array_end = (int)this->size;//load;
    //end of old array
    for(int i = 0; i < array_end; i++) {
        //loop through old
        int index = i;
        if(this->chains[index] == NULL) {
            continue;
        }
        else {
            hashnode *nod;
            int i=0;
            for(nod = this->chains[index]; nod != NULL; nod = nod->link) {
                if(nod == NULL) 
                    return;
                size_t tmp = strhash(nod->word) % newlen;
                //compute hash
                hashnode *newnod;
                newnod = malloc(sizeof(hashnode*));
                newnod->word = strdup(nod->word);
                newnod->link = NULL;
                if(new_array[tmp] == NULL) { 
                    //if new array does not already have a word at index
                    new_array[tmp] = newnod;
                }
                else {
                    //if word is here then link to old one
                    newnod->link = new_array[tmp];
                    new_array[tmp] = newnod;
                }
                printf("newarray has: %s @ {%d} \n", new_array[tmp]->word, tmp);
                //testing insertion
                i++;
            }
            free(nod);
        }
    }
    this->chains = new_array;
    this->size = newlen;
    free(new_array);
    printf("new size %d\n", this->size);
}

所以运行GDB后，我发现添加新节点时出现问题

Answer 1

根本没有理由为哈希表扩展分配新的冲突节点。扩展哈希表的算法相对简单:

1. 计算新的表格大小
2. 分配新表
3. 枚举旧表中的所有链
   1. 对于每个链，枚举所有节点
      1. 对于每个节点，根据新表大小计算新哈希
      2. 将节点移动到新表中的适当位置

完成上述操作后，您也完成了。只需将新表连接到哈希集，并确保将大小成员更新为新大小。旧表被丢弃。

以下代码假设您在加倍之前已正确管理哈希表。这样:

• 所有未使用的表槽都正确为 NULL
• 所有冲突列表都正确地以 NULL 结尾。

如果您无法保证这两个条件，那么将哈希表的大小加倍是最不用担心的。

void hashset_expand(hashset* hs)
{
    size_t new_size = 2 * (1 + hs->size), i, idx;
    hash node *next, *nod, **tbl = calloc(new_size, sizeof(*tbl));

    // walk old table, and each chain within it.
    for (i=0; i<hs->size; ++i)
    {
        next = hs->chains[i];
        while (next)
        {
            nod = next;
            next = next->link; // must be done **before** relink
            idx = strhash(nod->word) % new_size;
            nod->link = tbl[idx];
            tbl[idx] = nod;
        }
    }

    // finish up, deleting the old bed.
    free(hs->chains);
    hs->chains = tbl;
    hs->size = new_size;
}

这就是全部内容了。不要让事情变得更复杂。