[TOC] ## 概述 字典是存儲鍵值對的數據結構，把一個鍵和一個值映射起來，一一映射，鍵不能重復。在某些教程中，這種結構可能稱為符號表，關聯數組或映射 字典的實現有兩種方式：**哈希表`HashTable`和紅黑樹`RBTree`** ## go實現 set(不可重復集合) 使用一個容量為`cap`的`map`來實現不可重復集合,`map`的值我們不使用,所以值定義為空結構體`struct{}`，因為**空結構體不占用內存空間** ``` // 集合結構體 type Set struct { m map[int]struct{} // 用字典來實現，因為字段鍵不能重復 len int // 集合的大小 sync.RWMutex // 鎖，實現并發安全 } // 新建一個空集合 func NewSet(cap int64) *Set { temp := make(map[int]struct{}, cap) return &Set{ m: temp, } } ``` ## 實現 <details> <summary>main.go</summary> ``` package main import ( "fmt" "sync" ) type Set struct { m map[int]struct{} len int mu sync.Mutex } func NewSet(cap int )*Set{ return &Set{ m: make(map[int]struct{},cap), } } func (s *Set)Add(n int){ s.mu.Lock() defer s.mu.Unlock() s.m[n]= struct{}{} s.len++ } func (s *Set)Remove(n int){ s.mu.Lock() defer s.mu.Unlock() if s.len == 0 { return } delete(s.m,n) s.len-- } func (s *Set) Has(n int)bool{ s.mu.Lock() defer s.mu.Unlock() if s.len == 0 { return false } _,ok:=s.m[n] return ok } func (s *Set) Len()int { return s.len } func (s *Set) IsEmpty()bool { return s.len==0 } func (s *Set) Clear(){ s.mu.Lock() defer s.mu.Unlock() s.m= map[int]struct{}{} s.len=0 } func (s *Set) List()[]int{ s.mu.Lock() defer s.mu.Unlock() var nums []int for k, _ := range s.m { nums =append(nums,k) } return nums } func main() { //other() // 初始化一個容量為5的不可重復集合 s := NewSet(5) s.Add(1) s.Add(1) s.Add(2) fmt.Println("list of all items", s.List()) s.Clear() if s.IsEmpty() { fmt.Println("empty") } s.Add(1) s.Add(2) s.Add(3) if s.Has(2) { fmt.Println("2 does exist") } s.Remove(2) s.Remove(3) fmt.Println("list of all items", s.List()) /** list of all items [1 2] empty 2 does exist list of all items [1] */ } ``` </details> <br/>