4

我写了一个哈希表，它基本上由这两种结构组成：

typedef struct dictEntry {
    void *key;
    void *value;
    struct dictEntry *next;
} dictEntry;

typedef struct dict {
    dictEntry **table;
    unsigned long size;
    unsigned long items;
} dict;

dict.table是一个多维数组，其中包含所有存储的键/值对，它们又是一个链表。

如果哈希表的一半已满，我会通过将大小加倍并重新散列来扩展它：

dict *_dictRehash(dict *d) {
    int i;
    dict *_d;
    dictEntry *dit;

    _d = dictCreate(d->size * 2);

    for (i = 0; i < d->size; i++) {
        for (dit = d->table[i]; dit != NULL; dit = dit->next) {
            _dictAddRaw(_d, dit);
        }
    }

    /* FIXME memory leak because the old dict can never be freed */
    free(d); // seg fault

    return _d;
}

上面的函数使用旧哈希表中的指针并将其存储在新创建的哈希表中。释放旧dict d的时会发生分段错误。

我如何能够释放旧的哈希表结构而不必再次为键/值对分配内存？

编辑，为了完整起见：

dict *dictCreate(unsigned long size) {
    dict *d;

    d = malloc(sizeof(dict));
    d->size  = size;
    d->items = 0;
    d->table = calloc(size, sizeof(dictEntry*));

    return d;
}

void dictAdd(dict *d, void *key, void *value) {
    dictEntry *entry;

    entry = malloc(sizeof *entry);

    entry->key   = key;
    entry->value = value;
    entry->next  = '\0';

    if ((((float)d->items) / d->size) > 0.5) d = _dictRehash(d);

    _dictAddRaw(d, entry);
}

void _dictAddRaw(dict *d, dictEntry *entry) {
    int index = (hash(entry->key) & (d->size - 1));

    if (d->table[index]) {
        dictEntry *next, *prev;

        for (next = d->table[index]; next != NULL; next = next->next) {
            prev = next;

        }

        prev->next = entry;
    } else {
        d->table[index] = entry;
    }
    d->items++;
}
4

4 回答 4

3
  1. 最好的调试方法是针对 valgrind 运行代码。

但是给你一些观点：

  1. 当您free(d)期望destructor对您进行更多调用时struct dict，它将在内部释放分配给指向指针的指针的内存dictEntry

  2. 为什么要删除整个has表才能展开呢？无论如何，您有一个next指针，为什么不将新的哈希条目附加到它呢？

解决方案不是释放，d而是d通过分配更多struct dictEntry并将它们分配给适当 的来扩展next。

收缩时，d您将不得不迭代next以到达末尾，然后开始释放struct dictEntrys 内部的内存d。

于 2012-06-12T22:42:15.143 回答
3

为了阐明 Graham 的观点，您需要注意这个库中的内存是如何被访问的。用户有一个指向其字典的指针。当您重新哈希时，您释放了该指针引用的内存。虽然你为他们分配了一个新的字典，但新的指针永远不会返回给他们，所以他们不知道不要使用旧的。当他们再次尝试访问他们的字典时，它指向已释放的内存。

一种可能性是不要完全丢弃旧字典，而只丢弃您在字典中分配的 dictEntry 表。这样，您的用户将永远不必更新他们的指针，但您可以重新调整表以适应更有效的访问。尝试这样的事情：

void _dictRehash(dict *d) {
    printf("rehashing!\n");
    int i;
    dictEntry *dit;

    int old_size = d->size;
    dictEntry** old_table = d->table;
    int size = old_size * 2;

    d->table = calloc(size, sizeof(dictEntry*));
    d->size = size;
    d->items = 0;

    for (i = 0; i < old_size; i++) {
        for (dit = old_table[i]; dit != NULL; dit = dit->next) {
            _dictAddRaw(d, dit);
        }
    }

    free(old_table);
    return;

}

作为旁注，我不确定你的哈希函数是做什么的，但在我看来，这条线

int index = (hash(entry->key) & (d->size - 1));

有点不正统。你得到一个哈希值并按位和表的大小做一个，我想这在某种意义上是有效的，它可以保证在（我认为？）之内[0, max_size)，我认为你可能是%指模数。

于 2012-06-13T04:49:41.853 回答
1

您正在释放一个传递给您的函数的指针。仅当您知道调用您的函数的人并未仍在尝试使用的旧值时，这才是安全的d。检查所有调用的代码_dictRehash()并确保没有任何东西挂在旧指针上。

于 2012-06-12T22:41:49.330 回答
1

实际上是做什么的dictCreate？

我认为您在（固定大小）对象和指向indict的（可能是可变大小的）指针数组之间感到困惑。dictEntriesdict.table

也许您可以只realloc()使用 指向的内存dict.table，而不是创建一个新的“dict”对象并释放旧对象（顺便说一句，这并没有释放 dictentries 表！）

于 2012-06-12T22:59:35.173 回答