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