0

約100個の非負の32ビット整数のリストを1つの整数に凝縮したいと思います。理想的には、結果の整数は常に一意ですが、比較的まれな衝突はいくつか許容されます。これどうやってするの？

私はパズルソルバーを書いています。私の検索アルゴリズムの一部は、すでに見たパズルの状態を再探索することを避けることです。リストから生成された整数をstatesAlreadySeenテーブルへのキーとして使用します。現在、キーとして文字列を使用しています。ただし、文字列キーから整数キーに移行すると、パフォーマンスが大幅に向上するmap<,>ため、切り替えたいと思います。

編集：順序付けられていないマップの提案をありがとう！ただし、実際のハッシュ関数についてはまだ興味があります。IIRCには、基本的なビット操作とxoringを含む単純な関数があります。これを見て、衝突の確率について一般的な理解を得るのは素晴らしいことです。

4

1 に答える 1

2

コメントで示唆されているように、ハッシュ関数を使用する必要があります。最も簡単に達成できるのはboost::hash_range：

#include <boost/functional/hash.hpp>
std::size_t vectorhash(std::vector<int> f){
    size_t hash = std::size_t hash = boost::hash_range(f.begin(), f.end());
}

そうは言っても、状態を順序付けておく必要が本当にない場合（そして、なぜそうするのかわかりません）、stringキーを保持してに切り替えるというus2012のソリューションを使用しますunordered_map。これにより、コンテナーに処理を任せることができます。ハッシュ。

于 2013-02-18T00:52:17.140 に答える