C++でベクタを使用するハッシュテーブル検索関数

Question

ベクトルを使用してハッシュテーブルを作成しようとしていますか、または構造体を持つテーブルを使用するのが最善でしょうか？

vector<int>*hashtable = new vector<int>[m]; 

    for(int i = 0; i<N; i++){ 
     temp = T1[i] % m; 
     hashtable[temp].push_back(T1[i]); 


    for (int i = 0; i <= T2[0]; i++){ 
     valuefound = 0; 
    std::vector<int>::iterator it; 
    for (it = hashtable[i].begin(); it != hashtable[i].end(); ++it){ 
     if(T2[i+1] == *it){ 
      T3HS[i] = i; 
      valuefound = 1; 
      } 
     } 

} 

Answer 1

質問は次のようによく言い換えることができます。両方のテーブルに2つの値が存在するためです。 T3HSが見つかった要素のインデックスを保持しようとしているようです。

はあなたのコード：

for (int i = 0; i <= T2.length(); i++){ 
} 

Answer 2

がNまたはN+1ハッシュテーブルのベクトルがありますが、あなたはそれらだけのT2[0]を見ている：ベクトルをループし

for (int i = 0; i <= T2[0]; i++){ 
} 

は、私はいつも使用しています。 iがT2[0]とき

ところで、検索パターンループはT2[i+1]でT2配列の末尾を越えてアクセスします。

Answer 3

私と一緒にそこに着くためにしばらく時間がかかる。

for (int i = 0; i < N; i++) 
{ 
    temp = T1[i] % m; 
    hashtable[temp].push_back(T1[i]); 
} 

ビンに番号をソートして格納します。 Groovy。ここに問題はありません。しかし、これは：

std::vector<int>::iterator it; 
    for (it = hashtable[i].begin(); it != hashtable[i].end(); ++it) 
    { 
     if (T2[i + 1] == *it) 
     { 
      T3HS[i] = i; 
      valuefound = 1; 
     } 
    } 

数字のビンは表示されません。それは場所のすべてを見ている。あなたがしたいことは、正しいビンを見ることです。

int searchval = T2[i + 1]; // cache the number we're looking for. Easier debugging 
    int binindex = searchval % m; // get the bin for this number 
    std::vector<int>::iterator it; 
    // now we look just in that one bin. 
    for (it = hashtable[binindex].begin(); it != hashtable[binindex].end(); ++it) 
    { 
     if (searchval == *it) 
     { 
      T3HS[i] = i; 
      valuefound = 1; 
      break;// found it . Stop looking. 
     } 
    } 

はこの後少し改善のトンがあります：範囲ベースのforループ

int searchval = T2[i + 1]; 
    int binindex = searchval % m; 
    for (int val: hashtable[binindex]) 
    { 
     if (searchval == val) 
     { 
      T3HS[i] = i; 
      valuefound = 1; 
      break; 
     } 
    } 

次と

スタート、検索アルゴリズムを切り出し、独自の機能でそれを置きます。これはvaluefoundのような籾殻を取り除きます。この関数は、値が見つかったかどうかを返します。関数は、1つのことと1つのことだけを行う必要があります。時にはその1つのことが他の多くの機能を集約しています。まず、検索機能の中にハッシュテーブルを構築するwhtyを考えてみましょう。ハッシュテーブルを作成する関数とそれを検索する関数を持つ方が理にかなっています。どちらの機能も1つだけです。追加ボーナスとして、それらを分割することは、複数の検索のためにハッシュテーブルを再利用できることを意味します。

bool search (int searchval, vector<int>*hashtable, int m) 
{ 
    int binindex = searchval % m; 
    for (int val: hashtable[binindex]) 
    { 
     if (searchval == val) 
     { 
      return true; 
     } 
    } 
    return false; 
} 

と

for (int i = 0; i <= T2[0]; i++) 
{ 
    if (search(T2[i+1], hashtable, m)) 
    { 
     T3HS[i] = i; 
    } 
    else 
    { 
     T3HS[i] = -1; 
    } 
} 

それを呼び出すその後、あなたはさらに少し出範囲とvectorsと

int *T3HS = new int[T2[0]]; 

と

vector<int>*hashtable = new vector<int> [m]; 

のようなメモリリークのすべてを埋めます。決してnewあなたが絶対に持っていない限り、newにはdeleteが必要です。いつでもどこで物事を削除するかは、お尻の痛みになります。コンパイラがあなたのためにそれをやりましょう。

次に、ハッシュテーブルを記述する関数とデータのグループがあります。そのすべてをhashtableクラスにまとめてください。

最後に、hashtableの使い方を考えてください。あなたはそれを簡単かつ明瞭にしたいと思っています。 T2[0]にはリストの長さが含まれていることを説明するページ長いコメントは不要で、常にリストの長さより1つ小さいものでなければなりません。誰かがそれを間違って読むことを知っているだけです。あなたは1201ProgramAlarmをその間違いを犯してしまいました。彼らはダミーではありません。あなたは長さを含む別の変数を使うほうがはるかに優れています。また、どれくらい長いか知っているので、もう一度vectorを使用してください。

使用するのが簡単になればなるほど、誤用される可能性は低くなります。すべてを可能な限り明白にする。