{"action":"created","issue":{"url":"https://api.github.com/repos/eastany/eastany.github.com/issues/40","labels_url":"https://api.github.com/repos/eastany/eastany.github.com/issues/40/labels{/name}","comments_url":"https://api.github.com/repos/eastany/eastany.github.com/issues/40/comments","events_url":"https://api.github.com/repos/eastany/eastany.github.com/issues/40/events","html_url":"https://github.com/eastany/eastany.github.com/issues/40","id":78439128,"number":40,"title":"go map的实现","user":{"login":"eastany","id":4279344,"avatar_url":"https://avatars.githubusercontent.com/u/4279344?v=3","gravatar_id":"","url":"https://api.github.com/users/eastany","html_url":"https://github.com/eastany","followers_url":"https://api.github.com/users/eastany/followers","following_url":"https://api.github.com/users/eastany/following{/other_user}","gists_url":"https://api.github.com/users/eastany/gists{/gist_id}","starred_url":"https://api.github.com/users/eastany/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/eastany/subscriptions","organizations_url":"https://api.github.com/users/eastany/orgs","repos_url":"https://api.github.com/users/eastany/repos","events_url":"https://api.github.com/users/eastany/events{/privacy}","received_events_url":"https://api.github.com/users/eastany/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/eastany/eastany.github.com/labels/golang","name":"golang","color":"207de5"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-05-20T09:00:03Z","updated_at":"2015-05-20T13:42:36Z","closed_at":null,"body":"之前C版本的这里有一篇blog简单介绍了一下\r\nhttp://blog.codingnow.com/2013/08/reading_golang_source.html\r\n\r\n其实go版本的与C版本的实现应该相差不多，\r\n下面根据代码和注释 详细看看\r\n```\r\nconst (\r\n\tbucketCntBits = 3  //一个Bucket可以存放的kv对－－8\r\n\tbucketCnt     = 1 << bucketCntBits\r\n \r\n\t//Bucket的扩展阈值\r\n\tloadFactor = 6.5\r\n \r\n\t// kv的最大大小，用8位整形填充，\r\n\tmaxKeySize   = 128\r\n\tmaxValueSize = 128\r\n \r\n         //数据偏移是bmap的结构体大小，但是必须对齐，比如amd64p32的意思是64位对齐，尽管它指向32位\r\n\tdataOffset = unsafe.Offsetof(struct {\r\n\t\tb bmap\r\n\t\tv int64\r\n\t}{}.v)\r\n\tempty          = 0 // cell is empty\r\n\tevacuatedEmpty = 1 // cell is empty, bucket is evacuated.\r\n\tevacuatedX     = 2 // key/value is valid.  Entry has been evacuated to first half of larger table.\r\n\tevacuatedY     = 3 // same as above, but evacuated to second half of larger table.\r\n\tminTopHash     = 4 // minimum tophash for a normal filled cell.\r\n \r\n\t// flags\r\n\titerator    = 1 // there may be an iterator using buckets\r\n\toldIterator = 2 // there may be an iterator using oldbuckets\r\n \r\n\t// sentinel bucket ID for iterator checks\r\n\tnoCheck = 1<<(8*ptrSize) - 1\r\n \r\n\t// trigger a garbage collection at every alloc called from this code\r\n\tcheckgc = false\r\n)\r\n \r\n//Map的结构体\r\ntype hmap struct {\r\n\tcount int // map元素个数，也就是len(yourmap)\r\n\tflags uint8\r\n\tB     uint8  //  2^8*loadFactor\r\n\thash0 uint32 // hash seed\r\n\tbuckets    unsafe.Pointer // 数据指针：array of 2^B Buckets. may be nil if count==0.\r\n\toldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing\r\n\tnevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)\r\n \r\n\t// k,v都不包含指针的话，可避免扫描map\r\n\t// 但是bmap.overflow是指针. 为了保证超过阀值的buckets可用，把所有的overflow buckets指针存储到hmap.overflow.Overflow仅用于kv不包含指针的情况。\r\n\t// overflow[0]包含hmap.buckets中的overflow buckets.\r\n\t// overflow[1] 包含hmap.oldbuckets中的overflow buckets\r\n\t// 第一个可以间接实现减少hmap的静态大小.\r\n\t// 第二个可以间接实现指向切片hiter.overflow *[2]*[]*bmap\r\n}\r\n \r\n// A bucket for a Go map.\r\ntype bmap struct {\r\n\ttophash [bucketCnt]uint8\r\n\t// 紧接着是bucketCnt个key和bucketCnt个value\r\n\t// 把key编码在一起，value编码在一起虽然比kvkvkv这种复杂点，但是可以解决填充对齐的问题，如map[int64]int8.\r\n\t// 然后是overflow的指针\r\n}\r\n \r\n//map遍历的结构体\r\ntype hiter struct {\r\n\tkey         unsafe.Pointer //必须排在第一位，置空表示迭代结束\r\n\tvalue       unsafe.Pointer // 排第二位\r\n\tt           *maptype\r\n\th           *hmap\r\n\tbuckets     unsafe.Pointer // bucket ptr at hash_iter initialization time\r\n\tbptr        *bmap          // 迭代器当前bucket\r\n\toverflow    [2]*[]*bmap    // keeps overflow buckets alive\r\n\tstartBucket uintptr        // 迭代器开始的bucket\r\n\toffset      uint8          // 记录偏移量\r\n\twrapped     bool           // \r\n\tB           uint8\r\n\ti           uint8\r\n\tbucket      uintptr\r\n\tcheckBucket uintptr\r\n}\r\n \r\nfunc evacuated(b *bmap) bool {\r\n\th := b.tophash[0]\r\n\treturn h > empty && h < minTopHash\r\n}\r\n \r\nfunc (b *bmap) overflow(t *maptype) *bmap {\r\n\treturn *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-regSize))\r\n}\r\n \r\nfunc (h *hmap) setoverflow(t *maptype, b, ovf *bmap) {\r\n\tif t.bucket.kind&kindNoPointers != 0 {\r\n\t\th.createOverflow()\r\n\t\t*h.overflow[0] = append(*h.overflow[0], ovf)\r\n\t}\r\n\t*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-regSize)) = ovf\r\n}\r\n \r\nfunc (h *hmap) createOverflow() {\r\n\tif h.overflow == nil {\r\n\t\th.overflow = new([2]*[]*bmap)\r\n\t}\r\n\tif h.overflow[0] == nil {\r\n\t\th.overflow[0] = new([]*bmap)\r\n\t}\r\n}\r\n \r\n//实现map的make \r\nfunc makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {\r\n      //做一些校验\r\n\tif sz := unsafe.Sizeof(hmap{}); sz > 48 || sz != uintptr(t.hmap.size) {\r\n\t\tprintln(\"runtime: sizeof(hmap) =\", sz, \", t.hmap.size =\", t.hmap.size)\r\n\t\tthrow(\"bad hmap size\")\r\n\t}\r\n \r\n\tif hint < 0 || int64(int32(hint)) != hint {\r\n\t\tpanic(\"makemap: size out of range\")\r\n\t\t// TODO: make hint an int, then none of this nonsense\r\n\t}\r\n \r\n\tif !ismapkey(t.key) {\r\n\t\tthrow(\"runtime.makemap: unsupported map key type\")\r\n\t}\r\n \r\n\t// check compiler's and reflect's math\r\n\tif t.key.size > maxKeySize && (!t.indirectkey || t.keysize != uint8(ptrSize)) ||\r\n\t\tt.key.size <= maxKeySize && (t.indirectkey || t.keysize != uint8(t.key.size)) {\r\n\t\tthrow(\"key size wrong\")\r\n\t}\r\n\tif t.elem.size > maxValueSize && (!t.indirectvalue || t.valuesize != uint8(ptrSize)) ||\r\n\t\tt.elem.size <= maxValueSize && (t.indirectvalue || t.valuesize != uint8(t.elem.size)) {\r\n\t\tthrow(\"value size wrong\")\r\n\t}\r\n \r\n\t// invariants we depend on.  We should probably check these at compile time\r\n\t// somewhere, but for now we'll do it here.\r\n\tif t.key.align > bucketCnt {\r\n\t\tthrow(\"key align too big\")\r\n\t}\r\n\tif t.elem.align > bucketCnt {\r\n\t\tthrow(\"value align too big\")\r\n\t}\r\n\tif uintptr(t.key.size)%uintptr(t.key.align) != 0 {\r\n\t\tthrow(\"key size not a multiple of key align\")\r\n\t}\r\n\tif uintptr(t.elem.size)%uintptr(t.elem.align) != 0 {\r\n\t\tthrow(\"value size not a multiple of value align\")\r\n\t}\r\n\tif bucketCnt < 8 {\r\n\t\tthrow(\"bucketsize too small for proper alignment\")\r\n\t}\r\n\tif dataOffset%uintptr(t.key.align) != 0 {\r\n\t\tthrow(\"need padding in bucket (key)\")\r\n\t}\r\n\tif dataOffset%uintptr(t.elem.align) != 0 {\r\n\t\tthrow(\"need padding in bucket (value)\")\r\n\t}\r\n \r\n\t// 计算出实现hint需要多少个B\r\n\tB := uint8(0)\r\n\tfor ; hint > bucketCnt && float32(hint) > loadFactor*float32(uintptr(1)<<B); B++ {\r\n\t}\r\n \r\n\t// 初始化哈希表\r\n\tbuckets := bucket\r\n\tif B != 0 {\r\n\t\tif checkgc {\r\n\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t}\r\n\t\tbuckets = newarray(t.bucket, uintptr(1)<<B)\r\n\t}\r\n \r\n\t// initialize Hmap\r\n\tif checkgc {\r\n\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t}\r\n\tif h == nil {\r\n\t\th = (*hmap)(newobject(t.hmap))\r\n\t}\r\n\th.count = 0\r\n\th.B = B\r\n\th.flags = 0\r\n\th.hash0 = fastrand1()//随机种子\r\n\th.buckets = buckets\r\n\th.oldbuckets = nil\r\n\th.nevacuate = 0\r\n \r\n\treturn h\r\n}\r\n \r\n// mapaccess1返回h[key]的指针，如果不存在这个key则是值类型的零值.\r\n// 需要注意的是，这个返回将会使得map一直alive，所以最好不要过久的持有它，尤其是在map比较大的时候，会长久的驻留内存.\r\nfunc mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {\r\n\tif raceenabled && h != nil {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&t))\r\n\t\tpc := funcPC(mapaccess1)\r\n\t\tracereadpc(unsafe.Pointer(h), callerpc, pc)\r\n\t\traceReadObjectPC(t.key, key, callerpc, pc)\r\n\t}\r\n\tif h == nil || h.count == 0 {\r\n\t\treturn unsafe.Pointer(t.elem.zero)\r\n\t}\r\n\talg := t.key.alg\r\n\thash := alg.hash(key, uintptr(h.hash0))\r\n\tm := uintptr(1)<<h.B - 1\r\n\tb := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))\r\n\tif c := h.oldbuckets; c != nil {\r\n\t\toldb := (*bmap)(add(c, (hash&(m>>1))*uintptr(t.bucketsize)))\r\n\t\tif !evacuated(oldb) {\r\n\t\t\tb = oldb\r\n\t\t}\r\n\t}\r\n\ttop := uint8(hash >> (ptrSize*8 - 8))\r\n\tif top < minTopHash {\r\n\t\ttop += minTopHash\r\n\t}\r\n\tfor {\r\n\t\tfor i := uintptr(0); i < bucketCnt; i++ {\r\n\t\t\tif b.tophash[i] != top {\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\tk := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\r\n\t\t\tif t.indirectkey {\r\n\t\t\t\tk = *((*unsafe.Pointer)(k))\r\n\t\t\t}\r\n\t\t\tif alg.equal(key, k) {\r\n\t\t\t\tv := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\r\n\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\tv = *((*unsafe.Pointer)(v))\r\n\t\t\t\t}\r\n\t\t\t\treturn v\r\n\t\t\t}\r\n\t\t}\r\n\t\tb = b.overflow(t)\r\n\t\tif b == nil {\r\n\t\t\treturn unsafe.Pointer(t.elem.zero)\r\n\t\t}\r\n\t}\r\n}\r\n \r\n//这个就是常用的_,ok := m[key],不多做解释\r\nfunc mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {\r\n\tif raceenabled && h != nil {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&t))\r\n\t\tpc := funcPC(mapaccess2)\r\n\t\tracereadpc(unsafe.Pointer(h), callerpc, pc)\r\n\t\traceReadObjectPC(t.key, key, callerpc, pc)\r\n\t}\r\n\tif h == nil || h.count == 0 {\r\n\t\treturn unsafe.Pointer(t.elem.zero), false\r\n\t}\r\n\talg := t.key.alg\r\n\thash := alg.hash(key, uintptr(h.hash0))\r\n\tm := uintptr(1)<<h.B - 1\r\n\tb := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))\r\n\tif c := h.oldbuckets; c != nil {\r\n\t\toldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&(m>>1))*uintptr(t.bucketsize)))\r\n\t\tif !evacuated(oldb) {\r\n\t\t\tb = oldb\r\n\t\t}\r\n\t}\r\n\ttop := uint8(hash >> (ptrSize*8 - 8))\r\n\tif top < minTopHash {\r\n\t\ttop += minTopHash\r\n\t}\r\n\tfor {\r\n\t\tfor i := uintptr(0); i < bucketCnt; i++ {\r\n\t\t\tif b.tophash[i] != top {\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\tk := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\r\n\t\t\tif t.indirectkey {\r\n\t\t\t\tk = *((*unsafe.Pointer)(k))\r\n\t\t\t}\r\n\t\t\tif alg.equal(key, k) {\r\n\t\t\t\tv := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\r\n\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\tv = *((*unsafe.Pointer)(v))\r\n\t\t\t\t}\r\n\t\t\t\treturn v, true\r\n\t\t\t}\r\n\t\t}\r\n\t\tb = b.overflow(t)\r\n\t\tif b == nil {\r\n\t\t\treturn unsafe.Pointer(t.elem.zero), false\r\n\t\t}\r\n\t}\r\n}\r\n \r\n// 这个是用来遍历map,  for k,v := range m{}\r\nfunc mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {\r\n\tif h == nil || h.count == 0 {\r\n\t\treturn nil, nil\r\n\t}\r\n\talg := t.key.alg\r\n\thash := alg.hash(key, uintptr(h.hash0))\r\n\tm := uintptr(1)<<h.B - 1\r\n\tb := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))\r\n\tif c := h.oldbuckets; c != nil {\r\n\t\toldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&(m>>1))*uintptr(t.bucketsize)))\r\n\t\tif !evacuated(oldb) {\r\n\t\t\tb = oldb\r\n\t\t}\r\n\t}\r\n\ttop := uint8(hash >> (ptrSize*8 - 8))\r\n\tif top < minTopHash {\r\n\t\ttop += minTopHash\r\n\t}\r\n\tfor {\r\n\t\tfor i := uintptr(0); i < bucketCnt; i++ {\r\n\t\t\tif b.tophash[i] != top {\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\tk := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\r\n\t\t\tif t.indirectkey {\r\n\t\t\t\tk = *((*unsafe.Pointer)(k))\r\n\t\t\t}\r\n\t\t\tif alg.equal(key, k) {\r\n\t\t\t\tv := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\r\n\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\tv = *((*unsafe.Pointer)(v))\r\n\t\t\t\t}\r\n\t\t\t\treturn k, v\r\n\t\t\t}\r\n\t\t}\r\n\t\tb = b.overflow(t)\r\n\t\tif b == nil {\r\n\t\t\treturn nil, nil\r\n\t\t}\r\n\t}\r\n}\r\n \r\n//map分配函数\r\nfunc mapassign1(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {\r\n\tif h == nil {\r\n\t\tpanic(\"assignment to entry in nil map\")\r\n\t}\r\n\tif raceenabled {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&t))\r\n\t\tpc := funcPC(mapassign1)\r\n\t\tracewritepc(unsafe.Pointer(h), callerpc, pc)\r\n\t\traceReadObjectPC(t.key, key, callerpc, pc)\r\n\t\traceReadObjectPC(t.elem, val, callerpc, pc)\r\n\t}\r\n \r\n\talg := t.key.alg\r\n\thash := alg.hash(key, uintptr(h.hash0))\r\n \r\n\tif h.buckets == nil {\r\n\t\tif checkgc {\r\n\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t}\r\n\t\th.buckets = newarray(t.bucket, 1)\r\n\t}\r\n \r\nagain:\r\n\tbucket := hash & (uintptr(1)<<h.B - 1)\r\n\tif h.oldbuckets != nil {\r\n\t\tgrowWork(t, h, bucket)\r\n\t}\r\n\tb := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))\r\n\ttop := uint8(hash >> (ptrSize*8 - 8))\r\n\tif top < minTopHash {\r\n\t\ttop += minTopHash\r\n\t}\r\n \r\n\tvar inserti *uint8\r\n\tvar insertk unsafe.Pointer\r\n\tvar insertv unsafe.Pointer\r\n\tfor {\r\n\t\tfor i := uintptr(0); i < bucketCnt; i++ {\r\n\t\t\tif b.tophash[i] != top {\r\n\t\t\t\tif b.tophash[i] == empty && inserti == nil {\r\n\t\t\t\t\tinserti = &b.tophash[i]\r\n\t\t\t\t\tinsertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\r\n\t\t\t\t\tinsertv = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\r\n\t\t\t\t}\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\tk := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\r\n\t\t\tk2 := k\r\n\t\t\tif t.indirectkey {\r\n\t\t\t\tk2 = *((*unsafe.Pointer)(k2))\r\n\t\t\t}\r\n\t\t\tif !alg.equal(key, k2) {\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\t// already have a mapping for key.  Update it.\r\n\t\t\ttypedmemmove(t.key, k2, key)\r\n\t\t\tv := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\r\n\t\t\tv2 := v\r\n\t\t\tif t.indirectvalue {\r\n\t\t\t\tv2 = *((*unsafe.Pointer)(v2))\r\n\t\t\t}\r\n\t\t\ttypedmemmove(t.elem, v2, val)\r\n\t\t\treturn\r\n\t\t}\r\n\t\tovf := b.overflow(t)\r\n\t\tif ovf == nil {\r\n\t\t\tbreak\r\n\t\t}\r\n\t\tb = ovf\r\n\t}\r\n \r\n\t// did not find mapping for key.  Allocate new cell & add entry.\r\n\tif float32(h.count) >= loadFactor*float32((uintptr(1)<<h.B)) && h.count >= bucketCnt {\r\n\t\thashGrow(t, h)\r\n\t\tgoto again // Growing the table invalidates everything, so try again\r\n\t}\r\n \r\n\tif inserti == nil {\r\n\t\t// all current buckets are full, allocate a new one.\r\n\t\tif checkgc {\r\n\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t}\r\n\t\tnewb := (*bmap)(newobject(t.bucket))\r\n\t\th.setoverflow(t, b, newb)\r\n\t\tinserti = &newb.tophash[0]\r\n\t\tinsertk = add(unsafe.Pointer(newb), dataOffset)\r\n\t\tinsertv = add(insertk, bucketCnt*uintptr(t.keysize))\r\n\t}\r\n \r\n\t// store new key/value at insert position\r\n\tif t.indirectkey {\r\n\t\tif checkgc {\r\n\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t}\r\n\t\tkmem := newobject(t.key)\r\n\t\t*(*unsafe.Pointer)(insertk) = kmem\r\n\t\tinsertk = kmem\r\n\t}\r\n\tif t.indirectvalue {\r\n\t\tif checkgc {\r\n\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t}\r\n\t\tvmem := newobject(t.elem)\r\n\t\t*(*unsafe.Pointer)(insertv) = vmem\r\n\t\tinsertv = vmem\r\n\t}\r\n\ttypedmemmove(t.key, insertk, key)\r\n\ttypedmemmove(t.elem, insertv, val)\r\n\t*inserti = top\r\n\th.count++\r\n}\r\n \r\n //map key的删除，跟kv地址和大小 清理内存，把对应的key的tophash 置0\r\nfunc mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {\r\n\tif raceenabled && h != nil {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&t))\r\n\t\tpc := funcPC(mapdelete)\r\n\t\tracewritepc(unsafe.Pointer(h), callerpc, pc)\r\n\t\traceReadObjectPC(t.key, key, callerpc, pc)\r\n\t}\r\n\tif h == nil || h.count == 0 {\r\n\t\treturn\r\n\t}\r\n\talg := t.key.alg\r\n\thash := alg.hash(key, uintptr(h.hash0))\r\n\tbucket := hash & (uintptr(1)<<h.B - 1)\r\n\tif h.oldbuckets != nil {\r\n\t\tgrowWork(t, h, bucket)\r\n\t}\r\n\tb := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))\r\n\ttop := uint8(hash >> (ptrSize*8 - 8))\r\n\tif top < minTopHash {\r\n\t\ttop += minTopHash\r\n\t}\r\n\tfor {\r\n\t\tfor i := uintptr(0); i < bucketCnt; i++ {\r\n\t\t\tif b.tophash[i] != top {\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\tk := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\r\n\t\t\tk2 := k\r\n\t\t\tif t.indirectkey {\r\n\t\t\t\tk2 = *((*unsafe.Pointer)(k2))\r\n\t\t\t}\r\n\t\t\tif !alg.equal(key, k2) {\r\n\t\t\t\tcontinue\r\n\t\t\t}\r\n\t\t\tmemclr(k, uintptr(t.keysize))\r\n\t\t\tv := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*uintptr(t.keysize) + i*uintptr(t.valuesize))\r\n\t\t\tmemclr(v, uintptr(t.valuesize))\r\n\t\t\tb.tophash[i] = empty\r\n\t\t\th.count--\r\n\t\t\treturn\r\n\t\t}\r\n\t\tb = b.overflow(t)\r\n\t\tif b == nil {\r\n\t\t\treturn\r\n\t\t}\r\n\t}\r\n}\r\n \r\nfunc mapiterinit(t *maptype, h *hmap, it *hiter) {\r\n\t// 清空迭代器的所有指针\r\n\tit.key = nil\r\n\tit.value = nil\r\n\tit.t = nil\r\n\tit.h = nil\r\n\tit.buckets = nil\r\n\tit.bptr = nil\r\n\tit.overflow[0] = nil\r\n\tit.overflow[1] = nil\r\n \r\n\tif raceenabled && h != nil {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&t))\r\n\t\tracereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))\r\n\t}\r\n \r\n\tif h == nil || h.count == 0 {\r\n\t\tit.key = nil\r\n\t\tit.value = nil\r\n\t\treturn\r\n\t}\r\n \r\n\tif unsafe.Sizeof(hiter{})/ptrSize != 12 {\r\n\t\tthrow(\"hash_iter size incorrect\") // see ../../cmd/gc/reflect.c\r\n\t}\r\n\tit.t = t\r\n\tit.h = h\r\n \r\n\t// grab snapshot of bucket state\r\n\tit.B = h.B\r\n\tit.buckets = h.buckets\r\n\tif t.bucket.kind&kindNoPointers != 0 {\r\n\t\t//在迭代时，分配当前的切片并记录当前和之前的指针，可以保证相关的buckets一直存活，即使哈希表或overflow buckets一致在变化\r\n\t\th.createOverflow()\r\n\t\tit.overflow = *h.overflow\r\n\t}\r\n \r\n\t// 随机开始迭代，所以go的map迭代是无序的\r\n\tr := uintptr(fastrand1())\r\n\tif h.B > 31-bucketCntBits {\r\n\t\tr += uintptr(fastrand1()) << 31\r\n\t}\r\n\tit.startBucket = r & (uintptr(1)<<h.B - 1)\r\n\tit.offset = uint8(r >> h.B & (bucketCnt - 1))\r\n \r\n\t// iterator state\r\n\tit.bucket = it.startBucket\r\n\tit.wrapped = false\r\n\tit.bptr = nil\r\n \r\n\t// Remember we have an iterator.\r\n\t// Can run concurrently with another hash_iter_init().\r\n\tif old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {\r\n\t\tatomicor8(&h.flags, iterator|oldIterator)\r\n\t}\r\n \r\n\tmapiternext(it)\r\n}\r\n \r\nfunc mapiternext(it *hiter) {\r\n\th := it.h\r\n\tif raceenabled {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&it))\r\n\t\tracereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))\r\n\t}\r\n\tt := it.t\r\n\tbucket := it.bucket\r\n\tb := it.bptr\r\n\ti := it.i\r\n\tcheckBucket := it.checkBucket\r\n\talg := t.key.alg\r\n \r\nnext:\r\n\tif b == nil {\r\n\t\tif bucket == it.startBucket && it.wrapped {\r\n\t\t\t// end of iteration\r\n\t\t\tit.key = nil\r\n\t\t\tit.value = nil\r\n\t\t\treturn\r\n\t\t}\r\n\t\tif h.oldbuckets != nil && it.B == h.B {\r\n\t\t\t//在增长且未完成的时候去迭代，只能返回旧的，必然啊\r\n\t\t\toldbucket := bucket & (uintptr(1)<<(it.B-1) - 1)\r\n\t\t\tb = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))\r\n\t\t\tif !evacuated(b) {\r\n\t\t\t\tcheckBucket = bucket\r\n\t\t\t} else {\r\n\t\t\t\tb = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))\r\n\t\t\t\tcheckBucket = noCheck\r\n\t\t\t}\r\n\t\t} else {\r\n\t\t\tb = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))\r\n\t\t\tcheckBucket = noCheck\r\n\t\t}\r\n\t\tbucket++\r\n\t\tif bucket == uintptr(1)<<it.B {\r\n\t\t\tbucket = 0\r\n\t\t\tit.wrapped = true\r\n\t\t}\r\n\t\ti = 0\r\n\t}\r\n\tfor ; i < bucketCnt; i++ {\r\n\t\toffi := (i + it.offset) & (bucketCnt - 1)\r\n\t\tk := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))\r\n\t\tv := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))\r\n\t\tif b.tophash[offi] != empty && b.tophash[offi] != evacuatedEmpty {\r\n\t\t\tif checkBucket != noCheck {\r\n\t\t\t\t//对正在增长且未完成的时候，会错过一些其他的key\r\n\t\t\t\tk2 := k\r\n\t\t\t\tif t.indirectkey {\r\n\t\t\t\t\tk2 = *((*unsafe.Pointer)(k2))\r\n\t\t\t\t}\r\n\t\t\t\tif t.reflexivekey || alg.equal(k2, k2) {\r\n\t\t\t\t\t// If the item in the oldbucket is not destined for\r\n\t\t\t\t\t// the current new bucket in the iteration, skip it.\r\n\t\t\t\t\thash := alg.hash(k2, uintptr(h.hash0))\r\n\t\t\t\t\tif hash&(uintptr(1)<<it.B-1) != checkBucket {\r\n\t\t\t\t\t\tcontinue\r\n\t\t\t\t\t}\r\n\t\t\t\t} else {\r\n                                         //哈希不能重复，在散列过程中需要一个可重复的随机的选择决定方向，使用tophash的低位去决定这个方向、这就是为什么需要两个散列值evacuatedX&evacuatedY，他们的低位是不同的\r\n\t\t\t\t\tif checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {\r\n\t\t\t\t\t\tcontinue\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tif b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY {\r\n\t\t\t\t// 最佳选择\r\n\t\t\t\tif t.indirectkey {\r\n\t\t\t\t\tk = *((*unsafe.Pointer)(k))\r\n\t\t\t\t}\r\n\t\t\t\tit.key = k\r\n\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\tv = *((*unsafe.Pointer)(v))\r\n\t\t\t\t}\r\n\t\t\t\tit.value = v\r\n\t\t\t} else {\r\n\t\t\t\t//迭代开始时，map已经增长了，最佳的数据可能在别处\r\n\t\t\t\t// The golden data for this key is now somewhere else.\r\n\t\t\t\tk2 := k\r\n\t\t\t\tif t.indirectkey {\r\n\t\t\t\t\tk2 = *((*unsafe.Pointer)(k2))\r\n\t\t\t\t}\r\n\t\t\t\tif t.reflexivekey || alg.equal(k2, k2) {\r\n\t\t\t\t\t// 校验当前数据的哈希表\r\n\t\t\t\t\t// 这些代码主要是处理被更新，删除，或者删除后重新添加的，需要重新计算获取这个key\r\n\t\t\t\t\trk, rv := mapaccessK(t, h, k2)\r\n\t\t\t\t\tif rk == nil {\r\n\t\t\t\t\t\tcontinue // key删除了\r\n\t\t\t\t\t}\r\n\t\t\t\t\tit.key = rk\r\n\t\t\t\t\tit.value = rv\r\n\t\t\t\t} else {\r\n\t\t\t\t\t// if key!=key then the entry can't be deleted or\r\n\t\t\t\t\t// updated, so we can just return it.  That's lucky for\r\n\t\t\t\t\t// us because when key!=key we can't look it up\r\n\t\t\t\t\t// successfully in the current table.\r\n\t\t\t\t\tit.key = k2\r\n\t\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\t\tv = *((*unsafe.Pointer)(v))\r\n\t\t\t\t\t}\r\n\t\t\t\t\tit.value = v\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\tit.bucket = bucket\r\n\t\t\tit.bptr = b\r\n\t\t\tit.i = i + 1\r\n\t\t\tit.checkBucket = checkBucket\r\n\t\t\treturn\r\n\t\t}\r\n\t}\r\n\tb = b.overflow(t)\r\n\ti = 0\r\n\tgoto next\r\n}\r\n \r\nfunc hashGrow(t *maptype, h *hmap) {\r\n\tif h.oldbuckets != nil {\r\n\t\tthrow(\"evacuation not done in time\")\r\n\t}\r\n\toldbuckets := h.buckets\r\n\tif checkgc {\r\n\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t}\r\n\tnewbuckets := newarray(t.bucket, uintptr(1)<<(h.B+1))\r\n\tflags := h.flags &^ (iterator | oldIterator)\r\n\tif h.flags&iterator != 0 {\r\n\t\tflags |= oldIterator\r\n\t}\r\n\t// commit the grow (atomic wrt gc)\r\n\th.B++\r\n\th.flags = flags\r\n\th.oldbuckets = oldbuckets\r\n\th.buckets = newbuckets\r\n\th.nevacuate = 0\r\n \r\n\tif h.overflow != nil {\r\n\t\t// Promote current overflow buckets to the old generation.\r\n\t\tif h.overflow[1] != nil {\r\n\t\t\tthrow(\"overflow is not nil\")\r\n\t\t}\r\n\t\th.overflow[1] = h.overflow[0]\r\n\t\th.overflow[0] = nil\r\n\t}\r\n \r\n\t// the actual copying of the hash table data is done incrementally\r\n\t// by growWork() and evacuate().\r\n}\r\n \r\nfunc growWork(t *maptype, h *hmap, bucket uintptr) {\r\n\tnoldbuckets := uintptr(1) << (h.B - 1)\r\n \r\n\t// make sure we evacuate the oldbucket corresponding\r\n\t// to the bucket we're about to use\r\n\tevacuate(t, h, bucket&(noldbuckets-1))\r\n \r\n\t// evacuate one more oldbucket to make progress on growing\r\n\tif h.oldbuckets != nil {\r\n\t\tevacuate(t, h, h.nevacuate)\r\n\t}\r\n}\r\n \r\nfunc evacuate(t *maptype, h *hmap, oldbucket uintptr) {\r\n\tb := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))\r\n\tnewbit := uintptr(1) << (h.B - 1)\r\n\talg := t.key.alg\r\n\tif !evacuated(b) {\r\n\t\t// TODO: reuse overflow buckets instead of using new ones, if there\r\n\t\t// is no iterator using the old buckets.  (If !oldIterator.)\r\n \r\n\t\tx := (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))\r\n\t\ty := (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))\r\n\t\txi := 0\r\n\t\tyi := 0\r\n\t\txk := add(unsafe.Pointer(x), dataOffset)\r\n\t\tyk := add(unsafe.Pointer(y), dataOffset)\r\n\t\txv := add(xk, bucketCnt*uintptr(t.keysize))\r\n\t\tyv := add(yk, bucketCnt*uintptr(t.keysize))\r\n\t\tfor ; b != nil; b = b.overflow(t) {\r\n\t\t\tk := add(unsafe.Pointer(b), dataOffset)\r\n\t\t\tv := add(k, bucketCnt*uintptr(t.keysize))\r\n\t\t\tfor i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {\r\n\t\t\t\ttop := b.tophash[i]\r\n\t\t\t\tif top == empty {\r\n\t\t\t\t\tb.tophash[i] = evacuatedEmpty\r\n\t\t\t\t\tcontinue\r\n\t\t\t\t}\r\n\t\t\t\tif top < minTopHash {\r\n\t\t\t\t\tthrow(\"bad map state\")\r\n\t\t\t\t}\r\n\t\t\t\tk2 := k\r\n\t\t\t\tif t.indirectkey {\r\n\t\t\t\t\tk2 = *((*unsafe.Pointer)(k2))\r\n\t\t\t\t}\r\n\t\t\t\t// Compute hash to make our evacuation decision (whether we need\r\n\t\t\t\t// to send this key/value to bucket x or bucket y).\r\n\t\t\t\thash := alg.hash(k2, uintptr(h.hash0))\r\n\t\t\t\tif h.flags&iterator != 0 {\r\n\t\t\t\t\tif !t.reflexivekey && !alg.equal(k2, k2) {\r\n\t\t\t\t\t\t// If key != key (NaNs), then the hash could be (and probably\r\n\t\t\t\t\t\t// will be) entirely different from the old hash.  Moreover,\r\n\t\t\t\t\t\t// it isn't reproducible.  Reproducibility is required in the\r\n\t\t\t\t\t\t// presence of iterators, as our evacuation decision must\r\n\t\t\t\t\t\t// match whatever decision the iterator made.\r\n\t\t\t\t\t\t// Fortunately, we have the freedom to send these keys either\r\n\t\t\t\t\t\t// way.  Also, tophash is meaningless for these kinds of keys.\r\n\t\t\t\t\t\t// We let the low bit of tophash drive the evacuation decision.\r\n\t\t\t\t\t\t// We recompute a new random tophash for the next level so\r\n\t\t\t\t\t\t// these keys will get evenly distributed across all buckets\r\n\t\t\t\t\t\t// after multiple grows.\r\n\t\t\t\t\t\tif (top & 1) != 0 {\r\n\t\t\t\t\t\t\thash |= newbit\r\n\t\t\t\t\t\t} else {\r\n\t\t\t\t\t\t\thash &^= newbit\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t\ttop = uint8(hash >> (ptrSize*8 - 8))\r\n\t\t\t\t\t\tif top < minTopHash {\r\n\t\t\t\t\t\t\ttop += minTopHash\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t\tif (hash & newbit) == 0 {\r\n\t\t\t\t\tb.tophash[i] = evacuatedX\r\n\t\t\t\t\tif xi == bucketCnt {\r\n\t\t\t\t\t\tif checkgc {\r\n\t\t\t\t\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t\tnewx := (*bmap)(newobject(t.bucket))\r\n\t\t\t\t\t\th.setoverflow(t, x, newx)\r\n\t\t\t\t\t\tx = newx\r\n\t\t\t\t\t\txi = 0\r\n\t\t\t\t\t\txk = add(unsafe.Pointer(x), dataOffset)\r\n\t\t\t\t\t\txv = add(xk, bucketCnt*uintptr(t.keysize))\r\n\t\t\t\t\t}\r\n\t\t\t\t\tx.tophash[xi] = top\r\n\t\t\t\t\tif t.indirectkey {\r\n\t\t\t\t\t\t*(*unsafe.Pointer)(xk) = k2 // copy pointer\r\n\t\t\t\t\t} else {\r\n\t\t\t\t\t\ttypedmemmove(t.key, xk, k) // copy value\r\n\t\t\t\t\t}\r\n\t\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\t\t*(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v)\r\n\t\t\t\t\t} else {\r\n\t\t\t\t\t\ttypedmemmove(t.elem, xv, v)\r\n\t\t\t\t\t}\r\n\t\t\t\t\txi++\r\n\t\t\t\t\txk = add(xk, uintptr(t.keysize))\r\n\t\t\t\t\txv = add(xv, uintptr(t.valuesize))\r\n\t\t\t\t} else {\r\n\t\t\t\t\tb.tophash[i] = evacuatedY\r\n\t\t\t\t\tif yi == bucketCnt {\r\n\t\t\t\t\t\tif checkgc {\r\n\t\t\t\t\t\t\tmemstats.next_gc = memstats.heap_alloc\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t\tnewy := (*bmap)(newobject(t.bucket))\r\n\t\t\t\t\t\th.setoverflow(t, y, newy)\r\n\t\t\t\t\t\ty = newy\r\n\t\t\t\t\t\tyi = 0\r\n\t\t\t\t\t\tyk = add(unsafe.Pointer(y), dataOffset)\r\n\t\t\t\t\t\tyv = add(yk, bucketCnt*uintptr(t.keysize))\r\n\t\t\t\t\t}\r\n\t\t\t\t\ty.tophash[yi] = top\r\n\t\t\t\t\tif t.indirectkey {\r\n\t\t\t\t\t\t*(*unsafe.Pointer)(yk) = k2\r\n\t\t\t\t\t} else {\r\n\t\t\t\t\t\ttypedmemmove(t.key, yk, k)\r\n\t\t\t\t\t}\r\n\t\t\t\t\tif t.indirectvalue {\r\n\t\t\t\t\t\t*(*unsafe.Pointer)(yv) = *(*unsafe.Pointer)(v)\r\n\t\t\t\t\t} else {\r\n\t\t\t\t\t\ttypedmemmove(t.elem, yv, v)\r\n\t\t\t\t\t}\r\n\t\t\t\t\tyi++\r\n\t\t\t\t\tyk = add(yk, uintptr(t.keysize))\r\n\t\t\t\t\tyv = add(yv, uintptr(t.valuesize))\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\t// Unlink the overflow buckets & clear key/value to help GC.\r\n\t\tif h.flags&oldIterator == 0 {\r\n\t\t\tb = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))\r\n\t\t\tmemclr(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)\r\n\t\t}\r\n\t}\r\n \r\n\t// Advance evacuation mark\r\n\tif oldbucket == h.nevacuate {\r\n\t\th.nevacuate = oldbucket + 1\r\n\t\tif oldbucket+1 == newbit { // newbit == # of oldbuckets\r\n\t\t\t// Growing is all done.  Free old main bucket array.\r\n\t\t\th.oldbuckets = nil\r\n\t\t\t// Can discard old overflow buckets as well.\r\n\t\t\t// If they are still referenced by an iterator,\r\n\t\t\t// then the iterator holds a pointers to the slice.\r\n\t\t\tif h.overflow != nil {\r\n\t\t\t\th.overflow[1] = nil\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}\r\n \r\nfunc ismapkey(t *_type) bool {\r\n\treturn t.alg.hash != nil\r\n}\r\n \r\n// Reflect stubs.  Called from ../reflect/asm_*.s\r\n \r\n//go:linkname reflect_makemap reflect.makemap\r\nfunc reflect_makemap(t *maptype) *hmap {\r\n\treturn makemap(t, 0, nil, nil)\r\n}\r\n \r\n//go:linkname reflect_mapaccess reflect.mapaccess\r\nfunc reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {\r\n\tval, ok := mapaccess2(t, h, key)\r\n\tif !ok {\r\n\t\t// reflect wants nil for a missing element\r\n\t\tval = nil\r\n\t}\r\n\treturn val\r\n}\r\n \r\n//go:linkname reflect_mapassign reflect.mapassign\r\nfunc reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {\r\n\tmapassign1(t, h, key, val)\r\n}\r\n \r\n//go:linkname reflect_mapdelete reflect.mapdelete\r\nfunc reflect_mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {\r\n\tmapdelete(t, h, key)\r\n}\r\n \r\n//go:linkname reflect_mapiterinit reflect.mapiterinit\r\nfunc reflect_mapiterinit(t *maptype, h *hmap) *hiter {\r\n\tit := new(hiter)\r\n\tmapiterinit(t, h, it)\r\n\treturn it\r\n}\r\n \r\n//go:linkname reflect_mapiternext reflect.mapiternext\r\nfunc reflect_mapiternext(it *hiter) {\r\n\tmapiternext(it)\r\n}\r\n \r\n//go:linkname reflect_mapiterkey reflect.mapiterkey\r\nfunc reflect_mapiterkey(it *hiter) unsafe.Pointer {\r\n\treturn it.key\r\n}\r\n \r\n//go:linkname reflect_maplen reflect.maplen\r\nfunc reflect_maplen(h *hmap) int {\r\n\tif h == nil {\r\n\t\treturn 0\r\n\t}\r\n\tif raceenabled {\r\n\t\tcallerpc := getcallerpc(unsafe.Pointer(&h))\r\n\t\tracereadpc(unsafe.Pointer(h), callerpc, funcPC(reflect_maplen))\r\n\t}\r\n\treturn h.count\r\n}\r\n \r\n//go:linkname reflect_ismapkey reflect.ismapkey\r\nfunc reflect_ismapkey(t *_type) bool {\r\n\treturn ismapkey(t)\r\n}"},"comment":{"url":"https://api.github.com/repos/eastany/eastany.github.com/issues/comments/103892995","html_url":"https://github.com/eastany/eastany.github.com/issues/40#issuecomment-103892995","issue_url":"https://api.github.com/repos/eastany/eastany.github.com/issues/40","id":103892995,"user":{"login":"eastany","id":4279344,"avatar_url":"https://avatars.githubusercontent.com/u/4279344?v=3","gravatar_id":"","url":"https://api.github.com/users/eastany","html_url":"https://github.com/eastany","followers_url":"https://api.github.com/users/eastany/followers","following_url":"https://api.github.com/users/eastany/following{/other_user}","gists_url":"https://api.github.com/users/eastany/gists{/gist_id}","starred_url":"https://api.github.com/users/eastany/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/eastany/subscriptions","organizations_url":"https://api.github.com/users/eastany/orgs","repos_url":"https://api.github.com/users/eastany/repos","events_url":"https://api.github.com/users/eastany/events{/privacy}","received_events_url":"https://api.github.com/users/eastany/received_events","type":"User","site_admin":false},"created_at":"2015-05-20T13:42:36Z","updated_at":"2015-05-20T13:42:36Z","body":"对于map的使用，需要注意的几点：\r\n1.避免k,v的过渡长久持有，尤其是在大数据量的时候\r\n2.因为map设计是非线程安全的，所以如果需要可使用读写锁去实现，自己斟酌。如在遍历(读)的同时去新增(写)，可能遍历不到，等等。\r\n3.需要更新value的时候使用k去索引\r\n。。。明天看完再补充"}}