テンプレートクラスの合計ハッシュコリジョン数C++

Question

文字列を0〜999の整数にハッシュするテンプレートクラスを3つの異なる方法で作成しました。私はハッシュされた値とインデックス値を比較しようとしています。それらが異なる場合には、カウントに加算して、その数を合計の衝突回数で返します。私がこれを正しく一緒に投げたときに私がちょうど推測していたので、私はこれを正しくしていますか？

コード：

#include <string> 

#include <list> 

template<typename T> 
class Hash 
{ 
protected: 

    // Capacity of the hash table 
    static const size_t SIZE = 1000; 

    // Defines an entry in the hash table 
    class Entry 
    { 
    public: 
     std::string key; 
     T value; 
     bool used; 
     Entry() 
     { 
      used = false; 
      value = T(); 
     } 
    }; 

    // The hash table entries 
    Entry entries[SIZE]; 

    // Hash function #1 
    size_t hash1(const std::string& k) const; 

    // Hash function #2 
    size_t hash2(const std::string& k) const; 

    // Hash function #3 
    size_t hash3(const std::string& k) const; 

    // Calculate the hash of a given key 
    // TODO: change this to use the desired hash function 
    size_t hash(const std::string& k) const 
    { 
     return hash1(k); 
    } 

    // Perform linear probing on the given key and index to get index 
    size_t probe(const std::string& k, size_t i) const; 
public: 
    // Access data item in hash for the given key 
    T& operator[](const std::string& k); 

    void print() const 
    { 
     for (size_t i = 0; i < SIZE; i++) 
      std::cout << i << "-" << entries[i].used << "-" << entries[i].key 
        << "-" << entries[i].value << std::endl; 
    } 
    size_t collision(const std::string& k) const; 
}; 

template<typename T> 
size_t Hash<T>::hash1(const std::string& k) const 
{ 
    int index = 0; 
    for (size_t i = 0; i < k.size(); i++) 
     index += k[i]; 
    return index % SIZE; 
} 

template<typename T> 
size_t Hash<T>::hash2(const std::string& k) const 
{ 
    int index = 0; 
    for (size_t i = 0; i < k.size(); i++) 
    { 
     index += (k[i] + 27 * k[i] + 729 * k[i]); 
    } 
    return index % SIZE; 
} 

template<typename T> 
size_t Hash<T>::hash3(const std::string& k) const 
{ 
    int index = 0; 
    for (size_t i = 0; i < k.size(); i++) 
    { 
     index += 37 * index + k[i]; 
    } 
    return index % SIZE; 
} 

template<typename T> 
size_t Hash<T>::probe(const std::string& k, size_t i) const 
{ 
    int index = i; 
    int count = 0; 
    while (entries[index].used && entries[index].key != k && count < SIZE) 
     index = (index + 1) % SIZE; 
    return index; 
} 

template<typename T> 
T& Hash<T>::operator[](const std::string& k) 
{ 
    int index = hash(k); 
    if (entries[index].used && entries[index].key != k) 
     index = probe(k, index); 
    if (!entries[index].used) 
    { 
     entries[index].key = k; 
     entries[index].used = true; 
    } 
    return entries[index].value; 
} 

template<typename T> 
size_t Hash<T>::collision(const std::string& k) const 
{ 
    int count = 0; 
    for (int j = 0; j < SIZE; j++) 
    { 
     if (j == entries[j].value) 
     { 
      count++; 
     } 
    } 
    return count; 
} 

リストの大きさが一定で1000であるので、私は、ハッシュ値（エントリ[J]にその数を比較する場合、インデックス値は、このことを知る999に常に0であります.value）と同じで、値が同じで衝突があったので、カウントに加算することができます。

私の教授が「 ハッシュテーブルの各エントリを調べて、格納されているキー値のハッシュ値をテーブル内のインデックスと比較することでこれを判断できます。正直なところ、彼はそれが何を意味するのか分かりません。私はこれが完全に間違っているという強い思いがあるので、事前に謝罪するつもりです。

Answer 1

キーのハッシュは、テーブルのどこに値を入れるべきかを示します。値がキーのハッシュによって示された場所のテーブルにない場合は、衝突が発生しています。

あなたのコードは、私が見ている衝突を数えて2つの間違いを犯します：1.テーブル内の場所が使用されていないことを考慮していません。 2.キーのハッシュに対して計算やテストを行いません。私は彼が `インデックス==ハッシュ（エントリー[インデックス] .KEY）を比較するためのものだと思い

template<typename T> 
size_t Hash<T>::collision() const // doesn't seem to be any reason to pass in a key 
{ 
    size_t count = 0; // returning size_t, might as well use size_t 
         // negative collisions isn't a possibility anyway 
    for (size_t j = 0; j < SIZE; j++) // compare like datatypes where possible 
    { 
     if (entries[j].used) // can't be a collision if the location is empty 
     { 
      size_t index = hash(entries[j].key); // get correct index for key 
      if (j != index) // increment count if in wrong slot in table 
      { 
       count++; 
      } 
     } 

    } 
    return count; 
}