4

ハッシュテーブルを作成しましたが、基本的には次の 2 つの構造で構成されています。

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格納されたすべてのキーと値のペアを含む多次元配列であり、これもリンク リストです。

ハッシュテーブルの半分がいっぱいになった場合は、サイズを 2 倍にして再ハッシュすることで拡張します。

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 つ持っています。再ハッシュすると、そのポインターによって参照されるメモリが解放されます。それらに新しい辞書を割り当てましたが、新しいポインターは決して返されないため、古い辞書を使用しないことを知りません。辞書に再度アクセスしようとすると、解放されたメモリが指されます。

1 つの可能性は、古いディクショナリを完全に破棄するのではなく、ディクショナリ内に割り当てた 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 に答える
3
  1. これをデバッグする最善の方法は、コードを valgrind に対して実行することです。

しかし、あなたにいくつかの視点を与えてください：

  1. へのポインタへのポインタに割り当てられたメモリを内部的に解放する、より多くの呼び出しをfree(d)期待している場合destructorstruct dictdictEntry

  2. has テーブル全体を削除して展開する必要があるのはなぜですか? nextとにかくポインタがありますが、新しいハッシュエントリを追加するだけではどうですか?

解決策は、 を解放するのではなく、より多くを割り当てて適切な に割り当てること により、 をd拡張することです。dstruct dictEntrynext

を縮小するときdは、反復して最後に到達し、内の snextのメモリを解放し始める必要があります。struct dictEntryd

于 2012-06-12T22:42:15.143 に答える
1

実際には何をしdictCreateますか？

dict（固定サイズの）オブジェクトと（おそらく可変サイズの）dictEntriesinへのポインタの配列の間で混乱していると思いますdict.table。

おそらく、新しい 'dict' オブジェクトを作成して古いオブジェクトを解放するのではなく、realloc()が指すメモリだけを使用することもできますdict.table(ちなみに、とにかく辞書のテーブルを解放していません!)

于 2012-06-12T22:59:35.173 に答える
1

関数に渡されたポインターを解放しています。これは、関数を呼び出している人がまだ の古い値を使用しようとしていないことがわかっている場合にのみ安全ですd。呼び出すすべてのコードをチェック_dictRehash()し、古いポインタに何もかかっていないことを確認してください。

于 2012-06-12T22:41:49.330 に答える