go-map和redis-字典

map

结构图

• 哈希冲突采用链地址法解决，一般冲突数据会放在溢出桶中
• 扩容时会采用oldbucket和bucket，加逐步迁移的模式进行迁移，插入直接放到bucket，oldbucket数据等待被访问时做迁移

字典

用途

• k-v键值的存储
• hash(散列)存储

结构图

• 字典中采用ht0和ht1来支持扩容，ht1只有扩容时才会用到
• 哈希冲突也是采用链地址法，冲突部分形成一个单链表

go-map和redis-字典对比

相同点

• 扩容时都会有一个旧bucket或者字典来存储旧的数据
• 哈希冲突都采用链地址法来解决

不同点

• map在查找数据时用hash的高8位， tophash来标记bucket中的不同元素，先通过tophash排除不存在数据的桶，等找到存在的桶后再对比key确认更准确的值
• 字典则通过掩码(索引)来确定桶位置，再逐步比较key,找到对应的值
• map的冲突解决是采用溢出桶，完整的内存块，无指针消耗，cpu缓存利用率更高
• 字典的冲突解决是采用元素单链表模式，更加灵活，键值对差异较大也不影响