Component of the Week #11: `bslh_hash`

Summary:

Provide composable facilities for defining hash functions.

A hash table is a fundamental associative data structure that provides efficient — O(1) — algorithms to look up the data associated with a given value of its key type. This lookup depends on having a quality hash function that (quickly) maps arbitrary values of the key type to a fixed-width integral type (like std::size_t) with as few collisions as possible.

The C++ standard library has, since C++11, provided hash table based containers in the form of std::unordered_set and std::unordered_map (and their corresponding multi-value alternatives). In C++23, these expanded to included std::flat_map. BDE provides our own implementations in the bsl namespace, such as bslstl_unorderedset and bslstl_unorderedmap. In addition, BDE has more hash table based associated containers like bdlc_flathashmap and bdlcc_stripedunorderedmap.

All of these containers depend on being able to compute a hash value for an instance of the key type. The standard computes hash values through the use of std::hash<T>, which is a functor that may be specialized for user-defined types. This approach, however, has drawbacks — users are writing code themselves in namespace std, they must implement a correct and performant hashing algorithm themselves, and composing hashing operations in terms of hashing each member is not supported by the interface. BDE’s hashing system package, which is used by bsl::hash, aims to solve all of these problems.

bsl::hash computes the hash value of an object in three steps:

1) An instance of a hash algorithm is created (which at the time of this writing is, by default, an instance of bslh::WyHashIncrementalAlgorithm). This object will be used to accumulate a hash value efficiently.

2) The function hashAppend is then invoked with two parameters — the hash algorithm and the object being hashed, to update the hash value recursively for every relevant part of the object being hashed.

3) The final hash value that has accumulated in the hash algorithm object will be returned.

This hashing system separates concerns in certain key ways:

For any user-defined type, a function hashAppend can be defined that identifies the (salient) properties of that type relevant to computing a hash value for objects of that type. For a specific type T, a hashAppend for T should be a free function template in the same namespace or hidden friend, templated on the hash algorithm:
class T { /* ... */ };

template <typename t_HASH_ALGORITHM>
void hashAppend(t_HASH_ALGORITHM& hashAlg, const T& value);
This function need only do one thing – recursively call hashAppend for each of the constituent and subobjects of T that are salient parts of the value of an object of type T.

For any composite object, hashAppend can recursively be applied to all members that are part of the salient value of the object — i.e., exactly those members that participate in the determination of object equality done by operator==.

Raw bytes can be passed to update the hash algorithm directly by passing a pointer and size to the call operator of the hash algorithm.

For more information on implementing correct overloads of hashAppend, see the discussion on implementing hashAppend in the package documentation for bslh.
A hash algorithm can be selected, independently of the users implementation of hashAppend for their user-defined types. This allows the use of tested and vetted hash algorithms that typically provide an a good distribution of values, and avoid problems that may cause degenerate behavior in associative containers (such as not making use of all the bytes of the hash value).

By default bslh::Hash will use WyHash, which provides a good balance of performance and sensitivity to its inputs.

Users may, for example, wish to perform hashing with an algorithm with different guarantees, such as bslh::SipHashAlgorithm) that provides better protections against malicious inputs.

Putting this to use is simple. Let’s say you are writing a variation on a popular mining-themed game and want to keep track of graffiti written on the faces of voxels in your world. You begin by modeling voxel locations as a combination of a dimension and coordinates, while each face of a voxel can be identified using an enum, both of which you combine to make your Face type that represents any face of any voxel in your universe:

namespace mine {

class Location {
// ...
public:
    const bsl::string& getDimension() const;
    const int getX() const;
    const int getY() const;
    const int getZ() const;
// ...
};

enum class Facing {
    e_TOP, e_BOTTOM, e_NORTH, e_SOUTH, e_EAST, e_WEST
};

class Face {
// ...
public:
    const Location& getLocation() const;
    const Facing getFacing() const;
// ...
};

}  // close namespace mine

Now you’d like to track, in an associative container, what has been written on each face:

bsl::unordered_map<mine::Face, bsl::string> allGraffiti;

The problem here, of course, is that mine::Face does not support hashing. Solving that problem is easy, however, by defining a hashAppend in the same namespace:

namespace mine {
template <typename t_HASH_ALGORITHM>
void hashAppend(t_HASH_ALGORITHM& hashAlg, const Face& face)
{
    using bslh::hashAppend;
    hashAppend(hashAlg, face.getLocation());
    hashAppend(hashAlg, face.getFacing());
}
}  // close namespace mine

Of course, this will depend on having hashAppend work for the members we are recursively applying it to — an instance of another user-defined type mine::Location and our enum, mine::Facing. For the Location type we do exactly the same thing we did for Face and define an overload for hashAppend:

namespace mine {
template <typename t_HASH_ALGORITHM>
void hashAppend(t_HASH_ALGORITHM& hashAlg, const Location& location)
{
    using bslh::hashAppend;
    hashAppend(hashAlg, location.getDimension());
    hashAppend(hashAlg, location.getX());
    hashAppend(hashAlg, location.getY());
    hashAppend(hashAlg, location.getZ());
}
}  // close namespace mine

For the enum, the int coordinate values, and even for bsl::string we don’t need to do anythiing else — hashAppend already has the needed overloads in the right namespaces (bsl for bsl::string and bslh for the scalar types).

Now our bsl::unordered_map can be used to track all the graffiti we might ever want to track:

void initializeGraffiti()
{
    allGraffiti[ {{"overworld", 0, 40, 0}, Facing::e_TOP} ] = "Spawn Here";
    allGraffiti[ {{"nether", 0, 0, 0}, Facing:e_SOUTH} ]    = "Scary Place";
    allGraffiti[ {{"end", 0, -40, 0}, Facing:e_BOTTOM} ]    = "Fall Forever";
}

If you’d like to know more, check out the documentation for bslh_hash for details. There, and in the bslh package, you will find:

Other hash algorithms that can be used instead of the default.

The many BDE and std types that already have support for hashAppend.

Component of the Week #11: bslh_hash

Component of the Week #11: `bslh_hash`