面试题合集目录
map查找?
假设当前 B=4 即桶数量为2^B=16个,要从map中获取k4对应的value
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
k4的查找步骤:
①计算k4的hash值;
②通过低B位来确定在哪号桶,此时B为4,所以取k4对应哈希值的后4位,也就是0101,0101用十进制表示为5,所以在5号桶);
③根据k4对应的hash值高8位快速确定是在这个桶的哪个位置(额外说明一下,在bmap中存放了每个key对应的tophash,是key的哈希值高8位),一旦发现高8位一致,则会执行下一步;
④对比key完整的hash是否匹配,如果匹配则获取对应value;
⑤如果都没有找到,就去连接的下一个溢出桶中找。
tophash可以快速确定key是否正确,也可以把它理解成一种缓存措施,如果高8位都不对了,后面就没有必要比较了。
map的底层实现?
map是一种key-value的键值对存储结构,其中key不能重复,底层用hash表存储。
map的数据结构在源码结构中的关键字段如下,在src/runtime/map.go中: