Core/Utilities/HashCombineTests.cpp

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 #include <boost/test/unit_test.hpp>
0010
0011 #include "Acts/Utilities/HashCombine.hpp"
0012
0013 #include <array>
0014 #include <cstddef>
0015 #include <cstdint>
0016 #include <unordered_set>
0017
0018 using namespace Acts;
0019
0020 namespace ActsTests {
0021
0022 BOOST_AUTO_TEST_SUITE(UtilitiesSuite)
0023
0024 BOOST_AUTO_TEST_CASE(hashMix_nonIdentity) {
0025   // hashMix should not be the identity for small integers.
0026   // Note: fmix64(0) == 0 is a known fixed point of the murmur3 finalizer.
0027   for (std::size_t i = 1; i < 100; ++i) {
0028     BOOST_CHECK_NE(hashMix(i), i);
0029   }
0030 }
0031
0032 BOOST_AUTO_TEST_CASE(hashMix_distinct) {
0033   // consecutive inputs should produce distinct outputs
0034   std::unordered_set<std::size_t> seen;
0035   for (std::size_t i = 0; i < 10000; ++i) {
0036     auto [it, inserted] = seen.insert(hashMix(i));
0037     BOOST_CHECK(inserted);
0038   }
0039 }
0040
0041 BOOST_AUTO_TEST_CASE(hashMixAndCombine_basic) {
0042   // same inputs produce same hash
0043   std::size_t a = hashMixAndCombine(1, 2, 3);
0044   std::size_t b = hashMixAndCombine(1, 2, 3);
0045   BOOST_CHECK_EQUAL(a, b);
0046
0047   // different inputs produce different hashes
0048   std::size_t c = hashMixAndCombine(1, 2, 4);
0049   BOOST_CHECK_NE(a, c);
0050 }
0051
0052 BOOST_AUTO_TEST_CASE(hashMixAndCombine_orderMatters) {
0053   std::size_t a = hashMixAndCombine(1, 2);
0054   std::size_t b = hashMixAndCombine(2, 1);
0055   BOOST_CHECK_NE(a, b);
0056 }
0057
0058 BOOST_AUTO_TEST_CASE(hashMixAndCombine_consecutiveCollisionRate) {
0059   // Simulate barcode-like inputs: 5 small integer fields, many with zeros.
0060   // Hash into a 4096-bucket table and check collision quality.
0061   constexpr std::size_t nBuckets = 4096;
0062
0063   std::unordered_set<std::size_t> hashes;
0064   std::array<std::size_t, nBuckets> buckets{};
0065
0066   // Generate barcode-like inputs: particle ID 0..99999, across several
0067   // vertex primaries, with fixed other fields.
0068   std::size_t nInputs = 0;
0069   for (std::uint32_t vp = 0; vp < 10; ++vp) {
0070     for (std::uint32_t p = 0; p < 100000; ++p) {
0071       std::size_t h = hashMixAndCombine(vp, std::uint32_t{0}, p,
0072                                         std::uint32_t{0}, std::uint32_t{0});
0073       hashes.insert(h);
0074       buckets[h % nBuckets]++;
0075       ++nInputs;
0076     }
0077   }
0078
0079   // No full collisions for 1M distinct inputs
0080   BOOST_CHECK_EQUAL(hashes.size(), nInputs);
0081
0082   // Check that the distribution across buckets is reasonable.
0083   // With 1M items in 4096 buckets (~244 per bucket on average), a good hash
0084   // should keep the max bucket well below 2x the average.
0085   std::size_t maxBucket = *std::max_element(buckets.begin(), buckets.end());
0086   double avgBucket = static_cast<double>(nInputs) / nBuckets;
0087   double ratio = static_cast<double>(maxBucket) / avgBucket;
0088   BOOST_CHECK_LT(ratio, 2.0);
0089 }
0090
0091 BOOST_AUTO_TEST_CASE(hashMixAndCombine_multiFieldCollisionRate) {
0092   // All fields vary in small ranges (realistic barcode space)
0093   std::unordered_set<std::size_t> hashes;
0094   std::size_t nInputs = 0;
0095
0096   // 20 * 10 * 500 * 5 * 5 = 2'500'000 inputs
0097   for (std::uint32_t vp = 0; vp < 20; ++vp) {
0098     for (std::uint32_t vs = 0; vs < 10; ++vs) {
0099       for (std::uint32_t p = 0; p < 500; ++p) {
0100         for (std::uint32_t g = 0; g < 5; ++g) {
0101           for (std::uint32_t sp = 0; sp < 5; ++sp) {
0102             std::size_t h = hashMixAndCombine(vp, vs, p, g, sp);
0103             hashes.insert(h);
0104             ++nInputs;
0105           }
0106         }
0107       }
0108     }
0109   }
0110
0111   // All 2.5M inputs should produce unique hashes
0112   BOOST_CHECK_EQUAL(hashes.size(), nInputs);
0113 }
0114
0115 BOOST_AUTO_TEST_SUITE_END()
0116
0117 }  // namespace ActsTests