Source file
src/hash/maphash/maphash_test.go
1
2
3
4
5 package maphash
6
7 import (
8 "bytes"
9 "fmt"
10 "hash"
11 "internal/asan"
12 "math"
13 "reflect"
14 "strings"
15 "testing"
16 "unsafe"
17 )
18
19 func TestUnseededHash(t *testing.T) {
20 m := map[uint64]struct{}{}
21 for i := 0; i < 1000; i++ {
22 h := new(Hash)
23 m[h.Sum64()] = struct{}{}
24 }
25 if len(m) < 900 {
26 t.Errorf("empty hash not sufficiently random: got %d, want 1000", len(m))
27 }
28 }
29
30 func TestSeededHash(t *testing.T) {
31 s := MakeSeed()
32 m := map[uint64]struct{}{}
33 for i := 0; i < 1000; i++ {
34 h := new(Hash)
35 h.SetSeed(s)
36 m[h.Sum64()] = struct{}{}
37 }
38 if len(m) != 1 {
39 t.Errorf("seeded hash is random: got %d, want 1", len(m))
40 }
41 }
42
43 func TestHashGrouping(t *testing.T) {
44 b := bytes.Repeat([]byte("foo"), 100)
45 hh := make([]*Hash, 7)
46 for i := range hh {
47 hh[i] = new(Hash)
48 }
49 for _, h := range hh[1:] {
50 h.SetSeed(hh[0].Seed())
51 }
52 hh[0].Write(b)
53 hh[1].WriteString(string(b))
54
55 writeByte := func(h *Hash, b byte) {
56 err := h.WriteByte(b)
57 if err != nil {
58 t.Fatalf("WriteByte: %v", err)
59 }
60 }
61 writeSingleByte := func(h *Hash, b byte) {
62 _, err := h.Write([]byte{b})
63 if err != nil {
64 t.Fatalf("Write single byte: %v", err)
65 }
66 }
67 writeStringSingleByte := func(h *Hash, b byte) {
68 _, err := h.WriteString(string([]byte{b}))
69 if err != nil {
70 t.Fatalf("WriteString single byte: %v", err)
71 }
72 }
73
74 for i, x := range b {
75 writeByte(hh[2], x)
76 writeSingleByte(hh[3], x)
77 if i == 0 {
78 writeByte(hh[4], x)
79 } else {
80 writeSingleByte(hh[4], x)
81 }
82 writeStringSingleByte(hh[5], x)
83 if i == 0 {
84 writeByte(hh[6], x)
85 } else {
86 writeStringSingleByte(hh[6], x)
87 }
88 }
89
90 sum := hh[0].Sum64()
91 for i, h := range hh {
92 if sum != h.Sum64() {
93 t.Errorf("hash %d not identical to a single Write", i)
94 }
95 }
96
97 if sum1 := Bytes(hh[0].Seed(), b); sum1 != hh[0].Sum64() {
98 t.Errorf("hash using Bytes not identical to a single Write")
99 }
100
101 if sum1 := String(hh[0].Seed(), string(b)); sum1 != hh[0].Sum64() {
102 t.Errorf("hash using String not identical to a single Write")
103 }
104 }
105
106 func TestHashBytesVsString(t *testing.T) {
107 s := "foo"
108 b := []byte(s)
109 h1 := new(Hash)
110 h2 := new(Hash)
111 h2.SetSeed(h1.Seed())
112 n1, err1 := h1.WriteString(s)
113 if n1 != len(s) || err1 != nil {
114 t.Fatalf("WriteString(s) = %d, %v, want %d, nil", n1, err1, len(s))
115 }
116 n2, err2 := h2.Write(b)
117 if n2 != len(b) || err2 != nil {
118 t.Fatalf("Write(b) = %d, %v, want %d, nil", n2, err2, len(b))
119 }
120 if h1.Sum64() != h2.Sum64() {
121 t.Errorf("hash of string and bytes not identical")
122 }
123 }
124
125 func TestHashHighBytes(t *testing.T) {
126
127 const N = 10
128 m := map[uint64]struct{}{}
129 for i := 0; i < N; i++ {
130 h := new(Hash)
131 h.WriteString("foo")
132 m[h.Sum64()>>32] = struct{}{}
133 }
134 if len(m) < N/2 {
135 t.Errorf("from %d seeds, wanted at least %d different hashes; got %d", N, N/2, len(m))
136 }
137 }
138
139 func TestRepeat(t *testing.T) {
140 h1 := new(Hash)
141 h1.WriteString("testing")
142 sum1 := h1.Sum64()
143
144 h1.Reset()
145 h1.WriteString("testing")
146 sum2 := h1.Sum64()
147
148 if sum1 != sum2 {
149 t.Errorf("different sum after resetting: %#x != %#x", sum1, sum2)
150 }
151
152 h2 := new(Hash)
153 h2.SetSeed(h1.Seed())
154 h2.WriteString("testing")
155 sum3 := h2.Sum64()
156
157 if sum1 != sum3 {
158 t.Errorf("different sum on the same seed: %#x != %#x", sum1, sum3)
159 }
160 }
161
162 func TestSeedFromSum64(t *testing.T) {
163 h1 := new(Hash)
164 h1.WriteString("foo")
165 x := h1.Sum64()
166 h2 := new(Hash)
167 h2.SetSeed(h1.Seed())
168 h2.WriteString("foo")
169 y := h2.Sum64()
170 if x != y {
171 t.Errorf("hashes don't match: want %x, got %x", x, y)
172 }
173 }
174
175 func TestSeedFromSeed(t *testing.T) {
176 h1 := new(Hash)
177 h1.WriteString("foo")
178 _ = h1.Seed()
179 x := h1.Sum64()
180 h2 := new(Hash)
181 h2.SetSeed(h1.Seed())
182 h2.WriteString("foo")
183 y := h2.Sum64()
184 if x != y {
185 t.Errorf("hashes don't match: want %x, got %x", x, y)
186 }
187 }
188
189 func TestSeedFromFlush(t *testing.T) {
190 b := make([]byte, 65)
191 h1 := new(Hash)
192 h1.Write(b)
193 x := h1.Sum64()
194 h2 := new(Hash)
195 h2.SetSeed(h1.Seed())
196 h2.Write(b)
197 y := h2.Sum64()
198 if x != y {
199 t.Errorf("hashes don't match: want %x, got %x", x, y)
200 }
201 }
202
203 func TestSeedFromReset(t *testing.T) {
204 h1 := new(Hash)
205 h1.WriteString("foo")
206 h1.Reset()
207 h1.WriteString("foo")
208 x := h1.Sum64()
209 h2 := new(Hash)
210 h2.SetSeed(h1.Seed())
211 h2.WriteString("foo")
212 y := h2.Sum64()
213 if x != y {
214 t.Errorf("hashes don't match: want %x, got %x", x, y)
215 }
216 }
217
218 func negativeZero[T float32 | float64]() T {
219 var f T
220 f = -f
221 return f
222 }
223
224 func TestComparable(t *testing.T) {
225 testComparable(t, int64(2))
226 testComparable(t, uint64(8))
227 testComparable(t, uintptr(12))
228 testComparable(t, any("s"))
229 testComparable(t, "s")
230 testComparable(t, true)
231 testComparable(t, new(float64))
232 testComparable(t, float64(9))
233 testComparable(t, complex128(9i+1))
234 testComparable(t, struct{}{})
235 testComparable(t, struct {
236 i int
237 u uint
238 b bool
239 f float64
240 p *int
241 a any
242 }{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
243 type S struct {
244 s string
245 }
246 s1 := S{s: heapStr(t)}
247 s2 := S{s: heapStr(t)}
248 if unsafe.StringData(s1.s) == unsafe.StringData(s2.s) {
249 t.Fatalf("unexpected two heapStr ptr equal")
250 }
251 if s1.s != s2.s {
252 t.Fatalf("unexpected two heapStr value not equal")
253 }
254 testComparable(t, s1, s2)
255 testComparable(t, s1.s, s2.s)
256 c1 := make(chan struct{})
257 c2 := make(chan struct{})
258 testComparable(t, c1, c1)
259 testComparable(t, chan struct{}(nil))
260 testComparable(t, float32(0), negativeZero[float32]())
261 testComparable(t, float64(0), negativeZero[float64]())
262 testComparableNoEqual(t, math.NaN(), math.NaN())
263 testComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
264 testComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
265 testComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
266 testComparableNoEqual(t, c1, c2)
267 }
268
269 func testComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
270 seed := MakeSeed()
271 if Comparable(seed, v1) == Comparable(seed, v2) {
272 t.Fatalf("Comparable(seed, %v) == Comparable(seed, %v)", v1, v2)
273 }
274 }
275
276 var heapStrValue = []byte("aTestString")
277
278 func heapStr(t *testing.T) string {
279 return string(heapStrValue)
280 }
281
282 func testComparable[T comparable](t *testing.T, v T, v2 ...T) {
283 t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
284 var a, b T = v, v
285 if len(v2) != 0 {
286 b = v2[0]
287 }
288 var pa *T = &a
289 seed := MakeSeed()
290 if Comparable(seed, a) != Comparable(seed, b) {
291 t.Fatalf("Comparable(seed, %v) != Comparable(seed, %v)", a, b)
292 }
293 old := Comparable(seed, pa)
294 stackGrow(8192)
295 new := Comparable(seed, pa)
296 if old != new {
297 t.Fatal("Comparable(seed, ptr) != Comparable(seed, ptr)")
298 }
299 })
300 }
301
302 var use byte
303
304
305 func stackGrow(dep int) {
306 if dep == 0 {
307 return
308 }
309 var local [1024]byte
310
311 local[randUint64()%1024] = byte(randUint64())
312 use = local[randUint64()%1024]
313 stackGrow(dep - 1)
314 }
315
316 func TestWriteComparable(t *testing.T) {
317 testWriteComparable(t, int64(2))
318 testWriteComparable(t, uint64(8))
319 testWriteComparable(t, uintptr(12))
320 testWriteComparable(t, any("s"))
321 testWriteComparable(t, "s")
322 testComparable(t, true)
323 testWriteComparable(t, new(float64))
324 testWriteComparable(t, float64(9))
325 testWriteComparable(t, complex128(9i+1))
326 testWriteComparable(t, struct{}{})
327 testWriteComparable(t, struct {
328 i int
329 u uint
330 b bool
331 f float64
332 p *int
333 a any
334 }{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
335 type S struct {
336 s string
337 }
338 s1 := S{s: heapStr(t)}
339 s2 := S{s: heapStr(t)}
340 if unsafe.StringData(s1.s) == unsafe.StringData(s2.s) {
341 t.Fatalf("unexpected two heapStr ptr equal")
342 }
343 if s1.s != s2.s {
344 t.Fatalf("unexpected two heapStr value not equal")
345 }
346 testWriteComparable(t, s1, s2)
347 testWriteComparable(t, s1.s, s2.s)
348 testWriteComparable(t, float32(0), negativeZero[float32]())
349 testWriteComparable(t, float64(0), negativeZero[float64]())
350 testWriteComparableNoEqual(t, math.NaN(), math.NaN())
351 testWriteComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
352 testWriteComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
353 testWriteComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
354 }
355
356 func testWriteComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
357 seed := MakeSeed()
358 h1 := Hash{}
359 h2 := Hash{}
360 h1.seed, h2.seed = seed, seed
361 WriteComparable(&h1, v1)
362 WriteComparable(&h2, v2)
363 if h1.Sum64() == h2.Sum64() {
364 t.Fatalf("WriteComparable(seed, %v) == WriteComparable(seed, %v)", v1, v2)
365 }
366
367 }
368
369 func testWriteComparable[T comparable](t *testing.T, v T, v2 ...T) {
370 t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
371 var a, b T = v, v
372 if len(v2) != 0 {
373 b = v2[0]
374 }
375 var pa *T = &a
376 h1 := Hash{}
377 h2 := Hash{}
378 h1.seed = MakeSeed()
379 h2.seed = h1.seed
380 WriteComparable(&h1, a)
381 WriteComparable(&h2, b)
382 if h1.Sum64() != h2.Sum64() {
383 t.Fatalf("WriteComparable(h, %v) != WriteComparable(h, %v)", a, b)
384 }
385 WriteComparable(&h1, pa)
386 old := h1.Sum64()
387 stackGrow(8192)
388 WriteComparable(&h2, pa)
389 new := h2.Sum64()
390 if old != new {
391 t.Fatal("WriteComparable(seed, ptr) != WriteComparable(seed, ptr)")
392 }
393 })
394 }
395
396 func TestComparableShouldPanic(t *testing.T) {
397 s := []byte("s")
398 a := any(s)
399 defer func() {
400 e := recover()
401 err, ok := e.(error)
402 if !ok {
403 t.Fatalf("Comaparable(any([]byte)) should panic")
404 }
405 want := "hash of unhashable type []uint8"
406 if s := err.Error(); !strings.Contains(s, want) {
407 t.Fatalf("want %s, got %s", want, s)
408 }
409 }()
410 Comparable(MakeSeed(), a)
411 }
412
413 func TestWriteComparableNoncommute(t *testing.T) {
414 seed := MakeSeed()
415 var h1, h2 Hash
416 h1.SetSeed(seed)
417 h2.SetSeed(seed)
418
419 h1.WriteString("abc")
420 WriteComparable(&h1, 123)
421 WriteComparable(&h2, 123)
422 h2.WriteString("abc")
423
424 if h1.Sum64() == h2.Sum64() {
425 t.Errorf("WriteComparable and WriteString unexpectedly commute")
426 }
427 }
428
429 func TestComparableAllocations(t *testing.T) {
430 if purego {
431 t.Skip("skip allocation test in purego mode - reflect-based implementation allocates more")
432 }
433 if asan.Enabled {
434 t.Skip("skip allocation test under -asan")
435 }
436 seed := MakeSeed()
437 x := heapStr(t)
438 allocs := testing.AllocsPerRun(10, func() {
439 s := "s" + x
440 Comparable(seed, s)
441 })
442 if allocs > 0 {
443 t.Errorf("got %v allocs, want 0", allocs)
444 }
445
446 type S struct {
447 a int
448 b string
449 }
450 allocs = testing.AllocsPerRun(10, func() {
451 s := S{123, "s" + x}
452 Comparable(seed, s)
453 })
454 if allocs > 0 {
455 t.Errorf("got %v allocs, want 0", allocs)
456 }
457 }
458
459
460 var _ hash.Hash = &Hash{}
461 var _ hash.Hash64 = &Hash{}
462
463 func benchmarkSize(b *testing.B, size int) {
464 h := &Hash{}
465 buf := make([]byte, size)
466 s := string(buf)
467
468 b.Run("Write", func(b *testing.B) {
469 b.SetBytes(int64(size))
470 for i := 0; i < b.N; i++ {
471 h.Reset()
472 h.Write(buf)
473 h.Sum64()
474 }
475 })
476
477 b.Run("Bytes", func(b *testing.B) {
478 b.SetBytes(int64(size))
479 seed := h.Seed()
480 for i := 0; i < b.N; i++ {
481 Bytes(seed, buf)
482 }
483 })
484
485 b.Run("String", func(b *testing.B) {
486 b.SetBytes(int64(size))
487 seed := h.Seed()
488 for i := 0; i < b.N; i++ {
489 String(seed, s)
490 }
491 })
492 }
493
494 func BenchmarkHash(b *testing.B) {
495 sizes := []int{4, 8, 16, 32, 64, 256, 320, 1024, 4096, 16384}
496 for _, size := range sizes {
497 b.Run(fmt.Sprint("n=", size), func(b *testing.B) {
498 benchmarkSize(b, size)
499 })
500 }
501 }
502
503 func benchmarkComparable[T comparable](b *testing.B, v T) {
504 b.Run(reflect.TypeFor[T]().String(), func(b *testing.B) {
505 seed := MakeSeed()
506 for i := 0; i < b.N; i++ {
507 Comparable(seed, v)
508 }
509 })
510 }
511
512 func BenchmarkComparable(b *testing.B) {
513 type testStruct struct {
514 i int
515 u uint
516 b bool
517 f float64
518 p *int
519 a any
520 }
521 benchmarkComparable(b, int64(2))
522 benchmarkComparable(b, uint64(8))
523 benchmarkComparable(b, uintptr(12))
524 benchmarkComparable(b, any("s"))
525 benchmarkComparable(b, "s")
526 benchmarkComparable(b, true)
527 benchmarkComparable(b, new(float64))
528 benchmarkComparable(b, float64(9))
529 benchmarkComparable(b, complex128(9i+1))
530 benchmarkComparable(b, struct{}{})
531 benchmarkComparable(b, testStruct{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
532 }
533
View as plain text