0

データ構造を学んでいます。ハッシュ テーブル (チェーン/バケット) のサイズ変更関数を作成する必要があります。私のコードはコンパイルされますが、テーブルのサイズは変わりません。誰かが見て、サイズ変更機能に欠けているものについてのヒントを教えてもらえますか? ありがとうございました！

    struct hlink {
    TYPE value;
    struct hlink *next;
};

struct hashTable {
    struct hlink **table;
    int tableSize;
    int count;
};


void initHashTable (struct hashTable *ht, int size ) {
    assert (size > 0);

    //allocate memory for table 
    ht->table = (struct hlink **) malloc(size * sizeof(struct hlink *));
    assert(ht->table != 0);

    //initialize empty link list
    int i;
    for (i = 0; i < size; i++)
    {
        ht->table[i] = 0;
    }

    //set tableSize to be size
    ht->tableSize = size;
    ht->count = 0;
}


    void _resizeHashTable(struct hashTable *ht)
{
    //create and initialize new tablesize
    int new_tblSize = 2 * ht->tableSize;

    //old list
    struct hlink **oldList = ht->table;

    //new list
    struct hlink **newList = (struct hlink **) malloc(new_tblSize * sizeof(struct hlink*));

    //Copy old values to new table
    for (int i=0; i < new_tblSize; i++)
    {
        //compute hash value to find the new bucket
        int hashIndex = HASH(oldList[i]->value) % new_tblSize;
        if (hashIndex < 0)
            hashIndex += new_tblSize;

        newList[i]->value = oldList[i]->value;
        newList[i]->next = newList[hashIndex];
    }

    //Assign table and tablesize back to the old table
    free(ht->table);
    ht->table = newList;
    ht->tableSize = new_tblSize;

}


void hashTableAdd (struct hashTable *ht, TYPE newValue)
{
    // compute hash value to find the correct bucket
    int hashIndex = HASH(newValue) % ht->tableSize;
    if (hashIndex < 0)
        hashIndex += ht->tableSize;

    struct hlink * newLink = (struct hlink *) malloc(sizeof(struct hlink));
    assert(newLink != 0);

    newLink->value = newValue;
    newLink->next = ht->table[hashIndex];

    ht->table[hashIndex] = newLink;     //add to bucket 
    ht->count++;


    if ((ht->count / (double) ht->tableSize) > 8.0)
        _resizeHashTable(ht);
}
4

1 に答える 1

0

古いテーブルを解放していません。割り当てたばかりのものを解放しています。それ以外の

ht->table = new_tbl;
...
free(new_tbl);

あなたがすべき

free(ht->table);
ht->table = new_tbl;

あなたにも問題があります

//Copy old values to new table
for (int i=0; i < ht->tableSize; i++)
{
    new_tbl[i] = ht->table[i];
}

上記のようにテーブル バケット エントリをコピーするだけでは十分ではありませんが、新しいテーブル サイズがあるため、バケット リンク リストの各エントリを再ハッシュする必要があるため、新しいハッシュインデックスが作成される可能性があります。

int hashIndex = HASH(newValue) % ht->tableSize;

サイズを変更するときは、一時的に古いバケットごとに移動し、次に各リンク リスト エントリに移動して、新しいテーブルに移動することをお勧めします。エントリごとに、「% ht->tableSize」が異なるため、古いテーブルのバケット インデックスが新しいテーブルのバケット エントリと異なる場合があることに注意してください。

resize() の間、古いテーブルのリンク リストの割り当てを管理するように注意してください。これらは新しいテーブルで再利用できますが、ここで適切にコーディングするのは難しい場合があります。

以下は、いくつかの機能強化のアイデアです...

PSもお勧めします

if (ht->count > (ht->tableSize * 8))

それ以外の

if ((ht->count / (double) ht->tableSize) > 8.0)

PS また、テーブル サイズを 2 倍にするのではなく、4 倍にすることをお勧めします。さらに、素数のテーブルサイズがあるのはいい感じです。素数で「%ht->tableSize」を実行すると、弱いハッシュ関数の分散が改善されます。

hashTableDelete() を追加すると、4 倍にするのがうまくいきます。削除関数を使用してサイズ変更関数を再度呼び出すこともできますが、今回はテーブルが縮小されています。拡張しきい値 (例: tablesize*8) と縮小しきい値が異なることが重要です。ほぼ同じ場合、テーブルがその重要なサイズのときに追加および削除すると、「ハッシュのスラッシング」が発生する可能性があります。私は、成長のしきい値を 3、11、61、251、... (素数は 4**N 未満) に、収縮のしきい値を 1、7、31、119、... (素数が 2* 未満) にするのが好きです。 4**N)、したがって、テーブルが大きくなったり小さくなったりしても、再ハッシュを最小限に抑えます。

于 2013-05-23T20:05:30.807 に答える