Go地图在内部使用什么数据结构？

Question

我对以下内容感兴趣:

• 如何在内部实施Go地图？(哈希表,树......)
• 如果Go贴图是散列表,使用哪个散列函数？
• 如果Go地图是树木,它们是AVL,红黑还是其他类型？
• 如果Go贴图是基于阵列的,它们如何避免/处理碰撞？

Answer 1

Go map是内部的哈希表

正如@twotwotwo在评论中澄清的那样,如果CPU有支持指令,Go将使用基于AES的哈希.

否则Go将使用FNV哈希函数(如Patrick Mylund Nielsen @ Go-Nuts所述)

链接:

• 官方Go博客:http://blog.golang.org/go-maps-in-action
• 地图源代码:http://golang.org/src/pkg/runtime/hashmap.c
• 哈希源代码:http://golang.org/src/pkg/runtime/alg.c
• GoNuts Group:https://groups.google.com/forum/#!topic/golang -nuts/PP3CCBtbDsQ