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 testComparable(t, float32(0), negativeZero[float32]())
257 testComparable(t, float64(0), negativeZero[float64]())
258 testComparableNoEqual(t, math.NaN(), math.NaN())
259 testComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
260 testComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
261 testComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
262 }
263
264 func testComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
265 seed := MakeSeed()
266 if Comparable(seed, v1) == Comparable(seed, v2) {
267 t.Fatalf("Comparable(seed, %v) == Comparable(seed, %v)", v1, v2)
268 }
269 }
270
271 var heapStrValue = []byte("aTestString")
272
273 func heapStr(t *testing.T) string {
274 return string(heapStrValue)
275 }
276
277 func testComparable[T comparable](t *testing.T, v T, v2 ...T) {
278 t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
279 var a, b T = v, v
280 if len(v2) != 0 {
281 b = v2[0]
282 }
283 var pa *T = &a
284 seed := MakeSeed()
285 if Comparable(seed, a) != Comparable(seed, b) {
286 t.Fatalf("Comparable(seed, %v) != Comparable(seed, %v)", a, b)
287 }
288 old := Comparable(seed, pa)
289 stackGrow(8192)
290 new := Comparable(seed, pa)
291 if old != new {
292 t.Fatal("Comparable(seed, ptr) != Comparable(seed, ptr)")
293 }
294 })
295 }
296
297 var use byte
298
299
300 func stackGrow(dep int) {
301 if dep == 0 {
302 return
303 }
304 var local [1024]byte
305
306 local[randUint64()%1024] = byte(randUint64())
307 use = local[randUint64()%1024]
308 stackGrow(dep - 1)
309 }
310
311 func TestWriteComparable(t *testing.T) {
312 testWriteComparable(t, int64(2))
313 testWriteComparable(t, uint64(8))
314 testWriteComparable(t, uintptr(12))
315 testWriteComparable(t, any("s"))
316 testWriteComparable(t, "s")
317 testComparable(t, true)
318 testWriteComparable(t, new(float64))
319 testWriteComparable(t, float64(9))
320 testWriteComparable(t, complex128(9i+1))
321 testWriteComparable(t, struct{}{})
322 testWriteComparable(t, struct {
323 i int
324 u uint
325 b bool
326 f float64
327 p *int
328 a any
329 }{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
330 type S struct {
331 s string
332 }
333 s1 := S{s: heapStr(t)}
334 s2 := S{s: heapStr(t)}
335 if unsafe.StringData(s1.s) == unsafe.StringData(s2.s) {
336 t.Fatalf("unexpected two heapStr ptr equal")
337 }
338 if s1.s != s2.s {
339 t.Fatalf("unexpected two heapStr value not equal")
340 }
341 testWriteComparable(t, s1, s2)
342 testWriteComparable(t, s1.s, s2.s)
343 testWriteComparable(t, float32(0), negativeZero[float32]())
344 testWriteComparable(t, float64(0), negativeZero[float64]())
345 testWriteComparableNoEqual(t, math.NaN(), math.NaN())
346 testWriteComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
347 testWriteComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
348 testWriteComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
349 }
350
351 func testWriteComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
352 seed := MakeSeed()
353 h1 := Hash{}
354 h2 := Hash{}
355 h1.seed, h2.seed = seed, seed
356 WriteComparable(&h1, v1)
357 WriteComparable(&h2, v2)
358 if h1.Sum64() == h2.Sum64() {
359 t.Fatalf("WriteComparable(seed, %v) == WriteComparable(seed, %v)", v1, v2)
360 }
361
362 }
363
364 func testWriteComparable[T comparable](t *testing.T, v T, v2 ...T) {
365 t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
366 var a, b T = v, v
367 if len(v2) != 0 {
368 b = v2[0]
369 }
370 var pa *T = &a
371 h1 := Hash{}
372 h2 := Hash{}
373 h1.seed = MakeSeed()
374 h2.seed = h1.seed
375 WriteComparable(&h1, a)
376 WriteComparable(&h2, b)
377 if h1.Sum64() != h2.Sum64() {
378 t.Fatalf("WriteComparable(h, %v) != WriteComparable(h, %v)", a, b)
379 }
380 WriteComparable(&h1, pa)
381 old := h1.Sum64()
382 stackGrow(8192)
383 WriteComparable(&h2, pa)
384 new := h2.Sum64()
385 if old != new {
386 t.Fatal("WriteComparable(seed, ptr) != WriteComparable(seed, ptr)")
387 }
388 })
389 }
390
391 func TestComparableShouldPanic(t *testing.T) {
392 s := []byte("s")
393 a := any(s)
394 defer func() {
395 e := recover()
396 err, ok := e.(error)
397 if !ok {
398 t.Fatalf("Comaparable(any([]byte)) should panic")
399 }
400 want := "hash of unhashable type []uint8"
401 if s := err.Error(); !strings.Contains(s, want) {
402 t.Fatalf("want %s, got %s", want, s)
403 }
404 }()
405 Comparable(MakeSeed(), a)
406 }
407
408 func TestWriteComparableNoncommute(t *testing.T) {
409 seed := MakeSeed()
410 var h1, h2 Hash
411 h1.SetSeed(seed)
412 h2.SetSeed(seed)
413
414 h1.WriteString("abc")
415 WriteComparable(&h1, 123)
416 WriteComparable(&h2, 123)
417 h2.WriteString("abc")
418
419 if h1.Sum64() == h2.Sum64() {
420 t.Errorf("WriteComparable and WriteString unexpectedly commute")
421 }
422 }
423
424 func TestComparableAllocations(t *testing.T) {
425 if purego {
426 t.Skip("skip allocation test in purego mode - reflect-based implementation allocates more")
427 }
428 if asan.Enabled {
429 t.Skip("skip allocation test under -asan")
430 }
431 seed := MakeSeed()
432 x := heapStr(t)
433 allocs := testing.AllocsPerRun(10, func() {
434 s := "s" + x
435 Comparable(seed, s)
436 })
437 if allocs > 0 {
438 t.Errorf("got %v allocs, want 0", allocs)
439 }
440
441 type S struct {
442 a int
443 b string
444 }
445 allocs = testing.AllocsPerRun(10, func() {
446 s := S{123, "s" + x}
447 Comparable(seed, s)
448 })
449 if allocs > 0 {
450 t.Errorf("got %v allocs, want 0", allocs)
451 }
452 }
453
454
455 var _ hash.Hash = &Hash{}
456 var _ hash.Hash64 = &Hash{}
457
458 func benchmarkSize(b *testing.B, size int) {
459 h := &Hash{}
460 buf := make([]byte, size)
461 s := string(buf)
462
463 b.Run("Write", func(b *testing.B) {
464 b.SetBytes(int64(size))
465 for i := 0; i < b.N; i++ {
466 h.Reset()
467 h.Write(buf)
468 h.Sum64()
469 }
470 })
471
472 b.Run("Bytes", func(b *testing.B) {
473 b.SetBytes(int64(size))
474 seed := h.Seed()
475 for i := 0; i < b.N; i++ {
476 Bytes(seed, buf)
477 }
478 })
479
480 b.Run("String", func(b *testing.B) {
481 b.SetBytes(int64(size))
482 seed := h.Seed()
483 for i := 0; i < b.N; i++ {
484 String(seed, s)
485 }
486 })
487 }
488
489 func BenchmarkHash(b *testing.B) {
490 sizes := []int{4, 8, 16, 32, 64, 256, 320, 1024, 4096, 16384}
491 for _, size := range sizes {
492 b.Run(fmt.Sprint("n=", size), func(b *testing.B) {
493 benchmarkSize(b, size)
494 })
495 }
496 }
497
498 func benchmarkComparable[T comparable](b *testing.B, v T) {
499 b.Run(reflect.TypeFor[T]().String(), func(b *testing.B) {
500 seed := MakeSeed()
501 for i := 0; i < b.N; i++ {
502 Comparable(seed, v)
503 }
504 })
505 }
506
507 func BenchmarkComparable(b *testing.B) {
508 type testStruct struct {
509 i int
510 u uint
511 b bool
512 f float64
513 p *int
514 a any
515 }
516 benchmarkComparable(b, int64(2))
517 benchmarkComparable(b, uint64(8))
518 benchmarkComparable(b, uintptr(12))
519 benchmarkComparable(b, any("s"))
520 benchmarkComparable(b, "s")
521 benchmarkComparable(b, true)
522 benchmarkComparable(b, new(float64))
523 benchmarkComparable(b, float64(9))
524 benchmarkComparable(b, complex128(9i+1))
525 benchmarkComparable(b, struct{}{})
526 benchmarkComparable(b, testStruct{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
527 }
528
View as plain text