goalng中slice的查询速度比map要快这是真的吗？

在go中map的底层实现是hash-table，那么很容易知道hash的查找value的时间复杂度是O(1),那么为什么说slice的速度要比map要快呢，我们暂且不说这个结论正确与否，我们可以写一个测试代码来观测结果，再从结果反推这个结论是否成立，或者所在什么条件是成立的，闲言碎语不多所了。

测试代码：

package svsm
import (
    "testing"
)
var rootsValid = []string{"foo", "bar", "qwe", "asd"}
var void struct{}
var rootsValid2 = map[string]struct{}{"foo": void, "bar": void, "qwe": void, "asd": void}
// uses a slice
func BenchmarkSearch1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, v := range rootsValid {
            if v == "/ja" {
                break
            }
        }
    }
}
// uses a map
func BenchmarkSearch2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        if _, ok := rootsValid2["/ja"]; ok {
            continue
        }
    }
}

output:

测试结果确实说明map的查询速度比slice要慢，那么是不是可以，我们也说归并排序的速度比插入排序要慢呢，程序员同志显然是要大喊一声，Are you fucking kidding?
显然事情的本质时根算法的符号表达式有关，才会给人造成一种如此的错觉。

people often forget that O(1) doesn't mean instant, it just means unrelated to the size of the dataset. For a small enough dataset, O(N) linear search with a low per-element cost will beat out an O(1) hashmap lookup with a high one-time cost (hashing and random memory access).

上面这段话其实很清楚的说明了为什么这样了。讲到此处，还有一点要讲，比如在go中排序的算法中有提到一句，它会自己选择调用的排序算法，具体是什么我们是不知道的，比如依据经验公式 n<=35 使用插入（O(n^2)是比快速排序（nlogn）要快的

one more thing. 势必要给出一个规模大一些的证明map的搜索是比slice要快的例子。

package svsm
import (
    "testing"
)
var rootsValid = []string{"foo", "bar", "qwe", "asd", "a", "b", "c", "d", "e", "f", "g", "h",
    "i", "j", "k", "l", "m", "n", "o", "p", "q", "x", "y", "z",
    "1", "2", "3", "4", "5", "6", "7", "8", "9", "10",
}
var void struct{}
var rootsValid2 = map[string]struct{}{"foo": void, "bar": void, "qwe": void, "asd": void,
    "a": void, "b": void, "c": void, "d": void, "e": void, "f": void, "g": void, "h": void,
    "i": void, "j": void, "l": void, "m": void, "n": void, "o": void, "p": void, "q": void, "k": void, "x": void, "y": void, "z": void,
    "1": void, "2": void, "3": void, "4": void, "5": void, "6": void, "7": void, "8": void, "9": void, "10": void,
}
// uses a slice
func BenchmarkSearch1(b *testing.B) {
    for i := 0; i < b.N; i++ {
        for _, v := range rootsValid {
            if v == "/ja" {
                break
            }
        }
    }
}
// uses a map
func BenchmarkSearch2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        if _, ok := rootsValid2["/ja"]; ok {
            continue
        }
    }
}

output:

时间草图（修正图中右下要写的是O(nlogn,😄😄😄😄）

总结：我们可以这样说在某一个点的时候slice时比map快的，因为在小数据的时候，比较的次数少，直接寻址是特别快的，于此同时hash的过程是有开销的，这会造成初期的时候体现不出hash的优势。