面试者与面试官

1、Go语言中的Map是有序的还是无序的,为什么?

在Go语言中,字典Map是无序的。

因为 Go 中的 map 是基于 哈希表(hash table)实现的。哈希表的核心思想是通过哈希函数将键映射到特定的位置,然后存储值。由于哈希表是通过散列来决定每个元素的存储位置,元素的存储顺序是 由哈希值和碰撞解决策略 决定的,而不是按插入的顺序排列的。

Go 语言设计者故意没有为 map 提供顺序保证。Go 认为在多数应用场景中,顺序并不重要,尤其是在查找、插入和删除操作的效率比顺序更重要。因此,Go 选择使用无序的哈希表来实现 map,这使得 map 的查找和操作在大多数情况下是 常数时间复杂度 O(1)。

因此,如果使用 for … range 循环遍历的话每次迭代获得的 键 - 元素 对的顺序都可能是不同的。

另外,在Go的内部实现中是先通过一个叫做fastrand()的函数生成一个伪随机数,然后使用这个随机数作为每次遍历的起始桶位置,从而导致每次遍历的起始位置不是固定的。

2、Map字典的键类型不能是哪些类型,应该优先考虑哪些类型作为字典的键类型呢?

这在官方文档中有详细说明:

The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice. If the key type is an interface type, these comparison operators must be defined for the dynamic key values; failure will cause a run-time panic.

因此,Go 语言Map字典的键类型不可以是函数、字典和切片。因为 Go 语言的字典类型其实是一个哈希表(hash table)的特定实现,因此其中重要的一个步骤就是需要把键值转换为哈希值,所以,从性能的角度来看的话,“把键值转换为哈希值”以及“把要查找的键值与哈希桶中的键值做对比”, 都是比较耗时的操作。

因此,可以说,求哈希和判等操作的速度越快,对应的类型就越适合作为键类型,应该优先考虑。

3、在值为nil的字典上执行读或写操作会成功吗?

当我们仅声明而不初始化这个字典类型的变量时,这个变量的值就会是nil,比如像下面这样声明的变量mp就是nil。

func main() {
	var mp map[string]int
	fmt.Println(mp["key"]) // 这行会输出 0,不会 panic
}

在这样的nil字典上执行读操作是没有问题的。但是,如果是写操作(插入)的话,Go语言的运行时系统就会立即抛出一个 panic 致命性错误。

这需要从Map的底层结构来看了,在Go中,Map是引用类型,其底层是由一个 hmap 结构体 表示的,其的定义为:

// https://github.com/golang/go/blob/master/src/runtime/map_noswiss.go#L114
// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
	clearSeq   uint64

	extra *mapextra // optional fields
}

其中,buckets 指向存储键值对的 “桶数组”,所以,当map声明但未初始化时(即 var mp map[string]int),其值是nil,它的内部结构核心字段值如下:

{
	...	...
	count	: 0,
	buckets	: nil,		// 关键:未分配存储空间
	...	...
}

我们再查看Go源码src/runtime/map_fast64_noswiss.go 的实现也可以发现读取值为nil的Map时会返回零值:

func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {
	...	...
	if h == nil || h.count == 0 {
		return unsafe.Pointer(&zeroVal[0])
	}
	...	...
}

因为 var mp map[string]int 这个字典的key是字符串,key对应的值是int整型,而int整型的零值正是数字0,所以上面的 fmt.Println(mp[“key”]) 才会输出数字0。

而当执行写入操作时,由于根本没有存储空间来存放内容所以运行时直接抛出了 panic 错误。

例外情况:delete(mp, key) 不会 panic,因为 Go 语言允许对 nil map 进行删除操作,只是删除操作对 nil map 无任何效果。

{
	var mp map[string]int
	delete(mp, "key")      // 这里不会 panic
}