boost::openmethod::policies::fast_perfect_hash

Hash type ids using a fast, perfect hash function.

Synopsis

Declared in <boost/openmethod/policies/fast_perfect_hash.hpp>

struct fast_perfect_hash
    : type_hash

Description

fast_perfect_hash implements the type_hash policy using a hash function in the form H(x)=(M*x)>>S. It attempts to determine values for M and S that do not result in collisions for the set of registered type_ids. This may fail for certain sets of inputs, although it is very likely to succeed for addresses of std::type_info objects.

There is no guarantee that every value in the codomain of the function corresponds to a value in the domain, or even that the codomain is a dense range of integers. In other words, a lot of space may be wasted in presence of large sets of type_ids.

Example

// `vptr_vector` indexes by the type id unless a `type_hash` policy maps it to
// a small integer first. With `std_rtti`, where a type id is a pointer, that
// makes the difference between a vector of a few entries and one that cannot
// be allocated at all.
struct hashed_registry : registry<
                             policies::std_rtti, policies::fast_perfect_hash,
                             policies::vptr_vector> {};