寫在前面

開發(fā) hashset 常用的套路：

map[int]int8

map[int]bool

我們一般只用 map 的鍵來保存數(shù)據(jù)，值是沒有用的。所以來緩存集合數(shù)據(jù)會造成內(nèi)存浪費(fèi)。

空對象

空對象是個神奇的東西。它指的是沒有字段的結(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
  

• 聲明兩個空對象，它們指向同一個地址

  type A struct{}
  
  a := A{}
  
  b := A{}
  
  fmt.Println(&a == &b) // prints true
  

造成這個結(jié)果的原因是 Golang 的編譯器會把這種空對象都當(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
}

一個簡易的 hashset 實現(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)該不會有明顯變化；

• 內(nèi)存占用。我們的服務(wù)緩存較多、占用內(nèi)存較大，通過這個優(yōu)化實測可以減少 1.6 GB 的空間。不過這個優(yōu)化的空間取決于數(shù)據(jù)量。

參考文獻(xiàn)

• 【1】The empty struct - Dave Cheney

• 【2】gods - emirpasic

• 【3】 《Go 語言學(xué)習(xí)筆記》 - 雨痕。5.5 結(jié)構(gòu)。