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

2021-02-13 15:21

阅读:989

标签:方式   教程   clear   选择   书籍   英文单词   print   size   队列   

字典

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

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

一、字典

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

如:

键=>值

"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和红黑树RBTreeGolang语言中字典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,
    }
}

使用一个容量为capmap来实现不可重复集合。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。

  • 数据结构和算法(Golang实现)(1)简单入门Golang-前言
  • 数据结构和算法(Golang实现)(2)简单入门Golang-包、变量和函数
  • 数据结构和算法(Golang实现)(3)简单入门Golang-流程控制语句
  • 数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
  • 数据结构和算法(Golang实现)(5)简单入门Golang-接口
  • 数据结构和算法(Golang实现)(6)简单入门Golang-并发、协程和信道
  • 数据结构和算法(Golang实现)(7)简单入门Golang-标准库
  • 数据结构和算法(Golang实现)(8.1)基础知识-前言
  • 数据结构和算法(Golang实现)(8.2)基础知识-分治法和递归
  • 数据结构和算法(Golang实现)(9)基础知识-算法复杂度及渐进符号
  • 数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
  • 数据结构和算法(Golang实现)(11)常见数据结构-前言
  • 数据结构和算法(Golang实现)(12)常见数据结构-链表
  • 数据结构和算法(Golang实现)(13)常见数据结构-可变长数组
  • 数据结构和算法(Golang实现)(14)常见数据结构-栈和队列
  • 数据结构和算法(Golang实现)(15)常见数据结构-列表
  • 数据结构和算法(Golang实现)(16)常见数据结构-字典
  • 数据结构和算法(Golang实现)(17)常见数据结构-树
  • 数据结构和算法(Golang实现)(18)排序算法-前言
  • 数据结构和算法(Golang实现)(19)排序算法-冒泡排序
  • 数据结构和算法(Golang实现)(20)排序算法-选择排序
  • 数据结构和算法(Golang实现)(21)排序算法-插入排序
  • 数据结构和算法(Golang实现)(22)排序算法-希尔排序
  • 数据结构和算法(Golang实现)(23)排序算法-归并排序
  • 数据结构和算法(Golang实现)(24)排序算法-优先队列及堆排序
  • 数据结构和算法(Golang实现)(25)排序算法-快速排序
  • 数据结构和算法(Golang实现)(26)查找算法-哈希表
  • 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
  • 数据结构和算法(Golang实现)(28)查找算法-AVL树
  • 数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
  • 数据结构和算法(Golang实现)(30)查找算法-2-3-4树和普通红黑树

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

标签:方式   教程   clear   选择   书籍   英文单词   print   size   队列   

原文地址:https://www.cnblogs.com/nima/p/12724840.html


评论


亲,登录后才可以留言!