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

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

一、字典

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

如:

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

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

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

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

  1. package main
  2. import "fmt"
  3. func main() {
  4. // 新建一个容量为4的字典 map
  5. m := make(map[string]int64, 4)
  6. // 放三个键值对
  7. m["dog"] = 1
  8. m["cat"] = 2
  9. m["hen"] = 3
  10. fmt.Println(m)
  11. // 查找 hen
  12. which := "hen"
  13. v, ok := m[which]
  14. if ok {
  15. // 找到了
  16. fmt.Println("find:", which, "value:", v)
  17. } else {
  18. // 找不到
  19. fmt.Println("not find:", which)
  20. }
  21. // 查找 ccc
  22. which = "ccc"
  23. v, ok = m[which]
  24. if ok {
  25. // 找到了
  26. fmt.Println("find:", which, "value:", v)
  27. } else {
  28. // 找不到
  29. fmt.Println("not find:", which)
  30. }
  31. }

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

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

二、实现不可重复集合 Set

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

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

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

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

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

2.1.初始化一个集合

  1. // 新建一个空集合
  2. func NewSet(cap int64) *Set {
  3. temp := make(map[int]struct{}, cap)
  4. return &Set{
  5. m: temp,
  6. }
  7. }

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

  1. package main
  2. import (
  3. "fmt"
  4. "sync"
  5. )
  6. func main()
  7. // 为什么使用空结构体
  8. a := struct{}{}
  9. b := struct{}{}
  10. if a == b {
  11. fmt.Printf("right:%p\n", &a)
  12. }
  13. fmt.Println(unsafe.Sizeof(a))
  14. }

会打印出:

  1. right:0x1198a98
  2. 0

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

2.2.添加一个元素

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

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

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

2.3.删除一个元素

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

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

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

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

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

2.4.查看集合大小

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

时间复杂度:O(1)

2.5.查看集合是否为空

  1. // 集合是够为空
  2. func (s *Set) IsEmpty() bool {
  3. if s.Len() == 0 {
  4. return true
  5. }
  6. return false
  7. }

时间复杂度:O(1)

2.6.清除集合所有元素

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

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

时间复杂度:O(1)

2.7.将集合转化为列表

  1. func (s *Set) List() []int {
  2. s.RLock()
  3. defer s.RUnlock()
  4. list := make([]int, 0, s.len)
  5. for item := range s.m {
  6. list = append(list, item)
  7. }
  8. return list
  9. }

时间复杂度:O(n)

2.8.完整例子

  1. package main
  2. import (
  3. "fmt"
  4. "sync"
  5. "unsafe"
  6. )
  7. // 集合结构体
  8. type Set struct {
  9. m map[int]struct{} // 用字典来实现,因为字段键不能重复
  10. len int // 集合的大小
  11. sync.RWMutex // 锁,实现并发安全
  12. }
  13. // 新建一个空集合
  14. func NewSet(cap int64) *Set {
  15. temp := make(map[int]struct{}, cap)
  16. return &Set{
  17. m: temp,
  18. }
  19. }
  20. // 增加一个元素
  21. func (s *Set) Add(item int) {
  22. s.Lock()
  23. defer s.Unlock()
  24. s.m[item] = struct{}{} // 实际往字典添加这个键
  25. s.len = len(s.m) // 重新计算元素数量
  26. }
  27. // 移除一个元素
  28. func (s *Set) Remove(item int) {
  29. s.Lock()
  30. s.Unlock()
  31. // 集合没元素直接返回
  32. if s.len == 0 {
  33. return
  34. }
  35. delete(s.m, item) // 实际从字典删除这个键
  36. s.len = len(s.m) // 重新计算元素数量
  37. }
  38. // 查看是否存在元素
  39. func (s *Set) Has(item int) bool {
  40. s.RLock()
  41. defer s.RUnlock()
  42. _, ok := s.m[item]
  43. return ok
  44. }
  45. // 查看集合大小
  46. func (s *Set) Len() int {
  47. return s.len
  48. }
  49. // 清除集合所有元素
  50. func (s *Set) Clear() {
  51. s.Lock()
  52. defer s.Unlock()
  53. s.m = map[int]struct{}{} // 字典重新赋值
  54. s.len = 0 // 大小归零
  55. }
  56. // 集合是够为空
  57. func (s *Set) IsEmpty() bool {
  58. if s.Len() == 0 {
  59. return true
  60. }
  61. return false
  62. }
  63. // 将集合转化为列表
  64. func (s *Set) List() []int {
  65. s.RLock()
  66. defer s.RUnlock()
  67. list := make([]int, 0, s.len)
  68. for item := range s.m {
  69. list = append(list, item)
  70. }
  71. return list
  72. }
  73. // 为什么使用空结构体
  74. func other() {
  75. a := struct{}{}
  76. b := struct{}{}
  77. if a == b {
  78. fmt.Printf("right:%p\n", &a)
  79. }
  80. fmt.Println(unsafe.Sizeof(a))
  81. }
  82. func main() {
  83. //other()
  84. // 初始化一个容量为5的不可重复集合
  85. s := NewSet(5)
  86. s.Add(1)
  87. s.Add(1)
  88. s.Add(2)
  89. fmt.Println("list of all items", s.List())
  90. s.Clear()
  91. if s.IsEmpty() {
  92. fmt.Println("empty")
  93. }
  94. s.Add(1)
  95. s.Add(2)
  96. s.Add(3)
  97. if s.Has(2) {
  98. fmt.Println("2 does exist")
  99. }
  100. s.Remove(2)
  101. s.Remove(3)
  102. fmt.Println("list of all items", s.List())
  103. }

打印出:

  1. list of all items [1 2]
  2. empty
  3. 2 does exist
  4. list of all items [1]