map里面的key的hash是怎么实现的


源码：src/runtime/map.go
golang的map是内置关键字，不管是get还是set都需要通过key的hash找到对应的存储实体。具体的hash过程如下代码：

  1. type maptype struct {
  2.     typ        _type
  3.     key        *_type
  4.     elem       *_type
  5.     bucket     *_type // internal type representing a hash bucket
  6.     keysize    uint8  // size of key slot
  7.     elemsize   uint8  // size of elem slot
  8.     bucketsize uint16 // size of bucket
  9.     flags      uint32
  10. }
  12. //t *maptype
  13. alg := t.key.alg
  14. hash := alg.hash(key, uintptr(h.hash0))

这里其实就是拿到key对应的类型，然后获取当前key的类型的hash算法。然后调用hash函数。

hash函数的定义在这里：

  1. // typeAlg is also copied/used in reflect/type.go.
  2. // keep them in sync.
  3. type typeAlg struct {
  4.     // function for hashing objects of this type
  5.     // (ptr to object, seed) -> hash
  6.     hash func(unsafe.Pointer, uintptr) uintptr
  7.     // function for comparing objects of this type
  8.     // (ptr to object A, ptr to object B) -> ==?
  9.     equal func(unsafe.Pointer, unsafe.Pointer) bool
  10. }

可以知道，入参是指向key的指针，第二个参数是hash种子。

golang里面的对象的hash原理

golang里面每种数据类型的hash是与数据类型强相关的，并且是由编译器负责做类型绑定的。在src/runtime/alg.go 里面定义个一个map[type]typeAlg，用于表示每个数据类型对应的 typeAlg。

  1. var algarray = [alg_max]typeAlg{
  2.     alg_NOEQ:     {nil, nil},
  3.     alg_MEM0:     {memhash0, memequal0},
  4.     alg_MEM8:     {memhash8, memequal8},
  5.     alg_MEM16:    {memhash16, memequal16},
  6.     alg_MEM32:    {memhash32, memequal32},
  7.     alg_MEM64:    {memhash64, memequal64},
  8.     alg_MEM128:   {memhash128, memequal128},
  9.     alg_STRING:   {strhash, strequal},
  10.     alg_INTER:    {interhash, interequal},
  11.     alg_NILINTER: {nilinterhash, nilinterequal},
  12.     alg_FLOAT32:  {f32hash, f32equal},
  13.     alg_FLOAT64:  {f64hash, f64equal},
  14.     alg_CPLX64:   {c64hash, c64equal},
  15.     alg_CPLX128:  {c128hash, c128equal},
  16. }

上面的hash函数，最后实际上底层都会调用：func memhash(p unsafe.Pointer, seed, s uintptr) uintptr 函数。以strhash函数为例：

  1. func strhash(a unsafe.Pointer, h uintptr) uintptr {
  2.     x := (*stringStruct)(a)
  3.     return memhash(x.str, h, uintptr(x.len))
  4. }

下面看一下memhash函数, src/runtime/hash64.go

  1. // p表示需要hash的对象的地址
  2. // seed 是hash 种子，
  3. // s是需要hash的对象的字节数
  4. func memhash(p unsafe.Pointer, seed, s uintptr) uintptr {
  5.     if (GOARCH == "amd64" || GOARCH == "arm64") &&
  6.         GOOS != "nacl" && useAeshash {
  7.         return aeshash(p, seed, s)
  8.     }
  9.     h := uint64(seed + s*hashkey[0])
  10. tail:
  11.     switch {
  12.     case s == 0:
  13.     case s < 4:
  14.         h ^= uint64(*(*byte)(p))
  15.         h ^= uint64(*(*byte)(add(p, s>>1))) << 8
  16.         h ^= uint64(*(*byte)(add(p, s-1))) << 16
  17.         h = rotl_31(h*m1) * m2
  18.     case s <= 8:
  19.         h ^= uint64(readUnaligned32(p))
  20.         h ^= uint64(readUnaligned32(add(p, s-4))) << 32
  21.         h = rotl_31(h*m1) * m2
  22.     case s <= 16:
  23.         h ^= readUnaligned64(p)
  24.         h = rotl_31(h*m1) * m2
  25.         h ^= readUnaligned64(add(p, s-8))
  26.         h = rotl_31(h*m1) * m2
  27.     case s <= 32:
  28.         h ^= readUnaligned64(p)
  29.         h = rotl_31(h*m1) * m2
  30.         h ^= readUnaligned64(add(p, 8))
  31.         h = rotl_31(h*m1) * m2
  32.         h ^= readUnaligned64(add(p, s-16))
  33.         h = rotl_31(h*m1) * m2
  34.         h ^= readUnaligned64(add(p, s-8))
  35.         h = rotl_31(h*m1) * m2
  36.     default:
  37.         v1 := h
  38.         v2 := uint64(seed * hashkey[1])
  39.         v3 := uint64(seed * hashkey[2])
  40.         v4 := uint64(seed * hashkey[3])
  41.         for s >= 32 {
  42.             v1 ^= readUnaligned64(p)
  43.             v1 = rotl_31(v1*m1) * m2
  44.             p = add(p, 8)
  45.             v2 ^= readUnaligned64(p)
  46.             v2 = rotl_31(v2*m2) * m3
  47.             p = add(p, 8)
  48.             v3 ^= readUnaligned64(p)
  49.             v3 = rotl_31(v3*m3) * m4
  50.             p = add(p, 8)
  51.             v4 ^= readUnaligned64(p)
  52.             v4 = rotl_31(v4*m4) * m1
  53.             p = add(p, 8)
  54.             s -= 32
  55.         }
  56.         h = v1 ^ v2 ^ v3 ^ v4
  57.         goto tail
  58.     }
  60.     h ^= h >> 29
  61.     h *= m3
  62.     h ^= h >> 32
  63.     return uintptr(h)
  64. }


这个就是整体的hash实现。 对于amd64会使用汇编实现的aeshash函数计算hash。
具体aeshash实现，有兴趣可以看汇编：src/runtime/asm_amd64.s 里面的 runtime·aeshash 函数。

Hash 测试

下面以string作为key，来测试以下三种算法的性能：

  1. fnv算法
  2. memhash算法
  3. aeshash的汇编算法

fnv

测试背景：10000个uuid string;

  1. const LEN = 10000
  2. // the length of element is 36
  3. var keys [LEN][]byte
  5. func init(){
  6.     for i:=0; i<LEN; i++ {
  7.         k := uuid.New().String()
  8.         keys[i] = []byte(k)
  9.     }
  10. }
  12. // 777000ns
  13. func main(){
  14.     start := time.Now().UnixNano()
  15.     for _, k := range keys {
  16.         h := fnv.New64()
  17.         h.Write(k)
  18.         h.Sum64()
  19.     }
  20.     end := time.Now().UnixNano()
  21.     fmt.Println("total time:", end-start, "ns")
  22. }

执行结果：10000次hash大约是727000ns，也就是平均每次hash要花费72ns。

memhash

这个是调用golang runtime里面的内嵌hash代码，这部分是我从runtime里面copy出来的。
代码如下：

  1. package main
  3. const LEN = 10000
  4. // the length of element is 36
  5. var keys [LEN]string
  7. func init(){
  8.     for i:=0; i<LEN; i++ {
  9.         keys[i] = uuid.New().String()
  10.     }
  11. }
  12. // 178000ns
  13. func main()  {
  14.     start := time.Now().UnixNano()
  15.     for _, k := range keys {
  16.         memhash(unsafe.Pointer(&k), 1, 36)
  17.     }
  18.     end := time.Now().UnixNano()
  19.     fmt.Println("total time:", end-start, "ns")
  20. }
  22. // used in hash{32,64}.go to seed the hash function
  23. var hashkey [4]uintptr
  24. const PtrSize = 4 << (^uintptr(0) >> 63)
  25. func init()  {
  26.     for i:=0; i<4; i++ {
  27.         hashkey[i]= uintptr(rand.Int63())
  28.     }
  29.     hashkey[0] |= 1 // make sure these numbers are odd
  30.     hashkey[1] |= 1
  31.     hashkey[2] |= 1
  32.     hashkey[3] |= 1
  33. }
  34. func add(p unsafe.Pointer, x uintptr) unsafe.Pointer {
  35.     return unsafe.Pointer(uintptr(p) + x)
  36. }
  37. func rotl_31(x uint64) uint64 {
  38.     return (x << 31) | (x >> (64 - 31))
  39. }
  41. const (
  42.     // Constants for multiplication: four random odd 64-bit numbers.
  43.     m1 = 16877499708836156737
  44.     m2 = 2820277070424839065
  45.     m3 = 9497967016996688599
  46.     m4 = 15839092249703872147
  47. )
  49. const (
  50.     BigEndian           = false
  51.     DefaultPhysPageSize = 4096
  52.     PCQuantum           = 1
  53.     Int64Align          = 8
  54.     MinFrameSize        = 0
  55. )
  57. func readUnaligned64(p unsafe.Pointer) uint64 {
  58.     q := (*[8]byte)(p)
  59.     if BigEndian {
  60.         return uint64(q[7]) | uint64(q[6])<<8 | uint64(q[5])<<16 | uint64(q[4])<<24 |
  61.             uint64(q[3])<<32 | uint64(q[2])<<40 | uint64(q[1])<<48 | uint64(q[0])<<56
  62.     }
  63.     return uint64(q[0]) | uint64(q[1])<<8 | uint64(q[2])<<16 | uint64(q[3])<<24 | uint64(q[4])<<32 | uint64(q[5])<<40 | uint64(q[6])<<48 | uint64(q[7])<<56
  64. }
  66. // Note: These routines perform the read with an native endianness.
  67. func readUnaligned32(p unsafe.Pointer) uint32 {
  68.     q := (*[4]byte)(p)
  69.     if BigEndian {
  70.         return uint32(q[3]) | uint32(q[2])<<8 | uint32(q[1])<<16 | uint32(q[0])<<24
  71.     }
  72.     return uint32(q[0]) | uint32(q[1])<<8 | uint32(q[2])<<16 | uint32(q[3])<<24
  73. }
  75. func memhash(p unsafe.Pointer, seed, s uintptr) uintptr {
  76.     h := uint64(seed + s*hashkey[0])
  77. tail:
  78.     switch {
  79.     case s == 0:
  80.     case s < 4:
  81.         h ^= uint64(*(*byte)(p))
  82.         h ^= uint64(*(*byte)(add(p, s>>1))) << 8
  83.         h ^= uint64(*(*byte)(add(p, s-1))) << 16
  84.         h = rotl_31(h*m1) * m2
  85.     case s <= 8:
  86.         h ^= uint64(readUnaligned32(p))
  87.         h ^= uint64(readUnaligned32(add(p, s-4))) << 32
  88.         h = rotl_31(h*m1) * m2
  89.     case s <= 16:
  90.         h ^= readUnaligned64(p)
  91.         h = rotl_31(h*m1) * m2
  92.         h ^= readUnaligned64(add(p, s-8))
  93.         h = rotl_31(h*m1) * m2
  94.     case s <= 32:
  95.         h ^= readUnaligned64(p)
  96.         h = rotl_31(h*m1) * m2
  97.         h ^= readUnaligned64(add(p, 8))
  98.         h = rotl_31(h*m1) * m2
  99.         h ^= readUnaligned64(add(p, s-16))
  100.         h = rotl_31(h*m1) * m2
  101.         h ^= readUnaligned64(add(p, s-8))
  102.         h = rotl_31(h*m1) * m2
  103.     default:
  104.         v1 := h
  105.         v2 := uint64(seed * hashkey[1])
  106.         v3 := uint64(seed * hashkey[2])
  107.         v4 := uint64(seed * hashkey[3])
  108.         for s >= 32 {
  109.             v1 ^= readUnaligned64(p)
  110.             v1 = rotl_31(v1*m1) * m2
  111.             p = add(p, 8)
  112.             v2 ^= readUnaligned64(p)
  113.             v2 = rotl_31(v2*m2) * m3
  114.             p = add(p, 8)
  115.             v3 ^= readUnaligned64(p)
  116.             v3 = rotl_31(v3*m3) * m4
  117.             p = add(p, 8)
  118.             v4 ^= readUnaligned64(p)
  119.             v4 = rotl_31(v4*m4) * m1
  120.             p = add(p, 8)
  121.             s -= 32
  122.         }
  123.         h = v1 ^ v2 ^ v3 ^ v4
  124.         goto tail
  125.     }
  127.     h ^= h >> 29
  128.     h *= m3
  129.     h ^= h >> 32
  130.     return uintptr(h)
  131. }


执行结果：10000次hash大约是178000ns，也就是平均每次hash要花费17.8ns。

aeshash汇编

这部分代码也是从runtime asm代码copy出来做测试：
注意，需要把src/runtime/go_tls.h、funcdata.h、textflag.h 这个三个头文件放在当前目录下。

  1. // Copyright 2009 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.
  5. #include "go_asm.h"
  6. #include "go_tls.h"
  7. #include "funcdata.h"
  8. #include "textflag.h"
  10. //louyuting
  11. // func aeshashstr(p unsafe.Pointer, h uintptr) uintptr
  12. TEXT ·aeshashstr2(SB),NOSPLIT,$0-24
  13.     MOVQ    p+0(FP), AX    // ptr to string struct
  14.     MOVQ    8(AX), CX    // length of string
  15.     MOVQ    (AX), AX    // string data
  16.     LEAQ    ret+16(FP), DX
  17.     JMP    aeshashbody<>(SB)
  19. // AX: data
  20. // CX: length
  21. // DX: address to put return value
  22. TEXT aeshashbody<>(SB),NOSPLIT,$0-0
  23.     // Fill an SSE register with our seeds.
  24.     MOVQ    h+8(FP), X0            // 64 bits of per-table hash seed
  25.     PINSRW    $4, CX, X0            // 16 bits of length
  26.     PSHUFHW $0, X0, X0            // repeat length 4 times total
  27.     MOVO    X0, X1                // save unscrambled seed
  28.     PXOR    main·aeskeysched(SB), X0    // xor in per-process seed
  29.     AESENC    X0, X0                // scramble seed
  31.     CMPQ    CX, $16
  32.     JB    aes0to15
  33.     JE    aes16
  34.     CMPQ    CX, $32
  35.     JBE    aes17to32
  36.     CMPQ    CX, $64
  37.     JBE    aes33to64
  38.     CMPQ    CX, $128
  39.     JBE    aes65to128
  40.     JMP    aes129plus
  42. aes0to15:
  43.     TESTQ    CX, CX
  44.     JE    aes0
  46.     ADDQ    $16, AX
  47.     TESTW    $0xff0, AX
  48.     JE    endofpage
  50.     // 16 bytes loaded at this address won't cross
  51.     // a page boundary, so we can load it directly.
  52.     MOVOU    -16(AX), X1
  53.     ADDQ    CX, CX
  54.     MOVQ    $masks<>(SB), AX
  55.     PAND    (AX)(CX*8), X1
  56. final1:
  57.     PXOR    X0, X1    // xor data with seed
  58.     AESENC    X1, X1    // scramble combo 3 times
  59.     AESENC    X1, X1
  60.     AESENC    X1, X1
  61.     MOVQ    X1, (DX)
  62.     RET
  64. endofpage:
  65.     // address ends in 1111xxxx. Might be up against
  66.     // a page boundary, so load ending at last byte.
  67.     // Then shift bytes down using pshufb.
  68.     MOVOU    -32(AX)(CX*1), X1
  69.     ADDQ    CX, CX
  70.     MOVQ    $shifts<>(SB), AX
  71.     PSHUFB    (AX)(CX*8), X1
  72.     JMP    final1
  74. aes0:
  75.     // Return scrambled input seed
  76.     AESENC    X0, X0
  77.     MOVQ    X0, (DX)
  78.     RET
  80. aes16:
  81.     MOVOU    (AX), X1
  82.     JMP    final1
  84. aes17to32:
  85.     // make second starting seed
  86.     PXOR    main·aeskeysched+16(SB), X1
  87.     AESENC    X1, X1
  89.     // load data to be hashed
  90.     MOVOU    (AX), X2
  91.     MOVOU    -16(AX)(CX*1), X3
  93.     // xor with seed
  94.     PXOR    X0, X2
  95.     PXOR    X1, X3
  97.     // scramble 3 times
  98.     AESENC    X2, X2
  99.     AESENC    X3, X3
  100.     AESENC    X2, X2
  101.     AESENC    X3, X3
  102.     AESENC    X2, X2
  103.     AESENC    X3, X3
  105.     // combine results
  106.     PXOR    X3, X2
  107.     MOVQ    X2, (DX)
  108.     RET
  110. aes33to64:
  111.     // make 3 more starting seeds
  112.     MOVO    X1, X2
  113.     MOVO    X1, X3
  114.     PXOR    main·aeskeysched+16(SB), X1
  115.     PXOR    main·aeskeysched+32(SB), X2
  116.     PXOR    main·aeskeysched+48(SB), X3
  117.     AESENC    X1, X1
  118.     AESENC    X2, X2
  119.     AESENC    X3, X3
  121.     MOVOU    (AX), X4
  122.     MOVOU    16(AX), X5
  123.     MOVOU    -32(AX)(CX*1), X6
  124.     MOVOU    -16(AX)(CX*1), X7
  126.     PXOR    X0, X4
  127.     PXOR    X1, X5
  128.     PXOR    X2, X6
  129.     PXOR    X3, X7
  131.     AESENC    X4, X4
  132.     AESENC    X5, X5
  133.     AESENC    X6, X6
  134.     AESENC    X7, X7
  136.     AESENC    X4, X4
  137.     AESENC    X5, X5
  138.     AESENC    X6, X6
  139.     AESENC    X7, X7
  141.     AESENC    X4, X4
  142.     AESENC    X5, X5
  143.     AESENC    X6, X6
  144.     AESENC    X7, X7
  146.     PXOR    X6, X4
  147.     PXOR    X7, X5
  148.     PXOR    X5, X4
  149.     MOVQ    X4, (DX)
  150.     RET
  152. aes65to128:
  153.     // make 7 more starting seeds
  154.     MOVO    X1, X2
  155.     MOVO    X1, X3
  156.     MOVO    X1, X4
  157.     MOVO    X1, X5
  158.     MOVO    X1, X6
  159.     MOVO    X1, X7
  160.     PXOR    main·aeskeysched+16(SB), X1
  161.     PXOR    main·aeskeysched+32(SB), X2
  162.     PXOR    main·aeskeysched+48(SB), X3
  163.     PXOR    main·aeskeysched+64(SB), X4
  164.     PXOR    main·aeskeysched+80(SB), X5
  165.     PXOR    main·aeskeysched+96(SB), X6
  166.     PXOR    main·aeskeysched+112(SB), X7
  167.     AESENC    X1, X1
  168.     AESENC    X2, X2
  169.     AESENC    X3, X3
  170.     AESENC    X4, X4
  171.     AESENC    X5, X5
  172.     AESENC    X6, X6
  173.     AESENC    X7, X7
  175.     // load data
  176.     MOVOU    (AX), X8
  177.     MOVOU    16(AX), X9
  178.     MOVOU    32(AX), X10
  179.     MOVOU    48(AX), X11
  180.     MOVOU    -64(AX)(CX*1), X12
  181.     MOVOU    -48(AX)(CX*1), X13
  182.     MOVOU    -32(AX)(CX*1), X14
  183.     MOVOU    -16(AX)(CX*1), X15
  185.     // xor with seed
  186.     PXOR    X0, X8
  187.     PXOR    X1, X9
  188.     PXOR    X2, X10
  189.     PXOR    X3, X11
  190.     PXOR    X4, X12
  191.     PXOR    X5, X13
  192.     PXOR    X6, X14
  193.     PXOR    X7, X15
  195.     // scramble 3 times
  196.     AESENC    X8, X8
  197.     AESENC    X9, X9
  198.     AESENC    X10, X10
  199.     AESENC    X11, X11
  200.     AESENC    X12, X12
  201.     AESENC    X13, X13
  202.     AESENC    X14, X14
  203.     AESENC    X15, X15
  205.     AESENC    X8, X8
  206.     AESENC    X9, X9
  207.     AESENC    X10, X10
  208.     AESENC    X11, X11
  209.     AESENC    X12, X12
  210.     AESENC    X13, X13
  211.     AESENC    X14, X14
  212.     AESENC    X15, X15
  214.     AESENC    X8, X8
  215.     AESENC    X9, X9
  216.     AESENC    X10, X10
  217.     AESENC    X11, X11
  218.     AESENC    X12, X12
  219.     AESENC    X13, X13
  220.     AESENC    X14, X14
  221.     AESENC    X15, X15
  223.     // combine results
  224.     PXOR    X12, X8
  225.     PXOR    X13, X9
  226.     PXOR    X14, X10
  227.     PXOR    X15, X11
  228.     PXOR    X10, X8
  229.     PXOR    X11, X9
  230.     PXOR    X9, X8
  231.     MOVQ    X8, (DX)
  232.     RET
  234. aes129plus:
  235.     // make 7 more starting seeds
  236.     MOVO    X1, X2
  237.     MOVO    X1, X3
  238.     MOVO    X1, X4
  239.     MOVO    X1, X5
  240.     MOVO    X1, X6
  241.     MOVO    X1, X7
  242.     PXOR    main·aeskeysched+16(SB), X1
  243.     PXOR    main·aeskeysched+32(SB), X2
  244.     PXOR    main·aeskeysched+48(SB), X3
  245.     PXOR    main·aeskeysched+64(SB), X4
  246.     PXOR    main·aeskeysched+80(SB), X5
  247.     PXOR    main·aeskeysched+96(SB), X6
  248.     PXOR    main·aeskeysched+112(SB), X7
  249.     AESENC    X1, X1
  250.     AESENC    X2, X2
  251.     AESENC    X3, X3
  252.     AESENC    X4, X4
  253.     AESENC    X5, X5
  254.     AESENC    X6, X6
  255.     AESENC    X7, X7
  257.     // start with last (possibly overlapping) block
  258.     MOVOU    -128(AX)(CX*1), X8
  259.     MOVOU    -112(AX)(CX*1), X9
  260.     MOVOU    -96(AX)(CX*1), X10
  261.     MOVOU    -80(AX)(CX*1), X11
  262.     MOVOU    -64(AX)(CX*1), X12
  263.     MOVOU    -48(AX)(CX*1), X13
  264.     MOVOU    -32(AX)(CX*1), X14
  265.     MOVOU    -16(AX)(CX*1), X15
  267.     // xor in seed
  268.     PXOR    X0, X8
  269.     PXOR    X1, X9
  270.     PXOR    X2, X10
  271.     PXOR    X3, X11
  272.     PXOR    X4, X12
  273.     PXOR    X5, X13
  274.     PXOR    X6, X14
  275.     PXOR    X7, X15
  277.     // compute number of remaining 128-byte blocks
  278.     DECQ    CX
  279.     SHRQ    $7, CX
  281. aesloop:
  282.     // scramble state
  283.     AESENC    X8, X8
  284.     AESENC    X9, X9
  285.     AESENC    X10, X10
  286.     AESENC    X11, X11
  287.     AESENC    X12, X12
  288.     AESENC    X13, X13
  289.     AESENC    X14, X14
  290.     AESENC    X15, X15
  292.     // scramble state, xor in a block
  293.     MOVOU    (AX), X0
  294.     MOVOU    16(AX), X1
  295.     MOVOU    32(AX), X2
  296.     MOVOU    48(AX), X3
  297.     AESENC    X0, X8
  298.     AESENC    X1, X9
  299.     AESENC    X2, X10
  300.     AESENC    X3, X11
  301.     MOVOU    64(AX), X4
  302.     MOVOU    80(AX), X5
  303.     MOVOU    96(AX), X6
  304.     MOVOU    112(AX), X7
  305.     AESENC    X4, X12
  306.     AESENC    X5, X13
  307.     AESENC    X6, X14
  308.     AESENC    X7, X15
  310.     ADDQ    $128, AX
  311.     DECQ    CX
  312.     JNE    aesloop
  314.     // 3 more scrambles to finish
  315.     AESENC    X8, X8
  316.     AESENC    X9, X9
  317.     AESENC    X10, X10
  318.     AESENC    X11, X11
  319.     AESENC    X12, X12
  320.     AESENC    X13, X13
  321.     AESENC    X14, X14
  322.     AESENC    X15, X15
  323.     AESENC    X8, X8
  324.     AESENC    X9, X9
  325.     AESENC    X10, X10
  326.     AESENC    X11, X11
  327.     AESENC    X12, X12
  328.     AESENC    X13, X13
  329.     AESENC    X14, X14
  330.     AESENC    X15, X15
  331.     AESENC    X8, X8
  332.     AESENC    X9, X9
  333.     AESENC    X10, X10
  334.     AESENC    X11, X11
  335.     AESENC    X12, X12
  336.     AESENC    X13, X13
  337.     AESENC    X14, X14
  338.     AESENC    X15, X15
  340.     PXOR    X12, X8
  341.     PXOR    X13, X9
  342.     PXOR    X14, X10
  343.     PXOR    X15, X11
  344.     PXOR    X10, X8
  345.     PXOR    X11, X9
  346.     PXOR    X9, X8
  347.     MOVQ    X8, (DX)
  348.     RET
  351. // simple mask to get rid of data in the high part of the register.
  352. DATA masks<>+0x00(SB)/8, $0x0000000000000000
  353. DATA masks<>+0x08(SB)/8, $0x0000000000000000
  354. DATA masks<>+0x10(SB)/8, $0x00000000000000ff
  355. DATA masks<>+0x18(SB)/8, $0x0000000000000000
  356. DATA masks<>+0x20(SB)/8, $0x000000000000ffff
  357. DATA masks<>+0x28(SB)/8, $0x0000000000000000
  358. DATA masks<>+0x30(SB)/8, $0x0000000000ffffff
  359. DATA masks<>+0x38(SB)/8, $0x0000000000000000
  360. DATA masks<>+0x40(SB)/8, $0x00000000ffffffff
  361. DATA masks<>+0x48(SB)/8, $0x0000000000000000
  362. DATA masks<>+0x50(SB)/8, $0x000000ffffffffff
  363. DATA masks<>+0x58(SB)/8, $0x0000000000000000
  364. DATA masks<>+0x60(SB)/8, $0x0000ffffffffffff
  365. DATA masks<>+0x68(SB)/8, $0x0000000000000000
  366. DATA masks<>+0x70(SB)/8, $0x00ffffffffffffff
  367. DATA masks<>+0x78(SB)/8, $0x0000000000000000
  368. DATA masks<>+0x80(SB)/8, $0xffffffffffffffff
  369. DATA masks<>+0x88(SB)/8, $0x0000000000000000
  370. DATA masks<>+0x90(SB)/8, $0xffffffffffffffff
  371. DATA masks<>+0x98(SB)/8, $0x00000000000000ff
  372. DATA masks<>+0xa0(SB)/8, $0xffffffffffffffff
  373. DATA masks<>+0xa8(SB)/8, $0x000000000000ffff
  374. DATA masks<>+0xb0(SB)/8, $0xffffffffffffffff
  375. DATA masks<>+0xb8(SB)/8, $0x0000000000ffffff
  376. DATA masks<>+0xc0(SB)/8, $0xffffffffffffffff
  377. DATA masks<>+0xc8(SB)/8, $0x00000000ffffffff
  378. DATA masks<>+0xd0(SB)/8, $0xffffffffffffffff
  379. DATA masks<>+0xd8(SB)/8, $0x000000ffffffffff
  380. DATA masks<>+0xe0(SB)/8, $0xffffffffffffffff
  381. DATA masks<>+0xe8(SB)/8, $0x0000ffffffffffff
  382. DATA masks<>+0xf0(SB)/8, $0xffffffffffffffff
  383. DATA masks<>+0xf8(SB)/8, $0x00ffffffffffffff
  384. GLOBL masks<>(SB),RODATA,$256
  386. // func checkASM() bool
  387. TEXT ·checkASM(SB),NOSPLIT,$0-1
  388.     // check that masks<>(SB) and shifts<>(SB) are aligned to 16-byte
  389.     MOVQ    $masks<>(SB), AX
  390.     MOVQ    $shifts<>(SB), BX
  391.     ORQ    BX, AX
  392.     TESTQ    $15, AX
  393.     SETEQ    ret+0(FP)
  394.     RET
  396. // these are arguments to pshufb. They move data down from
  397. // the high bytes of the register to the low bytes of the register.
  398. // index is how many bytes to move.
  399. DATA shifts<>+0x00(SB)/8, $0x0000000000000000
  400. DATA shifts<>+0x08(SB)/8, $0x0000000000000000
  401. DATA shifts<>+0x10(SB)/8, $0xffffffffffffff0f
  402. DATA shifts<>+0x18(SB)/8, $0xffffffffffffffff
  403. DATA shifts<>+0x20(SB)/8, $0xffffffffffff0f0e
  404. DATA shifts<>+0x28(SB)/8, $0xffffffffffffffff
  405. DATA shifts<>+0x30(SB)/8, $0xffffffffff0f0e0d
  406. DATA shifts<>+0x38(SB)/8, $0xffffffffffffffff
  407. DATA shifts<>+0x40(SB)/8, $0xffffffff0f0e0d0c
  408. DATA shifts<>+0x48(SB)/8, $0xffffffffffffffff
  409. DATA shifts<>+0x50(SB)/8, $0xffffff0f0e0d0c0b
  410. DATA shifts<>+0x58(SB)/8, $0xffffffffffffffff
  411. DATA shifts<>+0x60(SB)/8, $0xffff0f0e0d0c0b0a
  412. DATA shifts<>+0x68(SB)/8, $0xffffffffffffffff
  413. DATA shifts<>+0x70(SB)/8, $0xff0f0e0d0c0b0a09
  414. DATA shifts<>+0x78(SB)/8, $0xffffffffffffffff
  415. DATA shifts<>+0x80(SB)/8, $0x0f0e0d0c0b0a0908
  416. DATA shifts<>+0x88(SB)/8, $0xffffffffffffffff
  417. DATA shifts<>+0x90(SB)/8, $0x0e0d0c0b0a090807
  418. DATA shifts<>+0x98(SB)/8, $0xffffffffffffff0f
  419. DATA shifts<>+0xa0(SB)/8, $0x0d0c0b0a09080706
  420. DATA shifts<>+0xa8(SB)/8, $0xffffffffffff0f0e
  421. DATA shifts<>+0xb0(SB)/8, $0x0c0b0a0908070605
  422. DATA shifts<>+0xb8(SB)/8, $0xffffffffff0f0e0d
  423. DATA shifts<>+0xc0(SB)/8, $0x0b0a090807060504
  424. DATA shifts<>+0xc8(SB)/8, $0xffffffff0f0e0d0c
  425. DATA shifts<>+0xd0(SB)/8, $0x0a09080706050403
  426. DATA shifts<>+0xd8(SB)/8, $0xffffff0f0e0d0c0b
  427. DATA shifts<>+0xe0(SB)/8, $0x0908070605040302
  428. DATA shifts<>+0xe8(SB)/8, $0xffff0f0e0d0c0b0a
  429. DATA shifts<>+0xf0(SB)/8, $0x0807060504030201
  430. DATA shifts<>+0xf8(SB)/8, $0xff0f0e0d0c0b0a09
  431. GLOBL shifts<>(SB),RODATA,$256

测试结果来看，10000个记录，大概也是182000ns, 每次大概是18.2ns。

总结：

算法 per hash cost
fnv 72ns
memhash 17.8ns
aeshash 汇编 18.2ns

从测试来看，memhash的hash和aeshash性能差不多，但是比fnv就要好很多了。

转自：https://blog.csdn.net/u010853261/article/details/104148615