檢索用於線性/二次哈希的探針長度

我的任務處理散列並使用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

檢索用於線性/二次哈希的探針長度

回答

相關問題