java - Java : このハッシュテーブル関数をより大規模に動作させる方法

Question

次のコードがあります。これは、30 個の文字列 (数値) を取り、"%29" で計算した後、それらをハッシュテーブルに入れます。

import java.util.Arrays;


public class HashFunction {

    String[] theArray;
    int arraySize;
    int itemsInArray = 0;

    public static void main(String[] args) {

        HashFunction theFunc = new HashFunction(30); // this is where you should be able to control the number of spaces availble in the hash table!!!

        // Simplest Hash Function

        // String[] elementsToAdd = { "1", "5", "17", "21", "26" };

        // theFunc.hashFunction1(elementsToAdd, theFunc.theArray);

        // Mod Hash Function
        // This contains exactly 30 items to show how collisions
        // will work

        String[] elementsToAdd2 = { "100", "510", "170", "214", "268", "398",
                "235", "802", "900", "723", "699", "1", "16", "999", "890",
                "725", "998", "978", "988", "990", "989", "984", "320", "321",
                "400", "415", "450", "50", "660", "624" };

        theFunc.hashFunction2(elementsToAdd2, theFunc.theArray);

        // Locate the value 660 in the Hash Table

        //theFunc.findKey("660");

        theFunc.displayTheStack();

    }

    // Simple Hash Function that puts values in the same
    // index that matches their value

    public void hashFunction1(String[] stringsForArray, String[] theArray) {

        for (int n = 0; n < stringsForArray.length; n++) {

            String newElementVal = stringsForArray[n];

            theArray[Integer.parseInt(newElementVal)] = newElementVal;

        }

    }



    public void hashFunction2(String[] stringsForArray, String[] theArray) {

                        int sumOfCollisions = 0;
                        float averageOfCollisions = 0;
                        int numberOfCollisions = 0;                        

        for (int n = 0; n < stringsForArray.length; n++) {

            String newElementVal = stringsForArray[n];

            // Create an index to store the value in by taking
            // the modulus

            int arrayIndex = Integer.parseInt(newElementVal) % 29;

            System.out.println("Modulus Index= " + arrayIndex + " for value "
                    + newElementVal);

            // Cycle through the array until we find an empty space


            while (theArray[arrayIndex] != "-1") {
                ++arrayIndex;
                                numberOfCollisions++;

                //System.out.println("Collision Try " + arrayIndex + " Instead");
                                //System.out.println("Number of Collisions = " + numberOfCollisions);
                // If we get to the end of the array go back to index 0

                arrayIndex %= arraySize;
            }


                        if (numberOfCollisions > 0)
                        {
                            System.out.println("                       Number of Collisions = " + numberOfCollisions);
                        }                       

            theArray[arrayIndex] = newElementVal;

        }

                        sumOfCollisions += numberOfCollisions;

                        averageOfCollisions = sumOfCollisions / 30;

                        System.out.println("Sum of Collisions = " + sumOfCollisions);

                        System.out.println("Average of Collisions = " + averageOfCollisions);                

    }

    // Returns the value stored in the Hash Table

    public String findKey(String key) {

        // Find the keys original hash key
        int arrayIndexHash = Integer.parseInt(key) % 29;

        while (theArray[arrayIndexHash] != "-1") {

            if (theArray[arrayIndexHash] == key) {

                // Found the key so return it
                System.out.println(key + " was found in index "
                        + arrayIndexHash);

                return theArray[arrayIndexHash];

            }

            // Look in the next index

            ++arrayIndexHash;

            // If we get to the end of the array go back to index 0

            arrayIndexHash %= arraySize;

        }

        // Couldn't locate the key

        return null;

    }

    HashFunction(int size) {

        arraySize = size;

        theArray = new String[size];

        Arrays.fill(theArray, "-1");

    }

    public void displayTheStack() {

        int increment = 0;

        for (int m = 0; m < 3; m++) {

            increment += 10;

            for (int n = 0; n < 71; n++)
                System.out.print("-");

            System.out.println();

            for (int n = increment - 10; n < increment; n++) {

                System.out.format("| %3s " + " ", n);

            }

            System.out.println("|");

            for (int n = 0; n < 71; n++)
                System.out.print("-");

            System.out.println();

            for (int n = increment - 10; n < increment; n++) {

                if (theArray[n].equals("-1"))
                    System.out.print("|      ");

                else
                    System.out
                            .print(String.format("| %3s " + " ", theArray[n]));

            }

            System.out.println("|");

            for (int n = 0; n < 71; n++)
                System.out.print("-");

            System.out.println();

        }

    }

}

便宜上、出力は次のとおりです。

    run:
Modulus Index= 13 for value 100
Modulus Index= 17 for value 510
Modulus Index= 25 for value 170
Modulus Index= 11 for value 214
Modulus Index= 7 for value 268
Modulus Index= 21 for value 398
Modulus Index= 3 for value 235
Modulus Index= 19 for value 802
Modulus Index= 1 for value 900
Modulus Index= 27 for value 723
Modulus Index= 3 for value 699
                       Number of Collisions = 1
Modulus Index= 1 for value 1
                       Number of Collisions = 2
Modulus Index= 16 for value 16
                       Number of Collisions = 2
Modulus Index= 13 for value 999
                       Number of Collisions = 3
Modulus Index= 20 for value 890
                       Number of Collisions = 3
Modulus Index= 0 for value 725
                       Number of Collisions = 3
Modulus Index= 12 for value 998
                       Number of Collisions = 3
Modulus Index= 21 for value 978
                       Number of Collisions = 4
Modulus Index= 2 for value 988
                       Number of Collisions = 7
Modulus Index= 4 for value 990
                       Number of Collisions = 9
Modulus Index= 3 for value 989
                       Number of Collisions = 14
Modulus Index= 27 for value 984
                       Number of Collisions = 15
Modulus Index= 1 for value 320
                       Number of Collisions = 23
Modulus Index= 2 for value 321
                       Number of Collisions = 31
Modulus Index= 23 for value 400
                       Number of Collisions = 31
Modulus Index= 9 for value 415
                       Number of Collisions = 37
Modulus Index= 15 for value 450
                       Number of Collisions = 40
Modulus Index= 21 for value 50
                       Number of Collisions = 43
Modulus Index= 22 for value 660
                       Number of Collisions = 47
Modulus Index= 15 for value 624
                       Number of Collisions = 61
Sum of Collisions = 61
Average of Collisions = 2.0
-----------------------------------------------------------------------
|   0  |   1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |   9  |
-----------------------------------------------------------------------
| 725  | 900  |   1  | 235  | 699  | 988  | 990  | 268  | 989  | 320  |
-----------------------------------------------------------------------
-----------------------------------------------------------------------
|  10  |  11  |  12  |  13  |  14  |  15  |  16  |  17  |  18  |  19  |
-----------------------------------------------------------------------
| 321  | 214  | 998  | 100  | 999  | 415  |  16  | 510  | 450  | 802  |
-----------------------------------------------------------------------
-----------------------------------------------------------------------
|  20  |  21  |  22  |  23  |  24  |  25  |  26  |  27  |  28  |  29  |
-----------------------------------------------------------------------
| 890  | 398  | 978  | 400  |  50  | 170  | 660  | 723  | 984  | 624  |
-----------------------------------------------------------------------
BUILD SUCCESSFUL (total time: 0 seconds)

ご覧のとおり、この特定のハッシュテーブルを構築するときに発生した衝突の平均回数を教えてくれるように設定しました。30 個の数字と 30 個のスペースがあります。使用可能なスペースの量のパラメータを 30 から 60 に変更しようとしましたが、何も変わりませんでした。これを修正する方法を見つけたいと思います。

このコードをワンランク上のものにしたいので、これは私にとって重要です。このプログラムをより大きな数のセット、おそらく1000以上の数で試してみたいと思いますが、1000以上の文字列番号を手動で入力したくありません。これを行うループをどのように記述すればよいでしょうか? たとえば、パラメーターに 1000 を入力すると、使用される文字列表記 (コードで見られるように) で 1000 の数字が生成されます。

また、これらの文字列番号を 1 回のプログラム実行で複数実行できるようにしたいと考えています。たとえば、ハッシュテーブルは1000個の数値を保持できるため、1つの数値、次に2、3などでプログラムを実行し、1000まで実行します。そして、これを実行するたびに、その特定の実行で発生した衝突の平均数を出力したい。数が 1 つだけの場合は衝突は発生せず、最終的には数が増えるにつれて衝突が発生します。

これを行うことで、使用可能なスポットに対する数の比率が変化するにつれて、衝突の量がどのように変化するかを示すグラフを作成できます。たとえば、x 軸は平均衝突数であり、y 軸は使用可能な合計スペースと比較した入力数値の量の比率です (値の範囲が 0 から 1.00 になることを意味します)。

時間を割いて教えてくださったすべての方々に、事前に感謝します。ほんとうにありがとう。

score 0 · Accepted Answer

プログラムで数値をランダムに生成するには、そのサイズの配列をループして乱数を挿入する整数パラメーターを受け取るメソッドを作成する必要があります。

int size_of_hash = Integer.parseInt( args[1] );

上記のコードは、コマンドラインから引数を取得し、それを使用して、ハッシュテーブルの大きさを決定する変数を作成します。この変数を使用してハッシュ関数を作成し、それを使用して配列を作成できます

メソッドを呼び出すことができます

public int[] createRandomArray( int size ) {
    Random r = new Random(); //java.util.Random - this class will randomly generate integers for you
     int random_array = //instantiate the array

     for( int i = 0; i <= size; i++ ) {
         //insert logic
      }

      return random_array;
 }

メソッドは不完全です。学ぶための最良の方法は、実践することです。ここで注意すべき重要な点は、この方法は本質的に単純な反復タスクを取り、プログラムにそれを実行させるということです。Javadoc は、Java エコシステム内の新しいリソースについて学習するための優れたリソースです。「javadoc random」とググるだけで、クラスが表示されるはずです。

メインメソッドをクラスのコンストラクタに変更し、プログラムの引数で指定できる試行回数を呼び出すようにメインメソッドを書き直すことをお勧めします。これにより、1 回だけではなく多数の試行を実行することで、より正確なデータを取得できます。

score 0 · Accepted Answer

次を使用します。

import java.util.Random; //that's where it is.
...
...//directly to the class
private Random r = new Random();
public String randomString(int limit)
{
    int n = r.nextInt(limit);
    return n+"";
}
...

これは、 (0 ～ limit -1)String内の a の形式で乱数を返します。数字limitの文字列が必要な場合は、これを行いますn

StringBuilder s = new StringBuilder();
for(int i = 0; i < n; i++)
    s.append(r.nextInt(10));
return s.toString();

java - Java : このハッシュ テーブル関数をより大規模に動作させる方法

2 に答える 2

Related

Reference

java - Java : このハッシュテーブル関数をより大規模に動作させる方法