检索用于线性/二次哈希的探针长度

我的任务处理散列并使用Horner多项式创建哈希函数。对于线性探测，我必须使用（1 + 1 /（1-L）** 2）/ 2（Usuccessful）或（1 + 1 /（1-L））/ 2（成功）计算出理论探针长度，然后对于与二次探测相对应的正确方程也是如此。然后，我必须将理论值与载荷因子0.1至0.9的实验值进行比较。我正在使用查找方法并搜索100个随机整数来获取实验数据。我遇到的问题是，一旦查找成功或失败，我无法获得正确的probeLength值。检索用于线性/二次哈希的探针长度

我创建了10000个随机整数来填充，然后我将搜索100个随机整数。

for(i = 0; i<10000; i++) 
{ 
int x = (int)(java.lang.Math.random() * size); 
randomints.add(x); 
} 
//Make arraylist of 10000 random ints to fill 

for(p = 0; p<100; p++) 
{ 
int x = (int)(java.lang.Math.random() * size); 
randomintsfind.add(x); 
}

后来我有一个循环，做了这个发现并记录了查找成功或失败的次数。这部分工作。它也应该追踪每个查找的probeLength，然后将它们全部加在一起，以便可以分别通过成功或失败的次数来分割，以找出平均值。那是我遇到问题的地方。 probeLength未被正确检索，我不知道为什么。

这是调用find方法并跟踪这些变量以及创建和填充的代码部分。

HashTableLinear theHashTable = new HashTableLinear(primesize); 

    for(int j=0; j<randomintscopy.length; j++)  // insert data 
     { 
     //aKey = (int)(java.lang.Math.random() * size);         
     aDataItem = new DataItem(randomintscopy[j]); 
     theHashTable.insert(aDataItem); 
     } 



for(int f = 0; f < randomintsfindcopy.length;f++) 
    { 

     aDataItem = theHashTable.find(randomintsfindcopy[f]); 
     if(aDataItem != null) 
     { 
     linearsuccess += 1; 
     experimentallinearsuccess += theHashTable.probeLength;    
     theHashTable.probeLength = 0;    
     } 
     else 
     { 
     linearfailure += 1; 
     experimentallinearfailure += theHashTable.probeLength; 
     theHashTable.probeLength = 0; 
     }  

    }

然后在HashTableLinear类

public DataItem find(int key) // find item with key 
    { 
    int hashVal = hashFunc(key); // hash the key 
    probeLength = 1; 
    while(hashArray[hashVal] != null) // until empty cell, 
    {        // found the key? 
    if(hashArray[hashVal].getKey() == key) 
     return hashArray[hashVal]; // yes, return item 
    ++hashVal;      // go to next cell 
    ++probeLength; 
    //System.out.println("Find Test: " + probeLength);     
    hashVal %= arraySize;  // wraparound if necessary 
    } 
    return null;     // can't find item 
    }

当我测试印刷在查找方法的probeLength值和在环调用find得到的值是彼此不同的查找方法。

来源

2014-04-01 Fluxxxy

我意识到我在想这个太难。它通过创建一个getter和一个setter来解决它，然后在找到或未找到该项目后设置该值，然后使用getter检索值。

来源

2014-04-01 20:34:06 Fluxxxy

检索用于线性/二次哈希的探针长度

回答

相关问题