bslalg_hashutil.h

Go to the documentation of this file.

/// @file bslalg_hashutil.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslalg_hashutil.h                                                  -*-C++-*-
#ifndef INCLUDED_BSLALG_HASHUTIL
#define INCLUDED_BSLALG_HASHUTIL
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslalg_hashutil bslalg_hashutil
/// @brief  Provide a utility of hash functions.
/// @addtogroup bsl
/// @{
/// @addtogroup bslalg
/// @{
/// @addtogroup bslalg_hashutil
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslalg_hashutil-purpose"> Purpose</a>
/// * <a href="#bslalg_hashutil-classes"> Classes </a>
/// * <a href="#bslalg_hashutil-description"> Description </a>
///   * <a href="#bslalg_hashutil-usage"> Usage </a>
///     * <a href="#bslalg_hashutil-example-1-dumping-out-hash-values"> Example 1: Dumping Out Hash Values </a>
///
/// # Purpose {#bslalg_hashutil-purpose}
/// Provide a utility of hash functions.
///
/// # Classes {#bslalg_hashutil-classes}
///
/// -  bslalg::HashUtil: utility for hash functions
///
/// # Description {#bslalg_hashutil-description}
/// This component provides a namespace class, `HashUtil`, for
/// hash functions.  At the current time it has one hash function,
/// `HashUtil::computeHash`, which will hash most fundamental types, and
/// pointers, rapidly.  Note that when a pointer is passed, only the bits in the
/// pointer itself are hashed, the memory the pointer refers to is not examined.
///
/// ## Usage {#bslalg_hashutil-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example 1: Dumping Out Hash Values {#bslalg_hashutil-example-1-dumping-out-hash-values}
///
///
/// Suppose we want to analyze our hash function by seeing how it distributes
/// integers across buckets.   We will declare 64 buckets, and distribute hits
/// among the bucket by indexing them with the low order 6 bits of the hash.
/// Then we will display the distribution of hits in each bucket, to see if
/// the hash function is distributing them evenly.
/// @code
/// int buckets[64];
/// @endcode
/// First, we hash on the values of i in the range `[ 0, 1 << 15 )`:
/// @code
/// {
///     memset(buckets, 0, sizeof(buckets));
///     for (int i = 0; i < (1 << 15); ++i) {
///         std::size_t hash = bslalg::HashUtil::computeHash(i);
///
///         ++buckets[hash & 63];
///     }
///     if (verbose) printf("Straight hash:\n");
///     int col = 0;
///     for (int i = 0; i < 64; ++i) {
///         if (verbose) printf("%s%5d", (0 == col ? "    " : ", "),
///                                                           buckets[i]);
///         ++col;
///         if (8 == col) {
///             col = 0;
///             if (verbose) printf("\n");
///         }
///     }
/// }
/// @endcode
/// Then, we will hash on the values of `4 * i` for i in the range
/// `[ 0, 1 << 15 )`.  This is interesting because pointers will often be 4-byte
/// aligned and have the 2 low-order bits always zero, so this will be a
/// simulation of that:
/// @code
/// {
///     memset(buckets, 0, sizeof(buckets));
///     for (int i = 0; i < (1 << 15); ++i) {
///         std::size_t hash = bslalg::HashUtil::computeHash(4 * i);
///
///         ++buckets[hash & 63];
///     }
///     if (verbose) printf("\nStraight * 4 hash:\n");
///     int col = 0;
///     for (int i = 0; i < 64; ++i) {
///         if (verbose) printf("%s%5d", (0 == col ? "    " : ", "),
///                                                           buckets[i]);
///         ++col;
///         if (8 == col) {
///             col = 0;
///             if (verbose) printf("\n");
///         }
///     }
/// }
/// @endcode
/// Next, we will xor the bottom 30 bits of the hash into the bottom 6 bits, so
/// we'll be observing more of the whole word:
/// @code
/// {
///     memset(buckets, 0, sizeof(buckets));
///     for (int i = 0; i < (1 << 15); ++i) {
///         std::size_t hash = bslalg::HashUtil::computeHash(i);
///         hash = hash ^ (hash >> 6) ^ (hash >> 12) ^ (hash >> 18) ^
///                       (hash >> 24);
///
///         ++buckets[hash & 63];
///     }
///     if (verbose) printf("\nFolded hash:\n");
///     int col = 0;
///     for (int i = 0; i < 64; ++i) {
///         if (verbose) printf("%s%5d", (0 == col ? "    " : ", "),
///                                                           buckets[i]);
///         ++col;
///         if (8 == col) {
///             col = 0;
///             if (verbose) printf("\n");
///         }
///     }
/// }
/// @endcode
/// Now, bear in mind that an identity hash will perform very optimally on the
/// first and third tests we did.  This time we will take the difference between
/// the current hash and the previous one, a test for which the identity
/// function would perform abominably:
/// @code
/// {
///     memset(buckets, 0, sizeof(buckets));
///     std::size_t prev = 0;
///     for (int i = 0; i < (1 << 15); ++i) {
///         std::size_t hash = bslalg::HashUtil::computeHash(i);
///
///         ++buckets[(hash - prev) & 63];
///         prev = hash;
///     }
///     if (verbose) printf("\nDiff hash:\n");
///     int col = 0;
///     for (int i = 0; i < 64; ++i) {
///         if (verbose) printf("%s%5d", (0 == col ? "    " : ", "),
///                                                           buckets[i]);
///         ++col;
///         if (8 == col) {
///             col = 0;
///             if (verbose) printf("\n");
///         }
///     }
/// }
/// @endcode
/// Finally, take the difference between the previous hash and the current one,
/// only this time, instead of subtracting, take a bitwise xor:
/// @code
/// {
///     memset(buckets, 0, sizeof(buckets));
///     std::size_t prev = 0;
///     for (int i = 0; i < (1 << 15); ++i) {
///         std::size_t hash = bslalg::HashUtil::computeHash(i);
///
///         ++buckets[(hash ^ prev) & 63];
///         prev = hash;
///     }
///     if (verbose) printf("\nXor diff hash:\n");
///     int col = 0;
///     for (int i = 0; i < 64; ++i) {
///         if (verbose) printf("%s%5d", (0 == col ? "    " : ", "),
///                                                           buckets[i]);
///         ++col;
///         if (8 == col) {
///             col = 0;
///             if (verbose) printf("\n");
///         }
///     }
/// }
/// @endcode
/// The output produced by this usage example follows:
/// @code
/// Straight hash:
///       508,   501,   511,   502,   522,   524,   515,   500
///       501,   519,   523,   520,   495,   514,   540,   497
///       500,   523,   525,   518,   491,   515,   527,   509
///       513,   500,   511,   520,   487,   515,   505,   520
///       519,   516,   505,   534,   507,   514,   522,   517
///       538,   514,   510,   510,   531,   491,   513,   506
///       515,   497,   504,   496,   541,   508,   501,   523
///       501,   523,   485,   492,   517,   510,   503,   534
///
/// Straight * 4 hash:
///       513,   512,   493,   517,   514,   472,   501,   527
///       528,   504,   527,   507,   516,   494,   534,   514
///       517,   500,   513,   533,   507,   499,   511,   540
///       492,   518,   530,   522,   503,   522,   505,   494
///       520,   492,   490,   508,   538,   560,   522,   487
///       521,   516,   493,   491,   532,   504,   497,   530
///       495,   534,   537,   504,   487,   525,   533,   497
///       510,   499,   511,   506,   523,   512,   498,   517
///
/// Folded hash:
///       537,   493,   517,   544,   501,   508,   535,   528
///       502,   530,   536,   541,   500,   475,   540,   510
///       521,   513,   501,   525,   497,   511,   521,   513
///       522,   523,   479,   479,   508,   490,   507,   523
///       577,   490,   520,   514,   493,   465,   468,   511
///       518,   544,   503,   484,   550,   514,   517,   500
///       510,   501,   542,   528,   517,   456,   513,   530
///       518,   484,   510,   506,   522,   477,   563,   493
///
/// Diff hash:
///       329,   329,   526,   660,   755,   726,   466,   398
///       235,   410,   424,   713,   695,   714,   535,   314
///       342,   274,   598,   662,   711,   772,   498,   463
///       268,   360,   399,   655,   672,   694,   584,   311
///       404,   282,   601,   678,   660,   661,   418,   377
///       245,   425,   462,   762,   682,   627,   588,   295
///       369,   331,   529,   712,   659,   688,   418,   357
///       238,   387,   467,   687,   730,   695,   540,   302
///
/// Xor diff hash:
///       329,   142,   535,   475,   781,   800,   567,   510
///       258,   258,   378,   549,   664,   906,   477,   496
///       298,   118,   554,   467,   765,   883,   576,   418
///       233,   226,   375,   608,   633,   903,   422,   388
///       404,   133,   648,   412,   658,   896,   521,   459
///       258,   256,   383,   601,   699,   836,   511,   599
///       413,   169,   660,   450,   658,   826,   524,   560
///       237,   255,   383,   573,   706,   834,   539,   715
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslalg
 * @{
 */
/** @addtogroup bslalg_hashutil
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bsls_types.h>
 
#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <bsls_nativestd.h>
#endif // BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
 
 
 
namespace bslalg {
                        // ===============
                        // struct HashUtil
                        // ===============
 
/// This `struct` provides a namespace for hash functions.
struct HashUtil {
 
    // CLASS METHODS
 
    /// Return a `size_t` hash value corresponding to the specified `key`.
    /// Note that the return value is seemingly random (i.e., the hash is
    /// good) but identical on all platforms (irrespective of endianness).
    ///
    /// NOTE: We reserve the right to change these hash functions to return
    /// different values.  The current implementation only returns a 32 bit
    /// value -- when `std::size_t` is 64 bits, the high-order 32
    /// bits of the return value are all zero.  This is not a feature, it is
    /// a bug that we will fix in a later release.
    static std::size_t computeHash(char key);
    static std::size_t computeHash(signed char key);
    static std::size_t computeHash(unsigned char key);
    static std::size_t computeHash(short key);
    static std::size_t computeHash(unsigned short key);
    static std::size_t computeHash(int key);
    static std::size_t computeHash(unsigned int key);
    static std::size_t computeHash(long key);
    static std::size_t computeHash(unsigned long key);
    static std::size_t computeHash(long long key);
    static std::size_t computeHash(unsigned long long key);
    static std::size_t computeHash(float key);
    static std::size_t computeHash(double key);
    static std::size_t computeHash(const void *key);
};
 
// ============================================================================
//                        INLINE FUNCTION DEFINITIONS
// ============================================================================
 
}  // close package namespace
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */