From e3140f789eb976e9d4ed9bf28ef6b6a171a6bb95 Mon Sep 17 00:00:00 2001
From: Sam Atman
Date: Fri, 6 Feb 2026 12:54:24 -0500
Subject: Slightly better hash reduction for comptime_map

This reduces collisions by 11% while adding no branching, so I'm calling
it a win.
---
 src/comptime_map.zig | 24 +++++++++++++++++++++---
 1 file changed, 21 insertions(+), 3 deletions(-)

(limited to 'src')

diff --git a/src/comptime_map.zig b/src/comptime_map.zig
index d41f6f8..3d61bd6 100644
--- a/src/comptime_map.zig
+++ b/src/comptime_map.zig
@@ -38,7 +38,7 @@ pub fn ComptimeHashMap(comptime K: type, comptime V: type, comptime ctx: type, c
         var key: K = kv.@"0";
         var value: V = kv.@"1";
 
-        const start_index = @as(usize, ctx.hash(undefined, key)) & (size - 1);
+        const start_index = reduceMulHi(ctx.hash(undefined, key), size);
 
         var roll_over = 0;
         var distance_from_start_index = 0;
@@ -88,7 +88,7 @@ pub fn ComptimeHashMap(comptime K: type, comptime V: type, comptime ctx: type, c
         }
 
         pub fn get(key: K) ?*const V {
-            const start_index = @as(usize, ctx.hash(undefined, key)) & (size - 1);
+            const start_index = reduceMulHi(ctx.hash(undefined, key), size);
             {
                 var roll_over: usize = 0;
                 while (roll_over <= max_distance_from_start_index) : (roll_over += 1) {
@@ -104,6 +104,11 @@ pub fn ComptimeHashMap(comptime K: type, comptime V: type, comptime ctx: type, c
     };
 }
 
+fn reduceMulHi(h: u64, m: u64) u64 {
+    // floor((h * m) / 2^64)
+    return @as(u64, @truncate((@as(u128, h) * @as(u128, m)) >> 64));
+}
+
 test "basic usage" {
     const map = ComptimeStringHashMap(usize, .{
         .{ "foo", 1 },
@@ -157,6 +162,20 @@ test "array pair comptime hash map" {
     try testing.expect(map.has(.{ 2, 4 }));
 }
 
+test "Next version tripwire" {
+    // Check for the bug on each version bump, if it goes away,
+    // well, that's useful information.
+    const v = @import("builtin").zig_version;
+    if (v.major == 0 and v.minor <= 15) return;
+    const map = AutoComptimeHashMap([2]u21, u21, .{
+        .{ .{ 2, 3 }, 5 },
+        .{ .{ 42, 56 }, 12 },
+        .{ .{ 2, 4 }, 6 },
+    });
+    try testing.expect(map.has(.{ 2, 3 })); // Still buggy :/
+    try testing.expect(map.has(.{ 23, 42 })); // No bug! :D
+}
+
 const std = @import("std");
 const hash_map = std.hash_map;
 const testing = std.testing;
@@ -183,4 +202,3 @@ const math = std.math;
 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 // SOFTWARE.
-
-- 
cgit v1.2.3