bslh_fibonaccibadhashwrapper.h

Go to the documentation of this file.

/// @file bslh_fibonaccibadhashwrapper.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslh_fibonaccibadhashwrapper.h                                     -*-C++-*-
#ifndef INCLUDED_BSLH_FIBONACCIBADHASHWRAPPER
#define INCLUDED_BSLH_FIBONACCIBADHASHWRAPPER
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslh_fibonaccibadhashwrapper bslh_fibonaccibadhashwrapper
/// @brief  Provide a wrapper to improve "bad" hash algorithms.
/// @addtogroup bsl
/// @{
/// @addtogroup bslh
/// @{
/// @addtogroup bslh_fibonaccibadhashwrapper
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslh_fibonaccibadhashwrapper-purpose"> Purpose</a>
/// * <a href="#bslh_fibonaccibadhashwrapper-classes"> Classes </a>
/// * <a href="#bslh_fibonaccibadhashwrapper-description"> Description </a>
///   * <a href="#bslh_fibonaccibadhashwrapper-requirements-upon-wrapped-hash-function-object"> Requirements Upon Wrapped Hash Function Object </a>
///   * <a href="#bslh_fibonaccibadhashwrapper-usage"> Usage </a>
///     * <a href="#bslh_fibonaccibadhashwrapper-example-1-obtaining-most-significant-and-least-significant-bit-variation"> Example 1: Obtaining Most-Significant and Least-Significant Bit Variation </a>
///
/// # Purpose {#bslh_fibonaccibadhashwrapper-purpose}
/// Provide a wrapper to improve "bad" hash algorithms.
///
/// # Classes {#bslh_fibonaccibadhashwrapper-classes}
///
/// -  bslh::FibonacciBadHashWrapper: wrapper to improve "bad" hashes
///
/// # Description {#bslh_fibonaccibadhashwrapper-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 {#bslh_fibonaccibadhashwrapper-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 {#bslh_fibonaccibadhashwrapper-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example 1: Obtaining Most-Significant and Least-Significant Bit Variation {#bslh_fibonaccibadhashwrapper-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.
/// @code
/// 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);
///     }
/// };
/// @endcode
/// Then, we instantiate an instance of the identity functor and the wrapped
/// functor.
/// @code
/// IdentityHash                                identity;
/// bslh::FibonacciBadHashWrapper<IdentityHash> wrapped;
/// @endcode
/// Finally, we examine the range of values obtained from small integer values:
/// @code
/// 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));
/// }
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslh
 * @{
 */
/** @addtogroup bslh_fibonaccibadhashwrapper
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bsls_types.h>  // 'bsls::Types::Uint64'
 
#include <stddef.h>      // 'size_t'
 
 
namespace bslh {
 
                      // =============================
                      // class FibonacciBadHashWrapper
                      // =============================
 
/// This class provides a hash algorithm wrapper that improves the
/// distribution of varying bits from the `HASH` applied to the `KEY`.
///
/// See @ref bslh_fibonaccibadhashwrapper 
template <class HASH>
class FibonacciBadHashWrapper {
 
    // DATA
    HASH d_hash;  // hash functor
 
  public:
    // PUBLIC CLASS DATA
 
    /// The value corresponds to:
    /// @code
    /// 2^64 / phi - 1
    /// @endcode
    /// where *phi* is the Golden Ratio and 1 is subtracted to avoid the
    /// value being a multiple of 2 (that would throw away one bit of
    /// information from the resultant hash value).  See
    /// https://en.wikipedia.org/wiki/Hash_function#Fibonacci_hashing.
    static const bsls::Types::Uint64 k_FIBONACCI_HASH_MULTIPLIER
                                                     = 11400714819323198485ull;
 
    // CREATORS
 
    /// Create a `FibonacciBadHashWrapper` having a default constructed
    /// hash.
    FibonacciBadHashWrapper();
 
    /// Create a `FibonacciBadHashWrapper` having the specified `hash`.
    explicit FibonacciBadHashWrapper(const HASH& hash);
 
     FibonacciBadHashWrapper(
                         const FibonacciBadHashWrapper& original) = default;
        // Create a 'FibonacciBadHashWrapper' object having the value of the
        // specified 'original' object.
 
     ~FibonacciBadHashWrapper() = default;
        // Destroy this object.
 
    // MANIPULATORS
     FibonacciBadHashWrapper& operator=(
                              const FibonacciBadHashWrapper& rhs) = default;
        // Assign to this object the value of the specified 'rhs' object, and
        // return a reference providing modifiable access to this object.
 
    // ACCESSORS
 
    /// Return the hash of the specified `key`, computed as the product
    /// of the result of the hash function supplied at construction and
    /// `k_FIBONACCI_HASH_MULTIPLIER`.
    template <class KEY>
    size_t operator()(const KEY& key) const;
};
 
// ============================================================================
//                             INLINE DEFINITIONS
// ============================================================================
 
                      // ------------------------------
                      // struct FibonacciBadHashWrapper
                      // ------------------------------
 
// CREATORS
template <class HASH>
inline
FibonacciBadHashWrapper<HASH>::FibonacciBadHashWrapper()
: d_hash()
{
}
 
template <class HASH>
inline
FibonacciBadHashWrapper<HASH>::FibonacciBadHashWrapper(const HASH& hash)
: d_hash(hash)
{
}
 
// ACCESSORS
template <class HASH>
template <class KEY>
inline
size_t FibonacciBadHashWrapper<HASH>::operator()(const KEY& key) const
{
    return static_cast<size_t>(d_hash(key) * k_FIBONACCI_HASH_MULTIPLIER);
}
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2020 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License.  You may obtain a copy
// of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  See the
// License for the specific language governing permissions and limitations
// under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */