Skip to main content

Map & LinkList

map​

map类型也称字典类型或映射类型，是一种包含多个key => value键值对的集合。

{
  name: "Alice",
  age: 16
}

数据特点​

  1. map是无序列表集合。
  2. map装载key => value键值对的结构。
  3. 一个key在map中具有唯一性。
  4. map的读、写、删效率相对比较高。
  5. Go语言中，slice、map、func不能作为key。key在系统插入中要对比重复性，不能作为比较运算的类型不能做key。
package main

import "fmt"

func main() {
  map1 := map[string]string{}
  map2 := map[string]string{}
  // invalid operation: map1 == map2 (map can only be compared to nil)
  fmt.Println(map1 == map2)
}

声明​

  1. 使用map[key type]value type语法进行声明：
package main

import "fmt"

func main() {
  myMap := map[string]string{}

  myMap["name"] = "Tom"
  myMap["age"] = "16"

  fmt.Println(myMap)
}

如上，key为string类型，value也为string类型。

  1. 在声明时进行初始化：
  • 最后一个key => value后面必须打逗号。
  • 字符串key必须加双引号。
package main

import "fmt"

func main() {
  rankKey := "rank"

  myMap := map[string]string{
    "name":  "golang",
    "age":   "16",
    rankKey: "12",
  }

  fmt.Println(myMap)
}
  1. 通过make声明初始化：
package main

import "fmt"

func main() {
  myMap := make(map[string]string, 3)
  
  rankKey := "rank"
  
  myMap["name"] = "golang"
  myMap["age"] = "16"
  myMap[rankKey] = "12"
  
  fmt.Println(myMap)
}

长度​

map的长度表示具有的key的数量，可通过len方法获取：

package main

import "fmt"

func main() {
  stringMap := make(map[string]string, 2)
  stringMap["name"] = "golang"
  fmt.Println(len(stringMap))
}

如果超出初始设置的长度，会自动进行扩容。

访问​

Go语言中map不支持点语法，需要通过map[key]语法获取：

package main

import "fmt"

func main() {
  stringMap := make(map[string]string, 1)
  // 写入
  stringMap["name"] = "golang"
  // 访问
  fmt.Println(stringMap["name"])
}

如果map中不存在要访问的key属性：

  1. 如果key为数值类型，默认值是0。
  2. 如果key为字符串类型，默认值是""。
  3. 如果key为字布尔类型，默认值是false。

如果某个key对应的值确实为0、""、false，可用获取语法第二个返回值来判断是否存在此属性：

package main

import "fmt"

func main() {
  stringMap := make(map[string]string, 2)
  stringMap["name"] = "golang"  

  name, nameExist := stringMap["name"]
  age, ageExist := stringMap["age"]  

  fmt.Println(nameExist, name) // true golang
  fmt.Println(ageExist, age)   // false ""  

  if value, existed := stringMap["score"]; existed {
    // ...
  }
}

写入​

map在增加属性前必须保证已被初始化，否则无法增加且会报错：

package main

func main() {
  var myMap map[int]int
  // panic: assignment to entry in nil map
  myMap[0] = 1
}

删除​

map删除key需要使用全局内置delete方法：

package main

import "fmt"

func main() {
  stringMap := make(map[string]string, 2)  

  stringMap["name"] = "golang"
  stringMap["age"] = "16"  

  delete(stringMap, "name")

  fmt.Println(stringMap)
}

删除不存在的key不会有任何操作和报错。

枚举​

枚举的过程是无序且顺序随机的，通过for循环达不到枚举效果，需要使用for range。

for range对于map的key的枚举顺序是随机的，每次可能产生不同的结果：

package main

import "fmt"

func main() {
  stringMap := make(map[string]string, 2)

  stringMap["name"] = "golang"
  stringMap["age"] = "16"

  for key, value := range stringMap {
   fmt.Println(key, value)
  }
}

因此不要试图用map定义时的key顺序来描述程序对key的排序。

键类型​

map需要通过键的对比来判断其唯一性，因此键需要能够进行==和!=比较。

像切片、map等都不能作为键的类型，像string、int、boolean、数组可作为键的类型。

package main

func main() {
  // invalid map key type []int
  testMap := map[[]int]int {}

  arr := [3]int{1, 2, 3}  
  arrMap := map[[3]int]int{
    arr: 1,
  }  
  fmt.Println(arrMap)
}

多类型值​

可通过interface实现值的多类型：

package main

func main() {
  studentInfoMap := map[string]interface{}{
    "name":    "Tom",
    "age":     12,
    "married": false,
  }
}

哈希​

任何一对键值对的存储都跟哈希值有关，哈希值决定了键值对存储在哪里。

/*
{ name: "Tom" }

name(key) -----hash算法(createHash(key))-----> hash值
*/
  1. 哈希的单一性。相同的key产生相同的hash值。
  2. 哈希的压缩性。理论性无穷大的key都可以通过哈希算法得到一个一定大的hash值。
  3. 哈希的映射性。映射就是key值与hash值之间的对应关系。
  4. 哈希的离散性。不同的hash值对应的数据存储在不同的空间内。
  5. 哈希的单行性。哈希算法不能从hash值反推回key值。
  6. 哈希的冲突性。key的可能性是无限的，而hash值是有限的，因此两个不同的key通过哈希算法后可能得到相同的hash值。

桶数组​

Bucket Array，也称为桶数组，是一种用于数据存储和查找的数据结构。它将数据划分为多个桶，每个桶存储具有相同特征的数据。

桶数组是一段连续的空间，每个元素对应一个链表，链表的每个节点可以存储8组键值对，并有一个指向下一个节点的指针，用于链表的遍历。

哈希存储

存储过程大致如下：

  1. 通过哈希算法计算键的哈希值。
  2. 通过算法计算该键值对将要存储在的桶数组的索引。
  3. 保存键值对。

当链表的长度的即将达到阈值时，会开辟一个新的桶数组，其大小为旧的桶数组的2倍。

新的数据存储新开启的空间中，而旧的数据当有写入操作时，会将其迁移到新的空间中，而不是一次性迁移。

链表​

区别​

  1. 数组与链表都是有序列表。
  2. 数组需要开辟一个连续的空间。数组的查询采用顺序位偏移的方式，性能效率较高。但是在插入元素时，尤其是在中间的某个位置插入，需要对后续元素进行移动，因此性能效率较低。
  3. 链表不需要开辟连续的空间。插入一个元素开辟一个空间，只需要将前后的指针进行重新指向，不需要对其它元素进行存储移动，性能相对较高。但在查询时，需要遍历元素进行查询，因此性能效率相对较低。

结构​

Go语言中的List是双向链表。

链表List是一个包含root和len的结构体。root为链表的哨兵元素，代表了列表的根；len为当前链表的长度(不包含哨兵元素)：

type List struct {
  root Element
  len int
}

Element是链表中每个节点的结构体，包含：

  1. next指针，指向下一个节点。
  2. prev指针，指向上一个节点。
  3. list指针，当前节点所属的链表。
  4. Value当前节点的值，interface{}类型。
type Element struct {
  next, prev *Element
  list *List
  Value interface{}
}

链表

初始化​

可通过是三种方式进行初始化：

list.List、new(list.List).Init()、list.New()

package main

import (
  "container/list"
  "fmt"
)

func main() {
  var linkList list.List
  // var linkList = new(list.List).Init()
  // var linkList = list.New()  

  //   next  prev  list  Value  len
  // {{<nil> <nil> <nil> <nil>} 0}
  fmt.Println(linkList)
}

遍历​

链表的变量需要通过for循环：

package main

import (
  "container/list"
  "fmt"
)

func main() {
  var linkList = list.New()  
  linkList.PushBack(1)
  linkList.PushBack(2)
  linkList.PushFront("a")
  linkList.PushBack("b")  

  for i := linkList.Front(); i != nil; i = i.Next() {
    fmt.Println(i.Value)
  }
}

方法​

可查看

Last updated on