map

map

随写

1. 遍历map时的元素顺序与添加键值对的顺序无关。

基本使用

创建

make创建

1

make(map[KeyType]ValueType, [cap])

或声明时填充

1
2
3
4

userInfo := map[string]string{
       "username": "pprof.cn",
       "password": "123456",
   }

判断某个key是否存在

1

value, ok := map[key]  

遍历

普通遍历

1
2
3

for k, v := range scoreMap {
      fmt.Println(k, v)
  }

只遍历key

1
2
3

for k := range scoreMap {
      fmt.Println(k)
  }

特定顺序遍历

将key保存在切片中进行操作

1
2
3
4
5
6
7
8
9
10

var keys = make([]string, 0, 200)
   for key := range scoreMap {
       keys = append(keys, key)
   }
   //对切片进行排序
   sort.Strings(keys)
   //按照排序后的key遍历map
   for _, key := range keys {
       fmt.Println(key, scoreMap[key])
   }

删除键值对

1

delete(map, key)  

底层

map

一种通过key来获取value的一个数据结构，其底层存储方式为数组

hash冲突

个数组下标只能存储一对key，value, hashkey(xiaoming)=4占用了下标0的位置，假设我们遇到另一个key，hashkey(xiaowang)也是4，这就是hash冲突

解决方法：

开放定址法：冲突的下标处开始往后探测，到达数组末尾时，从数组开始处探测，直到找到一个空位置存储这个key，当数组都找不到的情况下回扩容（事实上当数组容量快满的时候就会扩容了）；查找某一个key的时候，找到key对应的下标，比较key是否相等，如果相等直接取出来，否则按照顺寻探测直到碰到一个空位置，说明key不存在。

如下图：首先存储key=xiaoming在下标0处，当存储key=xiaowang时，hash冲突了，按照线性探测，存储在下标1处，（红色的线是冲突或者下标已经被占用了） 再者key=xiaozhao存储在下标4处，当存储key=xiaoliu是，hash冲突了，按照线性探测，从头开始，存储在下标2处 （黄色的是冲突或者下标已经被占用了）

拉链法（go map）：

何为拉链，简单理解为链表，当key的hash冲突时，我们在冲突位置的元素上形成一个链表，通过指针互连接，当查找时，发现key冲突，顺着链表一直往下找，直到链表的尾节点，找不到则返回空，如下图：）

开放定址（线性探测）和拉链的优缺点

• 由上面可以看出拉链法比线性探测处理简单
• 线性探测查找是会被拉链法会更消耗时间
• 线性探测会更加容易导致扩容，而拉链不会
• 拉链存储了指针，所以空间上会比线性探测占用多一点
• 拉链是动态申请存储空间的，所以更适合链长不确定的

go map实现原理

map是数组存储的的，每个数组下标处存储的是一个bucket

每个bucket中可以存储8个kv键值对，当每个bucket存储的kv对到达8个之后，会通过overflow指针指向一个新的bucket，从而形成一个链表,看bmap的结构，

map[int64]int8,key是int64（8个字节），value是int8（一个字节），kv的长度不同，如果按照kv格式存放，则考虑内存对齐v也会占用int64，而按照后者存储时，8个v刚好占用一个int64

当往map中存储一个kv对时，通过k获取hash值，hash值的低八位和bucket数组长度取余，定位到在数组中的那个下标，hash值的高八位存储在bucket中的tophash中，用来快速判断key是否存在，key和value的具体值则通过指针运算存储，当一个bucket满时，通过overfolw指针链接到下一个bucket。

• ← Previous Post
• Next Post →