Hashable

Description

The Hashable concept represents objects that can be normalized to a type-level hash.

In day to day programming, hashes are very important as a way to efficiently lookup objects in maps. While the implementation of maps is very different, the same idea of using hashes for efficient lookup applies in metaprogramming. The Hashable concept represents objects that can be summarized (possibly with loss of information) to a type, in a way suitable for use in hash-based data structures. Of course, in order for a hash to be well-behaved, it must obey some laws that are explained below.

Minimal complete definition

hash, satisfying the laws below

Laws

First, hana::hash must return a hana::type. Furthermore, for any two Hashable objects x and y, it must be the case that

x == y   implies   hash(x) == hash(y)

where == denotes hana::equal. In other words, any two objects that compare equal (with hana::equal) must also have the same hash. However, the reverse is not true, and two different objects may have the same hash. This situation of two different objects having the same hash is called a collision.

Concrete models

hana::integral_constant, hana::type, hana::string

Free model for IntegralConstants

Any IntegralConstant is Hashable, by normalizing its value to a hana::integral_constant. The type of the value held in the normalized integral_constant is unsigned long long for unsigned integral types, and signed long long for signed integral types.

Variables
constexpr auto	boost::hana::hash
	Returns a hana::type representing the compile-time hash of an object.Given an arbitrary object x, hana::hash returns a hana::type representing the hash of x. In normal programming, hashes are usually numerical values that can be used e.g. as indices in an array as part of the implementation of a hash table. In the context of metaprogramming, we are interested in type-level hashes instead. Thus, hana::hash must return a hana::type object instead of an integer. This hana::type must somehow summarize the object being hashed, but that summary may of course lose some information. More...

Variable Documentation

hash

constexpr auto boost::hana::hash

#include <boost/hana/fwd/hash.hpp>

Initial value:

= [](auto const& x) {
        return tag-dispatched;
    }

Returns a hana::type representing the compile-time hash of an object.Given an arbitrary object x, hana::hash returns a hana::type representing the hash of x. In normal programming, hashes are usually numerical values that can be used e.g. as indices in an array as part of the implementation of a hash table. In the context of metaprogramming, we are interested in type-level hashes instead. Thus, hana::hash must return a hana::type object instead of an integer. This hana::type must somehow summarize the object being hashed, but that summary may of course lose some information.

In order for the hash function to be defined properly, it must be the case that whenever x is equal to y, then hash(x) is equal to hash(y). This ensures that hana::hash is a function in the mathematical sense of the term.

Signature

Given a Hashable H, the signature is \( \mathtt{hash} : H \to \mathtt{type\_tag} \)

Parameters

x	An object whose hash is to be computed.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)

#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/hash.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/type.hpp>

#include <type_traits>
#include <utility>
namespace hana = boost::hana;


// Sample implementation of a compile-time set data structure. Of course,
// this naive implementation only works when no two elements of the same
// set have the same hash.
template <typename T>
struct bucket { };

template <typename ...T>
struct set
    : bucket<typename decltype(hana::hash(std::declval<T>()))::type>...
{ };

template <typename Set, typename T>
struct contains
    : std::is_base_of<
        bucket<typename decltype(hana::hash(std::declval<T>()))::type>,
        Set
    >
{ };

using Set = set<hana::int_<1>, hana::ulong<2>, hana::type<char>>;

static_assert(contains<Set, hana::int_<1>>{}, "");
static_assert(contains<Set, hana::ulong<2>>{}, "");
static_assert(contains<Set, hana::type<char>>{}, "");

static_assert(!contains<Set, hana::int_<3>>{}, "");
static_assert(!contains<Set, hana::type<float>>{}, "");

int main() { }