关于golang:Go基础编程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，故数组存储如下：

假如再加一个 9，取模为 2，如上 2 的地位被占了，这种状况叫哈希抵触

为了解决哈希抵触有两种计划：

链地址法
凋谢寻址法
- 线性探测法
- 二次探查
- 双重散列

链地址法：就是在被占地位加个 next 指针指向下一个数据，如下：