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]stringa["name"]="值" //panic: assignment to entry in nil map应用内置函数make()初始化
var a map[string]stringa = 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"]) //hellofmt.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]intfmt.Println(ages == nil) // "true"fmt.Println(len(ages) == 0) // "true"和slice一样，map之间也是不能进行相等比拟，惟一的例外是和nil进行比拟。要判断两个map是否蕴含雷同的key和value。
高并发下读写是不平安的
package mainimport ( "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 mainimport ( "fmt" "sync" "time")var wg sync.Mutexfunc 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 mainimport ( "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指针指向下一个数据，如下：