Cómo calcular la duración media de la sonda para el éxito y el fracaso - sonda lineal (Tablas Hash) [cerrada]

Question

Estoy haciendo un trabajo para mi clase de estructuras de datos. nos pidieron a estudio sondeo lineal con factores de carga de 0,1, 0,2, 0,3, ...., y 0.9. La fórmula para la prueba es:

La duración media de la sonda usando el sondeo lineal es aproximadamente

Éxito -> (1 + 1 / (1-L) ** 2) / 2
o
El no -.> (1 + 1 (1-L)) / 2

estamos obligados a encontrar el teórico utilizando la fórmula anterior que hice (sólo tiene que enchufar el factor de carga en la fórmula), entonces tenemos que calcular el empírica (que no lo bastante seguro de cómo hacerlo). aquí está el resto de los requisitos

  

** Para cada factor de carga, 10.000 enteros positivos generados aleatoriamente   entre 1 y 50000 (inclusive) voluntad   ser insertado en una mesa de la   tamaño "correcto", en el "derecho" es   estrictamente basado en el factor de ocupación   que está probando. se permiten repeticiones.   Asegúrese de que su fórmula de azar   ints generados es correcta. Hay un   clase llamada aleatoria en java.util. UTILIZAR   ¡eso! Después de una tabla de la derecha (basada   sobre L) tamaño se carga con 10 000   enteros, hacen 100 búsquedas de nuevo   enteros aleatorios generados a partir de la gama   de 1 a 50000. calcular el promedio   longitud de la sonda para cada uno de los dos   fórmulas e indicar los denominadores   utilizado en cada calculationSo, por ejemplo, cada prueba para una carga de 0,5 tendría una tabla de>> Tamaño   aproximadamente 20.000 (ajustado para ser   primo) y del mismo modo cada prueba para una   0.9 carga tendría una tabla de   tamaño aproximado 10000 / 0.9 (de nuevo   ajustado a ser primer).

     

El programa debe funcionar mostrando el   diversos factores de carga probados, la   sonda promedio para cada búsqueda (los dos   denominadores utilizados para calcular la   promedios se sumará a 100), y el   respuestas teóricas utilizando la fórmula   encima. . **

¿Cómo se calcula el éxito empírico?

aquí es mi código hasta ahora:

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

Se debe tener en cuenta que HashTable de Java utiliza un sistema cerrado de direccionamiento (Sin sonda) la aplicación, por lo que tiene cubos separados en los que muchos artículos se pueden colocar. Esto no es lo que busca en sus puntos de referencia. No estoy seguro acerca de la aplicación HashMap pero creo que utiliza direccionamiento abierto también.

Así que olvídate de las clases de JDK .. ya que desea calcular los valores empíricos debe escribir su propia versión de una tabla hash que utiliza el direccionamiento abierto aplicación con sondeo lineal , pero se debe tener cuidado de contar la longitud de la sonda cada vez que se intenta obtener un valor del mapa hash ..

Por ejemplo, usted puede escribir su HashMap y luego cuidar de tener

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

     return probeLength;
   }
}

A continuación, usted puede fácilmente mediante la búsqueda de referencia que el número de teclas que desea y el cálculo de la duración media de la sonda.

De lo contrario, puede simplemente proporcionar a la hasmap la capacidad de almacenar la longitud total de la sonda y el recuento de obtiene solicitado y recuperarlos después de la ejecución de referencia para el cálculo de valor medio.

Este tipo de ejercicios debe probar que los concordatos valor empírico con la teórica. Así que tener también en cuenta el hecho de que es posible que tenga muchos puntos de referencia, y luego hacer la media de todos ellos, asegurando que la varianza no es demasiado alto.