C++23 hash combiner and helper concepts

hash.h

#pragma once

// ============================================================================
//  C++23 hash combiner + hash related concepts / generic specializations
// ----------------------------------------------------------------------------
// (c) Raziel Anarki <[email protected]> - MIT licensed
// ----------------------------------------------------------------------------
// the algo mangled from:
// https://newbedev.com/c-why-is-boost-hash-combine-the-best-way-to-combine-hash-values
// tldr<link> = its not
// tldr<code> = way less collisions, while still being a relatively
//              simple/fast hash-algo, with ~2x ops (compated to boost)
// ----------------------------------------------------------------------------

#include <algorithm>        // std::ranges::fold_left
#include <bit>              // std::rotl
#include <cstddef>          // std::size_t, std::nullptr_t
#include <functional>       // std::hash
#include <initializer_list> // std::initializer_list
#include <tuple>            // std::apply, std::tuple
#include <type_traits>      // std:false_type, std::true_type, std::void_t
                            // std::is_nothrow_invocable_r_v
#include <utility>          // std::declval, std::pair

namespace nonstd
{

// ============================================================================
// 1. type "traits" and concept-s
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 1.1. alias `size_t` as `nonstd::hash_t` using a default specialization
// ----------------------------------------------------------------------------

using hash_t = decltype( std::hash<std::nullptr_t>{}( nullptr ) );

// ----------------------------------------------------------------------------
// 1.2. hashable type detection / requirement concept
// `T` is hashable if there is a non-throwing `std::hash<T>` specialization
// ----------------------------------------------------------------------------

template<class T>
concept hashable = requires( const std::remove_cvref_t<T>& type )
{
  std::is_nothrow_invocable_r_v<hash_t, decltype( std::hash<std::remove_cvref_t<T>>{}( type ) )>;
};

// ----------------------------------------------------------------------------
// 1.3. helper concept for any type having a `hash_t T::hash() noexcept` member
// so it can automatically specialized via `std::hash` (see 3.1.)
// and thus becoemes `nonstd::hashable`
// ----------------------------------------------------------------------------

template<class T>
concept has_hasher = requires( const std::remove_cvref_t<T>& type )
{
  std::is_nothrow_invocable_r_v<hash_t, decltype( type.hash() )>;
};

// ============================================================================
// 2. the (overtly detailed) impementation details
// ----------------------------------------------------------------------------

namespace detail
{

// ============================================================================
// 2.2. compile-time "magic-number" constants
// ----------------------------------------------------------------------------

// 2.2.1. [W]idth of the hash_t type in bytes
constexpr size_t W = sizeof( hash_t );

// 2.2.2. [T]hird bitwidth for left rotation of the seed
constexpr size_t T = ( ( W << 1 ) + ( W >> 1 ) );

// 2.2.3. [H]alf bitwidth for the bitmixer right shift
constexpr size_t H = ( ( W << 1 ) + ( W << 1 ) );

// 32bit (W=4) ->
//   T = 10 bits
//   H = 16 bits
// 64bit (W=8) ->
//   T = 20 bits
//   H = 32 bits
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 2.2.4. recursion depths for the constant expressions
// note: 128bit width size_t-s may require an extra `+ ( W >> 4)` term on `Rc`
// note: last two terms in `Ac` are just for symmety (yay)
// ----------------------------------------------------------------------------

// 2.2.4.1. recursive depth of the pseudo-Random bit distibution constexpr
constexpr size_t Rc = ( W << 1 ) + ( W >> 2 ) + ( W >> 3 );

// 2.2.4.2. recursive depth of the Alternating bit distibution constexpr
constexpr size_t Ac = ( W << 1 ) + ( 0 >> 2 ) + ( 0 >> 3 );

// 32bit (W=4) ->
//   Rc = 8 + 1 + 0 = 9  (steps)
//   Ac = 8              (steps)
// 64bit (W=8) ->
//   Rc = 16 + 2 + 1 = 19 (steps)
//   Ac = 16              (steps)
// ----------------------------------------------------------------------------

// ============================================================================
// 2.3. variable bit-width constexpr constant "generators"
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 2.3.1. pseudo[R]andom evenly distributed bits for the outer "disperser"
// ----------------------------------------------------------------------------

constexpr hash_t R( size_t c = Rc )
{
  return ( --c ? R( c ) * 10 : 0 ) + 7;
}

// 32bit (W=4) ->
//   R = 2e5b'f271 hexa
//     = 777777777 decimal
//     = 0010'1110'0101'1011'1111'0010'0111'0001 binary (14 zeroes / 18 ones)
// 64bit (W=8) ->
//   R = 6bf0'37ae'325f'1c71 hexdecicaml
//     = 7777777777777777777 decimal
//     = 0110'1011'1111'0000'0011'0111'1010'1110'0011'0010'0101'1111'0001'1100'0111'0001 binary (29 zeroes / 35 ones)
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 2.3.2. [A]lternating bits for the inner "comber"
// ----------------------------------------------------------------------------

constexpr hash_t A( size_t c = Ac )
{
  return ( --c ? A( c ) << 4 : 0 ) + 5;
}

// 32bit (W=4) ->
//   A = 0x55555555
//     = 0101'0101'0101'0101'0101'0101'0101'0101 binary
// 64bit, W=8 ->
//   A = 0x5555'5555'5555'5555
//     = 0101'0101'0101'0101'0101'0101'0101'0101'0101'0101'0101'0101'0101'0101'0101'0101 binary
// ----------------------------------------------------------------------------

// ============================================================================
// 2.4. hash combiner constexpr functions
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 2.4.1. [MXS] : MulXorShift "bit-magic":
// `M` times `X` xor `X` shifted right by `H`alf bits
// ----------------------------------------------------------------------------

constexpr hash_t mxs( const hash_t& M, const hash_t& X ) noexcept
{
  return M * ( X ^ ( X >> H ) );
}

// ----------------------------------------------------------------------------
// 2.4.2. [DSP] : bit-"DiSPerser" & "comber"
// first MXS seed with `A`lternating bits to "comb" bits evently
// and then MXS the result with the `R`andom" bits to disperse bits
// note: argument `I` is just for symmetry (yay)
// ----------------------------------------------------------------------------

constexpr hash_t dsp( const hash_t& Z, const hash_t& I ) noexcept
{
  return mxs( R(), mxs( A(), Z ) );
}

// ----------------------------------------------------------------------------
// 2.4.3. [RLD] : Rotate ~third bits Left then Disperse, the "fold-op":
// Rotl `S`eed hash by ~third bits, then xor with dispersed `C`ombinant hash
// note: `hash_t{}` for the `dsp` function `I`gnored arg (for symmetry) (yay)
// ----------------------------------------------------------------------------

constexpr hash_t rld( const hash_t& S, const hash_t& C ) noexcept
{
  return std::rotl( S, T ) ^ dsp( C, hash_t{} );
}

// ----------------------------------------------------------------------------

}  // namespace detail

// ============================================================================
// 2.5. C++23 template parameter pack combiner using `ranges::fold_left_first`
// ----------------------------------------------------------------------------

template<hashable... Types>
inline hash_t hash_combine( Types& ...items ) noexcept
{
  return std::ranges::fold_left_first(
    std::initializer_list{ std::hash<std::remove_cvref_t<Types>>{}( items )... },
    detail::rld
  );
}

// ----------------------------------------------------------------------------

};  // namespace nonstd

// ============================================================================
// 3. generic `std::hash` specialization templates
// ----------------------------------------------------------------------------

// ============================================================================
// 3.1. `std::hash` specialization for `nonstd::has_hasher` compatible classes
// (ie: classes having a public `hash_t T::hash() noexcept` method)
// ----------------------------------------------------------------------------

template<nonstd::has_hasher T>
requires ( !nonstd::hashable<T> )
struct std::hash<T>
{
  nonstd::hash_t operator()( const std::remove_cvref_t<T>& item ) const noexcept
  {
    return item.hash();
  }
};

// ----------------------------------------------------------------------------

// ============================================================================
// 3.2. `std::hash` specializaton for STL `std::pair` & `std::tuple`
// whose members are all `nonstd::hashable`
//
// this maybe "technically illegal" per spec, as neither are required to be
// "partially program-defined types", and (aside from the `nonstd::hashable`
// requirement) could be composed of library types
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 3.2.1. the `std::pair` specialization demonstrates hashing of
// structs / classes by combining indivdual hashes of members
// ----------------------------------------------------------------------------

template<nonstd::hashable First, nonstd::hashable Second>
struct std::hash<std::pair<First, Second>>
{
  nonstd::hash_t operator()( const std::pair<First, Second> &item ) const noexcept
  {
    return nonstd::hash_combine( item.first, item.second );
  }
};

// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// 3.2.2. the specialization for `std::tuple` simply just `std::apply`-es
// the hash combiner to the tempalte parameter pack
// ----------------------------------------------------------------------------

template<nonstd::hashable... Types>
struct std::hash<std::tuple<Types...>>
{
  nonstd::hash_t operator()( const std::tuple<Types...> &item ) const noexcept
  {
    return std::apply( nonstd::hash_combine, item );
  }
};

// ----------------------------------------------------------------------------