Types Don't Know #

Contents

• Introduction
• The Example
• Solution 1: Specialize std::hash<X>
  • What about implementing it with N3333?
• How to get X to use a general purpose hashing algorithm
  • Introducing the Universal hash function!
  • What is hash_append?
    • Rules Relating hash_append to operator==
  • hash_append for vector<T, A>
  • hash_append for std::pair<T, U>
  • hash_append for int
  • An Optimization: is_contiguously_hashable<T>:
  • Wait a minute. Isn't hash_append the same thing as boost::hash_combine?
  • Wait a minute. Isn't hash_append the same thing as serialization?
  • Is there a variadic version of hash_append?
  • How easily can algorithms other than FNV-1a be used?
  • What is involved in switching hashing algorithms?
  • How does one hash_append Pimpl designs?
  • How does one apply random seeding?
  • What about unordered containers?
  • How does the quality of the resulting hash codes compare to the hash_combine solution?
• Summary
  • Summary of proposed infrastructure
• Appendix A: type_erased_hasher
• Appendix B: B is for Bike Shed
• Appendix C: debugHasher
• Appendix D: Proposed Wording
• Acknowledgments

Introduction

This paper proposes a new hashing infrastructure that completely decouples hashing algorithms from individual types that need to be hashed. This decoupling divides the hashing computation among 3 different programmers who need not coordinate with each other:

1. Authors of hashable types (keys of type K) write their hashing support just once, using no specific hashing algorithm. This code resembles (and is approximately the same amount of work as) operator== and swap for a type.

2. Authors of hashing algorithms write a functor (e.g. H) that operates on a contiguous chunk of generic memory, represented by a void const* and a number of bytes. This code has no concept of a specific key type, only of bytes to be hashed.

3. Clients who want to hash keys of type K using hashing algorithm H will form a functor of type std::uhash<H> to give to an unordered container.

   unordered_set<K, uhash<H>> my_set;
   

   Naturally, there could be a default hashing algorithm supplied by the std::lib:

   unordered_set<K, uhash<>> my_set;
   

To start off with, we emphasize: there is nothing in this proposal that changes the existing std::hash, or the unordered containers. And there is also nothing in this proposal that would prohibit the committee from standardizing both this proposal, and either one of N3333 or N3876. N3333 and N3876 contradict each other, and thus compete with each other. Both cannot be standardized. This proposal, on the other hand, addresses a problem not addressed by N3333 or N3876. Nor does this proposal depend upon anything in N3333 or N3876.

This paper simply takes a completely different approach to producing hash codes from types, in order to solve a problem that was beyond the scope of N3333 and N3876. The problem solved herein is how to support the hashing of N different types of keys using M different hashing algorithms, using an amount of source code that is proportional to N+M, as opposed to the current system based on std::hash<T> which requires an amount of source code proportional to N*M. And consequently in practice today M==1, and the single hashing algorithm is supplied only by the std::lib implementor. As it is too difficult and error prone for the client to supply alternative algorithms for all of the built-in scalar types (int, long, double, etc.). Indeed, it has even been too difficult for the committee to supply hashing support for all of the types our clients might reasonably want to use as keys: pair, tuple, vector, complex, duration, forward_list etc.

This paper makes ubiquitous hash support for most types as easy and as practical as is today's support for swap and operator==.

This paper starts with an assertion:

Types should not know how to hash themselves.

The rest of this paper begins with demonstrating the problems created when software systems assume that types do know how to hash themselves, and what can be done to solve these problems.

The Example

Instead of starting with a basic example like std::string or int, this paper will introduce an example class X that is meant to be representative of a type that a programmer would write, and would want to create a hash code for:

namespace mine
{

class X
{
    std::tuple<short, unsigned char, unsigned char> date_;
    std::vector<std::pair<int, int>>                data_;

public:
    X();
    // ...
    friend bool operator==(X const& x, X const& y)
    {
        return std::tie(x.date_, x.data_) == std::tie(y.date_, y.data_);
    }
};

}  // mine

How do we write the hash function for X?

Solution 1: Specialize std::hash<X>

If we standardize N3876 which gives us hash_combine and hash_val from boost, then this is relatively doable:

}  // mine

namespace std
{

template <>
struct hash<mine::X>
{
    size_t
    operator()(mine::X const& x) const noexcept
    {
        size_t h = hash<tuple_element<0, decltype(x.date_)>::type>{}(get<0>(x.date_));
        hash_combine(h, get<1>(x.date_), get<2>(x.date_));
        for (auto const& p : x.data_)
            hash_combine(h, p.first, p.second);
        return h;
    }
};

}  // std

First we need to break out of our own namespace, and then specialize std::hash in namespace std. And we also need to add a friend statement to our class X:

friend struct std::hash<X>;

Without hash_combine from N3876 we would have to write our own hash_combine. This could easily result in a bad hash function as aptly described in N3876.

What about implementing it with N3333?

In our first attempt to use the tools presented in N3333, we were surprised at the difficulty, as we were expecting it to be easier. However after studying the reference implementation in LLVM, we succeeded in writing the following friend function of X:

friend
std::hash_code
hash_value(X const& x)
{
    using std::hash_value;
    return std::hash_combine
        (
            hash_value(std::get<0>(x.date_)),
            hash_value(std::get<1>(x.date_)),
            hash_value(std::get<2>(x.date_)),
            std::hash_combine_range(x.data_.begin(), x.data_.end())
        );
}

We also strongly suspect that with a little more work on the proposal, this could be simplified down to:

friend
std::hash_code
hash_value(X const& x)
{
    using std::hash_value;
    return std::hash_combine(hash_value(x.date_), std::hash_combine_range(x.data_.begin(), x.data_.end()));
}

Or possibly even:

friend
std::hash_code
hash_value(X const& x) noexcept
{
    using std::hash_value;
    return std::hash_combine(hash_value(x.date_), hash_value(x.data_));
}

The reduced burden on the author of X on writing the code to hash X is very much welcomed! However, hashing algorithms are notoriously difficult to write. Has the author of X written a good hashing algorithm?

The answer is that the author of X does not know, until he experiments with his data. The hashing algorithm is supplied by the std::lib implementor. If testing reveals that the algorithm chosen by the std::lib implementor is not appropriate for the client's data set, then everything offered by both N3333 and N3876 is for naught. The author of X is on his own, starting from scratch, to build an alternate hashing algorithm -- even if just to experiment.

This concern is not theoretical. If the keys to be hashed can be influenced by a malicious attacker, it is quite possible for the attacker to arrange for many distinct keys that all hash to the same hash code. Even some seeded hashing algorithms are vulnerable to such an attack.

Here is a very short and fast C++ program that can generate as many distinct keys as you like which all hash to the same hash code using MurmurHash3, even with a randomized seed. Here is another such C++ program demonstrating a similar seed-independent attack on CityHash64. These attacks do not mean that these are bad hashing algorithms. They simply are evidence that it is not wise to tie yourself down to a single hashing algorithm. And if the effort to change, or experiment with, hashing algorithms takes effort that is O(N) (where N is the number of types or sub-types to be hashed), then one is tied down.

This paper demonstrates infrastructure allowing the author of X to switch hashing algorithms with O(1) work, regardless of how many sub-types of X need to be hashed. No matter what hashing algorithm is used, the C++ code to hash X is the same:

template <class HashAlgorithm>
friend
void
hash_append(HashAlgorithm& h, X const& x) noexcept
{
    using std::hash_append;
    hash_append(h, x.date_, x.data_);
}

With this proposal, the author of X gets simplicity, without being heavily invested in any single hashing algorithm. The hashing algorithm is completely encapsulated in the templated parameter HashAlgorithm, and the author of X remains fully and gratefully ignorant of any specific hashing algorithm.

How to get X to use a general purpose hashing algorithm

The key to solving this problem is the recognition of one simple observation:

Types should not know how to hash themselves. However types do know what parts of their state should be exposed to a hashing algorithm.

The question now becomes: How do you present X to a general purpose hashing algorithm without binding it to any specific algorithm?

Just as an example, here is a very simple hashing algorithm that many have used with great success:

std::size_t
fnv1a (void const* key, std::size_t len)
{
    unsigned char const* p = static_cast<unsigned char const*>(key);
    unsigned char const* const e = p + len;
    std::size_t h = 14695981039346656037u;
    for (; p < e; ++p)
        h = (h ^ *p) * 1099511628211u;
    return h;
}

Although most modern hashing algorithms are much more complicated than fnv1a shown above, there are similarities among them.

• They generally take a stream of bytes as their input. This is often specified as a void const* and a size_t length.
• This interface implies that they work on a contiguous array of bytes.
• The algorithms generally have an initialization stage, often taking an optional seed, followed by an accumulation stage which depends on the supplied bytes, followed by a finalization stage after all of the bytes are consumed.

Not all, but most of the algorithms also have the property that they consume bytes in the order that they are received, possibly with a fixed sized internal buffer. This characteristic can be taken advantage of in order to hash discontiguous memory.

For example consider this minor repackaging of the FNV-1a algorithm:

class fnv1a
{
    std::size_t state_ = 14695981039346656037u;
public:
    using result_type = std::size_t;

    void
    operator()(void const* key, std::size_t len) noexcept
    {
        unsigned char const* p = static_cast<unsigned char const*>(key);
        unsigned char const* const e = p + len;
        for (; p < e; ++p)
            state_ = (state_ ^ *p) * 1099511628211u;
    }

    explicit
    operator result_type() noexcept
    {
        return state_;
    }
};

Now the algorithm can be accessed in 3 stages:

1. The algorithm is initialized in a constructor, in this case the implicit default constructor. Other constructors / initializations should be possible. But we start out with this simplest of algorithms.
2. The algorithm consumes bytes in the operator()(void const* key, std::size_t len) function. Note that this function can be called any number of times. In each call the hashed memory is contiguous. But there is no requirement at all that separate calls refer to a single block of memory. On each call, the state of the algorithm is recalled from the previous call (or from the initialization step) and updated with the new len bytes located at key.
3. The algorithm is finalized when the object is converted to a result_type (in this case a size_t). This is the finalization stage, which in this case is trivial, but could be arbitrarily complex.

With the FNV-1a algorithm divided into its 3 stages like this, one can call it in various ways, for example:

fnv1a::result_type
hash_contiguous(int (&data)[3])
{
    fnv1a h;
    h(data, sizeof(data));
    return static_cast<fnv1a::result_type>(h);
}

or

fnv1a::result_type
hash_discontiguous(int data1, int data2, int data3)
{
    fnv1a h;
    h(&data1, sizeof(data1));
    h(&data2, sizeof(data2));
    h(&data3, sizeof(data3));
    return static_cast<fnv1a::result_type>(h);
}

But either way it is called, given the same inputs, the algorithm outputs the exact same result:

int data[] = {5, 3, 8};
assert((hash_contiguous(data) == hash_discontiguous(5, 3, 8)));

We can say that fnv1a meets the requirements of a HashAlgorithm. A HashAlgorithm is a class type that can be constructed (default, or possibly with seeding), has an operator() member function with the signature represented above. The operator() member function processes bytes, updating the internal state of the HashAlgorithm. This internal state can be arbitrarily complex. Indeed an extreme example of internal state could be a copy of every chunk of memory supplied to the HashAlgorithm. And finally a HashAlgorithm can be explicitly converted to the nested type result_type, which when used with the unordered containers should be an alias for size_t.

At all times during its lifetime, a HashAlgorithm is CopyConstructible and CopyAssignable, with each copy getting an independent copy of the state from the right-hand-side of the copy (value semantics -- no aliasing among copies). Thus if one knew that two sequences of data shared a common prefix, one could hash the prefix in just one sequence, make a copy of the HashAlgorithm, and then continue after the prefix in each sequence with the two independent HashAlgorithms. This would be a pure optimization, getting the same results as if one had hashed each sequence in full.

Introducing the Universal hash function!

Given the concept of HashAlgorithm, a universal hash functor, which takes any type T can now be written (almost):

template <class HashAlgorithm>
struct uhash
{
    using result_type = typename HashAlgorithm::result_type;

    template <class T>
    result_type
    operator()(T const& t) const noexcept
    {
        HashAlgorithm h;
        using std::hash_append;
        hash_append(h, t);
        return static_cast<result_type>(h);
    }
};

Now one can use uhash<fnv1a> as the hash function for std::unordered_map, for example:

std::unordered_map<MyKey, std::string, uhash<fnv1a>> the_map;

First note several important attributes of uhash:

1. uhash depends only on the hashing algorithm, which is encapsulated in the HashAlgorithm. uhash does not depend upon the type T being hashed.
2. uhash is simple. Though such a utility should certainly be supplied by the std::lib, any programmer can very easily implement their own variant of uhash for desired customizations (e.g. random seeding, salting, or padding), without having to revisit the hashing code for distinct types.
3. For applications other than unordered containers, and for hashing algorithms that support it, the programmer can easily create a hash functor that returns something besides a size_t. For example, this could come in handy for computing a SHA-256 result. And all without having to revisit each individual type!

Let's walk through uhash one step at a time.

1. The HashAlgorithm is constructed (default constructed in this example, but that is not the only possibility). This step initializes the hashing algorithm encapsulated in the HashAlgorithm.

2. It is appended to using t as a key. The function hash_append is implemented for each type that supports hashing. We will see below that such support code need be written only once per type in order to support many hashing algorithms. It is implemented in the type's own namespace, but there are implementations in namespace std for most scalars (just like swap).

3. And then the HashAlgorithm is explicitly converted to the desired result. This is where the algorithm is "finalized."

The above hash functor is accessing the generic hashing algorithm by its 3 distinct phases. Additionally, this hash functor could even be defaulted to use your favorite hash algorithm:

template <class HashAlgorithm = fnv1a> struct uhash;

The question usually arises now: Are you proposing that uhash<> replace hash<T> as the default hash functor in the unordered containers? The answer is it really almost doesn't matter. With templated using declarations, it is just so easy for programmers to specify their own defaults:

namespace my
{
template <class Key, class T, class Hash = std::uhash<>, class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<Key const, T>>>
    using unordered_map = std::unordered_map<Key, T, Hash, Pred, Alloc>;
}  // my

// ...

my::unordered_map<MyKey, std::string> the_map;  // uses std::uhash<> instead of std::hash<MyKey>

What is hash_append?

The hash_append function is the way that individual types communicate with the HashAlgorithm.

Each type T is responsible only for exposing its hash-worthy state to the HashAlgorithm in the function hash_append. T is not responsible for combining hash codes. Nor is it responsible for any hashing arithmetic whatsoever. It is only responsible for pointing out where its data is, how many different chunks of data there are, and what order they should be presented to the HashAlgorithm.

For example, here is how X might implement hash_append:

class X
{
    std::tuple<short, unsigned char, unsigned char> date_;
    std::vector<std::pair<int, int>>                data_;

public:
    // ...
    friend bool operator==(X const& x, X const& y)
    {
        return std::tie(x.date_, x.data_) == std::tie(y.date_, y.data_);
    }

    // Hook into the system like this
    template <class HashAlgorithm>
    friend void hash_append(HashAlgorithm& h, X const& x) noexcept
    {
        using std::hash_append;
        hash_append(h, x.date_);
        hash_append(h, x.data_);
    }
}

Like swap, hash_append is a customization point for each type. Only a type knows what parts of itself it should expose to a HashAlgorithm, even though the type has no idea what algorithm is being used to do the hashing. Note that X need not concern itself with details like whether or not its sub-types are contiguously hashable. Those details will be handled by the hash_append for the individual sub-types. The only information the hash_append overload for X must implement is what sub-types need to be presented to the HashAlgorithm, and in what order. Furthermore the hash_append function is intimately tied to the operator== for the same type. For example if for some reason x.data_ did not participate in the equality computation, then it should also not participate in the hash_append computation.

Rules Relating hash_append to operator==

For all combination of two values of X, x and y, there are two rules to follow in designing hash_append for type X. Actually the second rule is more of a guideline. But it should be followed as closely as possible:

1. If x == y, then both x and y shall send the same message to the HashAlgorithm in hash_append.

2. If x != y, then x and y should send different messages to the HashAlgorithm in hash_append.

It is very important to keep these two rules in mind when designing the hash_append function for any type, or for any instantiation of a class template. Failure to follow the first rule will mean that equal values hash to different codes. Clients such as unordered containers will simply fail to work, resulting in run time errors if this rule is violated. Failure to follow the second guideline will result in hash collisions for the two different values that send identical messages to the HashAlgorithm, and will thus degrade the performance of clients such as unordered containers.

hash_append for vector<T, A>

For example std::vector<T, A> would never expose its capacity(), since capacity() can be different for vector's that otherwise compare equal. Likewise it should not expose its allocator_type to hash_append, since this value also does not participate in the equality computation.

Should vector expose its size() to the HashAlgorithm? To find out, lets look closer at the operator== for vector:

Two vector's x and y compare equal if x.size() == y.size() and if x[i] == y[i] for i in the range of 0 to x.size().

To meet rule 1, it is sufficient that every element in the vector be sent to the HashAlgorithm as part of the vector's message. A logical convention is that the elements will be sent in order from begin() to end(). But this alone will not satisfy rule 2. Consider:

std::vector<std::vector<int>> v1{};
std::vector<std::vector<int>> v2{1};
assert(v1 != v2);

v1 and v2 are not equal. v1.size() == 0 and v2.size() == 1. However v2.front().size() == 0. If an empty vector<int> sends no message at all to the HashAlgorithm, then v2, even though it is not empty, also sends no message to the HashAlgorithm. And therefore v1 and v2 send the same (0 length) message to the HashAlgorithm, violating rule 2.

One idea for fixing this is to special case 0-length vectors to output a special value such as "empty" or 0. However in the first case the result would be ambiguous with a vector<string> of length 1 containing the string "empty". The second case has the exact same problem but for vector<int>.

The right way to fix this problem is to have vector<T> send its size() in addition to sending all of its members to the HashAlgorithm. Now the only question is: Should it send its size before or after sending its members to the HashAlgorithm?

To answer this last question, consider another sequence container: forward_list<T>. It has the exact same issues as we have been discussing for vector<T>, but forward_list<T> has no size() member. In order to send its size(), forward_list<T> has to loop through all of its members to first compute size(). In order to avoid the requirement that hash_append for forward_list<T> make two passes through the list, we should specify that the size() of the container is sent to the HashAlgorithm after all of the elements are sent. And for consistency, we should do this for all std-containers for which hash_append is defined.

template <class HashAlgorithm, class T, class Alloc>
void
hash_append(HashAlgorithm& h, std::vector<T, Alloc> const& v) noexcept
{
    for (auto const& t : v)
        hash_append(h, t);
    hash_append(h, v.size());
}

I.e. vector considers itself a message composed of 0 or more sub-messages, and appends each sub-message (in order) to the state of the generic HashAlgorithm. And this is followed with a final message consisting of the size() of the vector.

Note that as N3333 and N3876 both stand today, this critically important but subtle detail is not treated, and is left up to the client (the author of X) to get right. This proposal states that this is a detail that the hash_append for vector (and every other hashable std-container) is responsible for.

Emphasis

The message a type sends to a HashAlgorithm is part of its public API. E.g. whether or not a container includes its size() in its hash_append message, and if so, whether the size() is prepended or appended to the message, is critical information a type's client needs to know, in order to ensure that their composition of some type's message with another type's message doesn't produce an ambiguous message (doesn't create collisions).

The standard should clearly document the message emanating from every hash_append it defines, to the extent possible. It might not be possible to nail down that an implementation is using IEEE floating point or two's complement signed integers. But the standard can certainly document the message produced by a vector or any other std-defined class type.

hash_append for std::pair<T, U>

The situation is simpler for std::pair<T, U>:

template <class HashAlgorithm, class T, class U>
void
hash_append (HashAlgorithm& h, std::pair<T, U> const& p) noexcept
{
    hash_append (h, p.first);
    hash_append (h, p.second);
}

All there is to do is to just hash_append the first and second members of the pair.

hash_append for int

Eventually hash_append will drill down to a scalar type such as int:

template <class HashAlgorithm>
void
hash_append(HashAlgorithm& h, int const& i) noexcept
{
    h(&i, sizeof(i));
}

Whereupon a contiguous chunk of memory is actually accumulated by the HashAlgorithm, using the HashAlgorithm's operator(). Recall that the HashAlgorithm has a member function operator()(const void* key, std::size_t len) noexcept. And the int is just a chunk of contiguous memory that is hashable. It is now prudent to deeply consider what it means to say that a type (such as int) is contiguously hashable.

A type T is contiguously hashable if for all combinations of two values of a type, say x and y, if x == y, then it must also be true that memcmp(addressof(x), addressof(y), sizeof(T)) == 0. I.e. if x == y, then x and y have the same bit pattern representation. A 2's complement int satisfies this property because every bit pattern an int can have results in a distinct value (rule 2). And there are no "padding bits" which might take on random values. This property is necessary because if two values are equal, then they must hash to the same hash code (rule 1).

An Optimization: is_contiguously_hashable<T>:

With that in mind we can easily imagine a type trait:

template <class T> struct is_contiguously_hashable;

which derives from either true_type or false_type. And on 2's complement systems, is_contiguously_hashable<int>::value is true. And we might anticipate that some other types, such as char and long long are also contiguously hashable. With this tool we can now easily write hash_append for all contiguously hashable types:

template <class HashAlgorithm, class T>
inline
std::enable_if_t
<
    is_contiguously_hashable<T>::value
>
hash_append(HashAlgorithm& h, T const& t) noexcept
{
    h(addressof(t), sizeof(t));
}

Now the task remains to specialize is_contiguously_hashable properly for those scalars we want to use this implementation of hash_append for, and for any other scalars, implement hash_append appropriately. As an example of the latter, consider IEEE floating point types.

An IEEE floating point type is not contiguously hashable because 0. == -0. but these two values are represented with different bit patterns. Rule 1 would be violated if hashed contiguously. Therefore the hash_append for IEEE floating point types must go to extra effort to ensure that 0. and -0. hash to identical hash codes, but without dictating a specific hash algorithm. This could be done like so:

template <class HashAlgorithm, class T>
inline
std::enable_if_t
<
    std::is_floating_point<T>::value
>
hash_append(HashAlgorithm& h, T t) noexcept
{
    if (t == 0)
        t = 0;
    h(&t, sizeof(t));
}

I.e. if the value is -0., reset the value to 0., and then contiguously hash the resulting bits.

N3333 also introduced a very similar is_contiguous_layout trait. Although the paper did not make it perfectly clear, we believe is_contiguously_hashable is approximately the same trait, but with a better name. Just because a type has a contiguous layout does not necessarily imply that a type is contiguously hashable. IEEE floating point is a case in point. IEEE floating point does have a contiguous layout (and is trivially copyable, and has a standard layout). And yet still it is not contiguously hashable because of how its operator== works with signed zeros (violating rule 1).

Class types that are composed of only contiguously hashable types and that have no padding bytes, may also be considered to be contiguously hashable. For example consider this specialization of is_contiguously_hashable<std::pair<T, U>>:

template <class T, class U>
struct is_contiguously_hashable<std::pair<T, U>>
    : public std::integral_constant<bool, is_contiguously_hashable<T>::value &&
                                          is_contiguously_hashable<U>::value &&
                                          sizeof(T) + sizeof(U) == sizeof(std::pair<T, U>)>
{
};

In English: If the pair's two types are both contiguously hashable, and if the size of the two members is the same size as the pair (so there are no padding bytes), then the entire pair itself is contiguously hashable!

This same logic can be applied to array, tuple, and possibly user-defined types as well (but only with the user-defined type's author's permission). Consequently, a great many types can be easily and safely classified as contiguously hashable. This is important because with modern hash algorithm implementations, the bigger the chunk of contiguous memory you can send to the HashAlgorithm at one time, the higher the performance (in terms of bytes-hashed/second) the HashAlgorithm is likely to perform.

With that in mind (the bigger the memory chunk the better), consider again hash_append for vector:

template <class HashAlgorithm, class T, class Alloc>
inline
std::enable_if_t
<
    !is_contiguously_hashable<T>::value
>
hash_append(HashAlgorithm& h, std::vector<T, Alloc> const& v) noexcept
{
    for (auto const& t : v)
        hash_append(h, t);
    hash_append(h, v.size());
}

template <class HashAlgorithm, class T, class Alloc>
inline
std::enable_if_t
<
    is_contiguously_hashable<T>::value
>
hash_append(HashAlgorithm& h, std::vector<T, Alloc> const& v) noexcept
{
    h(v.data(), v.size()*sizeof(T));
    hash_append(h, v.size());
}

I.e. if the T is contiguously hashable, then even though vector itself is not, there can still be a huge optimization made by having vector send its contiguous data buffer to hash_append.

Note that this is a pure optimization. I.e. the HashAlgorithm sees the exact same sequence of bytes, in the same order, whether or not this optimization for vector is done. But if it is done, then the HashAlgorithm sees almost all of the bytes at once.

This optimization could be made for vector without any help from the std::lib. Other optimizations are possible, but could only be made from within the std::lib. For example, what if T is bool in the above example? vector<bool> doesn't follow the usual vector rules. What about deque<T>? It could hash its internal contiguous buffers all at once, but there is no way to implement that without intimate knowledge of the internals of the deque implementation. Externally, the best one can do for deque<T> is to send each individual T to hash_append one at a time. This still gives the very same correct message, but is just much slower.

Because only the std::lib implementor can fully implement this optimization for types such as deque, bitset and vector<bool>, it is important that we standardize is_contiguously_hashable and hash_append instead of asking the programmer to implement them (for std-defined types).

If you believe your type to be contiguously hashable, you should specialize is_contiguously_hashable<YourType> appropriately, as has been shown for pair. This would mean that not only is hashing YourType optimized, but hashing vector<YourType>, et. al. is also optimized! But note that there is no bullet proof way to automate the registration of YourType with is_contiguously_hashable as IEEE floating point so ably demonstrates. To do so requires an in depth analysis of operator== for YourType, which only the author of YourType is qualified to do.

Wait a minute. Isn't hash_append the same thing as boost::hash_combine?

No!

boost::hash_combine is used to combine an already computed hash code with an object that is to be hashed with boost::hash<T> (and this is also the N3876 hash_combine, modulo using std::hash<T>).

The N3333 hash_combine takes two objects, hashes both of them with std::hash<T>, and combines those two hash codes into one.

In contrast hash_append is used to expose an object's hashable state to an arbitrary hashing algorithm. It is up to the generic hashing algorithm to decide how to combine later bytes with earlier bytes.

Wait a minute. Isn't hash_append the same thing as serialization?

It is very closely related. Close enough that there may be a way to elegantly combine the two. Each type can expose its state to a HashAlgorithm or Serializer. However there are differences. IEEE floating point is our poster-child for the difference. For hashing, IEEE floating point needs to hide the difference between -0. and 0. For serialization one needs to keep these two values distinct. Combining these two functions, for now, remains beyond the scope of this paper.

Is there a variadic version of hash_append?

Yes, this is easily written as:

template <class HashAlgorithm, class T0, class T1, class ...T>
inline
void
hash_append (HashAlgorithm& h, T0 const& t0, T1 const& t1, T const& ...t) noexcept
{
    hash_append (h, t0);
    hash_append (h, t1, t...);
}

This allows hash_append for X (for example) to be rewritten as:

template <class HashAlgorithm>
friend void hash_append(HashAlgorithm& h, X const& x) noexcept
{
    using std::hash_append;
    hash_append(h, x.date_, x.data_);
}

How easily can algorithms other than FNV-1a be used?

Algorithms such as CityHash are not efficiently adapted to this infrastructure, because as currently coded, CityHash actually hashes the end of the buffer first. However SpookyHash, which is reported to have quality comparable to CityHash is trivial to incorporate:

#include "SpookyV2.h"

class spooky
{
    SpookyHash state_;
public:
    using result_type = std::size_t;

    spooky(std::size_t seed1 = 1, std::size_t seed2 = 2) noexcept
    {
        state_.Init(seed1, seed2);
    }

    void
    operator()(void const* key, std::size_t len) noexcept
    {
        state_.Update(key, len);
    }

    explicit
    operator result_type() noexcept
    {
        std::uint64_t h1, h2;
        state_.Final(&h1, &h2);
        return h1;
    }

};

MurmurHash2, MurmurHash3, and the cryptographically secure algorithms SipHash and the SHA-2 family are also efficiently adaptable to this framework. Indeed, CityHash is the only hashing algorithm we have come across to date which is not efficiently adapted to this framework.

What is involved in switching hashing algorithms?

Given the class X shown above, with its complex state distributed among at least two different contiguous chunks of memory, and potentially many more if the container switched from vector to deque or list, one can create an unordered container with the default hash function like so:

std::unordered_set<X, std::uhash<>> my_set;

If one instead wanted to specify FNV-1a, the code is easily modified to:

std::unordered_set<X, std::uhash<fnv1a>> my_set;

This would change the hash code algorithm for every vector, every deque, every string, every char, every int, etc. for which X considered part of its hash-worthy state. That is, hashing algorithms are controlled at the top of the data structure chain, at the point where the client (e.g. unordered_map) asks for the hash. It is not controlled at all down at the bottom of the data structure chain. I.e. int has no clue how to hash itself. It only knows what state needs to be exposed to a hashing algorithm.

And there is no combining step. The hash algorithm works identically as if you had copied all of the various discontiguous chunks of state into one big contiguous chunk of memory, and fed that one big chunk to the hash algorithm.

If one wants to use spooky instead, simply change in one place:

std::unordered_set<X, std::uhash<spooky>> my_set;

If a new hashing algorithm is invented tomorrow, and you want to use it, all that needs to be done is to write an adaptor for it:

class new_hash_function
{
public:
    using result_type = std::size_t;

    new_hash_function() noexcept;

    void
    operator()(void const* key, std::size_t len) noexcept;

    explicit
    operator result_type() noexcept;
};

And then use it:

std::unordered_set<X, std::uhash<new_hash_function>> my_set;

You do not need to revisit the hash_append for X, nor for any of X's sub-types. The the N hashing algorithms x M sub-types problem has been solved!

How does one hash_append Pimpl designs?

So far, every hash_append function shown must be templated on HashAlgorithm so as to handle any hashing algorithm requested by some unknown, far away client. But with the Pimpl design, one can not send a templated HashAlgorithm past the implementation firewall.

Or can you ... ?

With the help of std::function one can type erase the templated HashAlgorithm, adapting it to a type with a concrete type, and pass that concrete HashAlgorithm through the implementation firewall. Imagine a class as shown here. Here is how it can support arbitrary hash algorithms with the proposed infrastructure:

class Handle
{
    struct CheshireCat;               // Not defined here
    CheshireCat* smile;               // Handle

public:
    // Other operations...

    // Hash support
    using type_erased_hasher = acme::type_erased_hasher<std::size_t>;

    friend
    void
    hash_append(type_erased_hasher&, CheshireCat const&);

    template <class HashAlgorithm>
    friend
    void
    hash_append(HashAlgorithm& h, Handle const& x)
    {
        using std::hash_append;
        if (x.smile == nullptr)
            hash_append(h, nullptr);
        else
        {
            type_erased_hasher temp(std::move(h));
            hash_append(temp, *x.smile);
            h = std::move(*temp.target<HashAlgorithm>());
        }
    }
};

So you still have to implement a templated hash_append for Handle, but the implementation of that function forwards to a non-template function which can be implemented in the source, within the definition of CheshireCat:

friend
void
hash_append(Handle::type_erased_hasher& h, CheshireCat const& c)
{
    using std::hash_append;
    hash_append(h, c.data1_, c.data2_, etc. ...);
}

Besides the type of the HashAlgorithm, hash_append for CheshireCat looks just like any other hash_append.

The magic is in acme::type_erased_hasher<std::size_t>, not proposed (thus the namespace acme). Appendix A outlines exactly how to code acme::type_erased_hasher<std::size_t>. In a nutshell, this is a HashAlgorithm adaptor, which takes any HashAlgorithm, stores it in a std::function<void(void const*, std::size_t)>, and makes the std::function behave like a HashAlgorithm.

Think about what has just happened here. You've compiled CheshireCat.cpp today. And tomorrow, when somebody invents a brand new hash algorithm, your CheshireCat.cpp uses it, with no re-compile necessary, for the cost of a virtual function call (or many such calls) to the HashAlgorithm. And yet no other client of this new HashAlgorithm (outside of those called by CheshireCat), is forced to access the new hashing algorithm via a virtual function call. That borders on magic!

It is this very concern (hashing of Pimpl's) that decided the name of the member function of HashAlgorithms which appends state to the hash algorithm:

void operator()(void const* key, std::size_t len) noexcept;

Had this member function been given any other name, such as:

void append(void const* key, std::size_t len) noexcept;

then programmers would not be able to use std::function to create a type-erased wrapper around a templated HashAlgorithm.

How does one apply random seeding?

Many hash algorithms can be randomly seeded during the initialization stage in such a way that the hash code produced for a type is constant between invocations by a single client (just like a non-seeded algorithm), but varies between clients. The variance might be per-process, but could also be as frequent as per-hash-functor construction, excluding copy or move construction. In the latter case one might have two distinct unordered_sets (for example) of the same type, and even containing the same data, and yet have the two containers result in different hash codes for the same values. Doing so can help harden an application from attacks when the application must hash keys supplied by an untrusted source.

This is remarkably easily done with this proposal. One codes one new hash functor, which can be used with any HashAlgorithm which accepts a seed, and for any type which already has hash_append implemented (even those CheshireCats which have already been compiled, and can not be recompiled).

Here is one possible implementation for a hash functor that is randomly seeded by a seed selected on a per-process basis:

std::tuple<std::uint64_t, std::uint64_t>
get_process_seed();

template <class HashAlgorithm = acme::siphash>
class process_seeded_hash
{
public:
    using result_type = typename HashAlgorithm::result_type;

    template <class T>
    result_type
    operator()(T const& t) const noexcept
    {
        std::uint64_t seed0;
        std::uint64_t seed1;
        std::tie(seed0, seed1) = get_process_seed();
        HashAlgorithm h(seed0, seed1);
        using std::hash_append;
        hash_append(h, t);
        return static_cast<result_type>(h);
    }
};

And then in a source:

namespace
{

std::tuple<std::uint64_t, std::uint64_t>
init_seeds()
{
    std::mt19937_64 eng{std::random_device{}()};
    return std::tuple<std::uint64_t, std::uint64_t>{eng(), eng()};
}

}   // unnamed

std::tuple<std::uint64_t, std::uint64_t>
get_process_seed()
{
    static std::tuple<std::uint64_t, std::uint64_t> seeds = init_seeds();
    return seeds;
}

And then use it:

std::unordered_set<MyType, process_seeded_hash<>> my_set;

In this example, the hashing algorithm is initialized with a random seed when process_seeded_hash is invoked. The same seed is used to initialize the algorithm on each hash functor invocation, and for all copies of the functor, for the life of the process.

Alternatively, one could randomly seed the hash functor on each default construction:

template <class HashAlgorithm = acme::siphash>
class randomly_seeded_hash
{
private:
    static std::mutex mut_s;
    static std::mt19937_64 rand_s;

    std::size_t seed0_;
    std::size_t seed1_;
public:
    using result_type = typename HashAlgorithm::result_type;

    randomly_seeded_hash()
    {
        std::lock_guard<std::mutex> _(mut_s);
        seed0_ = rand_s();
        seed1_ = rand_s();
    }

    template <class T>
    result_type
    operator()(T const& t) const noexcept
    {
        HashAlgorithm h(seed0_, seed1_);
        using std::hash_append;
        hash_append(h, t);
        return static_cast<result_type>(h);
    }
};

template <class HashAlgorithm>
std::mutex
randomly_seeded_hash<HashAlgorithm>::mut_s;

template <class HashAlgorithm>
std::mt19937_64
randomly_seeded_hash<HashAlgorithm>::rand_s{std::random_device{}()};

Perhaps using it like:

std::unordered_set<MyType, randomly_seeded_hash<acme::spooky>> my_set;

One uses the same technique to apply salting, or padding to a type to be hashed. E.g. one would prepend and/or append the salt or padding to the message of T by using additional calls to hash_append in the operator()(T const& t) of the hash functor.

Emphasis

There is no need for the standard to specify a random seeding policy or interface, because using this infrastructure the client can very easily specify his own random seeding policy without having to revisit every type that needs to be hashed, and without having to heavily invest in any given hashing algorithm. It can be done with only a few dozen lines of code. And he can easily do so in a per-use manner: I.e. in use-case A we need to randomly seed the hashing of types X and Y. And in use-case B we need to not seed the hashing of types Y and Z. Type Y is correctly handled in both use-cases, and without having to revisit Y or Y's sub-types. Y remains ignorant of the detail as to whether it is being hashed with a random seed or not (or even with what hashing algorithm).

Flexibility is built into this system in exactly the right places so as to achieve maximum options for the programmer with an absolute minimum of programmer intervention. The std::lib merely has to set up the right infrastructure, and provide a simple default.

What about unordered containers?

The unordered containers present a problem. The problem is not specific to this infrastructure. Neither N3333 nor N3876 solve this problem either. But we highlight the problem here so as to definitively state that we do not solve the problem here either.

Given two unordered_set<int>:

std::unordered_set<int> s1{1, 2, 3};
std::unordered_set<int> s2{3, 2, 1};

One can assert that s1 == s2, and yet if one iterates over s1 and s2, one will not (in general) come upon the same elements in the same order. So in what order do you hash the elements of an unordered sequence? Since s1 == s2, then hash(s1) == hash(s2) must also be true.

There are several answers to this dilemma that will work. However there is no answer that is definitely better than all other answers. Therefore we recommend that we not standardize a hash_append overload for any of the unordered containers. If a client really wants to hash an unordered container, then they can choose a technique that works for them, and do so.

For example, one could hash each element using a copy of the HashAlgorithm, and then append the sum of all hash codes to the state of the original HashAlgorithm:

template <class HashAlgorithm, class Key, class Hash, class Pred, class Alloc>
void
hash_append(HashAlgorithm& h, std::unordered_set<Key, Hash, Pred, Alloc> const& s)
{
    using result_type = typename HashAlgorithm::result_type;
    result_type k{};
    for (auto const& x : s)
    {
        HashAlgorithm htemp{h};
        hash_append(htemp, x);
        k += static_cast<result_type>(htemp);
    }
    hash_append(h, k, s.size());
}

Or one could sort all the elements and hash the elements in sorted order:

template <class HashAlgorithm, class Key, class Hash, class Pred, class Alloc>
void
hash_append(HashAlgorithm& h, std::unordered_set<Key, Hash, Pred, Alloc> const& s)
{
    hash_append(h, std::set<Key>(s.begin(), s.end()));
}

And there are various other schemes. They are all implementable. But they each have their advantages and disadvantages. Therefore this proposal proposes none of them. Should the future expose the ideal hash_append specification for unordered containers, it can always be added at that time.

How much does this cost, in terms of speed and hash quality, compared to the current N x M method of custom hash functor implementation?

The answer to this question is nothing. But to demonstrate this answer, X has been given a randomized default constructor:

std::mt19937_64 eng;

X::X()
{
    std::uniform_int_distribution<short> yeardata(1914, 2014);
    std::uniform_int_distribution<unsigned char> monthdata(1, 12);
    std::uniform_int_distribution<unsigned char> daydata(1, 28);
    std::uniform_int_distribution<std::size_t> veclen(0, 100);
    std::uniform_int_distribution<int> int1data(1, 10);
    std::uniform_int_distribution<int> int2data(-3, 3);
    std::get<0>(date_) = yeardata(eng);
    std::get<1>(date_) = monthdata(eng);
    std::get<2>(date_) = daydata(eng);
    data_.resize(veclen(eng));
    for (auto& p : data_)
    {
        p.first = int1data(eng);
        p.second = int2data(eng);
    }
}

Given this, one can easily create a great number of random X's and specify any hash algorithm. Herein I'm testing 7 implementations of hashing 1,000,000 X's:

• Using std::hash augmented with N3876 as shown in Solution 1.

• Using llvm::hash_value as shown here which is intended to be representative of N3333.

• Using uhash<fnv1a> where fnv1a is derived from here.

• Using uhash<jenkins1> where jenkins1 is derived from here.

• Using uhash<MurmurHash2A> where MurmurHash2A is derived from here.

• Using uhash<spooky> where spooky is derived from here.

• Using uhash<siphash> where siphash is derived from here.

The hash function quality tester suite used herein is described below.

1. This test looks at each 64 bit hash code as a collection of 16 hex-digits. The expectation is that each hex-digit should be roughly equally represented in each hexadecimal place of the hash code. The test returns maximum deviation of the average, from the expected average. An ideal score is 0.

2. This test simply counts the number of duplicate hashes. A score of 0 indicates each hash code is unique. A score of 1 indicates that all hash codes are the same.

3. This test is TestDistribution gratefully borrowed from the smhasher test suite. An ideal score is 0.

4. This test hashes the hash codes into a list of buckets sized to the number of hash codes (load factor == 1). It then scores each bucket with the number of comparisons required to look up each element in the bucket, and then averages the number of comparisons per lookup. Given a randomized hash, the result should be lf/2+1, where lf is load factor. This test returns the percent difference above/below the ideal randomized result.

5. This test hashes the hash codes into a list of buckets sized to the number of hash codes (load factor == 1). It then returns the max collision count among all of the buckets. This represents the maximum cost for a lookup of an element not found. Assuming the not-found-key hashes to a random bucket, the average cost of looking up a not-found-key is simply the load factor (i.e. independent of the quality of the hash function distribution).

A million hash codes are generated from a million randomized but unique X's, randomized by a default constructed std::mt19937_64, and fed to these tests. For each test, the smaller the result the better.

Test Results -- smaller is better

	test 1	test 2	test 3	test 4	test 5	total time (sec)
std::hash<X>	0.273744	0.0000460148	0.966285	-0.000257333	8	0.472963s
llvm::hash_value	0.012	0	0.000913715	0.000254667	8	0.545283s
fnv1a	0.012576	0	0.00111228	0.000248	9	0.84607s
jenkins1	0.0121775	0	0.00121271	-0.000572667	9	1.1119s
MurmurHash2A	15	0.000110984	6.36293	0.000393333	9	0.467501s
spooky	0.010816	0	0.000968923	-0.000359333	9	0.628721s
siphash	0.011072	0	0.00113216	-0.000162667	8	0.584353s

The intent in showing the above table is two-fold: To show that running times are competitive, and that with the exception of MurmurHash2A, and possibly std::hash<X>, the quality results are competitive. If one insists on picking "the best algorithm" from this table, we caution you with one additional test.

The table below represents the same test except that X's data members have been changed as shown:

std::tuple<short int, unsigned char, unsigned char> date_;
std::vector<std::pair<int, int short>>              data_;

Other than this change in types, no other change has been made. Not even the random values assigned to each type. Here are the results:

Test Results (alternative) -- smaller is better

	test 1	test 2	test 3	test 4	test 5	total time (sec)
std::hash<X>	0.273744	0.0000460148	0.966285	-0.000257333	8	0.476888s
llvm::hash_value	0.0111664	0	0.00105212	0.000167333	8	1.10327s
fnv1a	0.011456	0	0.00132384	-0.00015	9	0.708467s
jenkins1	0.010512	0	0.000864258	-0.000433333	10	0.9079s
MurmurHash2A	15	0.000115991	6.36293	-0.000863333	8	1.09589s
spooky	0.013328	0	0.00127677	-0.000210667	9	1.33591s
siphash	0.01224	0	0.00111516	0.000342667	8	1.63656s

While none of the quality metrics changes that much with this minor change, the timing tests did vary considerably. For example llvm::hash_value was previously one of the faster algorithms (fastest among those with good quality results), and is now 50% slower than the fastest among those with quality results. The take-away point is that there is no "best algorithm". But there is a lot of value in being able to easily change algorithms for testing, performance and security purposes.

Summary

This paper presents an infrastructure that decouples types from hashing algorithms. This decoupling has several benefits:

• Clients can very easily switch hashing algorithms used by very complex data structures, thus enabling comparisons as shown in the previous section.
• Hash algorithm designers can concentrate on designing better hash algorithms, with little worry about how these new algorithms can be incorporated into existing code.
• Type designers can create their hash support just once, without worrying about what hashing algorithm should be used.
• Clients can easily adopt most existing algorithms to this proposed infrastructure.
• The resulting hash codes are a true reflection of the original design of the hashing algorithms, even though applied to complex data structures spanning discontiguous memory.

Summary of proposed infrastructure

template <class T> struct is_contiguously_hashable;                                     // A type property trait
template <class HashAlgorithm> void hash_append(HashAlgorithm& h, T const& t) noexcept; // overloaded for each type T
template <class HashAlgorithm = unspecified-default-hasher> struct uhash;               // A hashing functor

There is an example implementation and lots of example code using the example implementation here. See hash_append.h for the example implementation.

Appendix A: type_erased_hasher

Though type_erased_hasher is not proposed, it easily could be if the committee so desires. Here is how it is implemented, whether by the programmer, or by a std::lib implementor:

template <class ResultType>
class type_erased_hasher
{
public:
    using result_type = ResultType;
    
private:    
    using function = std::function<void(void const*, std::size_t)>;

    function hasher_;
    result_type (*convert_)(function&);

public:
    template <class HashAlgorithm,
                 class = std::enable_if_t
                 <
                      std::is_constructible<function, HashAlgorithm>{} &&
                      std::is_same<typename std::decay_t<HashAlgorithm>::result_type,
                                   result_type>{}
                 >
             >
    explicit
    type_erased_hasher(HashAlgorithm&& h)
        : hasher_(std::forward<HashAlgorithm>(h))
        , convert_(convert<std::decay_t<HashAlgorithm>>)
    {
    }

    void
    operator()(void const* key, std::size_t len)
    {
        hasher_(key, len);
    }

    explicit
    operator result_type() noexcept
    {
        return convert_(hasher_);
    }

    template <class T>
    T*
    target() noexcept
    {
        return hasher_.target<T>();
    }

private:
    template <class HashAlgorithm>
    static
    result_type
    convert(function& f) noexcept
    {
        return static_cast<result_type>(*f.target<HashAlgorithm>());;
    }
};

type_erased_hasher must be templated on result_type (or have a concrete result_type), otherwise it can not have an explicit conversion operator to that type.

The type_erased_hasher stores a std::function<void(void const*, std::size_t)>, and a pointer to a function taking such a function and returning a result_type. The latter is necessary to capture the type of the HashAlgorithm in the type_erased_hasher constructor, so that the same HashAlgorithm type can later be used in the conversion to result_type.

The constructor is naturally templated on HashAlgorithm, which can be perfectly forwarded to the underlying std::function. The constructor also initialized the function pointer convert_ using the decayed type of HashAlgorithm. The pointed-to function will extract the HashAlgorithm from the std::function and explicitly convert it to the result_type.

Note that the conversion to result_type isn't explicitly used in the Pimpl example of this paper. However the hash_append of the private implementation may need to copy the type_erased_hasher, and possibly convert a copy to a result_type as part of its hash computation. Such code has been prototyped in motivating examples, such as the hash_append for an unordered sequence container.

The Pimpl example does need access to the stored HashAlgorithm after the call to hash_append to recover its state. This is accomplished with the target function which simply forwards to std::function's target function.

Appendix B: B is for Bike Shed

• In Elements of Programming, Stepanov uses the term uniquely represented for the property this paper refers to as contiguously hashable. Therefore another good name name for is_contiguously_hashable is is_uniquely_represented.

Appendix C: debugHasher

Another interesting "hash algorithm" is debugHasher. This is a small utility that can be used to help type authors debug their hash_append function. This utility is not proposed. It is simply presented herein to illustrate the utility of this overall hashing infrastructure design.

#include <iostream>
#include <iomanip>
#include <vector>

class debugHasher
{
    std::vector<unsigned char> buf_;
public:
    using result_type = std::size_t;

    void
    operator()(void const* key, std::size_t len) noexcept
    {
        unsigned char const* p = static_cast<unsigned char const*>(key);
        unsigned char const* const e = p + len;
        for (; p < e; ++p)
            buf_.push_back(*p);
    }

    explicit
    operator std::size_t() noexcept
    {
        std::cout << std::hex;
        std::cout << std::setfill('0');
        unsigned int n = 0;
        for (auto c : buf_)
        {
            std::cout << std::setw(2) << (unsigned)c << ' ';
            if (++n == 16)
            {
                std::cout << '\n';
                n = 0;
            }
        }
        std::cout << '\n';
        std::cout << std::dec;
        std::cout << std::setfill(' ');
        return buf_.size();
    }
};

debugHasher is a fake "hashing algorithm" that does nothing but collect the bytes sent to a hash by the entire collection of the calls to hash_append made by a key and all of its sub-types. The collection of bytes is output to cout when the hasher is converted to its result_type.

As can be readily seen, it is not difficult to create such a debugging tool. It is then used, just as easily:

std::vector<std::vector<std::pair<int, std::string>>> v {{{1, "abc"}},
                                                         {{2, "bca"}, {3, "cba"}},
                                                         {}};
std::cout << uhash<debugHasher>{}(v) << '\n';

Assuming a 32 bit int, 64 bit size_t, and little endian, this will reliably output:

01 00 00 00 61 62 63 00 01 00 00 00 00 00 00 00 
02 00 00 00 62 63 61 00 03 00 00 00 63 61 62 00 
02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
03 00 00 00 00 00 00 00 
56

The last line is simply the number of bytes that have been sent to the HashAlgorithm. The first 4 lines are those bytes, formatted as two hex digits per byte, with bytes separated by a space, and 16 bytes per line for readability. If one carefully inspects this byte stream and compares it to the data structure which has been "hashed", and to the proposed hash_append above for vector, string and pair, one can verify that the byte stream is consistent with the specification.

Improving debugHasher to collect useful statistics such as the number of times called, and the average number of bytes hashed per call, is left as a fun exercise for the reader.

Appendix D: Proposed Wording

Add a new section to [hash.requirements]:

HashAlgorithm requirements [hash.algo.rqmts]

A type H meets the HashAlgorithm requirements if all of the following are met:

• H::result_type is valid and denotes a MoveConstrutible type (14.8.2 [temp.deduct]).

• H is either default constructible, or constructible by some documented seed. This construction shall initialize H to a deterministic state such that if two instances are constructed with the same arguments, then they have equivalent state.

• H is CopyConstructible. Updates to the state of one copy shall have no impact on any other copy.

• H is CopyAssignable. Updates to the state of one copy shall have no impact on any other copy.

• void operator()(void const* key, std::size_t len);
  

  Requires: If len > 0, key points to len contiguous bytes to be consumed by the HashAlgorithm. The conversion to result_type has not been called on this object since construction, or since *this was assigned to.

  Effects: Updates the state of the HashAlgorithm using the len bytes referred to by {key, len}.

  If len == 0 then key is not dereferenced, and there are no effects.

  Consider two keys {k1, len1} and {k2, len2}, with len1 > 0 and len2 > 0. If len1 != len2, the two keys are considered not equivalent. If len1 == len2 and if memcmp(k1, k2, len1) == 0, the two keys are equivalent, else they are not equivalent.

  If two instances of HashAlgorithm (e.g. h1 and h2) have the same state prior to an update operation, and given two equivalent keys {k1, len} and {k2, len}, then after h1(k1, len) and h2(k2, len), then h1 and h2 shall have the same updated state. If {k1, len1} and {k2, len2} are not equivalent, then after h1(k1, len1) and h2(k2, len2), h1 and h2 should have different updated state.

  Given a key {k, len} with len > 0, one can create multiple keys each with length l_i, where the first key k₀ == k, and subsequent keys k_i == k_i-1 + l_i-1. Combined with a constraint that ∑ l_i == len, the single key {k, len} shall be equivalent to the application of all of the keys {k_i, l_i} applied in order.

  The HashAlgorithm shall not access this memory range after the update operation returns.

• explicit operator result_type();
  

  Requires: This operation has not been called on this object since construction or since *this was assigned to.

  Effects: Converts the state of the HashAlgorithm to a result_type. Two instances of the same type of HashAlgorithm, with the same state, shall return the same value. It is unspecified if this operation changes the state of the HashAlgorithm.

  Returns: The converted state.

Add a new section to [hash.requirements]:

HashAlgorithm-based Hash requirements [hash.algo.hash.rqmts]

A type H meets the HashAlgorithm-based Hash requirements if all of following are met:

• H meets the Hash requirements ([hash.requirements]).

• H is a class template instantiation of the form

  template <class HashAlgorithm, class Args> struct H;
  

  where Args is zero or more type arguments, and the first template parameter meets the HashAlgorithm requirements ([hash.algo.rqmts]). The HashAlgorithm parameter may be defaulted.

• H has the nested type:

  using result_type = typename HashAlgorithm::result_type;

• H is either default constructible, or constructible by some documented seed. This construction shall initialize H. H may be stateless or have state. If not stateless, different default constructions, and different seeded constructions (even with the same seeds), are not required to initialize H to the same state.

• H is CopyConstructible.

• H is CopyAssignable.

• template <class T>
      result_type
      operator()(T const& t) const;
  

  Requires: HashAlgorithm shall be constructible as specified by a concrete H type.

  Effects: Constructs a HashAlgorithm h with automatic storage. Each concrete H type shall specify how h is constructed. However h shall be constructed to the same state for every invocation of (*this)(t). Updates the state of the HashAlgorithm in an unspecified manner, except that there shall be exactly one call to:

  using std::hash_append;
  hash_append(h, t);
  

  at some time during the update operation. Furthermore, subsequent calls shall update the the local h with exactly the same state every time, except as changed by different values for t, unless there is an intervening assignment to *this between calls to this operator.

  Returns: static_cast<result_type>(h).

  [Note: For the same value of t, the same value is returned on subsequent calls unless there is an intervening assignment to *this between calls to this operator. — end note]

Add a new row to Table 49 — Type property predicates in [meta.unary.prop]:

Template	Condition	Preconditions
template <class T> struct is_contiguously_hashable;	A type T is contiguously hashable if for any two values x and y of a type, if x == y, then it must also be true that memcmp(addressof(x), addressof(y), sizeof(T)) == 0. It T is an array type, then T is contiguously hashable if remove_extent_t<T> is contiguously hashable.	T shall be a complete object type. A program may specialize this trait if T is a user-defined type and the specialization conforms to the Condition.

Add a new section to [unord.hash]:

hash_append [unord.hash_append]

template <class HashAlgorithm, class T>
void
hash_append(HashAlgorithm& h, T const& t);

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<T>::value is true.

Effects: h(addressof(t), sizeof(t)).

For any scalar types T, except for member pointers, for which is_contiguously_hashable<T>{} evaluates to false, there shall exist an overload of hash_append similar to that shown above for contiguously hashable types. For each of these overloads for scalar types T, the implementation shall ensure that for two values of T (e.g. t1 and t2), if t1 == t2, then hash_append(h, t1) shall update the state of h to the same state as does hash_append(h, t2). And if t1 != t2, then hash_append(h, t1) should update the state of h to a different state as does hash_append(h, t2). It is unspecified exactly what signature such overloads will have, so it is not portable to form function pointers to these overloads.

[Note:

For example, here is a plausible implementation of hash_append for IEEE floating point:

template <class HashAlgorithm, class T>
enable_if_t
<
    is_floating_point<T>{}
>
hash_append(HashAlgorithm& h, T t)
{
    if (t == 0)
        t = 0;
    h(&t, sizeof(t));
}

This implementation accepts the T by value instead of by const&, and gives -0. and 0. the same bit representation prior to forwarding the value to the HashAlgorithm (since these two values compare equal).

And here is a plausible definition for nullptr_t:

template <class HashAlgorithm>
void
hash_append(HashAlgorithm& h, nullptr_t)
{
    void const* p = nullptr;
    h(&p, sizeof(p));
}

— end note]

template <class HashAlgorithm, class T, size_t N>
void
hash_append(HashAlgorithm& h, T (&a)[N]);

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<T>::value is false.

Effects:

for (auto const& t : a)
    hash_append(h, t);

[Note: It is intentional that the hash_append for built-in arrays behave in exactly this way, sending a "message" to the HashAlgorithm of each element, in order, and nothing else. This "message" to the HashAlgorithm is considered part of a built-in array's API. It is also intentional that for arrays of T that are contiguously hashable, the exact same message is sent to the HashAlgorithm, except in one call instead of many. — end note]

template <class HashAlgorithm, class T0, class T1, class ...T>
inline
void
hash_append (HashAlgorithm& h, T0 const& t0, T1 const& t1, T const& ...t);

Effects:

hash_append (h, t0);
hash_append (h, t1, t...);

Add a new section to [unord.hash]:

uhash [unord.hash.uhash]

template <class HashAlgorithm = unspecified>
struct uhash
{
    using result_type = typename HashAlgorithm::result_type;

    template <class T>
    result_type
    operator()(T const& t) const;
};

Instantiations of uhash meet the HashAlgorithm-based Hash requirements ([hash.algo.hash.rqmts]).

The template parameter HashAlgorithm meets the HashAlgorithm requirements ([hash.algo.rqmts]). The unspecified default for this parameter refers to an implementation provided default HashAlgorithm.

template <class HashAlgorithm>
template <class T>
typename HashAlgorithm::result_type
uhash<HashAlgorithm>::operator()(T const& t) const;

Effects: Default constructs a HashAlgorithm with automatic storage duration (for example named h), and calls hash_append(h, t) (unqualified).

Returns: static_cast<result_type>(h).

Add to [type.info]:

class type_info {
...
};


template <HashAlgorithm>
    void hash_append(HashAlgorithm& h, type_info const& t);

...

template <HashAlgorithm>
    void hash_append(HashAlgorithm& h, type_info const& t);

Effects: Updates the state of h with data that is unique to t with respect to all other type_infos that compare not equal to t.

Add to the synopsis in [syserr]:

template <class HashAlgorithm>
    void hash_append(HashAlgorithm& h, error_code const& ec)

Add to [syserr.hash]:

template <class HashAlgorithm>
    void hash_append(HashAlgorithm& h, error_code const& ec)

Effects: hash_append(h, ec.value(), &ec.category());

Add to the synopsis in [utility]:

template <class T, class U>
struct is_contiguously_hashable<pair<T, U>>
    : public integral_constant<bool, is_contiguously_hashable<T>{} && 
                                     is_contiguously_hashable<U>{} &&
                                     sizeof(T) + sizeof(U) == sizeof(pair<T, U>)>
    {};

template <class HashAlgorithm, class T, class U>
    void
    hash_append(HashAlgorithm& h, pair<T, U> const& p)

Add a new section to [pairs]: [pairs.hash]:

Hashing pair [pairs.hash]

template <class HashAlgorithm, class T, class U>
    void
    hash_append(HashAlgorithm& h, pair<T, U> const& p)

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<pair<T, U>>::value is false.

Effects: hash_append(h, p.first, p.second);

Add to the synopsis in [tuple.general]:

template <class ...T>
    struct is_contiguously_hashable<tuple<T...>>;

template <class HashAlgorithm, class ...T>
    void
    hash_append(HashAlgorithm& h, tuple<T...> const& t)

Add to [tuple.special]:

template <class ...T>
    struct is_contiguously_hashable<tuple<T...>>;

Publicly derives from true_type if for each Type in T..., is_contiguously_hashable<Type>{} is true, and if the sum of all sizeof(Type) is equal to sizeof(tuple<T...>), else publicly derives from false_type.

template <class HashAlgorithm, class ...T>
    void
    hash_append(HashAlgorithm& h, tuple<T...> const& t)

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<tuple<T...>>::value is false.

Effects: Calls hash_append(h, get<I>(t)) for each I in the range [0, sizeof...(T)). If sizeof...(T) is 0, the function has no effects.

Add to the synopsis in [template.bitset]:

template <class HashAlgorithm, size_t N>
    void hash_append(HashAlgorithm& h, bitset<N> const& bs)

Add to [bitset.hash]:

template <class HashAlgorithm, size_t N>
    void hash_append(HashAlgorithm& h, bitset<N> const& bs)

Effects: Calls hash_append(h, w) successively for some w integral type for which each bit in w corresponds to a bit value contained in bs. The last w may contain padding bits which shall be set to 0. After all bits have been appended to h, calls hash_append(h, bs.size()).

Add to the synopsis in [memory.syn]:

template <class HashAlgorithm, class T, class D>
    void hash_append(HashAlgorithm& h, unique_ptr<T, D> const& p);
template <class HashAlgorithm, class T>
    void hash_append(HashAlgorithm& h, shared_ptr<T> const& p);

Add to [util.smartptr.hash]:

template <class HashAlgorithm, class T, class D>
    void hash_append(HashAlgorithm& h, unique_ptr<T, D> const& p);
template <class HashAlgorithm, class T>
    void hash_append(HashAlgorithm& h, shared_ptr<T> const& p);

Effects: hash_append(h, p.get());

Add to the synopsis in [time.syn]:

template <class Rep, class Period>
struct is_contiguously_hashable<duration<Rep, Period>>
    : public integral_constant<bool, is_contiguously_hashable<Rep>{}>
    {};

template <class Clock, class Duration>
struct is_contiguously_hashable<time_point<Clock, Duration>>
    : public integral_constant<bool, is_contiguously_hashable<Duration>{}>
    {};

template <class HashAlgorithm, class Rep, class Period>
    void
    hash_append(HashAlgorithm& h, duration<Rep, Period> const& d);

template <class HashAlgorithm, class Clock, class Duration>
    void
    hash_append(HashAlgorithm& h, time_point<Clock, Duration> const& tp);

Add a new section to [time.duration], [time.duration.hash]:

duration hash [time.duration.hash]

template <class HashAlgorithm, class Rep, class Period>
    void
    hash_append(HashAlgorithm& h, duration<Rep, Period> const& d);

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<duration<Rep, Period>>::value is false.

Effects: hash_append(h, d.count()).

Add a new section to [time.point], [time.point.hash]:

time_point hash [time.point.hash]

template <class HashAlgorithm, class Clock, class Duration>
    void
    hash_append(HashAlgorithm& h, time_point<Clock, Duration> const& tp);

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<time_point<Clock, Duration>>::value is false.

Effects: hash_append(h, tp.time_since_epoch()).

Add to the synopsis in [type.index.synopsis]:

template <class HashAlgorithm>
    void hash_append(HashAlgorithm& h, type_index const& ti);

Add to [type.index.hash]:

template <class HashAlgorithm>
    void hash_append(HashAlgorithm& h, type_index const& ti);

Effects: hash_append(h, *ti.target);

Add to the synopsis in [string.classes]:

template <class HashAlgorithm, class CharT, class Traits, class Alloc>
    void hash_append(HashAlgorithm& h, basic_string<CharT, Traits, Alloc> const& s);

Add to [basic.string.hash]:

template <class HashAlgorithm, class CharT, class Traits, class Alloc>
    void hash_append(HashAlgorithm& h, basic_string<CharT, Traits, Alloc> const& s);

Effects:

for (auto c : s)
    hash_append(h, c);
hash_append(h, s.size());

[Note: If is_contiguously_hashable<CharT>{} is true, then the following may replace the loop (as an optimization):

h(s.data(), s.size()*sizeof(CharT));

— end note]

Add to the synopsis of <array> in [sequences.general]:

template <class T, size_t N>
struct is_contiguously_hashable<array<T, N>>
    : public integral_constant<bool, is_contiguously_hashable<T>{} && 
                                     sizeof(T)*N == sizeof(array<T, N>)>
    {};

template <class HashAlgorithm, class T, size_t N>
    void
    hash_append(HashAlgorithm& h, array<T, N> const& a);

Add to the synopsis of <deque> in [sequences.general]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, deque<T, Allocator> const& x);

Add to the synopsis of <forward_list> in [sequences.general]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, forward_list<T, Allocator> const& x);

Add to the synopsis of <list> in [sequences.general]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, list<T, Allocator> const& x);

Add to the synopsis of <vector> in [sequences.general]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, vector<T, Allocator> const& x);

template <class HashAlgorithm, class Allocator>
    void
    hash_append(HashAlgorithm& h, vector<bool, Allocator> const& x);

Add to [array.special]:

template <class HashAlgorithm, class T, size_t N>
    void
    hash_append(HashAlgorithm& h, array<T, N> const& a);

Remarks: This function shall not participate in overload resolution, unless is_contiguously_hashable<array<T, N>>::value is false.

Effects:

for (auto const& t : a)
    hash_append(h, t);

Add to [deque.special]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, deque<T, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

[Note: When is_contiguously_hashable<T>{} is true, an implementation may optimize by calling h(p, s) on suitable contiguous sub-blocks of the deque. — end note]

Add to [forwardlist.spec]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, forward_list<T, Allocator> const& x);

Effects:

typename forward_list<T, Allocator>::size_type s{};
for (auto const& t : x)
{
    hash_append(h, t);
    ++s;
}
hash_append(h, s);

Add to [list.special]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, list<T, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

Add to [vector.special]:

template <class HashAlgorithm, class T, class Allocator>
    void
    hash_append(HashAlgorithm& h, vector<T, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

[Note: When is_contiguously_hashable<T>{} is true, an implementation may optimize by calling h(x.data(), x.size()*sizeof(T)) in place of the loop. — end note]

Add to [vector.bool]:

template <class HashAlgorithm, class Allocator>
    void
    hash_append(HashAlgorithm& h, vector<bool, Allocator> const& x);

Effects: Calls hash_append(h, w) successively for some w integral type for which each bit in w corresponds to a bit value contained in x. The last w may contain padding bits which shall be set to 0. After all bits have been appended to h, calls hash_append(h, x.size()).

Add to the synopsis of <map> in [associative.map.syn]:

template <class HashAlgorithm, class Key, class T, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, map<Key, T, Compare, Allocator> const& x);

template <class HashAlgorithm, class Key, class T, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, multimap<Key, T, Compare, Allocator> const& x);

Add to the synopsis of <set> in [associative.set.syn]:

template <class HashAlgorithm, class Key, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, set<Key, Compare, Allocator> const& x);

template <class HashAlgorithm, class Key, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, multiset<Key, Compare, Allocator> const& x);

Add to [map.special]:

template <class HashAlgorithm, class Key, class T, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, map<Key, T, Compare, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

Add to [multimap.special]:

template <class HashAlgorithm, class Key, class T, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, multimap<Key, T, Compare, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

Add to [set.special]:

template <class HashAlgorithm, class Key, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, set<Key, Compare, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

Add to [multiset.special]:

template <class HashAlgorithm, class Key, class Compare class Allocator>
    void
    hash_append(HashAlgorithm& h, multiset<Key, Compare, Allocator> const& x);

Effects:

for (auto const& t : x)
    hash_append(h, t);
hash_append(h, x.size());

Add to the synopsis in [complex.syn]:

template <class HashAlgorithm, class T>
    void hash_append(HashAlgorithm& h, complex<T> const& x);

Add to [complex.ops]:

template <class HashAlgorithm, class T>
    void hash_append(HashAlgorithm& h, complex<T> const& x);

Effects: Calls hash_append(h, x.real(), x.imag()).

Add to the synopsis in [thread.thread.id]:

template <class HashAlgorithm>
    void hash_append(HashAlgorithm& h, thread::id const& id);

Add to [thread.thread.id]:

template <class HashAlgorithm>
    void hash_append(HashAlgorithm& h, thread::id const& id);

Effects: Updates the state of h with id.

Acknowledgments

Thanks to Daniel James (et al.) for highlighting the problem of hashing zero-length containers with no message.

Thanks to Dix Lorenz (et al.) for pointing out that the result_type of the HashAlgorithm need not be size_t, and indeed, can not be if we want this infrastructure to fully handle cryptographic hash functions (which produce results larger than a size_t).

Thanks to Jeremy Maitin-Shepard for pointing out problems in an earlier scheme to hash std::string and arrays of char identically. Also thanks to Jeremy and Chris Jefferson for their guidance on hashing unordered sequences.

Additional thanks to Walter Brown, Daniel Krügler, and Richard Smith for their invaluable review and guidance.

This research has been generously supported by Ripple Labs. We would especially like to thank our colleagues on the RippleD team.