0

私が今取っているデータ構造とアルゴリズムのクラスは、アルゴリズムがどのように機能するかについての多くのペンと紙の理解ですが、実際のコーディングはほとんどありません. 私はプログラミング初心者なので、これはばかげた質問かもしれません。

概念的には、ハッシュとさまざまな方法の理由を理解していますが、この割り当てをコーディングする方法についてはわかりません。

基本的に、必要なソース コードを使用できます。本のコードは、 http: //users.cis.fiu.edu/~weiss/dsaajava3/code/SeparateChainingHashTable.javaおよびhttp://users.cis.fiu.edu/~weiss/dsaajava3/code/QuadraticProbingHashTable です。ジャワ

これらのコードのいずれかを使用すると、キーをテーブルに挿入するのに問題があるようです。このブロックを使用して挿入しています：

Random randomGenerator = new Random();
int randomInt = randomGenerator.nextInt(99999);
for (int i = 0; i < 100; i++) {
    H.insert(""+randomInt);
}

これは実際にはテーブルに何も挿入していないように見えますが、挿入の量にかかわらずサイズは一定のままです。また、必要なプローブの数を決定する方法もわかりません。

4

1 に答える 1

1 
Random randomGenerator = new Random();

for (int i = 0; i < 100; i++) {
    int randomInt = randomGenerator.nextInt(99999);
    H.insert(""+randomInt);
}

これを試してみてください。1行が悪い場所にあります。

プロービングの場合：

/**
     * Method that performs quadratic probing resolution.
     * @param x the item to search for.
     * @return the position where the search terminates.
     */
    private int findPos( AnyType x )
    {
        int offset = 1;
        int currentPos = myhash( x );

        while( array[ currentPos ] != null &&
                !array[ currentPos ].element.equals( x ) )
        {
            currentPos += offset;  // Compute ith probe
            offset += 2;
            if( currentPos >= array.length )
                currentPos -= array.length;
        }

        return currentPos;
    }

私が正しく理解していれば、このメソッドはプロービングを実行していますか? したがって、このメソッドが呼び出された回数を、重複する場合と重複しない場合の 2 つのオプションでカウントする必要があります。追加された現在の要素が重複し、2 つの整数である場合は、いくつかのフラグを使用します。このメソッドではif、フラグをチェックするために追加し、カウンターの 1 つを増やします。プローブの数があります。

編集：

[LIN-np]: 非素数テーブルサイズ 1000 の線形探索 [LIN-p]: 素数テーブルサイズ 1019 の線形探索。1019 は minPrime(1000)、つまり、 1000. [QDR-p]: 素数テーブル サイズ 1019 の二次プロービング [DBL-p]: 素数テーブル サイズ 1019 のダブル ハッシュと素数 97 の衝突解決ハッシュ。

プロービングを使用する HashTable を使用し、プロービングの量 (平均) をテストする必要があります。に 2 次プロービング アルゴリズムがありpublic class QuadraticProbingHashTable<AnyType>ます。また、ハッシュ テーブルの長さを 1019 に設定する必要があります。最初の演習では、線形プローブを使用する必要があります。したがって、基本的には、要素の追加を開始するときに、指定された前提条件で HashTables を使用する必要があります。

これは線形プロービング アルゴリズムです。

これはダブルハッシュアルゴリズムです

これをハッシュ テーブルに実装し、それが何回使用されるかを確認する必要があります。生成される衝突の数が何らかの形で表示されると思います。ハッピーコーディング。二次アルゴリズムが完了しました。前提条件を設定するだけです) (ハードコードの開始値を 1019 に設定)。

于 2014-11-18T21:46:25.817 に答える