1

JavaバージョンのようなハッシュテーブルをC++で実装しようとしています

私はそれがの形を持っていることを望みます

template <class Key, class Value> 
class hashtable {
...
}

すぐに、単純なハッシュ関数を使用できるように、Key を数値に変換する必要があることに気付きました。 

int h(int hashkey) { 
    return hashkey%some_prime;
}

しかし、問題は、キーの型が実行時にしか分からないことです。C++ で実行時に Key の型を確認することはできますか? または、このハッシュテーブル クラスを別の型で手動で作成する必要がありますか? それは簡単ですが、醜いです。エレガントなソリューションを知っている人はいますか？

4

3 に答える 3

3

C++ テンプレートは通常、ダック タイプです。つまり、テンプレートで整数型に明示的にキャストでき、適切な変換を実装するすべての型をキーとして使用できます。これには、ハッシュ関数がまともなものになるような方法でクラスが変換演算子を実装する必要があるという欠点があります。これは多くのことを求めています。

代わりに関数テンプレートを提供できます

template<typename T> int hash (T t);

組み込み型の特殊化に加えて、カスタム クラスをキーとして使用したいユーザーは、独自の特殊化を提供するだけで済みます。これはまともなアプローチだと思います。

于 2013-01-02T21:04:43.303 に答える
2

あなたはいくつかの誤解をしているようです。キーの型はコンパイル時に認識されます。これがテンプレートを使用するポイントです。第二に、どの型でも機能する完全に汎用的なハッシュ関数などというものは実際にはありません。関数のオーバーロードまたはテンプレートの特殊化を使用して、さまざまな型に対してさまざまなハッシュ関数を実装する必要があります。たとえば、文字列に使用される一般的なハッシュ関数は多数あります。

最後に、C++11 には、独自に実装する代わりに使用できる標準のハッシュ テーブル ( std::unordered_map ) が含まれています。

于 2013-01-02T20:57:57.827 に答える
1

「一般的な」ものを実装したい場合は、おそらく次のようなスケルトンから始めることができます:

template <class T, class K>
struct HashEntry {  // you would need this to deal with collision
    T curr;
    K next;
}

template <class V, size_t n>
class HashTable {
    void insert(V v)
    {
        ...
        size_t idx = v->getHashCode(n);
        ...
    }
private:
    HashEntry <V> table_[n];

}

通常、ポインター型でインスタンス化され、ポインターがどこに行くべきかを把握するために、型実装メンバー関数「getHashCode」が必要です...

于 2013-01-02T21:50:31.327 に答える