Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Combining hash values(結合散列值)

假設你有一個 point 類,代表一個二維空間上的位置:

class point
{
    int x;
    int y;
public:
    point() : x(0), y(0) {}
    point(int x, int y) : x(x), y(y) {}

    bool operator==(point const& other) const
    {
        return x == other.x && y == other.y;
    }
};

而你要用它作為一個 unordered_map 中的鍵。你就要為這個結構定制散列。為了做到這一點,我們要結合 xy 的散列值。函數 boost::hash_combine 就用於這個目的:

class point
{
    ...

    friend std::size_t hash_value(point const& p)
    {
        std::size_t seed = 0;
        boost::hash_combine(seed, p.x);
        boost::hash_combine(seed, p.y);

        return seed;
    }

    ...
};

對 hash_combine 的調用從 point 的不同成員逐步建造出散列,它可以對任何數量的部件重複調用。它在提供的部件上調用 hash_value,並將它和 seed 結合在一起。

這個例子的完整代碼在 /libs/functional/hash/examples/point.cpp

[Note] 注意

使用 boost::hash_combine 時調用順序的問題。

    std::size_t seed = 0;
    boost::hash_combine(seed, 1);
    boost::hash_combine(seed, 2);

    std::size_t seed = 0;
    boost::hash_combine(seed, 2);
    boost::hash_combine(seed, 1);

將導致不同的 seed。

如果你要為順序沒什麼關係的數據(比如,一個 set)計算一個散列值,你就必須確保這些數據總是以同樣的順序被使用。

為了計算一個迭代器 range 的散列,你可以用 boost::hash_range

std::vector<std::string> some_strings;
std::size_t hash = boost::hash_range(some_strings.begin(), some_strings.end());

PrevUpHomeNext