4

事前定義されたキーが12か月である配列を検索するための完全なハッシュテーブルを作成したいとします。したがって、

hash("January")==0
hash("December")==11

月の名前をgperfで実行し、優れたハッシュ関数を取得しましたが、16個のバケット（または範囲は16個）を提供しているようです。

#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 18
/* maximum key range = 16, duplicates = 0 */

生成されたgperfコードを見ると、そのハッシュ関数コードは、256サイズのテーブルからlenとcharの値のルックアップを単純に返します。どういうわけか、私の頭の中で私は派手な見た目の機能を想像しました... :)

正確に12個のバケットが必要な場合（つまり、未使用のバケットをスキップしたくない場合）はどうなりますか？このような小さなセットの場合、それは実際には問題ではありませんが、1000個の事前定義されたキーがあり、正確に1000個のバケットを続けて必要とする場合はどうでしょうか。

これを行うための決定論的な方法を見つけることができますか？

4

2 に答える 2

4

私が知っている gperf の唯一の代替手段は cmph です: http://cmph.sourceforge.net/しかし、ジェロームがコメントで言ったように、16 個のバケットを持つことで速度が向上します。

Minimal Perfect Hasihing を最初に見たとき、CiteseerX で非常に興味深い読み物を見つけましたが、それらのソリューションの 1 つを自分でコーディングしてみようという誘惑に抵抗しました。gperf や cmph よりも劣ったソリューションになってしまうことはわかっています。または、ソリューションが同等であると仮定しても、それに多くの時間を費やさなければならないことはわかっています。

于 2009-11-20T14:31:07.543 に答える