如何计算为成功和失败的平均探针长度 - 线性探针(哈希表)[关闭]
-
23-09-2019 - |
题
我在做我的数据结构类的任务。我们被要求对研究线性与.1 .2,.3,...,和0.9客座率探测。用于测试的公式是:
使用线性探测的平均探针长度大约是
成功 - >(1 + 1 /(1-L)** 2)/ 2 点击或点击 故障 - >(1 + 1(1-L))/ 2,点击 点击 我们必须找到使用上面,我没有(只需将公式中的负载因数)公式的理论,那么我们要计算的经验(我不太清楚该怎么做)。这里是要求的其余部分
**对于每个负载系数,万个随机生成的正整数 1到50000(含)之间的意愿 被插入的一个表 “正确”的大小,其中“右”是 严格基于负载因子 您正在测试。重复是允许的。 确保您的公式随机 产生整数是正确的。有一个 java.util中的类名为随机。采用 它!右表后(基于 在L)尺寸装有万 整型,做的新100个搜索 从范围产生的随机整数 的1〜50000计算平均 用于两个的探针长度 公式并注明分母 在每个calculationSo使用,例如,每个测试为0.5负载将具有>>大小的表 大约20,000(调整为 素),同样每次测试的 0.9负荷将有一个表 大小约为10,000 / 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类..因为你要计算你应该写自己的哈希表的版本,经验值,它使用的开放地址的实施与线性探测的,但每当你尝试从HashMap中的值,你应该采取计数探头长度的照顾..
例如,你可以写你的HashMap,然后采取有照顾
class YourHashMap
{
int empiricalGet(K key)
{
// search for the key but store the probe length of this get operation
return probeLength;
}
}
然后,您可以通过搜索你想要多少个键并计算平均值探头长度容易基准它。
否则你可以提供hasmap存储总探针长度的能力和被请求的计数和基准测试后进行检索,计算平均值。
这种练习必须证明与理论经验值concordates。因此,也考虑到这个事实,你可能需要很多的基准,然后做平均他们全部,确保方差不太高。