Acts/Utilities/HashCombine.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 #include <cstddef>
0012 #include <cstdint>
0013 #include <functional>
0014 #include <type_traits>
0015
0016 namespace Acts {
0017
0018 /// Apply a bit-mixing function to break up patterns in integer hash values.
0019 ///
0020 /// Many standard hash functions (including std::hash for integers) are the
0021 /// identity, which leads to poor distribution when values are small or
0022 /// sequential. This function applies avalanche mixing so that small changes
0023 /// in the input produce large, uniformly-distributed changes in the output.
0024 ///
0025 /// Uses the fmix64 finalizer from Austin Appleby's MurmurHash3.
0026 /// @see https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
0027 ///
0028 /// @param x the value to mix
0029 /// @return the mixed value
0030 constexpr std::uint64_t hashMix(std::uint64_t x) {
0031   x ^= x >> 33;
0032   x *= 0xff51afd7ed558ccdULL;
0033   x ^= x >> 33;
0034   x *= 0xc4ceb9fe1a85ec53ULL;
0035   x ^= x >> 33;
0036   return x;
0037 }
0038
0039 /// Combine one or more values into a single hash.
0040 ///
0041 /// Each value is passed through @c std::hash and @c hashMix, then folded
0042 /// together using an asymmetric combine step (fold-left). This produces
0043 /// well-distributed, order-dependent hashes even for small or sequential
0044 /// integer inputs where @c std::hash is typically the identity.
0045 ///
0046 /// @code
0047 /// std::uint64_t h = Acts::hashMixAndCombine(a, b, c);
0048 /// @endcode
0049 ///
0050 /// @tparam T the type of the first value
0051 /// @tparam Rest the types of any additional values
0052 /// @param value the first value to hash
0053 /// @param rest additional values to fold in
0054 /// @return the combined hash
0055 template <typename T, typename... Rest>
0056 [[nodiscard]]
0057 constexpr std::uint64_t hashMixAndCombine(const T& value, const Rest&... rest) {
0058   std::uint64_t seed = hashMix(std::hash<T>{}(value));
0059   if constexpr (sizeof...(rest) > 0) {
0060     // Fold-left combine adapted from boost::hash_combine's 32-bit formula,
0061     // extended to 64-bit with wider shifts. The XOR with shifted seed makes
0062     // the operation asymmetric, preserving argument order.
0063     // @see https://github.com/boostorg/container_hash/blob/e3cbbebc8a1f9833287c8eb52fb0484ba744646b/include/boost/container_hash/hash.hpp#L469-L473
0064     auto foldLeft = [&seed](const auto& v) {
0065       std::uint64_t h = hashMix(std::hash<std::decay_t<decltype(v)>>{}(v));
0066       seed ^= h + 0x9e3779b97f4a7c15ULL + (seed << 12) + (seed >> 4);
0067     };
0068     (foldLeft(rest), ...);
0069   }
0070   return seed;
0071 }
0072
0073 }  // namespace Acts