golang map 元素访问

[yuqiandoudou]

文章表述：主要是对 key 进行 hash 计算，计算后用 low bits 和高 8 位 hash 找到对应的位置。
https://github.com/cch123/golang-notes/blob/master/map.md
问题：如果两个key的hash值不同，但是low bits 和高 8 位 hash 这两项相同。这个时候元素如何查找，以元素如何插入。

[yangxikun]

top hash 是为了加速查找，top hash 相同的情况下，还得判断 key 是否真的相同

[XYZ0901]

这里就是哈希冲突了呀，就是拉链法了呀

[xianyunyh]

这个问题我也曾经疑惑过，不过多多看了几次源码后，恍然大悟。

golang的哈希表的 bucket 最上面的 tophash 字段存放每个key经过哈希计算的高八位 值，每次查找都需要从头遍历bucket.tophash，插入的时候，也是从头遍历，寻找tophash中的空位。

如果两个key 同时落到一个bucket 里。并且高8位tophash相同，那么这时候会有个冲突，会先进行 key 比较。如果key相同，就找到该元素，否则会到继续查找。

查找逻辑

for ; b != nil; b = b.overflow(t) {
  for i := uintptr(0); i < bucketCnt; i++ {
      //跳过不相等的索引
	if b.tophash[i] != top {
		continue
	}
	k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
	if t.indirectkey() {
		k = *((*unsafe.Pointer)(k))
	}
         //进行key比较 
	if t.key.equal(key, k) {
           //省略部分代码,找到直接返回
	   return e, true
	}
  }
}