-
Notifications
You must be signed in to change notification settings - Fork 2
/
go_map.html
347 lines (327 loc) · 25.5 KB
/
go_map.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2021-01-23 Sat 18:03 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>GO Map内部实现</title>
<meta name="generator" content="Org mode" />
<link rel="stylesheet" type="text/css" href="./css/org-css.css"/>
<link rel="stylesheet" type="text/css" href="./css/gitalk.css"/> <script src="./js/gitalk.min.js"></script>
</head>
<body>
<div id="org-div-home-and-up">
<a accesskey="h" href="index.html"> UP </a>
|
<a accesskey="H" href="index.html"> HOME </a>
</div><div id="content">
<h1 class="title">GO Map内部实现</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#orgc7c8cab">1. go map操作</a></li>
<li><a href="#org848853a">2. 内部实现</a></li>
<li><a href="#orgbdc0c0b">3. 总结</a></li>
</ul>
</div>
</div>
<div id="outline-container-orgc7c8cab" class="outline-2">
<h2 id="orgc7c8cab"><span class="section-number-2">1</span> go map操作</h2>
<div class="outline-text-2" id="text-1">
<p>
map类型不管在哪个语言中都是很常用的类型，它具有O(1)的存取速度。十分高效，虽然内存可能会多占用一点。但是也是非常值得的事情，网上的文章大多是讨论slice的内部结构，很少讨论map，不过map跟slice同作为 <code>引用类型</code> 看看内部实现也是很有必要的。map的操作主要有以下内容：
</p>
<div class="org-src-container">
<pre class="src src-go"><span style="color: #676E95;">//</span><span style="color: #676E95;">创建map</span>
<span style="color: #ffcb6b;">a</span> := <span style="color: #82aaff;">make</span>(<span style="color: #89DDFF;">map</span>[<span style="color: #c792ea;">string</span>]<span style="color: #c792ea;">string</span>)
<span style="color: #676E95;">//</span><span style="color: #676E95;">存入</span>
a[<span style="color: #c3e88d;">"first"</span>] = <span style="color: #c3e88d;">"first"</span>
<span style="color: #676E95;">//</span><span style="color: #676E95;">读取</span>
fmt.<span style="color: #82aaff;">Println</span>(a[<span style="color: #c3e88d;">"first"</span>])
</pre>
</div>
<p>
不是所有的key都能作为map的key类型，只有能够比较的类型才能作为key类型。所以例如切片，函数，map类型是不能作为map的key类型的。具体可见<a href="https://blog.golang.org/go-maps-in-action">https://blog.golang.org/go-maps-in-action</a>。
在go语言中，map是非线程安全的，也就是说go中的map类型不能放在多个goroutine中，只能自己维护线程安全。
</p>
</div>
</div>
<div id="outline-container-org848853a" class="outline-2">
<h2 id="org848853a"><span class="section-number-2">2</span> 内部实现</h2>
<div class="outline-text-2" id="text-2">
<p>
在实现map的过程中，最需要注意的就是 <code>装载因子</code> ,当它过大时需要增长map的空间，重新映射值到新的空间。
源码位置: $GOROOT/src/runtime/hashmap.go
</p>
<div class="org-src-container">
<pre class="src src-go"><span style="color: #89DDFF;">type</span> <span style="color: #c792ea;">hmap</span> <span style="color: #89DDFF;">struct</span> {
<span style="color: #676E95;">// </span><span style="color: #676E95;">Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">../reflect/type.go. Don't change this structure without also changing that code!</span>
count <span style="color: #c792ea;">int</span> <span style="color: #676E95;">// </span><span style="color: #676E95;"># live cells == size of map. Must be first (used by len() builtin) map中key的个数，被len()函数使用。</span>
flags <span style="color: #c792ea;">uint8</span>
B <span style="color: #c792ea;">uint8</span> <span style="color: #676E95;">// </span><span style="color: #676E95;">log_2 of # of buckets (can hold up to loadFactor * 2^B items) </span>
hash0 <span style="color: #c792ea;">uint32</span> <span style="color: #676E95;">// </span><span style="color: #676E95;">hash seed</span>
buckets <span style="color: #c792ea;">unsafe.Pointer</span> <span style="color: #676E95;">// </span><span style="color: #676E95;">array of 2^B Buckets. may be nil if count==0.</span>
oldbuckets <span style="color: #c792ea;">unsafe.Pointer</span> <span style="color: #676E95;">// </span><span style="color: #676E95;">previous bucket array of half the size, non-nil only when growing</span>
nevacuate <span style="color: #c792ea;">uintptr</span> <span style="color: #676E95;">// </span><span style="color: #676E95;">progress counter for evacuation (buckets less than this have been evacuated)</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">If both key and value do not contain pointers and are inline, then we mark bucket</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">type as containing no pointers. This avoids scanning such maps.</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">However, bmap.overflow is a pointer. In order to keep overflow buckets</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">alive, we store pointers to all overflow buckets in hmap.overflow.</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">Overflow is used only if key and value do not contain pointers.</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">overflow[0] contains overflow buckets for hmap.buckets.</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">overflow[1] contains overflow buckets for hmap.oldbuckets.</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">The first indirection allows us to reduce static size of hmap.</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">The second indirection allows to store a pointer to the slice in hiter.</span>
overflow *[2]*[]*<span style="color: #c792ea;">bmap</span>
}
</pre>
</div>
<p>
这是源码中map的header,其中buckets主要存放数据，结构如下图所示:
</p>
<div id="org644ca97" class="figure">
<p><img src="..//image/2016-08-18-162914_462x441_scrot.png" alt="2016-08-18-162914_462x441_scrot.png" />
</p>
</div>
<p>
首先buckets指向一个数组的bucket，取值的时候。先对key进行hash算法得到的值假若为h,用h对len(buckets)取余为hl那么就在buckets[hl]这一个链表中找。
</p>
<p>
对于一个bucket，最多存放8个kv对，以此存放key的hash值的高八位，八个key，八个value，指向下一个bucket的指针。如下图所示:
<img src="../image/2016-08-19-141335_329x487_scrot.png" alt="2016-08-19-141335_329x487_scrot.png" />
这里key跟key放在一起而不是形成k|v|k|v的原因是减少内存对齐的内存消耗。
</p>
<p>
当map中的kv对越来越多的时候，会造成buckets的重新分配，新的buckets的大小是原来大小的2倍。但是老的buckets的值并不会立即移动到新buckets中来，而是等下一次存或者删除哪个bucket，就移动那一个bucket链。
</p>
<p>
访问map的源码:
</p>
<div class="org-src-container">
<pre class="src src-go"><span style="color: #676E95;">// </span><span style="color: #676E95;">mapaccess1 returns a pointer to h[key]. Never returns nil, instead</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">it will return a reference to the zero object for the value type if</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">the key is not in the map.</span>
<span style="color: #676E95;">// </span><span style="color: #d0bf8f;">NOTE</span><span style="color: #676E95;">: The returned pointer may keep the whole map live, so don't</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">hold onto it for very long.</span>
<span style="color: #89DDFF;">func</span> <span style="color: #82aaff;">mapaccess1</span>(<span style="color: #ffcb6b;">t</span> *<span style="color: #c792ea;">maptype</span>, <span style="color: #ffcb6b;">h</span> *<span style="color: #c792ea;">hmap</span>, <span style="color: #ffcb6b;">key</span> <span style="color: #c792ea;">unsafe.Pointer</span>) <span style="color: #c792ea;">unsafe.Pointer</span> {
<span style="color: #89DDFF;">if</span> raceenabled && h != <span style="color: #f78c6c;">nil</span> {
<span style="color: #ffcb6b;">callerpc</span> := <span style="color: #82aaff;">getcallerpc</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(&t))
<span style="color: #ffcb6b;">pc</span> := <span style="color: #82aaff;">funcPC</span>(mapaccess1)
<span style="color: #82aaff;">racereadpc</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(h), callerpc, pc)
<span style="color: #82aaff;">raceReadObjectPC</span>(t.key, key, callerpc, pc)
}
<span style="color: #89DDFF;">if</span> msanenabled && h != <span style="color: #f78c6c;">nil</span> {
<span style="color: #82aaff;">msanread</span>(key, t.key.size)
}
<span style="color: #89DDFF;">if</span> h == <span style="color: #f78c6c;">nil</span> || h.count == 0 {
<span style="color: #89DDFF;">return</span> unsafe.<span style="color: #82aaff;">Pointer</span>(&zeroVal[0])
}
<span style="color: #89DDFF;">if</span> h.flags&hashWriting != 0 {
<span style="color: #82aaff;">throw</span>(<span style="color: #c3e88d;">"concurrent map read and map write"</span>)
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">得到key的hash函数</span>
<span style="color: #ffcb6b;">alg</span> := t.key.alg
<span style="color: #ffcb6b;">hash</span> := alg.<span style="color: #82aaff;">hash</span>(key, <span style="color: #82aaff;">uintptr</span>(h.hash0))
<span style="color: #ffcb6b;">m</span> := <span style="color: #82aaff;">uintptr</span>(1)<<h.B - 1
<span style="color: #676E95;">//</span><span style="color: #676E95;">根据hash值对m取余找到对于的bucket</span>
<span style="color: #ffcb6b;">b</span> := (*bmap)(<span style="color: #82aaff;">add</span>(h.buckets, (hash&m)*<span style="color: #82aaff;">uintptr</span>(t.bucketsize)))
<span style="color: #89DDFF;">if</span> <span style="color: #ffcb6b;">c</span> := h.oldbuckets; c != <span style="color: #f78c6c;">nil</span> {
<span style="color: #676E95;">//</span><span style="color: #676E95;">如果老的bucket还没有迁移，在老的bucket里面找,</span>
<span style="color: #ffcb6b;">oldb</span> := (*bmap)(<span style="color: #82aaff;">add</span>(c, (hash&(m>>1))*<span style="color: #82aaff;">uintptr</span>(t.bucketsize)))
<span style="color: #89DDFF;">if</span> <span style="color: #89DDFF; font-weight: bold;">!</span><span style="color: #82aaff;">evacuated</span>(oldb) {
b = oldb
}
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">hash的高8位</span>
<span style="color: #ffcb6b;">top</span> := <span style="color: #82aaff;">uint8</span>(hash >> (sys.PtrSize*8 - 8))
<span style="color: #89DDFF;">if</span> top < minTopHash {
top += minTopHash
}
<span style="color: #89DDFF;">for</span> {
<span style="color: #89DDFF;">for</span> <span style="color: #ffcb6b;">i</span> := <span style="color: #82aaff;">uintptr</span>(0); i < bucketCnt; i++ {
<span style="color: #676E95;">//</span><span style="color: #676E95;">如果hash的高8位跟记录的不一样，就找下一个</span>
<span style="color: #89DDFF;">if</span> b.tophash[i] != top {
<span style="color: #89DDFF;">continue</span>
}
<span style="color: #ffcb6b;">k</span> := <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(b), dataOffset+i*<span style="color: #82aaff;">uintptr</span>(t.keysize))
<span style="color: #89DDFF;">if</span> t.indirectkey {
k = *((*unsafe.Pointer)(k))
}
<span style="color: #89DDFF;">if</span> alg.<span style="color: #82aaff;">equal</span>(key, k) {
<span style="color: #676E95;">//</span><span style="color: #676E95;">如果找到了同一个key，取出value.</span>
<span style="color: #ffcb6b;">v</span> := <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(b), dataOffset+bucketCnt*<span style="color: #82aaff;">uintptr</span>(t.keysize)+i*<span style="color: #82aaff;">uintptr</span>(t.valuesize))
<span style="color: #89DDFF;">if</span> t.indirectvalue {
v = *((*unsafe.Pointer)(v))
}
<span style="color: #89DDFF;">return</span> v
}
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">这个bucket没找到，找这个bucket链的下一个bucket</span>
b = b.<span style="color: #82aaff;">overflow</span>(t)
<span style="color: #89DDFF;">if</span> b == <span style="color: #f78c6c;">nil</span> {
<span style="color: #89DDFF;">return</span> unsafe.<span style="color: #82aaff;">Pointer</span>(&zeroVal[0])
}
}
}
</pre>
</div>
<p>
从map的读取代码中，我们可以看到map的buckets的结构跟前面说的一样.
</p>
<p>
map存值的源码:
</p>
<div class="org-src-container">
<pre class="src src-go"><span style="color: #89DDFF;">func</span> <span style="color: #82aaff;">mapassign1</span>(<span style="color: #ffcb6b;">t</span> *<span style="color: #c792ea;">maptype</span>, <span style="color: #ffcb6b;">h</span> *<span style="color: #c792ea;">hmap</span>, <span style="color: #ffcb6b;">key</span> <span style="color: #c792ea;">unsafe.Pointer</span>, <span style="color: #ffcb6b;">val</span> <span style="color: #c792ea;">unsafe.Pointer</span>) {
<span style="color: #89DDFF;">if</span> h == <span style="color: #f78c6c;">nil</span> {
<span style="color: #82aaff;">panic</span>(<span style="color: #82aaff;">plainError</span>(<span style="color: #c3e88d;">"assignment to entry in nil map"</span>))
}
<span style="color: #89DDFF;">if</span> raceenabled {
<span style="color: #ffcb6b;">callerpc</span> := <span style="color: #82aaff;">getcallerpc</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(&t))
<span style="color: #ffcb6b;">pc</span> := <span style="color: #82aaff;">funcPC</span>(mapassign1)
<span style="color: #82aaff;">racewritepc</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(h), callerpc, pc)
<span style="color: #82aaff;">raceReadObjectPC</span>(t.key, key, callerpc, pc)
<span style="color: #82aaff;">raceReadObjectPC</span>(t.elem, val, callerpc, pc)
}
<span style="color: #89DDFF;">if</span> msanenabled {
<span style="color: #82aaff;">msanread</span>(key, t.key.size)
<span style="color: #82aaff;">msanread</span>(val, t.elem.size)
}
<span style="color: #89DDFF;">if</span> h.flags&hashWriting != 0 {
<span style="color: #82aaff;">throw</span>(<span style="color: #c3e88d;">"concurrent map writes"</span>)
}
h.flags |= hashWriting
<span style="color: #676E95;">//</span><span style="color: #676E95;">得到key的hash函数</span>
<span style="color: #ffcb6b;">alg</span> := t.key.alg
<span style="color: #ffcb6b;">hash</span> := alg.<span style="color: #82aaff;">hash</span>(key, <span style="color: #82aaff;">uintptr</span>(h.hash0))
<span style="color: #676E95;">//</span><span style="color: #676E95;">如果buckets为空，则分配一个</span>
<span style="color: #89DDFF;">if</span> h.buckets == <span style="color: #f78c6c;">nil</span> {
h.buckets = <span style="color: #82aaff;">newarray</span>(t.bucket, 1)
}
<span style="color: #f78c6c;">again</span>:
<span style="color: #676E95;">//</span><span style="color: #676E95;">得到hash的低b位,等同于对buckets的大小取余</span>
<span style="color: #ffcb6b;">bucket</span> := hash & (<span style="color: #82aaff;">uintptr</span>(1)<<h.B - 1)
<span style="color: #676E95;">//</span><span style="color: #676E95;">如果老的bucket还没有迁移，则对老的bucket迁移</span>
<span style="color: #89DDFF;">if</span> h.oldbuckets != <span style="color: #f78c6c;">nil</span> {
<span style="color: #82aaff;">growWork</span>(t, h, bucket)
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">根据hash值的低b位找到对于的bucket</span>
<span style="color: #ffcb6b;">b</span> := (*bmap)(unsafe.<span style="color: #82aaff;">Pointer</span>(<span style="color: #82aaff;">uintptr</span>(h.buckets) + bucket*<span style="color: #82aaff;">uintptr</span>(t.bucketsize)))
<span style="color: #676E95;">//</span><span style="color: #676E95;">计算hash值的高8位</span>
<span style="color: #ffcb6b;">top</span> := <span style="color: #82aaff;">uint8</span>(hash >> (sys.PtrSize*8 - 8))
<span style="color: #89DDFF;">if</span> top < minTopHash {
top += minTopHash
}
<span style="color: #89DDFF;">var</span> <span style="color: #ffcb6b;">inserti</span> *<span style="color: #c792ea;">uint8</span>
<span style="color: #89DDFF;">var</span> <span style="color: #ffcb6b;">insertk</span> <span style="color: #c792ea;">unsafe.Pointer</span>
<span style="color: #89DDFF;">var</span> <span style="color: #ffcb6b;">insertv</span> <span style="color: #c792ea;">unsafe.Pointer</span>
<span style="color: #89DDFF;">for</span> {
<span style="color: #89DDFF;">for</span> <span style="color: #ffcb6b;">i</span> := <span style="color: #82aaff;">uintptr</span>(0); i < bucketCnt; i++ {
<span style="color: #89DDFF;">if</span> b.tophash[i] != top {
<span style="color: #89DDFF;">if</span> b.tophash[i] == empty && inserti == <span style="color: #f78c6c;">nil</span> {
<span style="color: #676E95;">//</span><span style="color: #676E95;">如果以后没有找到，这里先预留一个可以插入的位置</span>
inserti = &b.tophash[i]
insertk = <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(b), dataOffset+i*<span style="color: #82aaff;">uintptr</span>(t.keysize))
insertv = <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(b), dataOffset+bucketCnt*<span style="color: #82aaff;">uintptr</span>(t.keysize)+i*<span style="color: #82aaff;">uintptr</span>(t.valuesize))
}
<span style="color: #89DDFF;">continue</span>
}
<span style="color: #ffcb6b;">k</span> := <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(b), dataOffset+i*<span style="color: #82aaff;">uintptr</span>(t.keysize))
<span style="color: #ffcb6b;">k2</span> := k
<span style="color: #89DDFF;">if</span> t.indirectkey {
k2 = *((*unsafe.Pointer)(k2))
}
<span style="color: #89DDFF;">if</span> <span style="color: #89DDFF; font-weight: bold;">!</span>alg.<span style="color: #82aaff;">equal</span>(key, k2) {
<span style="color: #89DDFF;">continue</span>
}
<span style="color: #676E95;">// </span><span style="color: #676E95;">找到一个相同的key</span>
<span style="color: #676E95;">// </span><span style="color: #676E95;">already have a mapping for key. Update it.</span>
<span style="color: #89DDFF;">if</span> t.needkeyupdate {
<span style="color: #82aaff;">typedmemmove</span>(t.key, k2, key)
}
<span style="color: #ffcb6b;">v</span> := <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(b), dataOffset+bucketCnt*<span style="color: #82aaff;">uintptr</span>(t.keysize)+i*<span style="color: #82aaff;">uintptr</span>(t.valuesize))
<span style="color: #ffcb6b;">v2</span> := v
<span style="color: #89DDFF;">if</span> t.indirectvalue {
v2 = *((*unsafe.Pointer)(v2))
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">更新值</span>
<span style="color: #82aaff;">typedmemmove</span>(t.elem, v2, val)
<span style="color: #676E95;">//</span><span style="color: #676E95;">跳出循环到完成</span>
<span style="color: #89DDFF;">goto</span> <span style="color: #f78c6c;">done</span>
}
<span style="color: #ffcb6b;">ovf</span> := b.<span style="color: #82aaff;">overflow</span>(t)
<span style="color: #89DDFF;">if</span> ovf == <span style="color: #f78c6c;">nil</span> {
<span style="color: #89DDFF;">break</span>
}
b = ovf
}
<span style="color: #676E95;">// </span><span style="color: #676E95;">did not find mapping for key. Allocate new cell & add entry.</span>
<span style="color: #89DDFF;">if</span> <span style="color: #82aaff;">float32</span>(h.count) >= loadFactor*<span style="color: #82aaff;">float32</span>((<span style="color: #82aaff;">uintptr</span>(1)<<h.B)) && h.count >= bucketCnt {
<span style="color: #82aaff;">hashGrow</span>(t, h)
<span style="color: #89DDFF;">goto</span> <span style="color: #f78c6c;">again</span> <span style="color: #676E95;">// </span><span style="color: #676E95;">Growing the table invalidates everything, so try again</span>
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">没有找到可以插入的位置，分配一个</span>
<span style="color: #89DDFF;">if</span> inserti == <span style="color: #f78c6c;">nil</span> {
<span style="color: #676E95;">// </span><span style="color: #676E95;">all current buckets are full, allocate a new one.</span>
<span style="color: #ffcb6b;">newb</span> := (*bmap)(<span style="color: #82aaff;">newobject</span>(t.bucket))
h.<span style="color: #82aaff;">setoverflow</span>(t, b, newb)
inserti = &newb.tophash[0]
insertk = <span style="color: #82aaff;">add</span>(unsafe.<span style="color: #82aaff;">Pointer</span>(newb), dataOffset)
insertv = <span style="color: #82aaff;">add</span>(insertk, bucketCnt*<span style="color: #82aaff;">uintptr</span>(t.keysize))
}
<span style="color: #676E95;">// </span><span style="color: #676E95;">store new key/value at insert position</span>
<span style="color: #89DDFF;">if</span> t.indirectkey {
<span style="color: #ffcb6b;">kmem</span> := <span style="color: #82aaff;">newobject</span>(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
<span style="color: #89DDFF;">if</span> t.indirectvalue {
<span style="color: #ffcb6b;">vmem</span> := <span style="color: #82aaff;">newobject</span>(t.elem)
*(*unsafe.Pointer)(insertv) = vmem
insertv = vmem
}
<span style="color: #676E95;">//</span><span style="color: #676E95;">存kv</span>
<span style="color: #82aaff;">typedmemmove</span>(t.key, insertk, key)
<span style="color: #82aaff;">typedmemmove</span>(t.elem, insertv, val)
*inserti = top
h.count++
<span style="color: #f78c6c;">done</span>:
<span style="color: #89DDFF;">if</span> h.flags&hashWriting == 0 {
<span style="color: #82aaff;">throw</span>(<span style="color: #c3e88d;">"concurrent map writes"</span>)
}
h.flags &^= hashWriting
}
</pre>
</div>
<p>
其他的源码就不一一列举了, 有兴趣可以看runtime/hashmap.go。
</p>
</div>
</div>
<div id="outline-container-orgbdc0c0b" class="outline-2">
<h2 id="orgbdc0c0b"><span class="section-number-2">3</span> 总结</h2>
<div class="outline-text-2" id="text-3">
<p>
总的来说golang的map类型实现比较中规中矩，亮点是延迟移动bucket。一个bucket能存放8个kv对的设计也很有趣。感觉上综合了链表与数组的优点。
</p>
</div>
</div>
</div>
<div id="postamble" class="status">
<div id="gitalk" /> <script> var gitalk = new Gitalk({
clientID: 'f30e66bb5ab9089aa742',
clientSecret: '5d256d445447bd4db16540c2aab0e0884218ed12',
repo: 'guidao.github.io',
owner: 'guidao',
admin: ['guidao'],
id: location.pathname, // Ensure uniqueness and length less than 50
distractionFreeMode: false // Facebook-like distraction free mode
})
gitalk.render('gitalk') </script>
</div>
</body>
</html>