成功と失敗の平均プローブ長計算する方法 - リニアプローブ（ハッシュテーブル）[閉鎖]

StackOverflow https://stackoverflow.com/questions/2564090

  •  23-09-2019
  •  | 
  •  

質問

私は私のデータ構造クラスの割り当てをやっています。我々は、0.1、0.2、0.3、...、および0.9の負荷因子とプロービングリニア研究にするように求めていました。試験のための式は：

はプロービング線形用いて平均プローブ長はおおよそである

サクセス - >（1 + 1 /（1-L）** 2）/ 2
または
故障 - >（1 + 1（1-L））/ 2

私たちは、私が（ちょうど式で負荷率をプラグ）でした上記の式を使用して理論を見つけることが必要であり、我々は（私はないかなり確実で行う方法）経験を計算する必要があります。ここでの要件の残りの部分がある。

  

**各負荷率については、万個のランダムに生成された正のint   1〜50000（両端を含む）の意志   のテーブルに挿入されます   「右」サイズ、「右」であります   厳密に負荷率に基づいて   あなたがテストしています。反復が許可されています。   必ずそのランダムのためのあなたの式   生成されたint型は正しいです。 aがあります   java.utilのランダムと呼ばれるクラス。つかいます   それ！右の表の後（ベース   L時）サイズは、万がロードされています   int型は、新規の100件の検索を行います   範囲から生成されたランダムint型   1計算50000までの平均の   両者のそれぞれのためのプローブの長さ   式と分母を示しています   各calculationSoで使用される、例えば、0.5荷重に対する各試験は、>>サイズのテーブルを有するであろう   約2万（になるように調整   プライム）とAについて同様に各試験   0.9負荷がのテーブルを持っているでしょう   おおよそのサイズ万/ 0.9（再び   ）プライムなるように調整します。

     

プログラムが表示する実行する必要があります   様々な負荷要因は、テスト   各検索の平均プローブ（二   計算するために使用される分母   平均値）は100に追加し、します   式を使用して理論的な答え   上記。 。**

私は経験的成功を計算する方法を教えてください。

ここに私のコードは、これまででます：

import java.util.Random;
/**
 *
 * @author Johnny
 */
class DataItem
{
    private int iData;
    public DataItem(int it)
    {iData = it;}
    public int getKey()
    {
        return iData;
    }
}

class HashTable
{
private DataItem[] hashArray;
private int arraySize;
public HashTable(int size)
{
    arraySize = size;
    hashArray = new DataItem[arraySize];
}
public void displayTable()
{
    int sp=0;
    System.out.print("Table: ");
    for(int j=0; j<arraySize; j++)
{
    if(sp>50){System.out.println("");sp=0;}

    if(hashArray[j] != null){
        System.out.print(hashArray[j].getKey() + " ");sp++;}
    else
    {System.out.print("** "); sp++;}
}
    System.out.println("");
}

public int hashFunc(int key)
{
    return key %arraySize;
}

public void insert(DataItem item)
{
    int key = item.getKey();
    int hashVal = hashFunc(key);

    while(hashArray[hashVal] != null &&
                    hashArray[hashVal].getKey() != -1)
    {
        ++hashVal;
        hashVal %= arraySize;
    }
    hashArray[hashVal]=item;
}
public int hashFunc1(int key)
{
    return key % arraySize;
}

public int hashFunc2(int key)
{
// non-zero, less than array size, different from hF1
// array size must be relatively prime to 5, 4, 3, and 2
    return 5 - key % 5;
}


public DataItem find(int key) // find item with key
// (assumes table not full)
    {
    int hashVal = hashFunc1(key); // hash the key
    int stepSize = hashFunc2(key); // get step size
    while(hashArray[hashVal] != null) // until empty cell,
    { // is correct hashVal?
        if(hashArray[hashVal].getKey() == key)
            return hashArray[hashVal]; // yes, return item
        hashVal += stepSize; // add the step
        hashVal %= arraySize; // for wraparound
    }
    return null; // can’t find item
    }
}
public class n00645805 {
/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    double b=1;
    double L;
    double[] tf = new double[9];
    double[] ts = new double[9];
    double d=0.1;
    DataItem aDataItem;
    int aKey;
    HashTable h1Table = new HashTable(100003); //L=.1
    HashTable h2Table = new HashTable(50051);  //L=.2
    HashTable h3Table = new HashTable(33343);  //L=.3
    HashTable h4Table = new HashTable(25013);  //L=.4
    HashTable h5Table = new HashTable(20011);  //L=.5
    HashTable h6Table = new HashTable(16673);  //L=.6
    HashTable h7Table = new HashTable(14243);  //L=.7
    HashTable h8Table = new HashTable(12503);  //L=.8
    HashTable h9Table = new HashTable(11113);  //L=.9

    fillht(h1Table);
    fillht(h2Table);
    fillht(h3Table);
    fillht(h4Table);
    fillht(h5Table);
    fillht(h6Table);
    fillht(h7Table);
    fillht(h8Table);
    fillht(h9Table);
    pm(h1Table);
    pm(h2Table);
    pm(h3Table);
    pm(h4Table);
    pm(h5Table);
    pm(h6Table);
    pm(h7Table);
    pm(h8Table);
    pm(h9Table);

    for (int j=1;j<10;j++)
    {
        //System.out.println(j);
        L=Math.round((b-d)*100.0)/100.0;
        System.out.println(L);
        System.out.println("ts "+(1+(1/(1-L)))/2);
        System.out.println("tf "+(1+(1/((1-L)*(1-L))))/2);
        tf[j-1]=(1+(1/(1-L)))/2;
        ts[j-1]=(1+(1/((1-L)*(1-L))))/2;
        d=d+.1;
    }
    display(ts,tf);
}
public static void fillht(HashTable a)
{
    Random r = new Random();
    for(int j=0; j<10000; j++)
    {
        int aKey;
        DataItem y;
        aKey =1+Math.round(r.nextInt(50000));
        y = new DataItem(aKey);
        a.insert(y);

    }
}
public static void pm(HashTable a)
{
    DataItem X;
    int numsuc=0;
    int numfail=0;
    int aKey;
    Random r = new Random();
    for(int j=0; j<100;j++)
    {
        aKey =1+Math.round(r.nextInt(50000));
        X = a.find(aKey);
        if(X != null)
        {
            //System.out.println("Found " + aKey);
            numsuc++;
        }
        else
        {
            //System.out.println("Could not find " + aKey);
            numfail++;
        }

    }
    System.out.println("# of succ is "+ numsuc+" # of failures is "+ numfail);
}
public static void display(double[] s, double[] f)
{

}

}

役に立ちましたか？

解決

あなたは多くの項目を配置することができる別のバケツを持っているので、JavaのHashTableは、閉じられたアドレッシング（なしプロービング）実装を使用していることを考慮に入れる必要があります。これは、あなたのベンチマークで探しているものではありません。私はHashMapの実装についてはよく分からないが、私はそれがあまりにも取り組む開い使用だと思います。

ですから、経験値を計算したいので、あなたはをプロービングリニアのとのオープン取り組むの実装を使用してハッシュテーブルの独自のバージョンを作成する必要があります。.. JDKクラスを忘れるが、あなたはハッシュマップから値を取得しようとするたびに、プローブの長さを数えるの世話をする必要があります..

あなたのハッシュマップを作成し、その後持つの世話をすることができますたとえば、

class YourHashMap
{
   int empiricalGet(K key)
   {
     // search for the key but store the probe length of this get operation

     return probeLength;
   }
}

次にすることができます簡単にあなたが望むどのように多くのキーを検索し、平均プローブ長さを算出することで、ベンチマークを。

それ以外の場合はあなただけhasmapに総プローブの長さを格納する能力と要求されますの数を提供し、平均値を算出するためのベンチマークの実行後にそれらを取得することができます。

演習のこの種の理論的な1と経験値のconcordatesことを証明しなければなりません。だから、アカウントにもたくさんのベンチマークを必要とするかもしれないという事実を取り、その後、すべてのそれらの平均を行い、分散が高すぎないことを保証します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top