1

新しいC++11標準には、順序付けされていないコンテナーがあります。特に、（デフォルトのハッシュ関数）に基づいた場所にをstd::unordered_map<Key, Value>格納します。同様に、に基づいた場所にキーを格納します。std::pair<Key, Value>std::hash<Key>std::unordered_set<Key>std::hash<Key>

私の質問は、キーと値のペアの値のみをに基づいた場所に格納するにはどうすればよいstd::hash<Key>ですか？これは、完全なハッシュ関数を使用する場合、つまり、異なるキーが異なるハッシュインデックスにマップされる場合に役立ちます（したがって、衝突の解決は必要ありません）。

unordered_setはキーのみを使用し、unordered_mapはキーと値の両方を使用するため、新しいC++11標準のunorderedSTLコンテナーではそのようなカスタマイズは許可されていないようです。既存のSTLコンテナからそのようなデータ構造を取得するための良い方法は何でしょうか？

より一般的には、キーの署名を表すタイプはどこにあるかにstd::pair<T, Value>基づいて、をどのように場所に格納できますか？たとえば、Keyが大規模なデータ構造である場合、64ビットのハッシュキーを計算し、これを2つの32ビット部分に分割します。上位32ビットとValueがaを形成し、下位32ビットがこの場所を決定します。ペアが保存されます。std::hash<Key>Tstd::pair<uint32_t, Value>

これが役立つアプリケーションは、たとえばコンピュータチェスです。この場合、キータイプとしての位置（一部のプログラムでは数キロバイト）が64ビットキーにハッシュされ、そのうち上位32ビットと一部の検索関連情報のみが値として使用されます。タイプはstd::pair、ハッシュキーの下位32ビットに基づく場所に（通常は合計16バイトのみ）格納されます。

4

5 に答える 5

1

キーとして使用する型のハッシュ関数を実装してから、ハッシュ値を保持する型を作成し、その型にstd :: hashを特殊化して、ハッシュ値を返すだけにします。これで、ハッシュを計算し、ハッシュの計算に使用したデータを破棄して、値とそのハッシュをマップに貼り付けることができます。

値を取得するには、何らかの方法でキーデータを再構築し、ハッシュ値を再計算してから、マップでそのハッシュを検索します。

于 2012-01-09T21:56:07.810 に答える
1

C ++ 11ハッシュは実際にはタイプであるsize_tため、次のように実行できます。

template <typename T>
struct with_hash
{
    size_t hash;
    T value;
};

template<> struct std::hash<with_hash>
{
    typedef size_t result_type;
    typedef with_hash argument_type;
    size_t operator()(const with_hash &x)
    {
         return x.hash;
    }
};

template <typename T>
using perfectly_hashed = std::unordered_set< with_hash<T> >;

あちこちにいくつかの構文上の砂糖があります...

于 2012-01-09T21:45:52.463 に答える
1

ハッシュ値に継続的にアクセスせずにハッシュに対して操作を実行する汎用的な方法はありません。たとえば、ハッシュが内部でツリーを使用するとします。ハッシュに新しいノードを追加するには、そのハッシュ値をツリー上の既存のノードのハッシュ値と比較する必要があります。それらの値をツリーに保存しなかった場合、どうすればそれを行うことができますか？

あなたが求めていることはおそらく不可能ではありませんが、典型的なハッシュアルゴリズムのどれもそれを行うことができません。そして、とにかく意味がないようです。コレクションをトラバース可能にするために何かを保存する必要があります。ハッシュ以外のものがハッシュと同様にどのように機能するかを確認するのは困難です。それが検索対象だからです。にとって。

ハッシュが「大きすぎる」場合は、ハッシュのハッシュを使用します。（もちろん、ハッシュの衝突に対処する必要があります。）

于 2012-01-09T21:48:23.260 に答える
1

私はこれを完全に間違っているかもしれませんが、std::unordered_map<uint32_t, std::pair<uint32_t, Value>>挿入と抽出のためのいくつかの素晴らしいユーティリティ関数を使ってみませんか？

// demonstration with 32bit 'hash' and 16bit 'lo' and 'hi'
#include <unordered_map>
#include <string>
#include <stdint.h>
#include <iostream>

int main(){
    typedef std::unordered_map<uint16_t, std::pair<uint16_t, std::string>> map_type;
    map_type m;
    std::string key = "hello", value = "world";
    uint32_t hash = std::hash<std::string>()(key);
    uint16_t lo = hash & 0xFFFF, hi = hash >> 16; // make a nice function for this
    m.insert(std::make_pair(lo, std::make_pair(hi, value))); // and this
    auto it = m.find(lo); // and this
    std::cout << "hash: " << hash << '\n'
              << "lo: " << it->first << '\n'
              << "hi: " << it->second.first << '\n'
              << "lo | (hi << 16): " << (it->first | (uint32_t(it->second.first) << 16)) << '\n'
              << "value: " << it->second.second << '\n';
}

Ideoneのライブデモ。

出力：

hash: 1335831723
lo: 11435
hi: 20383
lo | (hi << 16): 1335831723
value: world
于 2012-01-09T22:16:12.033 に答える
1

私の質問は、std :: hashに基づく場所に、キーと値のペアの値のみを格納するにはどうすればよいですか？これは、完全なハッシュ関数を使用する場合、つまり、異なるキーが異なるハッシュインデックスにマップされる場合に役立ちます（したがって、衝突の解決は必要ありません）。

完全なハッシュ関数では不十分です。ハッシュの衝突がないことを保証する必要があるだけでなく、バ​​ケットの衝突がないことも確認する必要があります。データ構造がキーのハッシュを検出できないため、バケットの数が変更されないようにする必要があります。

于 2012-01-10T17:22:56.950 に答える