Go语言 如何在初始化Map时设置容量,以防止重复

k3fezbri  于 12个月前  发布在  Go
关注(0)|答案(3)|浏览(137)
s := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
capacity := len(s)
m := make(map[int]bool, capacity)
for _, n := range s {
    m[n] = true
}

字符串
map是否会在for循环中重排序?或者容量应该乘以一个因子来防止重排序,比如:

capacity := len(s) * 1.3

jk9hmnmh

jk9hmnmh1#

您不需要因子。规格:制作切片、Map和元素:
使用map类型和大小提示n调用make将创建一个map,该map具有初始空间以容纳n map元素。具体行为取决于实现。
同样来自内置make()的文档:
唐飞:一个空的map被分配了足够的空间来容纳指定数量的元素。大小可以被省略,在这种情况下,分配一个小的起始大小。

hc2pp10m

hc2pp10m2#

此代码是最佳代码,只要s的值小于capacity,就不需要更改

vlurs2pr

vlurs2pr3#

package main

import (
    "fmt"
    "unsafe"
)

const (
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits
)

type emptyInterface struct {
    _type unsafe.Pointer
    value unsafe.Pointer
}

// 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)

    extra *mapextra // optional fields
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // nextOverflow holds a pointer to a free overflow bucket.
    nextOverflow *bmap
}

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

type maptype struct {
    typ    _type
    key    *_type
    elem   *_type
    bucket *_type // internal type representing a hash bucket
    // function for hashing keys (ptr to key, seed) -> hash
    hasher     func(unsafe.Pointer, uintptr) uintptr
    keysize    uint8  // size of key slot
    elemsize   uint8  // size of elem slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

type tflag uint8
type nameOff int32
type typeOff int32

// Needs to be in sync with ../cmd/link/internal/ld/decodesym.go:/^func.commonsize,
// ../cmd/compile/internal/reflectdata/reflect.go:/^func.dcommontype and
// ../reflect/type.go:/^type.rtype.
// ../internal/reflectlite/type.go:/^type.rtype.
type _type struct {
    size       uintptr
    ptrdata    uintptr // size of memory prefix holding all pointers
    hash       uint32
    tflag      tflag
    align      uint8
    fieldAlign uint8
    kind       uint8
    // function for comparing objects of this type
    // (ptr to object A, ptr to object B) -> ==?
    equal func(unsafe.Pointer, unsafe.Pointer) bool
    // gcdata stores the GC type data for the garbage collector.
    // If the KindGCProg bit is set in kind, gcdata is a GC program.
    // Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
    gcdata    *byte
    str       nameOff
    ptrToThis typeOff
}

func mapTypeAndValue(m interface{}) (*maptype, *hmap) {
    ei := (*emptyInterface)(unsafe.Pointer(&m))
    return (*maptype)(ei._type), (*hmap)(ei.value)
}

func main() {
    PredefinedSizeMap()
}

func PredefinedSizeMap() {
    m := make(map[int]int, 1000000)
    _, hm := mapTypeAndValue(m)

    fmt.Printf("Elements | h.B | Buckets\n\n")

    fmt.Printf("%8d | %3d | %8d\n", hm.count, hm.B, 1<<hm.B)

    for i := 0; i < 1000000; i++ {
        m[i] = i * 3
    }

    fmt.Printf("%8d | %3d | %8d\n", hm.count, hm.B, 1<<hm.B)
}

字符串
产出:

Elements | h.B | Buckets

       0 |  18 |   262144
 1000000 |  18 |   262144


我们可以看到水桶数量没有变化,

相关问题