site logo

Keep doing what you want, never give up.

招聘会
文章配图

大厂面试 - 拼多多:Go字典Map

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,它的内部结构核心字段值如下: