| 50 | |
| 51 | template <class T> |
| 52 | uint32_t GetHashSizeFor(std::span<T const> const& vals, uint32_t maxCollisions) |
| 53 | { |
| 54 | uint32_t hsize = (uint32_t)vals.size() + 1; |
| 55 | uint32_t collisions{ 0 }; |
| 56 | uint32_t numBuckets{ 0 }; |
| 57 | for (;;) { |
| 58 | numBuckets = GetNearestSmallMultiHashMapPrime(hsize + 1); |
| 59 | |
| 60 | collisions = 0; |
| 61 | |
| 62 | BitSet<> buckets; |
| 63 | buckets.EnsureSize(numBuckets); |
| 64 | for (auto const& k : vals) { |
| 65 | auto hash = (uint32_t)HashMapHash(k) % numBuckets; |
| 66 | if (buckets[hash]) { |
| 67 | collisions++; |
| 68 | } |
| 69 | |
| 70 | buckets.Set(hash); |
| 71 | } |
| 72 | |
| 73 | if (collisions <= maxCollisions) { |
| 74 | return numBuckets; |
| 75 | } |
| 76 | |
| 77 | hsize = numBuckets + 1; |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | |
| 82 | template <class T> |
no test coverage detected