hash - Go:为什么我的哈希表实现这么慢？

Question

所以我正在尝试制作一个超轻量级、故意占用大量内存但非常快速的哈希表，用于非常快速的查找，我不关心内存使用情况，也不关心它是否会犯罕见的错误。

基本上它只是创建一个巨大的数组(是数组，不是 slice )，使用修改后的 FNVa 散列(修改为仅给出数组边界内的散列)对字符串进行散列，然后使用散列保存或查找值作为数组索引。理论上，这应该是存储和检索键=>值对的最快方法。

这是我的基准:

package main
import (
"fmt"
"time"
)

const dicsize250 = 2097152000 // tested 115 collisions

type Dictionary250_uint16 struct {
  dictionary [dicsize250]uint16
}

func (d *Dictionary250_uint16) Add(s string, v uint16) {
    i := id(s,dicsize250)
    d.dictionary[i]=v
    return
}

func (d *Dictionary250_uint16) Delete(s string) {
    i := id(s,dicsize250)
    d.dictionary[i]=0
    return
}

func (d *Dictionary250_uint16) Exists(s string) bool {
    i := id(s,dicsize250)
    if d.dictionary[i]==0 {
        return false
        } else {
        return true
    }
}

func (d *Dictionary250_uint16) Find(s string) uint16 {
    i := id(s,dicsize250)
    return d.dictionary[i]
}

// This is a FNVa hash algorithm, modified to limit to dicsize
func id(s string, dicsize uint64) uint64 {
    var hash uint64 = 2166136261
    for _, c := range s {
        hash = (hash^uint64(c))*16777619
    }
    return hash%dicsize
}

var donothing bool
func main() {

dic := new(Dictionary250_uint16)
dic.Add(`test1`,10)
dic.Add(`test2`,20)
dic.Add(`test3`,30)
dic.Add(`test4`,40)
dic.Add(`test5`,50)

mc := make(map[string]uint16)
mc[`test1`]=10
mc[`test2`]=10
mc[`test3`]=10
mc[`test4`]=10
mc[`test5`]=10

var t1 uint
var t2 uint
var t3 uint
donothing = true

// Dic hit
t1 = uint(time.Now().UnixNano())
for i:=0; i<50000000; i++ {
        if dic.Exists(`test4`) {
            donothing = true
        }
}
t3 = uint(time.Now().UnixNano())
t2 = t3-t1
fmt.Println("Dic (hit) took ",t2)

// Dic miss
t1 = uint(time.Now().UnixNano())
for i:=0; i<50000000; i++ {
        if dic.Exists(`whate`) {
            donothing = true
        }
}
t3 = uint(time.Now().UnixNano())
t2 = t3-t1
fmt.Println("Dic (miss) took ",t2)

// Map hit
t1 = uint(time.Now().UnixNano())
for i:=0; i<50000000; i++ {
    _,ok := mc[`test4`]
    if ok {
        donothing=true
        }
}
t3 = uint(time.Now().UnixNano())
t2 = t3-t1
fmt.Println("Map (hit) took ",t2)

// Map miss
t1 = uint(time.Now().UnixNano())
for i:=0; i<50000000; i++ {
    _,ok := mc[`whate`]
    if ok {
        donothing=true
        }
}
t3 = uint(time.Now().UnixNano())
t2 = t3-t1
fmt.Println("Map (miss) took ",t2)

donothing = false
}

我得到的结果是:

Dic (hit) took  2,858,604,059
Dic (miss) took  2,457,173,526
Map (hit) took  1,574,306,146
Map (miss) took  2,525,206,080

基本上，我的哈希表实现比仅使用 map 要慢很多，尤其是在命中方面。我看不出这是怎么可能的，因为 map 是一个繁重的实现(相比之下)，它从来没有发生过任何碰撞，并且进行了更多的计算。而我的实现非常简单，并且依赖于拥有大量所有可能的索引。

我做错了什么？

Answer 1

一方面，与内置 map 相比，您使用的内存量非常大，但这是您提到的想要做出的权衡。

使用标准库基准实用程序。它将为您提供坚实的工作基础、更轻松的分析访问并消除大量猜测。我有时间将您的一些代码剪切并粘贴到基准测试中:

func BenchmarkDictHit(b *testing.B) {
    donothing = true

    dic := new(Dictionary250_uint16)
    dic.Add(`test1`, 10)
    dic.Add(`test2`, 20)
    dic.Add(`test3`, 30)
    dic.Add(`test4`, 40)
    dic.Add(`test5`, 50)

    // The initial Dict allocation is very expensive!
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        if dic.Exists(`test4`) {
            donothing = true
        }
    }
}

func BenchmarkDictMiss(b *testing.B) {
    donothing = true

    dic := new(Dictionary250_uint16)
    dic.Add(`test1`, 10)
    dic.Add(`test2`, 20)
    dic.Add(`test3`, 30)
    dic.Add(`test4`, 40)
    dic.Add(`test5`, 50)

    // The initial Dict allocation is very expensive!
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        if dic.Exists(`test6`) {
            donothing = true
        }
    }
}

func BenchmarkMapHit(b *testing.B) {
    donothing = true
    mc := make(map[string]uint16)
    mc[`test1`] = 10
    mc[`test2`] = 10
    mc[`test3`] = 10
    mc[`test4`] = 10
    mc[`test5`] = 10

    b.ResetTimer()

    // Map hit
    for i := 0; i < b.N; i++ {
        _, ok := mc[`test4`]
        if ok {
            donothing = true
        }
    }

    donothing = false
}
func BenchmarkMapMiss(b *testing.B) {
    donothing = true
    mc := make(map[string]uint16)
    mc[`test1`] = 10
    mc[`test2`] = 10
    mc[`test3`] = 10
    mc[`test4`] = 10
    mc[`test5`] = 10

    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        _, ok := mc[`test6`]
        if ok {
            donothing = true
        }
    }
    donothing = false
}

如果没有 ResetTimer() 调用，支持 slice 的初始分配将主导基准测试时间，即使在运行中分摊，它也会严重扭曲结果。重置后，基准时间看起来是有序的:

BenchmarkDictHit    50000000            39.6 ns/op         0 B/op          0 allocs/op
BenchmarkDictMiss   50000000            39.1 ns/op         0 B/op          0 allocs/op
BenchmarkMapHit 100000000           22.9 ns/op         0 B/op          0 allocs/op
BenchmarkMapMiss    50000000            36.8 ns/op         0 B/op          0 allocs/op

您的 id 函数需要遍历一个字符串。对于字符串，范围不会迭代字节，它会寻找会更昂贵的 rune 。您将希望直接索引字符串，或者可能在整个过程中使用 []byte (在成本方面大致相同)。通过更好的字符串处理，这些是我测试的最终时间。

BenchmarkDictHit    100000000           17.8 ns/op         0 B/op          0 allocs/op
BenchmarkDictMiss   100000000           17.2 ns/op         0 B/op          0 allocs/op