Make sure hashmap cap is power of 2

zyedidia · Apr 13, 2022 · 8166217 · 8166217
1 parent c1f83ec
commit 8166217
Showing 1 changed file with 9 additions and 0 deletions.
diff --git a/hashmap/map.go b/hashmap/map.go
@@ -31,11 +31,20 @@ type ops[T any] struct {
 	hash   func(t T) uint64
 }
 
+func pow2ceil(num uint64) uint64 {
+	power := uint64(1)
+	for power < num {
+		power *= 2
+	}
+	return power
+}
+
 // New constructs a new map with the given capacity.
 func New[K, V any](capacity uint64, equals g.EqualsFn[K], hash g.HashFn[K]) *Map[K, V] {
 	if capacity == 0 {
 		capacity = 1
 	}
+	capacity = pow2ceil(capacity)
 	return &Map[K, V]{
 		entries:  make([]entry[K, V], capacity),
 		capacity: capacity,