bslh_defaulthashalgorithm

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Security
  • Speed
  • Hash Distribution
  • Hash Consistency
  • Usage
    • Example: Creating and Using a Hash Table

Purpose

Provide a reasonable hashing algorithm for default use.

Classes

• bslh::DefaultHashAlgorithm: a default hashing algorithm

See also

bslh_hash, bslh_defaultseededhashalgorithm

Description

bslh::DefaultHashAlgorithm provides an unspecified default hashing algorithm. The supplied algorithm is suitable for general purpose use in a hash table. The underlying algorithm is subject to change in future releases.

This class satisfies the requirements for regular bslh hashing algorithms, defined in bslh_hash.h. More information can be found in the package level documentation for bslh (internal users can also find information here {TEAM BDE:USING MODULAR HASHING<GO>})

Security

In this context "security" refers to the ability of the algorithm to produce hashes that are not predictable by an attacker. Security is a concern when an attacker may be able to provide malicious input into a hash table, thereby causing hashes to collide to buckets, which degrades performance. There are no security guarantees made by bslh::DefaultHashAlgorithm, meaning attackers may be able to engineer keys that will cause a Denial of Service (DoS) attack in hash tables using this algorithm. If security is required, an algorithm that documents better secure properties should be used, such as bslh_siphashalgorithm .

Speed

The default hash algorithm will compute a hash on the order of O(n) where n is the length of the input data. Note that this algorithm will produce hashes fast enough to be used to hash keys in a hash table. The chosen algorithm will be quicker than specialized algorithms such as SipHash, but not as fast as hashing using the identity function.

Hash Distribution

The default hash algorithm will distribute hashes in a pseudo-random distribution across the key space. The hash function will exhibit avalanche behavior, meaning changing one bit of input will result in a 50% chance of each output bit changing. Avalanche behavior is enough to guarantee good key distribution, even when values are consecutive.

Hash Consistency

The default hash algorithm guarantees only that hashes will remain consistent within a single process, meaning different hashes may be produced on machines of different endianness or even between runs on the same machine. Therefor it is not recommended to send hashes from bslh::DefaultHashAlgorithm over a network. It is also not recommended to write hashes from bslh::DefaultHashAlgorithm to any memory accessible by multiple machines.

Usage

This section illustrates intended usage of this component.

Example: Creating and Using a Hash Table

Suppose we have any array of types that define operator==, and we want a fast way to find out if values are contained in the array. We can create a HashTable data structure that is capable of looking up values in O(1) time.

Further suppose that we will be storing futures (the financial instruments) in this table. Since futures have standardized names, we don't have to worry about any malicious values causing collisions. We will want to use a general purpose hashing algorithm with a good hash distribution and good speed. This algorithm will need to be in the form of a hash functor – an object that will take objects stored in our array as input, and yield an integer value. The functor can pass the attributes of the TYPE that are salient to hashing into the hashing algorithm, and then return the hash that is produced.

We can use the result of the hash function to index into our array of buckets. Each bucket is simply a pointer to a value in our original array of TYPE objects. We will resolve hash collisions in our array through linear probing, where we will search consecutive buckets following the bucket where the collision occurred, testing occupied buckets for equality with the value we are searching on, and concluding that the value is not in the table if we encounter an empty bucket before we encounter one referring to an equal element.

First, we define our HashTable template class, with the two type parameters: TYPE (the type being referenced) and HASHER (a functor that produces the hash).

/// This class template implements a hash table providing fast lookup of
/// an external, non-owned, array of values of (template parameter)
/// `TYPE`.
///
/// The (template parameter) `TYPE` shall have a transitive, symmetric
/// `operator==` function.  There is no requirement that it have any
/// kind of creator defined.
///
/// The `HASHER` template parameter type must be a functor with a method
/// having the following signature:
///..
///  size_t operator()(TYPE)  const;
///                   -OR-
///  size_t operator()(const TYPE&) const;
///..
/// and `HASHER` shall have a publicly accessible default constructor
// and destructor.
///
/// Note that this hash table has numerous simplifications because we
/// know the size of the array and never have to resize the table.
template <class TYPE, class HASHER>
class HashTable {
 
    // DATA
    const TYPE       *d_values;          // Array of values table is to
                                         // hold
    size_t            d_numValues;       // Length of 'd_values'.
    const TYPE      **d_bucketArray;     // Contains ptrs into 'd_values'
    size_t            d_bucketArrayMask; // Will always be '2^N - 1'.
    HASHER            d_hasher;          // User supplied hashing algorithm
 
  private:
    // PRIVATE ACCESSORS
 
    /// Look up the specified `value`, having the specified `hashValue`,
    /// and load its index in `d_bucketArray` into the specified `idx`.
    /// If not found, return the vacant entry in `d_bucketArray` where
    /// it should be inserted.  Return `true` if `value` is found and
    /// `false` otherwise.
    bool lookup(size_t      *idx,
                const TYPE&  value,
                size_t       hashValue) const;
 
  public:
    // CREATORS
 
    /// Create a hash table referring to the specified `valuesArray`
    /// having length of the specified `numValues`.  No value in
    /// `valuesArray` shall have the same value as any of the other
    /// values in `valuesArray`
    HashTable(const TYPE *valuesArray,
              size_t      numValues);
 
    /// Free up memory used by this hash table.
    ~HashTable();
 
    // ACCESSORS
 
    /// Return true if the specified 'value' is found in the table and
    /// false otherwise.
    bool contains(const TYPE& value) const;
};

Then, we define a Future class, which holds a c-string name, char callMonth, and short callYear.

/// This class identifies a future contract.  It tracks the name, call
/// month and year of the contract it represents, and allows equality
/// comparison.
class Future {
 
    // DATA
    const char *d_name;    // held, not owned
    const char  d_callMonth;
    const short d_callYear;
 
  public:
    // CREATORS
 
    /// Create a `Future` object out of the specified `name`,
    /// `callMonth`, and `callYear`.
    Future(const char *name, const char callMonth, const short callYear)
    : d_name(name), d_callMonth(callMonth), d_callYear(callYear)
    {}
 
    /// Create a 'Future' with default values.
    Future() : d_name(""), d_callMonth('\0'), d_callYear(0)
    {}
 
    // ACCESSORS
 
    /// Return the month that this future expires.
    const char * getMonth() const
    {
        return &d_callMonth;
    }
 
    /// Return the name of this future.
    const char * getName() const
    {
        return d_name;
    }
 
    /// Return the year that this future expires.
    const short * getYear() const
    {
        return &d_callYear;
    }
 
    /// Compare this to the specified `other` object and return true if
    /// they are equal.
    bool operator==(const Future& other) const
    {
        return (!strcmp(d_name, other.d_name))  &&
           d_callMonth == other.d_callMonth &&
           d_callYear  == other.d_callYear;
    }
};
 
/// Compare compare the specified `lhs` and `rhs` objects and return
/// true if they are not equal.
bool operator!=(const Future& lhs, const Future& rhs)
{
    return !(lhs == rhs);
}

Next, we need a hash functor for Future. We are going to use the DefaultHashAlgorithm because it is a fast, general purpose hashing algorithm that will provide an easy way to combine the attributes of Future objects that are salient to hashing into one reasonable hash that will distribute the items evenly throughout the hash table. Moreover, when a new hashing algorithm is discovered to be a better default, we can be automatically be upgraded to use it as soon as bslh::DefaultHashAlgorithm is updated.

/// This struct is a functor that will apply the `DefaultHashAlgorithm`
/// to objects of type `Future`.
struct HashFuture {
 
    /// Return the hash of the of the specified `future`.  Note that
    /// this uses the `DefaultHashAlgorithm` to quickly combine the
    /// attributes of `Future` objects that are salient to hashing into
    /// a hash suitable for a hash table.
    size_t operator()(const Future& future) const
    {
        DefaultHashAlgorithm hash;
 
        hash(future.getName(),  strlen(future.getName()));
        hash(future.getMonth(), sizeof(char));
        hash(future.getYear(),  sizeof(short));
 
        return static_cast<size_t>(hash.computeHash());
    }
};

Then, we want to actually use our hash table on Future objects. We create an array of Futures based on data that was originally from some external source:

    Future futures[] = { Future("Swiss Franc", 'F', 2014),
                         Future("US Dollar", 'G', 2015),
                         Future("Canadian Dollar", 'Z', 2014),
                         Future("British Pound", 'M', 2015),
                         Future("Deutsche Mark", 'X', 2016),
                         Future("Eurodollar", 'Q', 2017)};
    enum { NUM_FUTURES = sizeof futures / sizeof *futures };

Next, we create our HashTable hashTable. We pass the functor that we defined above as the second argument:

    HashTable<Future, HashFuture> hashTable(futures, NUM_FUTURES);

Now, we verify that each element in our array registers with count:

    for ( int i = 0; i < 6; ++i) {
        ASSERT(hashTable.contains(futures[i]));
    }

Finally, we verify that futures not in our original array are correctly identified as not being in the set:

    ASSERT(!hashTable.contains(Future("French Franc", 'N', 2019)));
    ASSERT(!hashTable.contains(Future("Swiss Franc", 'X', 2014)));
    ASSERT(!hashTable.contains(Future("US Dollar", 'F', 2014)));