murmurhash3.go raw

   1  package bloom
   2  
   3  import (
   4  	"encoding/binary"
   5  )
   6  
   7  // The following constants are used by the MurmurHash3 algorithm.
   8  const (
   9  	murmurC1 = 0xcc9e2d51
  10  	murmurC2 = 0x1b873593
  11  	murmurR1 = 15
  12  	murmurR2 = 13
  13  	murmurM  = 5
  14  	murmurN  = 0xe6546b64
  15  )
  16  
  17  // MurmurHash3 implements a non-cryptographic hash function using the MurmurHash3 algorithm. This implementation yields
  18  // a 32-bit hash value which is suitable for general hash-based lookups. The seed can be used to effectively randomize
  19  // the hash function. This makes it ideal for use in bloom filters which need multiple independent hash functions.
  20  func MurmurHash3(seed uint32, data []byte) uint32 {
  21  	dataLen := uint32(len(data))
  22  	hash := seed
  23  	k := uint32(0)
  24  	numBlocks := dataLen / 4
  25  	// Calculate the hash in 4-byte chunks.
  26  	for i := uint32(0); i < numBlocks; i++ {
  27  		k = binary.LittleEndian.Uint32(data[i*4:])
  28  		k *= murmurC1
  29  		k = (k << murmurR1) | (k >> (32 - murmurR1))
  30  		k *= murmurC2
  31  		hash ^= k
  32  		hash = (hash << murmurR2) | (hash >> (32 - murmurR2))
  33  		hash = hash*murmurM + murmurN
  34  	}
  35  	// Handle remaining bytes.
  36  	tailIdx := numBlocks * 4
  37  	k = 0
  38  	switch dataLen & 3 {
  39  	case 3:
  40  		k ^= uint32(data[tailIdx+2]) << 16
  41  		fallthrough
  42  	case 2:
  43  		k ^= uint32(data[tailIdx+1]) << 8
  44  		fallthrough
  45  	case 1:
  46  		k ^= uint32(data[tailIdx])
  47  		k *= murmurC1
  48  		k = (k << murmurR1) | (k >> (32 - murmurR1))
  49  		k *= murmurC2
  50  		hash ^= k
  51  	}
  52  	// Finalization.
  53  	hash ^= dataLen
  54  	hash ^= hash >> 16
  55  	hash *= 0x85ebca6b
  56  	hash ^= hash >> 13
  57  	hash *= 0xc2b2ae35
  58  	hash ^= hash >> 16
  59  	return hash
  60  }
  61