What data structure do Go maps use internally?

Question

I'm interested in the following:

• How are Go maps implemented internally? (hash tables, trees...)
• If Go maps are hash tables, which hash function is used?
• If Go maps are trees, are they AVL, red-black, or some other type?
• If Go maps are array-based, how do they avoid/handle collisions?

Answer 1

Go maps are hash tables internally

As @twotwotwo clarified in the comment, Go will use an AES-based hash if the CPU has supporting instructions for it.

Otherwise Go will use a FNV hash function (As stated by Patrick Mylund Nielsen @ Go-Nuts)

Links:

• Official Go Blog: http://blog.golang.org/go-maps-in-action
• Map Source Code: http://golang.org/src/pkg/runtime/hashmap.c
• Hash Source Code: http://golang.org/src/pkg/runtime/alg.c
• GoNuts Group: https://groups.google.com/forum/#!topic/golang-nuts/PY3CCBtbDsQ