Go基础编程:Map

一夕烟云 · · 611 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Map

《Go语言圣经》:哈希表是一种巧妙并且实用的数据结构。它是一个无序key/value对的集合,其中所有的key都是不同的,然后通过给定的key可以在常数时间复杂度内检索、更新或删除对应的value。

在Go语言中,一个map就是一个哈希表的引用,map类型可以写为map[K]V,其中K和V分别对应key和value。map中所有的key都有相同的类型,所以的value也有着相同的类型,但是key和value之间可以是不同的数据型。其中K对应的key必须是支持==比较运算符的数据类型,所以map可以通过测试key是否相等来判断是否已经存在。虽然浮点数类型也是支持相等运算符比较的,但是将浮点数用做key类型则是一个坏的想法,最坏的情况是可能出现的NaN和任何浮点数都不相等。对于V对应的value数据类型则没有任何的限制。

声明

map是引用类型,可以用如下声明:

var type_name map[keytype]valuetype

在向map存储数据前必须初始化

var a map[string]string
a["name"]="值" //panic: assignment to entry in nil map

使用内置函数make()初始化

var a map[string]string
a = make(map[string]string)
a["name"] = "值"
fmt.Println(a) //map[name:值]

可以声明和初始化一起

var a = make(map[string]string)
a["name"] = "值"
fmt.Println(a) //map[name:值]

声明并初始化带上数据

var a map[string]string = map[string]string{"id": "110"}
a["name"] = "值"
fmt.Println(a) //map[id:110 name:值]

基本操作

添加数据,只要初始化后,可以随便添加:

var a = make(map[string]string)
a["id"]= "001"
a["name"]="hello"
a["age"]="23"
fmt.Println(a) //map[age:23 id:001 name:hello]

修改数据

var a = make(map[string]string)
a["name"] = "hello"
fmt.Println(a) //map[name:hello]
a["name"] = "worrld"
fmt.Println(a) //map[name:worrld]

获取数据,就算没有对应的key也不会报错,这个操作是安全的,会返回对应value的空值

var a = make(map[string]string)
a["name"] = "hello"
fmt.Println(a["name"]) //hello
fmt.Println(a["id"])   //此处无数据,无报错

删除数据,使用内置函数delete(),删除无此key的元素也不报错,这个操作是安全的

var a = make(map[string]string)
a["id"] = "001"
a["name"] = "hello"
fmt.Println(a) //map[id:001 name:hello]
delete(a, "id")//删除key为id的元素
fmt.Println(a)   //map[name:hello]
delete(a, "age") //删除key为age 的元素,无报错
fmt.Println(a)   //map[name:hello]

返回为空值不代表key不存在,因为这个key的value可能就是空值,需要用下面方法

第一个返回参数是此key对应的value,第二个参数是是否存在的bool值,存在即为true

if value, ok := a["name"]; ok {
    fmt.Println("key存在,value为:", value)
}

遍历,用for range变量,语法和遍历切片一样 , map是无序的,打印顺序每次不一定一样

var a = make(map[string]string)
a["id"] = "001"
a["name"] = "hello"
a["lan"] = "go"
for k, v := range a {
    fmt.Printf("%s=>%sn", k, v)
}

map中的元素不是有个变量,不能取地址操作,禁止对map元素取址的原因是map可能随着元素数量的增长而重新分配更大的内存空间,从而可能导致之前的地址无效。

fmt.Printf("%p", &a["id"]) //cannot take the address of a["id"]

map的零值为nil,也就是没有引用任何哈希表。

var ages map[string]int
fmt.Println(ages == nil) // "true"
fmt.Println(len(ages) == 0) // "true"

和slice一样,map之间也是不能进行相等比较,唯一的例外是和nil进行比较。要判断两个map是否包含相同的key和value。

高并发下读写是不安全的

package main
​
import (
    "time"
)
​
func main() {
​
     var a = make(map[string]int)
    ​
     for i := 0; i < 100; i++ {
         go func() {
            a["id"] = 1 //fatal error: concurrent map writes
         }()
     }
    ​
     time.Sleep(1 * time.Second)
​
}
​

高并发下读写需要加锁

package main
​
import (
     "fmt"
     "sync"
     "time"
)
​
var wg sync.Mutex
​
func main() {
     var a = make(map[string]int)
    ​
     for i := 0; i < 100; i++ {
         go func() {
             wg.Lock()
             a["id"] = i
             wg.Unlock()
         }()
     }
    ​
     time.Sleep(1 * time.Second)
    ​
     fmt.Println(a) //map[id:100]
}

在高并发下建议使用标准包下的sync.Map

package main
​
import (
     "fmt"
     "sync"
)
​
func main() {
​
     var a sync.Map
    ​
     //添加元素:key,value
     a.Store("name", "hello")
     a.Store("age","22")
     //获取一个元素key
     if value, ok := a.Load("name"); ok {
         fmt.Println("key存在,value为:", value)
     }
     //
     //参数是一对key:value,如果该key存在且没有被标记删除则返回原先的value(不更新)和true;不存在则store,返回该value 和false
     if actual, loaded := a.LoadOrStore("id", "001"); !loaded {
         fmt.Printf("不存在key为id,并增加%sn", actual)
     }
     if actual, loaded := a.LoadOrStore("id", "002"); loaded {
         fmt.Printf("key为id,不改变value:%sn", actual)
     }
    ​
     //遍历
     a.Range(func(key, value interface{}) bool {
         fmt.Printf("key:%s,value:%sn", key,value)
     return true
     })
     //删除key
     a.Delete("id")
     if value, ok := a.Load("id"); !ok {
         fmt.Printf("id删除了,value为空:%sn",value)
     }

     //获取并删除
     //第一个是值,有返回,无是为nil,第二个是判断key是否存在,存在为true
     if value ,loaded :=a.LoadAndDelete("age");loaded{
        fmt.Printf("age删除了,删除前value为:%sn",value)
     }
     if value, ok := a.Load("age"); !ok {
        fmt.Printf("age删除了,value为空:%sn",value)
     }
​
}
​

哈希表

Go的Map是哈希表的引用,上面讲了map的用法,但什么是哈希表呢?

哈希表是为快速获取数据的,时间复杂度约为O(1),数组的获取数据的时间复杂度也为O(1)。哈希表的底层是由数组组成的,所以怎么把哈希表的key转为数组下标是关键。

哈希算法f(key)可以用于将任意大小的数据映射到固定大小值的函数,常见的包括MD5、SHA系列等

哈希表key->value 大致流程是下面:

key  ->   f(key)   ->  数组下标  -> value

数组下标可以通过把key通过哈希算法获取固定大小值然后对一个数取模(常见的数是数组长度和质数),下面是对数组长度取模

为了方便,用一些简单的数字代替哈希好的key

假设有个长度为7的数组,哈希好的key有 2,4,6,12,故他们分别取模为:2,4,6,5,故数组存储如下:

image.png

假设再加一个9,取模为2,如上2的位置被占了,这种情况叫哈希冲突

为了解决哈希冲突有两种方案:

  1. 链地址法
  2. 开放寻址法

    • 线性探测法
    • 二次探查
    • 双重散列

链地址法:就是在被占位置加个next指针指向下一个数据,如下:
image.png


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:一夕烟云

查看原文:Go基础编程:Map

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

611 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传