哈希表（線性探測）

我正在做一個使用線性探測的哈希表，當負載因子（即哈希表中輸入的元素的數量）/（哈希表的大小）超過負載因數時，我必須調整數組的大小變得大於0.5，我不得不調整大小的數組。我通過初始化包含與hashtable相關的函數的類中的指針進行大小調整。我將指針等於一個大小爲100的結構數組（結構只包含一個字符串）。每次加載因子變得大於0.5，我調整數組的大小，通過創建一個新的數組的前一個大小的兩倍，並指向新的數組的指針。我也有一個int，其中存儲當前大小的數組，並且每更新一次使用resize函數的實例。插入的元素數隨着每次調用插入函數而遞增。我是否正確地做到這一點？以下是我的代碼哈希表（線性探測）

#include <cstring> 
#include <vector> 
#include <math.h> 
#include <iomanip> 

using namespace std; 

int power(int a,int b) 
{ 
    for (int i=0;i<b;i++) 
    { 
     a*=a; 
    } 
    return a; 
}; 

struct Bucket 
{ 
    string word; 
}; 

const int size=100; 

class LProbing 
{ 
    private: 
      int a; //a constant which is used in hashing 
      int cursize; //current size of hash table 
      Bucket *Table; //pointer to array of struct 
      int loadfactor; //ratio of number of elements entered over size of hashtable 
      int n; //number of elements entered 
      Bucket table[size]; //array of structs 
    public: 
      LProbing(int A); //constant is decided by user 
      void resize(); 
      void insert(string word); 
      void Lookup(string word); 
}; 

LProbing::LProbing(int A) 
{ 
    cursize=size;     
    a=A; 
    Table=table; 
    loadfactor=0; //initially loadfactor is 0 as number of elements entered are 0 
    n=0; 
} 

void LProbing::resize() 
{ 
    cout<<"resize"<<endl; 
    loadfactor=n/cursize; //ensuring if resize needs to be done 
    if (loadfactor<=0.5) 
    { 
     return; 
    }          
    const int s=2*cursize; 
    Bucket PTable[s]; 
    for (int i=0;i<cursize;i++) 
    { 
     if (Table[i].word.empty()) 
     continue; 

     //rehashing the word onto the new array 
     string w=Table[i].word;  
     int key=0; 
     for (int j=0;j<w.size();j++) 
     { 
      unsigned char b=(unsigned char)w[j]; 
      key+=(int)power(a,i)*b; 
     } 
     key=key%(2*cursize); 
     PTable[key].word=w; //entering the word in the new array 
    } 
    Table=PTable; //putting pointer equal to new array 
    cursize=2*cursize; //doubling the current size of array 
} 

void LProbing::insert(string word) 
{ 
    cout<<"1"<<endl; 
    n++; //incrementing the number of elements entered with every call to insert 

    //if loadfactor is greater than 0.5, resize array 
    loadfactor=n/cursize; 
    if (loadfactor>0.5) 
    {    
     resize(); 
    }     
    //hashing the word 
    int k=0; 
    for (int i=0;i<word.size();i++) 
    { 
     unsigned char b=(unsigned char)word[i]; 
     int c=(int)((power(a,i))*b); 
     k+=c; 
     cout<<c<<endl; 
    } 

    int key=0; 
    key=k%cursize; 
    cout<<key<<endl; 
    //if the respective key index is empty enter the word in that slot 
    if (Table[key].word.empty()==1) 
    { 
     cout<<"initial empty slot"<<endl; 
     Table[key].word=word; 
    } 
    else //otherwise enter in the next slot 
    { 
     //searching array for empty slot 
     while (Table[key].word.empty()==0) 
     { 
     k++; 
     key=k%cursize; 
     } 
     //when empty slot found,entering the word in that bucket 
     Table[key].word=word; 
     cout<<"word entered"<<endl; 
    } 
}    

#include "Linear Probing.cpp" 
#include <fstream> 

using namespace std; 

int main() 
{ 
    LProbing H(35); 
    ifstream fin; 
    fin.open("dict.txt"); 
    vector<string> D; 

    string d; 
    while (getline(fin,d)) 
    { 
     if (!d.empty()) 
     { 
      D.push_back(d); 
     } 
    } 
    fin.close(); 
    for (int i=0;i<D.size();i++) 
    { 
     H.insert(D[i]); 
    } 
    system("PAUSE"); 
    return 0; 
}

來源

2013-04-03 digi_exp527

說服自己，它的工作（或沒有），構建了一套單元測試。 – NPE

當我在單詞文件上運行此代碼時，我有時會得到key.i的負值。我不明白爲什麼會發生這種情況，因爲我沒有減去任何東西，並且在計算它的值之前先將每個字母都轉換爲無符號字符。 –

由於否定鍵，程序會給出錯誤。 –