数据结构和算法(Golang实现)(16)常见数据结构-字典

头像
9527
    阅读 6 分钟
    1

    我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于 阅读更友好的GitBook。

    字典

    我们翻阅书籍时，很多时候都要查找目录，然后定位到我们要的页数，比如我们查找某个英文单词时，会从英语字典里查看单词表目录，然后定位到词的那一页。

    计算机中，也有这种需求。

    一、字典

    字典是存储键值对的数据结构，把一个键和一个值映射起来，一一映射，键不能重复。在某些教程中，这种结构可能称为符号表，关联数组或映射。我们暂且称它为字典，较好理解。

    如：

    键=>值 "cat"=>2 "dog"=>1 "hen"=>3

    我们拿出键cat的值，就是2了。

    Golang提供了这一数据结构：map，并且要求键的数据类型必须是可比较的，因为如果不可比较，就无法知道键是存在还是不存在。

    Golang字典的一般的操作如下：

     package main import "fmt" func main() { // 新建一个容量为4的字典 map m := make(map[string]int64, 4) // 放三个键值对 m["dog"] = 1 m["cat"] = 2 m["hen"] = 3 fmt.Println(m) // 查找 hen which := "hen" v, ok := m[which] if ok { // 找到了 fmt.Println("find:", which, "value:", v) } else { // 找不到 fmt.Println("not find:", which) } // 查找 ccc which = "ccc" v, ok = m[which] if ok { // 找到了 fmt.Println("find:", which, "value:", v) } else { // 找不到 fmt.Println("not find:", which) } }

    字典的实现有两种方式：哈希表HashTable和红黑树RBTree。Golang语言中字典map的实现由哈希表实现，具体可参考标准库runtime下的map.go文件。

    我们会在《查找算法》章节：散列查找和红黑树中，具体分析字典的两种实现方式。

    二、实现不可重复集合 Set

    一般很多编程语言库，会把不可重复集合（Collection）命名为Set，这个Set中文直译为集合，在某些上下文条件下，我们大脑要自动过滤，集合这词指的是不可重复集合还是指统称的集合，在这里都可以看到中文博大精深。

    不可重复集合Set存放数据，特点就是没有数据会重复，会去重。你放一个数据进去，再放一个数据进去，如果两个数据一样，那么只会保存一份数据。

    集合Set可以没有顺序关系，也可以按值排序，算一种特殊的列表。

    因为我们知道字典的键是不重复的，所以只要我们不考虑字典的值，就可以实现集合，我们来实现存整数的集合Set：

    // 集合结构体 type Set struct { m map[int]struct{} // 用字典来实现，因为字段键不能重复 len int // 集合的大小 sync.RWMutex // 锁，实现并发安全 }

    2.1.初始化一个集合

    // 新建一个空集合 func NewSet(cap int64) *Set { temp := make(map[int]struct{}, cap) return &Set{ m: temp, } }

    使用一个容量为cap的map来实现不可重复集合。map的值我们不使用，所以值定义为空结构体struct{}，因为空结构体不占用内存空间。如：

    package main import ( "fmt" "sync" ) func main() // 为什么使用空结构体 a := struct{}{} b := struct{}{} if a == b { fmt.Printf("right:%p\n", &a) } fmt.Println(unsafe.Sizeof(a)) }

    会打印出：

    right:0x1198a98 0

    空结构体的内存地址都一样，并且不占用内存空间。

    2.2.添加一个元素

    // 增加一个元素 func (s *Set) Add(item int) { s.Lock() defer s.Unlock() s.m[item] = struct{}{} // 实际往字典添加这个键 s.len = len(s.m) // 重新计算元素数量 }

    首先，加并发锁，实现线程安全，然后往结构体s *Set里面的内置map添加该元素：item，元素作为字典的键，会自动去重。同时，集合大小重新生成。

    时间复杂度等于字典设置键值对的复杂度，哈希不冲突的时间复杂度为：O(1)，否则为O(n)，可看哈希表实现一章。

    2.3.删除一个元素

    // 移除一个元素 func (s *Set) Remove(item int) { s.Lock() s.Unlock() // 集合没元素直接返回 if s.len == 0 { return } delete(s.m, item) // 实际从字典删除这个键 s.len = len(s.m) // 重新计算元素数量 }

    同理，先加并发锁，然后删除map里面的键：item。时间复杂度等于字典删除键值对的复杂度，哈希不冲突的时间复杂度为：O(1)，否则为O(n)，可看哈希表实现一章。

    2.3.查看元素是否在集合中

    // 查看是否存在元素 func (s *Set) Has(item int) bool { s.RLock() defer s.RUnlock() _, ok := s.m[item] return ok }

    时间复杂度等于字典获取键值对的复杂度，哈希不冲突的时间复杂度为：O(1)，否则为O(n)，可看哈希表实现一章。

    2.4.查看集合大小

    // 查看集合大小 func (s *Set) Len() int { return s.len }

    时间复杂度：O(1)。

    2.5.查看集合是否为空

    // 集合是够为空 func (s *Set) IsEmpty() bool { if s.Len() == 0 { return true } return false }

    时间复杂度：O(1)。

    2.6.清除集合所有元素

    // 清除集合所有元素 func (s *Set) Clear() { s.Lock() defer s.Unlock() s.m = map[int]struct{}{} // 字典重新赋值 s.len = 0 // 大小归零 }

    将原先的map释放掉，并且重新赋一个空的map。

    时间复杂度：O(1)。

    2.7.将集合转化为列表

    func (s *Set) List() []int { s.RLock() defer s.RUnlock() list := make([]int, 0, s.len) for item := range s.m { list = append(list, item) } return list }

    时间复杂度：O(n)。

    2.8.完整例子

    package main import ( "fmt" "sync" "unsafe" ) // 集合结构体 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, } } // 增加一个元素 func (s *Set) Add(item int) { s.Lock() defer s.Unlock() s.m[item] = struct{}{} // 实际往字典添加这个键 s.len = len(s.m) // 重新计算元素数量 } // 移除一个元素 func (s *Set) Remove(item int) { s.Lock() s.Unlock() // 集合没元素直接返回 if s.len == 0 { return } delete(s.m, item) // 实际从字典删除这个键 s.len = len(s.m) // 重新计算元素数量 } // 查看是否存在元素 func (s *Set) Has(item int) bool { s.RLock() defer s.RUnlock() _, ok := s.m[item] return ok } // 查看集合大小 func (s *Set) Len() int { return s.len } // 清除集合所有元素 func (s *Set) Clear() { s.Lock() defer s.Unlock() s.m = map[int]struct{}{} // 字典重新赋值 s.len = 0 // 大小归零 } // 集合是够为空 func (s *Set) IsEmpty() bool { if s.Len() == 0 { return true } return false } // 将集合转化为列表 func (s *Set) List() []int { s.RLock() defer s.RUnlock() list := make([]int, 0, s.len) for item := range s.m { list = append(list, item) } return list } // 为什么使用空结构体 func other() { a := struct{}{} b := struct{}{} if a == b { fmt.Printf("right:%p\n", &a) } fmt.Println(unsafe.Sizeof(a)) } 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]

    系列文章入口

    我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于 阅读更友好的GitBook。

    go算法数据结构
    9527
    495 声望150 粉丝
    « 上一篇
    数据结构和算法(Golang实现)(15)常见数据结构-列表
    下一篇 »
    数据结构和算法(Golang实现)(17)常见数据结构-树

    引用和评论

    推荐阅读
    头像
    数据结构和算法(Golang实现)(28)查找算法-AVL树

    9527赞 5阅读 4.3k

    头像
    使用 Iris 框架写的一个后台 API 练手项目

    snowlyg赞 3阅读 14.3k评论 3

    头像
    稚晖君公司最新合伙人，公开了！

    CodeSheep赞 1阅读 6.6k

    头像
    运筹优化工具ortools解读与实践-ortools求解CP问题

    喜东东阅读 8.6k

    头像
    【Triton 教程】triton_language.interleave

    超神经HyperAI阅读 4.7k

    头像
    树形结构效率对比

    老污的猫阅读 4k

    头像
    我天，Java 已沦为老四。。

    CodeSheep阅读 3.7k

    0 条评论
    得票最新