1

問題は解決しました (まだ回答を受け入れることができません。while ループを変更したところ、機能するようになりました。将来の視聴者のために以下に回答しました): ハッシュ アルゴリズムが原因で頭痛がします。キーのファイルから入力を読み取り、少量のキーでコードが機能します。300 ワードのようにすると、問題が発生します。ハッシュ関数は一番下にあり、この while ループはメイン関数の本体にあり、Java で記述されています。ハッシュ関数はうまく機能し、私がばかげて本体を変更して元のコードを失うまで、本体も同様に機能しました。オーバーフローの問題をカバーしたと思いますが、どんな助けでも大歓迎です、ありがとう!

tSize の計算方法:

//Calcking tSize
tSize = (int)(items*tSizeFactor);

//Making tSize prime
while(!isPrime((int)tSize))
    tSize++;

ファイルから読み取るときの while ループ:

while(line != null) {
                //Getting the address to place the value in
                position = hash(line.toCharArray(), (int)tSize);

                //If there is something there we enter the if statement
                if(hashTable[position][0] != null) {
                    //while we haven't found a spot and i < tableSize we update the last position we were at and move through the array
                    for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) {
                        //prevPosition is used to update the link in the spot just before our final destination, allows wrap around in the array
                        prevPosition = position;
                        //we add +i to the original position and modulo the table size allowing wrap around in the array
                        position = (position+i)%(int)tSize;
                    }
                    //finally when we found a spot we update the previous position to link to the new item
                    hashTable[prevPosition][1] = Integer.toString(position);
                }

                //Adding the values to the hash table and setting the link to -1
                hashTable[position][0] = new String(line);
                hashTable[position][1] = new String(Integer.toString(-1));

                line = reader.readLine();
            }

public static int hash(char ch[],final int TSIZE) {
        int sum = 7;
        for(int i = 0; i < ch.length; i++) {
            sum = sum*31+ch[i];
            sum <<= 3;
        }

        if(sum < 0)
            sum *= -1;

        return sum%TSIZE;
    }
4

3 に答える 3

0

まず、1 つの質問ですが、ビルトインのハッシュテーブルを使用しないのはなぜですか?

あなたのコードを読んで、いくつかの問題を見つけました。現在のコードからはそれ以上の情報を知ることができないため、正しくない可能性があります。例えばtSize。

  • を持っていtSizeます。ハッシュテーブルの容量だと思います。しかし、あなたがいつそれを増やしたのかわかりませんでした。これは、少なくともパフォーマンスの問題です。しかし、あなたの実装では、それは機能的な問題です。たとえば、tSize が 100 の場合、ハッシュテーブルには最大 100 個の要素を含めることができます。

  • これを for ループで見てください:

    for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) {
    prevPosition = position;
    position = (hash(line.toCharArray(), (int)tSize)+i)%((int)tSize);
}

これは、衝突が発生したときに実行されます (ハッシュ関数を再度呼び出す理由がわかりませんでした。ループして空きスロットを見つけることができます)。元の を保持しkey、空き位置を参照させます。ただし、最悪の場合、ハッシュ関数を再度呼び出した後、新しいpositionがまだ占有されている (再び衝突する) 場合は、 を上書きしprePositionて元の を失いますkey。これは、ハッシュテーブルからデータを取得するときに問題になります。

  • 以上の2点によります。ハッシュテーブルがいっぱいになると、コードは最後の要素を上書きし続けます。
于 2013-04-09T23:18:23.527 に答える
0

  1. new String(line) は役に立ちません。

  2. for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++)

    位置 0 は使用されていませんか?

  3. prevPosition は、if(hashTable[position][0] != null) {ブロックに対してローカルにすることができます。

  4. 前の位置をハッシュテーブルに保存するのは役に立たないようです。

    UPD

  5. 位置 = (位置 + i)%(int)tSize;

これを試してみてください http://en.wikipedia.org/wiki/Quadratic_probing

于 2013-04-09T23:17:55.870 に答える
0

問題を解決したwhileループを変更しました：

while(line != null) {
                    //Getting the address to place the value in
                    position = hash(line.toCharArray(), (int)tSize);

                    //If there is something there we enter the if statement
                    if(hashTable[position][0] != null) {

                        //Go to the end of the chain
                        while(hashTable[position][1].compareTo("-1") != 0)
                            position = Integer.parseInt(hashTable[position][1]);

                        //Save the position of the end of the chain
                        prevPosition = position;

                        //while we haven't found a spot and i < tableSize we update the last position we were at and move through the array
                        for(int i = 1; i < (int)tSize && hashTable[position][0] != null; i++) {
                            //we add +i to the original position and modulo the table size allowing wrap around in the array
                            position = (position+i)%(int)tSize;
                            System.out.println("Position: " + position);
                        }

                        //finally when we found a spot we update the previous position to link to the new item
                        hashTable[prevPosition][1] = Integer.toString(position);
                    }

                    //Adding the values to the hash table and setting the link to -1
                    hashTable[position][0] = new String(line);
                    hashTable[position][1] = new String(Integer.toString(-1));

                    line = reader.readLine();
                }
于 2013-04-10T01:29:32.740 に答える