Equality Predicates and Hash Functions

| Home | Libraries | People | FAQ | More

## Equality Predicates and Hash Functions

While the associative containers use an ordering relation to specify how the elements are stored, the unordered associative containers use an equality predicate and a hash function. For example, `boost::unordered_map` is declared as:

    template <
        class Key, class Mapped,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<std::pair<Key const, Mapped> > >
    class unordered_map;

The hash function comes first as you might want to change the hash function but not the equality predicate. For example, if you wanted to use the FNV-1 hash you could write:

    boost::unordered_map<std::string, int, hash::fnv_1>
        dictionary;

There is an implementation of FNV-1 in the examples directory.

If you wish to use a different equality function, you will also need to use a matching hash function. For example, to implement a case insensitive dictionary you need to define a case insensitive equality predicate and hash function:

    struct iequal_to
        : std::binary_function<std::string, std::string, bool>
    {
        bool operator()(std::string const& x,
            std::string const& y) const
        {
            return boost::algorithm::iequals(x, y, std::locale());
        }
    };

    struct ihash
        : std::unary_function<std::string, std::size_t>
    {
        std::size_t operator()(std::string const& x) const
        {
            std::size_t seed = 0;
            std::locale locale;

            for(std::string::const_iterator it = x.begin();
                it != x.end(); ++it)
            {
                boost::hash_combine(seed, std::toupper(*it, locale));
            }

            return seed;
        }
    };

Which you can then use in a case insensitive dictionary:

    boost::unordered_map<std::string, int, ihash, iequal_to>
        idictionary;

This is a simplified version of the example at /libs/unordered/examples/case_insensitive.hpp which supports other locales and string types.

| Caution
Be careful when using the equality (`==`) operator with custom equality predicates, especially if you're using a function pointer. If you compare two containers with different equality predicates then the result is undefined. For most stateless function objects this is impossible - since you can only compare objects with the same equality predicate you know the equality predicates must be equal. But if you're using function pointers or a stateful equality predicate (e.g. boost::function) then you can get into trouble.

### Custom Types

Similarly, a custom hash function can be used for custom types:

    struct point {
        int x;
        int y;
    };

    bool operator==(point const& p1, point const& p2)
    {
        return p1.x == p2.x && p1.y == p2.y;
    }

    struct point_hash
        : std::unary_function<point, std::size_t>
    {
        std::size_t operator()(point const& p) const
        {
            std::size_t seed = 0;
            boost::hash_combine(seed, p.x);
            boost::hash_combine(seed, p.y);
            return seed;
        }
    };

    boost::unordered_multiset<point, point_hash> points;

Since the default hash function is Boost.Hash, we can extend it to support the type so that the hash function doesn't need to be explicitly given:

    struct point {
        int x;
        int y;
    };

    bool operator==(point const& p1, point const& p2)
    {
        return p1.x == p2.x && p1.y == p2.y;
    }

    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;
    }

    // Now the default function objects work.
    boost::unordered_multiset<point> points;

See the Boost.Hash documentation for more detail on how to do this. Remember that it relies on extensions to the draft standard - so it won't work on other implementations of the unordered associative containers.

Table 27.3. Methods for accessing the hash and equality functions.

Method | Description
--- | ---
`hasher hash_function() const` | Returns the container's hash function.
`key_equal key_eq() const` | Returns the container's key equality function.