2

C で記述されたハッシュ テーブルの個別にチェーンされた実装では、重複したキーを LIFO の順序で挿入および削除できます。

テーブルのサイズを変更する (サイズを 2 倍にする) 条件は、各リストに平均 10 項目が含まれている場合です。コードは次のようになります。

void maybeExpand(Hashtable* table)
{
    if (table->items < table->lists * 10)
        return;

    /* resize */
}

ハッシュ テーブルの全容量ではなく、項目数とリスト数の比率を比較していることに注意してください。

問題は、テーブルが重複キーのみで構成され、リストあたりのアイテムの平均数が 10 を超える場合です。サイズを変更してもリストの数とアイテムの数は変わらないため、ハッシュ テーブルのサイズは変更され続けます。

ハッシュ テーブルで重複キーを許可することが適切な決定であるかどうか疑問に思います。もしそうなら、上記の場合はどうすればよいでしょうか?

4

1 に答える 1

0

キーごとに複数の値を許可するハッシュテーブルが必要か、単純に上書きできるハッシュテーブルが必要かは、状況によって異なります。ハッシュテーブルの使用方法が不明な場合は、何らかのスイッチを使用して両方を提供します。

すべてのエントリが同じハッシュバケットにハッシュされるケースは予測が困難です。いずれにせよ、適切なハッシュ関数を選択することは良い投資です。ただし、一般的には、最悪のケースではなく、平均的なケースのみを最適化する必要があります。

于 2013-02-22T15:34:03.143 に答える