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