[library Boost.Functional/Hash
    [authors [James, Daniel]]
    [copyright 2005 Daniel James]
    [purpose A TR1 hash function object that can be extended to hash user
        defined types]
    [category higher-order]
    [id hash]
    [dirname hash]
    [license
        Distributed under the Boost Software License, Version 1.0.
        (See accompanying file LICENSE_1_0.txt or copy at
        <ulink url="http://www.boost.org/LICENSE_1_0.txt">
            http://www.boost.org/LICENSE_1_0.txt
        </ulink>)
    ]
]

[/ QuickBook Document version 1.0 ]
[/ Feb 8, 2005 ]

[def __note__       [$images/note.png]]
[def __alert__      [$images/alert.png]]
[def __tip__        [$images/tip.png]]
[def __boost_hash   [classref boost::hash]]
[def __hash_value   [funcref boost::hash_value hash_value]]
[def __hash_combine [funcref boost::hash_combine]]
[def __hash_range   [funcref boost::hash_range]]

[section:intro Introduction]

[def __tr1__ [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf
    C++ Standard Library Technical Report]]
[def __tr1-short__ [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf
    Technical Report]]
[def __multi-index__ [@../../libs/multi_index/doc/index.html
    Boost Multi-Index Containers Library]]
[def __multi-index-short__ [@../../libs/multi_index/doc/index.html
    Boost.MultiIndex]]
[def __issues__ [@http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
    Library Extension Technical Report Issues List]]
[def __hash-function__ [@http://en.wikipedia.org/wiki/Hash_function hash function]]
[def __hash-table__ [@http://en.wikipedia.org/wiki/Hash_table hash table]]

__boost_hash is an implementation of the __hash-function__ object
specified by the __tr1-short__. It is intended for use as the default hash function
for unordered associative containers, and the __multi-index__'s hash indexes.

As it is compliant with the __tr1-short__, it will work with:

* integers
* floats
* pointers
* strings

It also implements the extension proposed by Peter Dimov in issue 6.18 of the
__issues__, this adds support for:

* arrays
* `std::pair`
* the standard containers.
* extending __boost_hash for custom types.

[endsect]

[section:tutorial Tutorial]

When using a hash index with __multi-index-short__, you don't need to do
anything to use __boost_hash as it uses it by default.
To find out how to use a user-defined type, read the
[link hash.custom section on extending boost::hash for a custom data type].

If your standard library supplies its own implementation of the unordered
associative containers and you wish to use
__boost_hash, just use an extra template parameter:

    std::unordered_multiset<std::vector<int>, __boost_hash<int> >
            set_of_ints;

    std::unordered_set<std::pair<int, int>, __boost_hash<std::pair<int, int> >
            set_of_pairs;

    std::unordered_map<int, std::string, __boost_hash<int> > map_int_to_string;

To use __boost_hash directly, create an instance and call it as a function:

    #include <boost/hash/hash.hpp>

    int main()
    {
        __boost_hash<std::string> string_hash;

        std::size_t h = string_hash("Hash me");
    }

If you wish to make use of the extensions, you will need to include the
appropriate header (see the
[link hash.reference.specification reference documentation] for the full list).

    #include <boost/hash/pair.hpp>

    int main()
    {
        __boost_hash<std::pair<int, int> > pair_hash;

        std::size_t h = pair_hash(std::make_pair(1, 2));
    }

Or alternatively, include `<boost/hash.hpp>` for the full library.

For an example of generic use, here is a function to generate a vector
containing the hashes of the elements of a container:

    template <class Container>
    std::vector<std::size_t> get_hashes(Container const& x)
    {
        std::vector<std::size_t> hashes;
        std::transform(x.begin(), x.end(), std::insert_iterator(hashes),
            __boost_hash<typename Container::value_type>());

        return hashes;
    }

[endsect]

[section:custom Extending boost::hash for a custom data type]

__boost_hash is implemented by calling the function __hash_value.
The namespace isn't specified so that it can detect overloads via argument
dependant lookup. So if there is a free function `hash_value` in the same
namespace as a custom type, it will get called.

If you have a structure `library::book`, where each `book` is uniquely
defined by it's member `id`:

    namespace library
    {
        struct book
        {
            int id;
            std::string author;
            std::string title;

            // ....
        };

        bool operator==(book const& a, book const& b)
        {
            return a.id == b.id;
        }
    }

Then all you would need to do is write the function `library::hash_value`:

    namespace library
    {
        std::size_t hash_value(book const& b)
        {
            __boost_hash<int> hasher;
            return hasher(b.id);
        }
    }

And you can now use __boost_hash with book:

    library::book knife(3458, "Zane Grey", "The Hash Knife Outfit");
    library::book dandelion(1354, "Paul J. Shanley",
        "Hash & Dandelion Greens");

    __boost_hash<library::book> book_hasher;
    std::size_t knife_hash_value = book_hasher(knife);

    // If std::unordered_set is available:
    std::unordered_set<library::book, __boost_hash<library::book> > books;
    books.insert(knife);
    books.insert(library::book(2443, "Lindgren, Torgny", "Hash"));
    books.insert(library::book(1953, "Snyder, Bernadette M.",
        "Heavenly Hash: A Tasty Mix of a Mother's Meditations"));

    assert(books.find(knife) != books.end());
    assert(books.find(dandelion) == books.end());

The full example can be found in:
[@../../libs/functional/hash/examples/books.hpp /libs/functional/hash/examples/books.hpp]
and
[@../../libs/functional/hash/examples/books.cpp /libs/functional/hash/examples/books.cpp].

[blurb
When writing a hash function, first look at how the equality function works.
Objects that are equal must generate the same hash value.
When objects are not equal the should generate different hash values.
In this object equality was based just on the id, if it was based
on the objects name and author the hash function should take them into account
(how to do this is discussed in the next section).
]

[endsect]

[section:combine Combining hash values]

Say you have a point class, representing a two dimensional location:

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

and you wish to use it as the key for an `unordered_map`. You need to
customise the hash for this structure. To do this we need to combine
the hash values for `x` and `y`. The function
__hash_combine is supplied for this purpose:

    class point
    {
        ...

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

            return seed;
        }

        ...
    };

Calls to hash_combine incrementally build the hash from the different members
of point, it can be repeatedly called for any number of elements. It calls
__hash_value on the supplied element, and combines it with the seed.

Full code for this example is at
[@../../libs/functional/hash/examples/point.cpp /libs/functional/hash/examples/point.cpp].

[blurb
'''
When using __hash_combine the order of the
calls matters.
<programlisting>
    std::size_t seed = 0;
    boost::hash_combine(seed, 1);
    boost::hash_combine(seed, 2);
</programlisting>
results in a different seed to:
<programlisting>
    std::size_t seed = 0;
    boost::hash_combine(seed, 2);
    boost::hash_combine(seed, 1);
</programlisting>
If you are calculating a hash value for data where the order of the data
doesn't matter in comparisons (e.g. a set) you will have to ensure that the
data is always supplied in the same order.
'''
]

To calculate the hash of an iterator range you can use __hash_range:

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

[endsect]

[section:portability Portability]

__boost_hash is written to be as portable as possible, but unfortunately, several
older compilers don't support argument dependent lookup (ADL) - the mechanism
used for customization.  On those compilers custom overloads for hash_value
need to be declared in the boost namespace.

On a strictly standards compliant compiler, an overload defined in the
boost namespace won't be found when __boost_hash is instantiated,
so for these compilers the overload should only be declared in the same
namespace as the class.

Let's say we have a simple custom type:

    namespace foo
    {
        struct custom_type
        {
            int value;

            friend inline std::size_t hash_value(custom_type x)
            {
                __boost_hash<int> hasher;
                return hasher(x.value);
            }
        };
    }

On a compliant compiler, when `hash_value` is called for this type,
it will look at the namespace inside the type and find `hash_value`
but on a compiler which doesn't support ADL `hash_value` won't be found.

So on these compilers define a member function:

    #ifndef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP
            friend inline std::size_t hash_value(custom_type x)
            {
                __boost_hash<int> hasher;
                return hasher(x.value);
            }