字典
最后更新于：2022-04-02 04:10:54
[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,
}
}
```
## 实现
main.go
```
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]
*/
}
```
';