[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/>