線性探測散列函數不工作？

Question

我的線性探測功能有什麼問題？

bool HashTable_lp::insert(const string & x) 
{ 
    // Insert x as active 
    int currentPos = findPos(x); 
    if(isActive(currentPos)) 
     return true; 
    array[ currentPos ] = HashEntry(x, ACTIVE); 

    if(++currentSize > array.size()/2) 
     rehash(); 
    return false; 
} 

Answer 1

您通常需要一個while循環，直到找到空插槽。另一個問題是，你將一個單元格的字符串散列化爲活動狀態，意味着單元格包含的值與要插入的值相同。一般來說，您需要檢查您的密鑰的值以針對現有條目插入。這可能是值得做的插件版本，不支持這樣做檢查，用戶可以在保證產品尚未在哈希表，以避免這些比較的情況下...

bool HashTable_lp::insert(const string & x) 
{ 
    // Insert x as active 
    int currentPos = findPos(x); 
    while(isActive(currentPos)){ 
     // here key gets out of array[currentPos] the string key 
     if(key(currentPos)==x) return true; // already in hash 
     currentPos++; // linearly probe to next guy 
    } 
    // at this point we know currentPos is empty 
    array[ currentPos ] = HashEntry(x, ACTIVE); 

    if(++currentSize > array.size()/2) // ensure load factor is .5 to guarantee probing works! 
     rehash(); 
    return false; 
}