Как рассчитать среднюю длину зонда для успеха и неудачи - Линейный зонд (Хеш-таблицы)

Question

Я выполняю задание для своего класса Data Structures. нас попросили изучить линейное зондирование с коэффициентами нагрузки .1, .2, .3, .... и .9. Формула для тестирования:

Средняя длина зонда с использованием линейного зонда примерно равна

Успех -> (1 + 1 / (1-L) ** 2) / 2
или
Отказ -> (1 + 1 (1-L)) / 2.

мы должны найти теоретическое, используя формулу выше, которую я сделал (просто включите коэффициент загрузки в формулу), затем мы должны вычислить эмпирическое (что я не совсем уверен, как это сделать). вот остальные требования

** Для каждого фактора нагрузки 10 000 случайно сгенерированных положительных целых от 1 до 50000 (включительно) будет быть вставлен в таблицу «правильный» размер, где «правильный» строго на основе коэффициента нагрузки вы тестируете Повторы разрешены. Будьте уверены, что ваша формула для случайного сгенерированные целые числа правильны. Eсть класс с именем Random в java.util. ИСПОЛЬЗОВАНИЕ Это! После таблицы справа (на основе на L) размер загружен с 10000 Ints, сделать 100 поисков недавно сгенерированные случайные числа из диапазона от 1 до 50000. Вычислить среднее длина зонда для каждого из двух формулы и указать знаменатели Например, для каждого теста для нагрузки .5 будет использоваться таблица размера>> приблизительно 20000 (с учетом премьер), а так же каждый тест для .9 нагрузки будет иметь таблицу приблизительный размер 10000 / .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)
{

}

* *} Тысяча двадцать-один

Answer 1

Следует учитывать, что HashTable в Java использует реализацию с закрытой адресацией (без зондирования), поэтому у вас есть отдельные сегменты, в которые можно поместить много элементов. Это не то, что вы ищете в своих тестах. Я не уверен в реализации HashMap, но думаю, что она также использует открытую адресацию.

Так что забудьте о классах JDK .. поскольку вы хотите вычислять эмпирические значения, вы должны написать свою собственную версию хеш-таблицы, которая использует реализацию с открытой адресацией с линейным зондированием , но вы должны позаботьтесь о подсчете длины зонда всякий раз, когда вы пытаетесь получить значение из хэш-карты.

Например, вы можете написать свою хэш-карту, а затем позаботиться о наличии

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

     return probeLength;
   }
}

Затем вы можете легко сравнить его, выполнив поиск требуемого количества клавиш и рассчитав среднюю длину зонда.

В противном случае вы можете просто предоставить hasmap возможность сохранять общую длину зонда и количество запрошенных запросов и извлекать их после запуска теста для вычисления среднего значения.

Этот вид упражнений должен доказать, что эмпирическая ценность соответствует теоретической. Поэтому примите также во внимание тот факт, что вам может понадобиться много тестов, а затем выполните среднее из всех, убедившись, что дисперсия не слишком высока.