bslh_fibonaccibadhashwrapper

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements Upon Wrapped Hash Function Object
  • Usage
    • Example 1: Obtaining Most-Significant and Least-Significant Bit Variation

Purpose

Provide a wrapper to improve "bad" hash algorithms.

Classes

• bslh::FibonacciBadHashWrapper: wrapper to improve "bad" hashes

Description

This component provides a functor type, bslh::FibonacciBadHashWrapper, that can be used to wrap a hash algorithm ameliorating the unwanted properties of a poor hash function.

For example, the identity function is often used to hash integer values (see bsl::hash<int>), and although the identity function has the property that two different input values are unlikely to result in the same hash value, it does not have many of the other desirable properties of a hash function (common input values are not evenly distributed over the range of hash values, a small change the input does not change the hash value extensively, and it is easy to determine the input from a hash value).

The bslh::FibonacciBadHashWrapper can be used on the output of a bad hash function (like the identity function) to address some (but not all) of those deficiencies. Specifically, the resulting hash value is more evenly distributed over the range, and a small change in the input will result in a larger change in the hash value.

Requirements Upon Wrapped Hash Function Object

The wrapped hash function object must be a function object, default constructible, copy constructible, and destructible. The result of operator() must be convertable to size_t. For an instance of a hash functor, operator() must provide the same result for each argument value for the lifetime of the functor. For the bslh::FibonacciBadHashWrapper to support the type KEY in its operator(), the wrapped hash function's operator() must be invokable with the type KEY.

Usage

This section illustrates intended usage of this component.

Example 1: Obtaining Most-Significant and Least-Significant Bit Variation

Suppose we are using a hash table that requires variation in the most-significant and least-significant bits to operate efficiently (e.g., Abseil's flat hash map). The keys we will be using are small integer values, and we would like to use the identity function as the hash functor since it is efficient. A simple and efficient method to obtain a hash functor with the necessary qualities is to wrap the identity functor with bslh::FibonaccaBadHashWrapper.

First, we define our IdentityHash class.

class IdentityHash {
    // This class provides a hash algorithm that provides the "identity"
    // mapping from key to hash.
 
  public:
    size_t operator()(const int key) const
        // Return the specified 'key'.
    {
        return static_cast<size_t>(key);
    }
};

Then, we instantiate an instance of the identity functor and the wrapped functor.

IdentityHash                                identity;
bslh::FibonacciBadHashWrapper<IdentityHash> wrapped;

Finally, we examine the range of values obtained from small integer values:

if (8 == sizeof(size_t)) {
    ASSERT(18446744073709551614ull == identity(-2));
    ASSERT(18446744073709551615ull == identity(-1));
    ASSERT(                      0 == identity( 0));
    ASSERT(                      1 == identity( 1));
    ASSERT(                      2 == identity( 2));
 
    ASSERT(14092058508772706262ull == wrapped(-2));
    ASSERT( 7046029254386353131ull == wrapped(-1));
    ASSERT(                      0 == wrapped( 0));
    ASSERT(11400714819323198485ull == wrapped( 1));
    ASSERT( 4354685564936845354ull == wrapped( 2));
}
else {
    ASSERT(4294967294u == identity(-2));
    ASSERT(4294967295u == identity(-1));
    ASSERT(          0 == identity( 0));
    ASSERT(          1 == identity( 1));
    ASSERT(          2 == identity( 2));
 
    ASSERT(  23791574u == wrapped(-2));
    ASSERT(2159379435u == wrapped(-1));
    ASSERT(          0 == wrapped( 0));
    ASSERT(2135587861u == wrapped( 1));
    ASSERT(4271175722u == wrapped( 2));
}