comment calculer la longueur moyenne de la sonde de succès et d'échec - sonde linéaire (des tables de hachage) [fermée]

Question

Je fais une mission pour ma classe Structures de données. on nous a demandé d'étudier linéaire de sondage avec des facteurs de charge de 0,1, 0,2, 0,3, .... et .9. La formule pour le test est:

La longueur moyenne de la sonde à l'aide de palpage linéaire est à peu près

Réussite -> (1 + 1 / (1-L) ** 2) / 2
ou
Le non -> (1 + 1 (1-L)) / 2
.
nous devons trouver la théorie en utilisant la formule ci-dessus que je ne (fiche que le facteur de charge dans la formule), alors nous devons calculer l'empirique (que je pas tout à fait sûr de savoir comment faire). voici le reste des exigences

  

** Pour chaque facteur de charge, 10.000 ints positifs générés au hasard   entre 1 et 50000 (inclus) seront   être insérée dans une table de la   taille « droit », où « droit » est   strictement en fonction du facteur de charge   vous testez. Répète sont autorisés.   Assurez-vous que votre formule au hasard   ints généré est correct. Il y a un   classe appelée aléatoire dans java.util. UTILISATION   il! Après une table du droit (base   taille à L) est chargé avec 10 000   ints, faire 100 recherches de nouvelles   ints générés au hasard dans la gamme   de 1 à 50000. Calculer la moyenne   longueur de la sonde pour chacun des deux   formules et indiquent les dénominateurs   utilisé dans chaque calculationSo, par exemple, chaque test pour une charge 0,5 aurait une table de>> Taille   environ 20 000 (ajusté pour être   premier) et de même chaque test pour   .9 charge aurait une table de   taille approximative 10 000 / 0,9 (encore une fois   ajusté pour être premier).

     

Le programme doit exécuter l'affichage de la   divers facteurs de charge testés, le   Sonde moyenne pour chaque recherche (les deux   dénominateurs utilisés pour calculer la   moyennes seront à 100), et   réponses théoriques à l'aide de la formule   au dessus de. . **

Comment calculer le succès empirique?

voici mon code jusqu'à présent:

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)
{

}

}

Answer 1

Vous devez prendre en compte que la HashTable Java utilise un adressage fermé (pas de sondage) la mise en œuvre, de sorte que vous avez des seaux séparés dans lesquels peuvent être placés de nombreux articles. Ce n'est pas ce que vous cherchez dans vos repères. Je ne suis pas sûr de la mise en œuvre de HashMap mais je pense qu'il utilise l'adressage ouvert aussi.

Alors oubliez les classes .. JDK puisque vous voulez calculer les valeurs empiriques que vous devez écrire votre propre version d'une table de hachage qui utilise le adressage ouvert mise en œuvre avec linéaire sondage mais vous devez prendre soin de compter la longueur de la sonde chaque fois que vous essayez d'obtenir une valeur de la table de hachage ..

Par exemple, vous pouvez écrire votre hashmap puis prendre soin d'avoir

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

     return probeLength;
   }
}

Ensuite, vous pouvez comparer facilement en recherchant le nombre de touches que vous voulez et le calcul de la longueur de la sonde moyenne.

Sinon, vous pouvez simplement fournir la hasmap la capacité de stockage de la longueur totale de la sonde et le nombre de demande et obtient les récupérer après la course de référence pour calculer la valeur moyenne.

Ce genre d'exercices doit prouver que la valeur empirique concordats avec le théorique. Alors, prenez également en compte le fait que vous pouvez avoir besoin de nombreux points de repère, puis faire la moyenne de tous, assurant que la variance est pas trop élevé.