0Pricing
C++ Academy · レッスン

カスタムハッシュ関数

独自の型をハッシュします

「カスタムハッシュ関数」はCoddyKit上の無料C++ Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC++ Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C++ Academyコースには全4レッスンが含まれています。

カスタムハッシュが必要な理由

順序付けされないコンテナでは、キーをハッシュする方法が必要です。組み込み型と std::string にはすでにハッシュ関数がありますが、独自の型にはありません。自分で用意する必要があります。

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

std::hash テンプレート

std::hash は値を size_t に対応付けるファンクタです。関数と同じように呼び出せます。

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

ハッシュする構造体

2つの int を持つ Point があるとします。これを unordered_set に格納するには、等価性とハッシュの両方が必要です。

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

ハッシュファンクタを記述する

ハッシュファンクタは、size_t を返す operator() を持つ構造体です。通常は XOR とシフトを使って、各フィールドのハッシュを組み合わせます。

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

ハッシュファンクタを使う

ハッシュファンクタを、順序付けされないコンテナの2番目のテンプレート引数として渡します。

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

等価性も必要

2つのキーのハッシュが衝突すると、それらは同じバケットに入ります。するとコンテナは operator== を使って両者を区別するため、等価性の定義が必須です。

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

ハッシュを map のキーに使う

同じカスタムハッシュを使えば、構造体を unordered_map のキーにできます。

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

複数のフィールドを組み合わせる

よく使われるヘルパーでは、boost::hash_combine に似た乗算と加算のパターンを使い、フィールドを1つずつ処理してハッシュを組み合わせます。

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

良好なハッシュ分布

常に同じ値を返す粗悪なハッシュでは、すべての要素が1つのバケットに入り、計算量が O(n) に低下します。すべてのフィールドのビットを適切に混ぜてください。

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

std::hash の特殊化

別の方法として、独自の型に対して std::hash を特殊化すれば、ファンクタを明示的に渡さずに使えるようになります。

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

ハッシュとしてのラムダ

C++20 では、型を渡すことでステートレスなラムダをハッシュとして使うこともできます。

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

クイックチェック

カスタムハッシュについて、理解度を確認しましょう。

まとめ

カスタム型をハッシュする方法として、次のことを学びました。

  • size_t を返すハッシュファンクタを用意する（または std::hash を特殊化する）
  • 衝突したキーを区別できるよう、operator== も用意する
  • 適切な分布になるよう、各フィールドのハッシュを適切に組み合わせる

次は、バケットと負荷率がパフォーマンスに与える影響を調べます。

よくある質問

「カスタムハッシュ関数」レッスンは無料ですか？

はい。「カスタムハッシュ関数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C++ Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C++ Academyコースには全4レッスンが含まれています。

「カスタムハッシュ関数」で何を学びますか？

独自の型をハッシュします ブラウザで直接実行するハンズオンコードでC++ Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

C++ Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのC++ Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「カスタムハッシュ関数」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このC++ Academyレッスンでコードを書いて実行できますか？

はい。すべてのC++ Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. std::unordered_map
  2. unordered_set
  3. カスタムハッシュ関数
  4. パフォーマンス上の考慮事項
← C++ Academyに戻る