Source file src/hash/maphash/maphash_test.go

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package maphash
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"hash"
    11  	"testing"
    12  )
    13  
    14  func TestUnseededHash(t *testing.T) {
    15  	m := map[uint64]struct{}{}
    16  	for i := 0; i < 1000; i++ {
    17  		h := new(Hash)
    18  		m[h.Sum64()] = struct{}{}
    19  	}
    20  	if len(m) < 900 {
    21  		t.Errorf("empty hash not sufficiently random: got %d, want 1000", len(m))
    22  	}
    23  }
    24  
    25  func TestSeededHash(t *testing.T) {
    26  	s := MakeSeed()
    27  	m := map[uint64]struct{}{}
    28  	for i := 0; i < 1000; i++ {
    29  		h := new(Hash)
    30  		h.SetSeed(s)
    31  		m[h.Sum64()] = struct{}{}
    32  	}
    33  	if len(m) != 1 {
    34  		t.Errorf("seeded hash is random: got %d, want 1", len(m))
    35  	}
    36  }
    37  
    38  func TestHashGrouping(t *testing.T) {
    39  	b := bytes.Repeat([]byte("foo"), 100)
    40  	hh := make([]*Hash, 7)
    41  	for i := range hh {
    42  		hh[i] = new(Hash)
    43  	}
    44  	for _, h := range hh[1:] {
    45  		h.SetSeed(hh[0].Seed())
    46  	}
    47  	hh[0].Write(b)
    48  	hh[1].WriteString(string(b))
    49  
    50  	writeByte := func(h *Hash, b byte) {
    51  		err := h.WriteByte(b)
    52  		if err != nil {
    53  			t.Fatalf("WriteByte: %v", err)
    54  		}
    55  	}
    56  	writeSingleByte := func(h *Hash, b byte) {
    57  		_, err := h.Write([]byte{b})
    58  		if err != nil {
    59  			t.Fatalf("Write single byte: %v", err)
    60  		}
    61  	}
    62  	writeStringSingleByte := func(h *Hash, b byte) {
    63  		_, err := h.WriteString(string([]byte{b}))
    64  		if err != nil {
    65  			t.Fatalf("WriteString single byte: %v", err)
    66  		}
    67  	}
    68  
    69  	for i, x := range b {
    70  		writeByte(hh[2], x)
    71  		writeSingleByte(hh[3], x)
    72  		if i == 0 {
    73  			writeByte(hh[4], x)
    74  		} else {
    75  			writeSingleByte(hh[4], x)
    76  		}
    77  		writeStringSingleByte(hh[5], x)
    78  		if i == 0 {
    79  			writeByte(hh[6], x)
    80  		} else {
    81  			writeStringSingleByte(hh[6], x)
    82  		}
    83  	}
    84  
    85  	sum := hh[0].Sum64()
    86  	for i, h := range hh {
    87  		if sum != h.Sum64() {
    88  			t.Errorf("hash %d not identical to a single Write", i)
    89  		}
    90  	}
    91  
    92  	if sum1 := Bytes(hh[0].Seed(), b); sum1 != hh[0].Sum64() {
    93  		t.Errorf("hash using Bytes not identical to a single Write")
    94  	}
    95  
    96  	if sum1 := String(hh[0].Seed(), string(b)); sum1 != hh[0].Sum64() {
    97  		t.Errorf("hash using String not identical to a single Write")
    98  	}
    99  }
   100  
   101  func TestHashBytesVsString(t *testing.T) {
   102  	s := "foo"
   103  	b := []byte(s)
   104  	h1 := new(Hash)
   105  	h2 := new(Hash)
   106  	h2.SetSeed(h1.Seed())
   107  	n1, err1 := h1.WriteString(s)
   108  	if n1 != len(s) || err1 != nil {
   109  		t.Fatalf("WriteString(s) = %d, %v, want %d, nil", n1, err1, len(s))
   110  	}
   111  	n2, err2 := h2.Write(b)
   112  	if n2 != len(b) || err2 != nil {
   113  		t.Fatalf("Write(b) = %d, %v, want %d, nil", n2, err2, len(b))
   114  	}
   115  	if h1.Sum64() != h2.Sum64() {
   116  		t.Errorf("hash of string and bytes not identical")
   117  	}
   118  }
   119  
   120  func TestHashHighBytes(t *testing.T) {
   121  	// See issue 34925.
   122  	const N = 10
   123  	m := map[uint64]struct{}{}
   124  	for i := 0; i < N; i++ {
   125  		h := new(Hash)
   126  		h.WriteString("foo")
   127  		m[h.Sum64()>>32] = struct{}{}
   128  	}
   129  	if len(m) < N/2 {
   130  		t.Errorf("from %d seeds, wanted at least %d different hashes; got %d", N, N/2, len(m))
   131  	}
   132  }
   133  
   134  func TestRepeat(t *testing.T) {
   135  	h1 := new(Hash)
   136  	h1.WriteString("testing")
   137  	sum1 := h1.Sum64()
   138  
   139  	h1.Reset()
   140  	h1.WriteString("testing")
   141  	sum2 := h1.Sum64()
   142  
   143  	if sum1 != sum2 {
   144  		t.Errorf("different sum after resetting: %#x != %#x", sum1, sum2)
   145  	}
   146  
   147  	h2 := new(Hash)
   148  	h2.SetSeed(h1.Seed())
   149  	h2.WriteString("testing")
   150  	sum3 := h2.Sum64()
   151  
   152  	if sum1 != sum3 {
   153  		t.Errorf("different sum on the same seed: %#x != %#x", sum1, sum3)
   154  	}
   155  }
   156  
   157  func TestSeedFromSum64(t *testing.T) {
   158  	h1 := new(Hash)
   159  	h1.WriteString("foo")
   160  	x := h1.Sum64() // seed generated here
   161  	h2 := new(Hash)
   162  	h2.SetSeed(h1.Seed())
   163  	h2.WriteString("foo")
   164  	y := h2.Sum64()
   165  	if x != y {
   166  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   167  	}
   168  }
   169  
   170  func TestSeedFromSeed(t *testing.T) {
   171  	h1 := new(Hash)
   172  	h1.WriteString("foo")
   173  	_ = h1.Seed() // seed generated here
   174  	x := h1.Sum64()
   175  	h2 := new(Hash)
   176  	h2.SetSeed(h1.Seed())
   177  	h2.WriteString("foo")
   178  	y := h2.Sum64()
   179  	if x != y {
   180  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   181  	}
   182  }
   183  
   184  func TestSeedFromFlush(t *testing.T) {
   185  	b := make([]byte, 65)
   186  	h1 := new(Hash)
   187  	h1.Write(b) // seed generated here
   188  	x := h1.Sum64()
   189  	h2 := new(Hash)
   190  	h2.SetSeed(h1.Seed())
   191  	h2.Write(b)
   192  	y := h2.Sum64()
   193  	if x != y {
   194  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   195  	}
   196  }
   197  
   198  func TestSeedFromReset(t *testing.T) {
   199  	h1 := new(Hash)
   200  	h1.WriteString("foo")
   201  	h1.Reset() // seed generated here
   202  	h1.WriteString("foo")
   203  	x := h1.Sum64()
   204  	h2 := new(Hash)
   205  	h2.SetSeed(h1.Seed())
   206  	h2.WriteString("foo")
   207  	y := h2.Sum64()
   208  	if x != y {
   209  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   210  	}
   211  }
   212  
   213  // Make sure a Hash implements the hash.Hash and hash.Hash64 interfaces.
   214  var _ hash.Hash = &Hash{}
   215  var _ hash.Hash64 = &Hash{}
   216  
   217  func benchmarkSize(b *testing.B, size int) {
   218  	h := &Hash{}
   219  	buf := make([]byte, size)
   220  	s := string(buf)
   221  
   222  	b.Run("Write", func(b *testing.B) {
   223  		b.SetBytes(int64(size))
   224  		for i := 0; i < b.N; i++ {
   225  			h.Reset()
   226  			h.Write(buf)
   227  			h.Sum64()
   228  		}
   229  	})
   230  
   231  	b.Run("Bytes", func(b *testing.B) {
   232  		b.SetBytes(int64(size))
   233  		seed := h.Seed()
   234  		for i := 0; i < b.N; i++ {
   235  			Bytes(seed, buf)
   236  		}
   237  	})
   238  
   239  	b.Run("String", func(b *testing.B) {
   240  		b.SetBytes(int64(size))
   241  		seed := h.Seed()
   242  		for i := 0; i < b.N; i++ {
   243  			String(seed, s)
   244  		}
   245  	})
   246  }
   247  
   248  func BenchmarkHash(b *testing.B) {
   249  	sizes := []int{4, 8, 16, 32, 64, 256, 320, 1024, 4096, 16384}
   250  	for _, size := range sizes {
   251  		b.Run(fmt.Sprint("n=", size), func(b *testing.B) {
   252  			benchmarkSize(b, size)
   253  		})
   254  	}
   255  }
   256  

View as plain text