Hash function of std::vector<std::string> for std::unordered_map

C++ で std::unordered_map のキーに自作クラスを与えるには std::hash 関数の特殊化をする必要があります。 本稿では std::vector<std::string> を内部で保持しているクラスの hash function の作り方について説明します。

例えば以下のクラスを std::unordered_map のキーとして使いたいとします。

using namespace std;

class Path
{
public:
    explicit Path(vector<string> routes) : routes_(std::move(routes)) {}
    vector<string> routes_;
};

で、この Path クラスに hash 関数を定義するために、まずは vector<string> に対して以下のように hash 関数を定義します。 後でこの hash 関数を使って Path クラスの hash 関数を定義します。

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template<typename T> struct hash<vector<T>>
{
  inline size_t operator()(const vector<T>& v) const noexcept
  {
    size_t seed = v.size();

    for (auto &e : v) {
      hash_combine(seed, e);
    }

    return seed;
  }
};

hash_combine は boost を使っている場合は boost のものを使えばいいと思います。boost の実装と同じなので。 hash 関数がこれでよい理由は https://www.postgresql.org/message-id/CAEepm%3D3Tp65SUDYuOugTxrMx%2BtFVsdLrDL6AxbO0w2vsv3c1-g%40mail.gmail.com などを参照してください。私も詳しくは読んではいません。

{追記}

Reading Performance in Practice of String Hashing Functions に論文の内容をまとめました。

{追記ここまで}

ここまでできたら後は Path クラスの hash を定義するだけです。

struct PathHash
{
  inline size_t operator()(const Path& key) const noexcept {
    std::hash<std::vector<std::string>> hasher;
    return hasher(key.routes_);
  }
};

namespace std {

template<> struct hash<Path>
{
  inline size_t operator()(const Path& v) const noexcept
  {
    PathHash hasher;
    return hasher(v);
  }
};

}

以上です。

Comments

comments powered by Disqus