之前在面试今日头条时被问到了map的实现原理，当时答的不是很好。现在从网上找了些资料记录下map的实现原理。
什么是map
map 是一种通过key来获取value的数据结构，其底层存储方式为数组，在存储时 key不能重复，当key重复的时候，value进行覆盖，我们通过key进行hash计算，然后对数组的长度取余，得到key存储在数组的哪个下标位置，最后将key和value转化为一个结构体，放到数组的下标中。
hash冲突
在key进行hash的时候，会出现hash冲突的问题，主要有下面几个解决办法
开放定址法
在存储key-value的时候发现hashkey(key)的下标已经被别key占用，那我们在这个数组中空间中重新找一个没被占用的存储这个冲突的key，那么没被占用的有很多，找哪个好呢？常见的有线性探测法，线性补偿探测法，随机探测法，这里我们主要说一下线性探测法。
- 线性探测：从冲突的地方向下探测，直到找到一个空位置来存储这个key，当数组都找不到的情况下，会进行扩容。
- 拉链法：当出现冲突的时候，会在冲突的位置生成一个链表，通过指针相互链接，当查找冲突的时候，就顺着链表一直往下找。
Golang中map的实现原理
在go中，map是用来进行数据存储的，每个数组下标处存储的是一个bucket，这个bucket的类型如下
type bmap {
tophash [bucketCnt]uint8
}
tophash 用来快速查找key值是否在在bucket中，不是每次都是通过真值进行比较，至于kv的存放，不是k1v1,k2v2，而是k1k2,v1v2，主要是因为map[int64]int8，key是int64(8字节)，value是int8(一个字节)， key和value的长度不同，如果按照kv格式来存数据，则会占用较多的内存。
最后分析下go的整体内存结构，当向map中写入数据的时候，通过k获取hash值，hash值的低八位和bucket数组长度取余，定位到在数组中的那个下标，hash值的高八位存储在bucket中的tophash中，用来快速判断key是否存在，key和value的具体值则通过指针运算存储，当一个bucket满时，通过overfolw指针链接到下一个bucket。
网友评论