0

これはプレフィックスハッシュ関数です。この方法で衝突の数を数えたいのですが、どうすればよいかわかりません。簡単そうに見えますが、いい方法が思いつかない…。

int HashTable_qp::preHash(string & key, int tableSize )
{
    string pad = "AA";
    //some words in the input are less than 3 letters
    //I choose to pad the string with A because all padded characters 
    //have same ascii val, which is low, and will hopefully alter the results less
    if (key.length() < 3)
    {
        key.append(pad);
    }
    return ( key[0] + 27 * key[1] + 729 * key[2] ) % tableSize;
}
4

3 に答える 3

1

ヒストグラムを作成します。

 unsigned histogram[tablesize] = {0};

いくつかの（すべての）可能な文字列を生成し、それらのハッシュ値を計算し、それに応じてヒストグラムを更新します。

for(iter=0; iter < somevalue; iter++) {
 hashval = hashfunc( string.iterate(iter) ); // I don't know c++
 histogram[hashval] +=1;
 }

次に、塊/クラスターのハッシュテーブルを分析する必要があります。経験則では(tablesize==iter)、の場合、カウント= 1で約30％のセル、約30％が空であると予想されます。残りは2つ以上あります。

すべてを合計し(count*(count+1))/2、テーブルサイズで割ると、約1.5になるはずです。悪いハッシュ関数はより高い値を与え、完全なハッシュはcount = 1（したがって：ratio = 1）のセルのみを持ちます。線形プロービングでは、もちろんtablesize = niterを使用しないでください。ただし、tablesizeを2倍に大きくしてください。ただし、同じメトリック（プローブの数/エントリの数）を使用して、そのパフォーマンスを分析できます。

更新：ハッシュ関数とそのパフォーマンスに関する優れた紹介は、http： //www.strchr.com/hash_functionsにあります。

于 2011-12-06T00:17:18.593 に答える
1

基礎となるデータ構造と同じように int hash = preHash(&key, array.length); if(array[hash] != null) this.count++; 配列である場合: リンクされたリストの配列である場合:

if(array[hash] != null && *(array[hash]) != null)
this.count++

stl ライブラリにしかアクセスできない場合は、ハッシュ関数を呼び出した後、追加する前にその要素が null であることをテストするだけで十分だと思います。

于 2011-12-05T23:53:38.227 に答える
0

それぞれが 1 つのハッシュを表す整数の配列を作成できます。完了したら、ネストされたループで配列を介してハッシュをループバックさせます。次の配列がある場合、

[0] -> 13
[1] -> 5
[2] -> 12
[3] -> 7
[4] -> 5

0..nの各アイテムiについて、アイテムi+1..nの一致をチェックします。英語では、次のようになります。各要素がその後の要素のいずれかと等しいかどうかを確認します。

于 2011-12-05T23:49:00.100 に答える