4

テンプレートを介して C++ で HashTable を実装しようとしています。署名は次のとおりです。

template<class T1, class T2>
class HashTable {

public:
void add(T1 a, T2 b);

void hashFunction(T1 key, T2 value)
{

// how to implement this function using key as a generic 
// we need to know the object type of key

}
};

そのため、汎用キーを含む実装を進めることができません。

Java では、キーを文字列に簡単にキャストできたので、キーのハッシュを文字列として実装することに満足していました。しかし、C++ で私が知っているのは、目的のオブジェクトにオブジェクトを動的にキャストできる RTTI の概念があるということです。

このメソッドがまったく正しい場合、その動的キャストを実装する方法は?

この場合、テンプレートを使用してジェネリックを実装するのが正しい方法ではない場合は、より良い方法を提案してください。

4

2 に答える 2

10

通常はstd::hashこれを使用し、必要に応じて型実装者にそのテンプレートを特殊化させます。

size_t key_hash = std::hash<T1>()(key);

与えられたランダムな型に対してハッシュ関数を一般的に実装する方法はありません。2 つのオブジェクトが等しい場合、それらのハッシュ コードは同じでなければなりません。ハッシュ関数を介してオブジェクトの生メモリを単純に実行することもできますが、型operator==はオブジェクト データの一部 (同期オブジェクトなど) を無視するオーバーロードを実装する場合があります。その場合、等しいオブジェクトに対して異なるハッシュ値を返す可能性があります (そして非常に簡単に)。

于 2013-04-26T19:21:46.117 に答える
4

キーと値の両方をハッシュしたいのは奇妙です。その後、キーだけでどのように価値を得ることができますか?

C++11 を使用std::hash<T1>している場合は、一部の型 (整数、文字列、ポインター) に提供され、他のクラスに特化したものを使用することをお勧めします。さらに、3 番目のテンプレート パラメーター クラスを使用して変更できるようにすることをお勧めします。やり方unordered_mapを見る

template<typename K, typename V, typename H = std::hash<T>>
class HashTable {
   //...
   void hashFunction(const T1& key) {
        hash = H()(key);
        //process hash somehow, probably you need get reminder after division to number of buckets or something same
        return hash % size;
   }
}

等値演算子は複雑な方法でオーバーライドされる可能性があるため、ほとんどのタイプで問題なく機能する独自のハッシュを作成することは不可能に思えます

于 2013-04-26T19:25:31.527 に答える