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 testComparable(t, float32(0), negativeZero[float32]())
258 testComparable(t, float64(0), negativeZero[float64]())
259 testComparableNoEqual(t, math.NaN(), math.NaN())
260 testComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
261 testComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
262 testComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
263 }
264
265 func testComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
266 seed := MakeSeed()
267 if Comparable(seed, v1) == Comparable(seed, v2) {
268 t.Fatalf("Comparable(seed, %v) == Comparable(seed, %v)", v1, v2)
269 }
270 }
271
272 var heapStrValue = []byte("aTestString")
273
274 func heapStr(t *testing.T) string {
275 return string(heapStrValue)
276 }
277
278 func testComparable[T comparable](t *testing.T, v T, v2 ...T) {
279 t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
280 var a, b T = v, v
281 if len(v2) != 0 {
282 b = v2[0]
283 }
284 var pa *T = &a
285 seed := MakeSeed()
286 if Comparable(seed, a) != Comparable(seed, b) {
287 t.Fatalf("Comparable(seed, %v) != Comparable(seed, %v)", a, b)
288 }
289 old := Comparable(seed, pa)
290 stackGrow(8192)
291 new := Comparable(seed, pa)
292 if old != new {
293 t.Fatal("Comparable(seed, ptr) != Comparable(seed, ptr)")
294 }
295 })
296 }
297
298 var use byte
299
300
301 func stackGrow(dep int) {
302 if dep == 0 {
303 return
304 }
305 var local [1024]byte
306
307 local[randUint64()%1024] = byte(randUint64())
308 use = local[randUint64()%1024]
309 stackGrow(dep - 1)
310 }
311
312 func TestWriteComparable(t *testing.T) {
313 testWriteComparable(t, int64(2))
314 testWriteComparable(t, uint64(8))
315 testWriteComparable(t, uintptr(12))
316 testWriteComparable(t, any("s"))
317 testWriteComparable(t, "s")
318 testComparable(t, true)
319 testWriteComparable(t, new(float64))
320 testWriteComparable(t, float64(9))
321 testWriteComparable(t, complex128(9i+1))
322 testWriteComparable(t, struct{}{})
323 testWriteComparable(t, struct {
324 i int
325 u uint
326 b bool
327 f float64
328 p *int
329 a any
330 }{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
331 type S struct {
332 s string
333 }
334 s1 := S{s: heapStr(t)}
335 s2 := S{s: heapStr(t)}
336 if unsafe.StringData(s1.s) == unsafe.StringData(s2.s) {
337 t.Fatalf("unexpected two heapStr ptr equal")
338 }
339 if s1.s != s2.s {
340 t.Fatalf("unexpected two heapStr value not equal")
341 }
342 testWriteComparable(t, s1, s2)
343 testWriteComparable(t, s1.s, s2.s)
344 testWriteComparable(t, float32(0), negativeZero[float32]())
345 testWriteComparable(t, float64(0), negativeZero[float64]())
346 testWriteComparableNoEqual(t, math.NaN(), math.NaN())
347 testWriteComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
348 testWriteComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
349 testWriteComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
350 }
351
352 func testWriteComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
353 seed := MakeSeed()
354 h1 := Hash{}
355 h2 := Hash{}
356 h1.seed, h2.seed = seed, seed
357 WriteComparable(&h1, v1)
358 WriteComparable(&h2, v2)
359 if h1.Sum64() == h2.Sum64() {
360 t.Fatalf("WriteComparable(seed, %v) == WriteComparable(seed, %v)", v1, v2)
361 }
362
363 }
364
365 func testWriteComparable[T comparable](t *testing.T, v T, v2 ...T) {
366 t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
367 var a, b T = v, v
368 if len(v2) != 0 {
369 b = v2[0]
370 }
371 var pa *T = &a
372 h1 := Hash{}
373 h2 := Hash{}
374 h1.seed = MakeSeed()
375 h2.seed = h1.seed
376 WriteComparable(&h1, a)
377 WriteComparable(&h2, b)
378 if h1.Sum64() != h2.Sum64() {
379 t.Fatalf("WriteComparable(h, %v) != WriteComparable(h, %v)", a, b)
380 }
381 WriteComparable(&h1, pa)
382 old := h1.Sum64()
383 stackGrow(8192)
384 WriteComparable(&h2, pa)
385 new := h2.Sum64()
386 if old != new {
387 t.Fatal("WriteComparable(seed, ptr) != WriteComparable(seed, ptr)")
388 }
389 })
390 }
391
392 func TestComparableShouldPanic(t *testing.T) {
393 s := []byte("s")
394 a := any(s)
395 defer func() {
396 e := recover()
397 err, ok := e.(error)
398 if !ok {
399 t.Fatalf("Comaparable(any([]byte)) should panic")
400 }
401 want := "hash of unhashable type []uint8"
402 if s := err.Error(); !strings.Contains(s, want) {
403 t.Fatalf("want %s, got %s", want, s)
404 }
405 }()
406 Comparable(MakeSeed(), a)
407 }
408
409 func TestWriteComparableNoncommute(t *testing.T) {
410 seed := MakeSeed()
411 var h1, h2 Hash
412 h1.SetSeed(seed)
413 h2.SetSeed(seed)
414
415 h1.WriteString("abc")
416 WriteComparable(&h1, 123)
417 WriteComparable(&h2, 123)
418 h2.WriteString("abc")
419
420 if h1.Sum64() == h2.Sum64() {
421 t.Errorf("WriteComparable and WriteString unexpectedly commute")
422 }
423 }
424
425 func TestComparableAllocations(t *testing.T) {
426 if purego {
427 t.Skip("skip allocation test in purego mode - reflect-based implementation allocates more")
428 }
429 if asan.Enabled {
430 t.Skip("skip allocation test under -asan")
431 }
432 seed := MakeSeed()
433 x := heapStr(t)
434 allocs := testing.AllocsPerRun(10, func() {
435 s := "s" + x
436 Comparable(seed, s)
437 })
438 if allocs > 0 {
439 t.Errorf("got %v allocs, want 0", allocs)
440 }
441
442 type S struct {
443 a int
444 b string
445 }
446 allocs = testing.AllocsPerRun(10, func() {
447 s := S{123, "s" + x}
448 Comparable(seed, s)
449 })
450 if allocs > 0 {
451 t.Errorf("got %v allocs, want 0", allocs)
452 }
453 }
454
455
456 var _ hash.Hash = &Hash{}
457 var _ hash.Hash64 = &Hash{}
458
459 func TestHashInterface(t *testing.T) {
460 testhash.TestHash(t, func() hash.Hash { return new(Hash) })
461 }
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