Go map

哈希表

• map又称为哈希表，是一种无序的键值对（key-value pair）的集合。
• map也是一种集合，因此可时使用迭代数组或切片的方式来进行迭代。
• map特点是通过key来快速检索数据，key类似于索引，指向数据的值。
• map是无序的，因此无法决定它的返回顺序，因为map是使用哈希查找表来实现的。

Golang中map用来存储键值对类型的数据，map内部是一种HashMap，表面上看只是键值对结构，实际上在存储键值对的过程中涉及到数组和链表。

HashMap之所以高效，是因为结合了顺序存储（数组）和链式存储（链表）两种存储结构。数组是HashMap的主干，在数组下有一个类型为链表的元素。

• 数组：数组存储区间是连续的，占用内存严重，空间复杂度很大，但数组的二分查找时间复杂度小。
  数组的特点：寻址容易，插入和删除困难。
• 链表：链表存储区间离散，占用内存比较宽松，空间复杂度很小，但时间复杂度很大。
  链表的特点：寻址困难，插入和删除容易。

哈希表即满足了数据的查找方便，同时不占用太多的内存空间，使用也十分容易。

哈希表有多种不同的实现方法，常见的实现方式 - 拉链法（链表的数组）。

HashMap结构

当存储一个键值对时，HashMap首先通过哈希函数将key转换为数组下标，真正的key-value是存储在该数组对应的链表中。

HashMap的数组是有限的，当存储的键值对很多数组不够，或两个键值对哈希运算后的值相同时，就会出现不同的键值对存储在同一个数组下，也就是发生哈希碰撞。当发生哈希碰撞时，键值对就会存储在该数组对应链表的下一个节点上。

哈希碰撞

map的设计也称为 The dictionary problem，它的任务是设计一种数据结构来维护一个集合的数据，可同时对集合进行增删改查的操作。

最重要的数据结构有两种：

• 哈希查找表 Hashtable
• 搜索树 Searchtree

哈希查找表用一个哈希函数将key分配到不同的桶（bucket，数组下标index），开销主要在哈希函数的计算以及数组的常数访问时间，在很多场景下哈希查找表的性能很高。

哈希查找表一般会存在“碰撞”的问题，就是说不同的key被哈希到了同一个bucket桶。一般有两种应对方法：

• 链表法：链表法将一个bucket实现成一个链表，落在同一个bucket中的key都会插入这个链表。
• 开放地址法：开放地址法则是碰撞发生后，通过一定的规律，在数组的后面挑选空位，用来放置新的key。

声明

var hashtable = map[keyType]valueType

• hashtable 表示map的变量名
• keyType 表示键类型
• valueType 表示值类型，原始类型。
• keyType和valueType之间允许存在空格

var hashtable map[string]string
fmt.Printf("%v\n", hashtable)/map[]
fmt.Printf("%v\n", hashtable== nil)//true
fmt.Printf("%d\n", len(hashtable))//0

• map可以动态增长，因此在声明时无需指定长度。
• 默认未初始化的map的值是nil
• 使用len()函数可获取map中元素键值对pair的个数

声明并初始化

var hashtable = map[string]string{"id":"1", "name":"alice"}
fmt.Printf("%v\n", hashtable)//map[id:1 name:alice]
fmt.Printf("%d\n", len(hashtable))// 2

fmt.Printf("id = %v, name = %v, gender = %v\n", dict["id"], dict["name"], dict["gender"])
// id = 1, name = alice, gender =

使用make()构建

由于map是引用类型因此可以使用make()函数来构造，但不能使用new()，因为new()会分配一个引用对象同时会获得一个空引用指针，相当于声明一个未初始化的变量且获取其地址。

dict := make(map[string]string)
dict["id"] = "1"
dict["name"] = "alice"
fmt.Printf("dict = %v\n", dict)//dict = map[id:1 name:alice]

容量

map和数组不同之处在于map可以根据新增的键值对动态的伸缩，因此不存在固定长度或最大容量的限制。

使用make()函数构建map时可以显式地指定初始容量，出于性能考虑推荐创建时指定容量。

dict := make(map[string]string, 100)
fmt.Printf("dict = %v, len = %d\n", dict, len(dict))//dict = map[], len = 0

当map中需要使用一个键来表示拥有多个值的值时，怎么办呢？比如，处理UNIX进程时需要以父进程作为键，所有子进程组成的切片作为值。

pid := make(map[int] []int)
pid[31421] = []int{31423, 31429}
fmt.Printf("pid = %v\n", pid)//pid = map[31421:[31423 31429]]

遍历

可使用for range组合循环遍历map以访问映射中每个键值对

dict := make(map[string]string)
dict["id"] = "1"
dict["name"] = "alice"
dict["gender"] = "female"

for key,value := range dict{
    fmt.Printf("key = %s, value = %s\n", key, value)
}

遍历map时会同时获取键和值，若只需要遍历键或值可将其修改为_即以匿名变量形式实现。

for _,value := range dict{
    fmt.Printf("value = %s\n", value)
}

若只需要遍历键而无需值时可将值省略掉

for key := range dict{
    fmt.Printf("key = %s\n", key)
}

遍历map时输出的元素顺序和填充时的顺序无关，若需要以特定顺序遍历需预先作排序处理。

dict := make(map[string]string)
dict["id"] = "1"
dict["name"] = "alice"
dict["gender"] = "female"

var list []string
for key := range dict{
    list = append(list, key)
}
sort.Strings(list)

fmt.Printf("list = %v\n", list)//list = [gender id name]

删除元素

Go语言内置的delete()函数可从map删除指定键值对

delete(map, key)

例如：删除dict中键status

dict := make(map[string] int)
dict["id"] = 1
dict["score"] = 100
dict["status"] = 1

delete(dict, "status")

for k,v := range dict{
    fmt.Printf("k = %v, v = %v\n", k, v)
}

清空元素

Go语言中清空map映射的唯一办法的重新make一个新的map，无需担心垃圾回收，因为Go语言中并行垃圾回收的效果要比清空函数更高效。