Map 的哈希过程遇到的问题
来源：1-9 神奇的内置数据结构
EwdAger
2021-06-08 16:43:29
不知道我对把 key hash 以后找具体 bucket 下的 tophash 理解有没有问题，如果有问题麻烦曹大也帮忙纠错一下：
首先通过哈希函数计算 key，得到一个 hash value，然后取二进制位的后 5 位(low bits), 和 bucketMask 进行 & 运算，得到的就是 bucket 所在位置。然后取 hash value 二进制位的头八位转化为十进制，存入对应 bucket bmap 的 tophash 数组里。先判断当前 tophash 对应的 key 是否为空，如果为空该位置就是对应位置，如果不为空，则表明发生哈希冲突，需要使用拉链法在该 tophash 后链一个新的 tophash-key-value 结构
问题一：
找到了对应 bucket，bmap结构中的 tophash 的位置是如何确定的？
问题二：
发生哈希冲突时，使用拉链法链的新结构是个什么结构？ bmap 里的 tophash、 keys、 values不都是长度为 8 的数组嘛？难道要链一个新的tophash-key-value结构？
1回答
-
Xargin
2021-06-08
问题一：
找到了对应
bucket，bmap结构中的tophash的位置是如何确定的？要遍历，一个 bucket 里面最多有 8 个 entry，要把这 8 个 entry 的 tophash[i] 遍历完，如果 tophash[i] = 输入 key 的 tophash，那么需要再比较实际的 key 是否等于输入的 key，如果相等，这时候覆盖掉第 i 个位置的 value
如果一直没找到相等的，则需要把 overflow 都遍历完毕，全完毕之后都没有，说明需要插入到第一次的 empty entry 的位置上(这个在遍历一开始就记录过了)
问题二：
发生哈希冲突时，使用拉链法链的新结构是个什么结构？
bmap里的tophash、keys、values不都是长度为 8 的数组嘛？难道要链一个新的tophash-key-value结构？就是我们课上那个图的样子，overflow 指针指向一个新的 bmap。bmap 里面还是有 tophash、keys、values
0
相似问题