寫在前面
開發(fā) hashset 常用的套路：
map[int]int8
map[int]bool
我們一般只用 map 的鍵來保存數(shù)據(jù)戏阅，值是沒有用的。所以來緩存集合數(shù)據(jù)會(huì)造成內(nèi)存浪費(fèi)啤它。
空對(duì)象
空對(duì)象是個(gè)神奇的東西奕筐。它指的是沒有字段的結(jié)構(gòu)類型舱痘。
type Q struct{}
它牛逼的地方在于：
-
可以和普通結(jié)構(gòu)一樣操作
var a = []struct{}{struct{}{}} fmt.Println(len(a)) // prints 1 -
不占用空間
var s struct{} fmt.Println(unsafe.Sizeof(s)) // prints 0 -
聲明兩個(gè)空對(duì)象，它們指向同一個(gè)地址
type A struct{} a := A{} b := A{} fmt.Println(&a == &b) // prints true
造成這個(gè)結(jié)果的原因是 Golang 的編譯器會(huì)把這種空對(duì)象都當(dāng)成runtime.zerobase處理离赫。
var zerobase uintptr
hashset
有了上面的介紹芭逝，就可以利用空結(jié)構(gòu)來優(yōu)化 hashset 了。
var itemExists = struct{}{}
type Set struct {
items map[interface{}]struct{}
}
func New() *Set {
return &Set{items: make(map[interface{}]struct{})}
}
func (set *Set) Add(item interface{}) {
set.items[item] = itemExists
}
func (set *Set) Remove(item interface{}) {
delete(set.items, item)
}
func (set *Set) Contains(item interface{}) bool {
if _, contains := set.items[item]; !contains {
return false
}
return true
}
一個(gè)簡(jiǎn)易的 hashset 實(shí)現(xiàn)就完成了渊胸。
性能比較
func BenchmarkIntSet(b *testing.B) {
var B = NewIntSet(3)
B.Set(10).Set(11)
for i := 0; i < b.N; i++ {
if B.Exists(1) {
}
if B.Exists(11) {
}
if B.Exists(1000000) {
}
}
}
func BenchmarkMap(b *testing.B) {
var B = make(map[int]int8, 3)
B[10] = 1
B[11] = 1
for i := 0; i < b.N; i++ {
if _, exists := B[1]; exists {
}
if _, exists := B[11]; exists {
}
if _, exists := B[1000000]; exists {
}
}
}
BenchmarkIntSet-2 50000000 35.3 ns/op 0 B/op 0 allocs/op
BenchmarkMap-2 30000000 41.2 ns/op 0 B/op 0 allocs/op
結(jié)論
性能旬盯，有些提升，但不是特別明顯翎猛。尤其是線上壓力不大的情況性能應(yīng)該不會(huì)有明顯變化胖翰；
內(nèi)存占用。我們的服務(wù)緩存較多切厘、占用內(nèi)存較大萨咳，通過這個(gè)優(yōu)化實(shí)測(cè)可以減少 1.6 GB 的空間。不過這個(gè)優(yōu)化的空間取決于數(shù)據(jù)量疫稿。
參考文獻(xiàn)
【3】 《Go 語言學(xué)習(xí)筆記》 - 雨痕培他。5.5 結(jié)構(gòu)。
