哈希表（或曰字典、映射）本身指示的是集合中键值间的映射关系，其实现依赖：

• 哈希函数
  • 完成键-索引映射的关键函数，因而也很大程度上决定了哈希表读写性能。理论上完美哈希函数为输出范围大于输入范围；但实践中，键数远大于函数可映射范围，故哈希冲突有必然性。
  • 关键点：高效键-索引映射；键-索引均匀分布；
• 冲突解决方法
  • 因哈希冲突有必然性，需要哈希表实现中工程解决冲突，使索引成立。

冲突解决方法：

开放寻址法

核心：依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中

底层实现：数组，哈希函数取余确定基本位置，对已占用位置（哈希冲突）顺延偏移

index := hash("$key$") % array.len + occupiedN

性能因素：装载因子，一般性能拐点为70%

拉链法

核心与底层实现：链表数组，哈希确定键（key）对应桶（一般定长），可动态分配存储空间（键——桶，桶扩容）

性能因素：转载因子（元素数量/桶数量），一般性能拐点为1，在到达时一般进行桶扩容

runtime.hmap(Go 1.18)

type hmap struct {
	count     int //当前哈希表中的元素数量
	flags     uint8
	B         uint8 //bucket桶数量的对数
	noverflow uint16
	hash0     uint32 //哈希函数种子，引入随机性

	buckets    unsafe.Pointer
	oldbuckets unsafe.Pointer //扩容时暂存buckets的字段，大小为当前buckets的一半
	nevacuate  uintptr

	extra *mapextra
}

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}

buckets中存储的桶数据结构为runtime.bmap（存储能力一般为8个键值对），桶分为正常桶、溢出桶。桶检索（如键索引存在哈希冲突）通过哈希值高8位uint8进行。