{"id":345611,"date":"2023-02-17T21:00:28","date_gmt":"2023-02-17T21:00:28","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=345611"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2023-02-17T21:00:28","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=345611","title":{"rendered":"<span>Hashmap(map) \u043f\u043e \u0432\u0435\u0440\u0441\u0438\u0438 Golang. \u0427\u0430\u0441\u0442\u044c 2<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/6c1\/82c\/190\/6c182c190b7e3376475a76859c4e3c7a.png\" alt=\"github.com\/w1kend\/gophers\" title=\"github.com\/w1kend\/gophers\" width=\"2160\" height=\"1620\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6c1\/82c\/190\/6c182c190b7e3376475a76859c4e3c7a.png\"\/><figcaption>github.com\/w1kend\/gophers<\/figcaption><\/figure>\n<p>\u0412\u0441\u0435\u043c \u043f\u0440\u0438\u0432\u0435\u0442. \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c hashmap \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u043e\u0432 Go 1.19. \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c generic \u043a\u043b\u044e\u0447\u0438 \u0438 \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b. \u0423\u0437\u043d\u0430\u0435\u043c \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u043d\u0435\u0440\u0435\u0444\u043b\u0435\u043a\u0441\u0438\u0432\u043d\u044b\u0435 \u043a\u043b\u044e\u0447\u0438, \u043a\u0430\u043a \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u043e\u0441\u0442\u0430 \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u0440\u043e \u043a\u043e\u0440\u043e\u0431\u043e\u0447\u043d\u043e\u0435 \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435.<\/p>\n<p><a href=\"https:\/\/habr.com\/ru\/post\/704796\" rel=\"noopener noreferrer nofollow\">\u0427\u0430\u0441\u0442\u044c 1<\/a><\/p>\n<h3>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0438\u0437 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0447\u0430\u0441\u0442\u0438:<\/h3>\n<ul>\n<li>\n<p>\u0431\u0430\u043a\u0435\u0442 &#8212; \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u043a\u043b\u044e\u0447\u0438, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438 \u0442\u043e\u043f\u0445\u0435\u0448;<\/p>\n<\/li>\n<li>\n<p>\u0440\u043e\u0441\u0442 &#8212; \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u043e\u0433\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 (\u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c) \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0440\u043e\u0441\u0442 \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u0443\u044e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u043c\u0430\u043f\u043e\u0439. \u0412\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u04452 \u0431\u0430\u043a\u0435\u0442\u043e\u0432;<\/p>\n<\/li>\n<li>\n<p>\u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f &#8212; \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u0441\u0442\u0430\u0440\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b &#171;\u044d\u0432\u0430\u043a\u0443\u0438\u0440\u0443\u044e\u0442\u0441\u044f&#187; \u0432 \u043d\u043e\u0432\u043e\u0435 \u043c\u0435\u0441\u0442\u043e.<\/p>\n<\/li>\n<\/ul>\n<h2>Generic \u043a\u043b\u044e\u0447\u0438<\/h2>\n<p>\u0425\u044d\u0448\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0447\u0442\u043e <s>\u0434\u0432\u0438\u0436\u0435\u0442\u0441\u044f<\/s> comparable:<\/p>\n<p>\u0418\u0437 \u043a\u043e\u0440\u043e\u0431\u043a\u0438 Go \u043d\u0435 \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0444\u0443\u043d\u043a\u0446\u0438\u044f\u043c \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0432 map. \u041e\u0434\u043d\u0430\u043a\u043e \u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f \u0432 \u044d\u0442\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438 &#8212; \u0432 go 1.19 \u0432 \u043f\u0430\u043a\u0435\u0442\u0435 maphash \u0431\u044b\u043b\u0438\u00a0<a href=\"https:\/\/pkg.go.dev\/hash\/maphash#Bytes\" rel=\"noopener noreferrer nofollow\">\u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u044b<\/a>\u00a0\u0444\u0443\u043d\u043a\u0446\u0438\u0438\u00a0<code>Bytes<\/code>\u00a0\u0438\u00a0<code>String<\/code>\u00a0\u0434\u043b\u044f \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0431\u0430\u0439\u0442 \u0438 \u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u041d\u043e \u0434\u043b\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f generic \u043a\u043b\u044e\u0447\u0435\u0439 \u0432 \u043d\u0430\u0448\u0435\u0439 map&#8217;\u0435 \u044d\u0442\u043e\u0433\u043e \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e. \u0411\u0443\u0434\u0435\u043c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043c\u0430\u0433\u0438\u0435\u0439, \u043f\u0440\u043e \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c\u00a0<a href=\"https:\/\/www.dolthub.com\/blog\/2022-12-19-maphash\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<h3>dolthub\/maphash \u0438\u043b\u0438 \u043a\u0430\u043a \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437 runtime<\/h3>\n<p>\u041a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 Go \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0432 \u043d\u0430\u0448\u0435\u043c \u043a\u043e\u0434\u0435. \u041d\u0430\u0439\u0442\u0438 \u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435\u00a0<code>maptype<\/code>:<\/p>\n<p><a href=\"https:\/\/github.com\/golang\/go\/blob\/ba913774543d7388b7bb1843fc7c1b935aebedda\/src\/runtime\/type.go#L356\" rel=\"noopener noreferrer nofollow\"><em>runtime\/type.go<\/em><\/a><\/p>\n<pre><code class=\"go\">type maptype struct {     \/* ... *\/ \/\/ function for hashing keys (ptr to key, seed) -> hash hasher     func(unsafe.Pointer, uintptr) uintptr     \/* ... *\/ }<\/code><\/pre>\n<p>\u0414\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u043d\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u043e\u0432 \u0438 \u043f\u0430\u043a\u0435\u0442\u0430\u00a0<code>unsafe<\/code>:<\/p>\n<p><a href=\"https:\/\/github.com\/dolthub\/maphash\/blob\/74e1e1ea1577958fc17c2c43d2b6baba8f2243a5\/runtime.go#L31\" rel=\"noopener noreferrer nofollow\"><em>dolthub\/maphash\/runtime.go<\/em><\/a><\/p>\n<pre><code class=\"go\">func getRuntimeHasher[K comparable]() (h hashfn, seed uintptr) { a := any(make(map[K]struct{})) \/\/ \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u043f\u0443 \u0441 \u043d\u0443\u0436\u043d\u044b\u043c \u0442\u0438\u043f\u043e\u043c \u043a\u043b\u044e\u0447\u0430 i := (*mapiface)(unsafe.Pointer(&amp;a)) \/\/ \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c \u043a \u043d\u0430\u0448\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u0430 \u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c h, seed = i.typ.hasher, uintptr(i.val.hash0) \/\/ \u0437\u0430\u0431\u0438\u0440\u0430\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0443 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430 return }  type mapiface struct { typ *maptype val *hmap }  \/\/ go\/src\/runtime\/type.go type maptype struct {     \/* ... *\/ hasher func(unsafe.Pointer, uintptr) uintptr \/\/ \u0437\u0430\u0432\u0435\u0442\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f     \/* ... *\/ }  \/\/ go\/src\/runtime\/map.go type hmap struct {     \/* ... *\/ }<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f\u00a0 \u0434\u043b\u044f <code>comparable<\/code>\u00a0\u0442\u0438\u043f\u043e\u0432:<\/p>\n<pre><code class=\"go\">func (h Hasher[K]) Hash(key K) uint64 \/\/ K - comparable<\/code><\/pre>\n<h4>\u0417\u0430\u0447\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0430\u0433\u0438\u044e?<\/h4>\n<p>\u0425\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u043f\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/AES_instruction_set\" rel=\"noopener noreferrer nofollow\">AES<\/a>\u00a0\u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430. \u042d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 (\u0432 \u0442\u0435\u043e\u0440\u0438\u0438) \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u043a\u043e\u0434\u0430 \u043d\u0430 \u0447\u0438\u0441\u0442\u043e\u043c Go.<\/p>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0441\u0435\u0431\u0435. \u0422\u0435\u043f\u0435\u0440\u044c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043c\u0430\u043f\u044b \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"go\">type hmap[K comparable, V any] struct {     \/* ... *\/ hasher  maphash.Hasher[K]     \/* ... *\/ }  func New[K comparable, V any](size int) Hashmap[K, V] { h := new(hmap[K, V])  B := uint8(0) for overLoadFactor(size, B) { B++ } h.B = B  h.buckets = make([]bucket[K, V], bucketsNum(h.B))      \/* \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0434 *\/ h.hasher = maphash.NewHasher[K]() \/\/ \u043d\u043e\u0432\u044b\u0439 \u0445\u044d\u0448\u0435\u0440 \u0434\u043b\u044f comparable \u0442\u0438\u043f\u043e\u0432  return h }  \/\/ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435  func (h *hmap[K, V]) locateBucket(key K) (tophash uint8, targetBucket uint64) { hash := h.hasher.Hash(key)     \/* ... *\/ }<\/code><\/pre>\n<h4>\u041f\u0440\u043e \u043d\u0435\u0440\u0435\u0444\u043b\u0435\u043a\u0441\u0438\u0432\u043d\u044b\u0435 \u043a\u043b\u044e\u0447\u0438<\/h4>\n<p>\u0422\u0430\u043a\u0438\u043c\u0438 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u0440\u0430\u0432\u043d\u044b \u0441\u0430\u043c\u0438 \u0441\u0435\u0431\u0435 &#8212;\u00a0<code>x != x<\/code>. \u0418\u0445 \u0432 Go \u0435\u0441\u0442\u044c.<\/p>\n<p>\u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u00a0<code>NaN<\/code>\u00a0\u043a\u0430\u043a \u043a\u043b\u044e\u0447 \u0432 \u043c\u0430\u043f\u0435 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0438 \u043e\u0433\u043e\u0432\u043e\u0440\u043a\u0430\u043c\u0438:<\/p>\n<ul>\n<li>\n<p>\u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0441 \u0442\u0430\u043a\u0438\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442;<\/p>\n<\/li>\n<li>\n<p>\u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u0442\u0430\u043a\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438;<\/p>\n<\/li>\n<li>\n<p>\u043d\u0435\u043b\u044c\u0437\u044f \u0443\u0434\u0430\u043b\u0438\u0442\u044c;<\/p>\n<\/li>\n<li>\n<p>\u0445\u044d\u0448 \u043e\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0437\u043d\u044b\u0439, \u043f\u043e-\u044d\u0442\u043e\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u0430\u043d\u044b \u043f\u043e \u0440\u0430\u0437\u043d\u044b\u043c \u0431\u0430\u043a\u0435\u0442\u0430\u043c.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"go\">  m := make(map[float64]int)   for i := 0; i &lt; 4; i++ {       m[math.NaN()] = i   }   fmt.Println(m)             \/\/ map[NaN:1 NaN:0 NaN:3 NaN:2]   fmt.Println(m[math.NaN()]) \/\/ 0<\/code><\/pre>\n<h3>\u042d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f<\/h3>\n<p>\u0420\u043e\u0441\u0442 \u043c\u0430\u043f\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0443\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445:<\/p>\n<ul>\n<li>\n<p>\u0431\u0430\u043a\u0435\u0442\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u043d\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c ~80%. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432\u0434\u0432\u043e\u0435;<\/p>\n<\/li>\n<li>\n<p>\u0438 \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 (\u043d\u0435 \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d) &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e overflow \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0441\u0430\u043c\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. <\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u041a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u043f\u044b \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c N \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0438 \u043a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u043d\u0438\u0445 (\u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0438\u043d\u0430\u0447\u0435 \u0441\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b \u0442\u0440\u0438\u0433\u0435\u0440 \u043d\u0430 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u0440\u043e\u0441\u0442) \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u044f\u043b\u0441\u044f \u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043b\u043e\u0441\u044c \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u0432 overflow \u0431\u0430\u043a\u0435\u0442\u0430\u0445. \u0414\u0430\u043b\u0435\u0435 \u0443\u0434\u0430\u043b\u044f\u043b\u0438\u0441\u044c \u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u043b\u0438\u0441\u044c \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u0430\u0445. \u0417\u0430\u043f\u043e\u043b\u043d\u0438\u0432 \u0442\u0430\u043a \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u043a\u043e\u0433\u0434\u0430 \u0441\u0430\u043c\u0438 \u0431\u0430\u043a\u0435\u0442\u044b \u043f\u043e\u043b\u0443\u043f\u0443\u0441\u0442\u044b\u0435, \u0430 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u043b\u0435\u0436\u0438\u0442 \u0432 overflow. <\/p>\n<p>\u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432 \u0442\u043e\u043c \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435\/\u0432\u0441\u0442\u0430\u0432\u043a\u0435\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u043d\u0443\u0436\u043d\u043e \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c\u0443 \u0431\u0430\u043a\u0435\u0442\u0443, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u043e overflow.<\/p>\n<\/div>\n<\/details>\n<p>\u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043e\u0442\u00a0<a href=\"https:\/\/github.com\/python\/cpython\/blob\/7b20a0f55a16b3e2d274cc478e4d04bd8a836a9f\/Python\/hashtable.c#L295\" rel=\"noopener noreferrer nofollow\">Python<\/a>\u00a0\u0438\u00a0<a href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/dcf1523bf2dba234371190a70a41cfcb77907196\/src\/java.base\/share\/classes\/java\/util\/HashMap.java#L713\" rel=\"noopener noreferrer nofollow\">Java<\/a>\u00a0\u0432 Go \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e. \u041a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0435\u0440\u0435\u0434 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u044f\u0442\u0441\u044f \u0434\u0430\u043d\u043d\u044b\u0435 \u0438\u0437 1-2 \u0431\u0430\u043a\u0435\u0442\u043e\u0432.<\/p>\n<p>\u0414\u043b\u044f \u0440\u043e\u0441\u0442\u0430 \u043d\u0430\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u043e\u0432\u044b\u0445 \u043f\u043e\u043b\u0435\u0439:<\/p>\n<pre><code class=\"go\">type hmap[K comparable, V any] struct { len int \/\/ \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u043c\u0430\u043f\u0435 B   uint8 \/\/ log_2 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 buckets []bucket[K, V] \/\/ \u0441\u043b\u0430\u0439\u0441 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 hasher  maphash.Hasher[K] \/\/ \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437 \u0440\u0430\u043d\u0442\u0430\u0439\u043c\u0430      \/* \u043d\u043e\u0432\u044b\u0435 \u043f\u043e\u043b\u044f *\/ oldbuckets   *[]bucket[K, V] \/\/ \u0441\u043b\u0430\u0439\u0441 \u0441\u0442\u0430\u0440\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 numEvacuated uint64 \/\/ \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0430 \u0440\u043e\u0441\u0442\u0430. \u0432\u0441\u0435 \u0431\u0430\u043a\u0435\u0442\u044b \u043c\u0435\u043d\u044c\u0448\u0435 \u044d\u0442\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u044b }<\/code><\/pre>\n<p>\u041f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430 \u0432 \u0440\u043e\u0441\u0442\u0443:<\/p>\n<pre><code class=\"go\">\/\/ \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 func (m *hmap[K, V]) startGrowth() { oldBuckets := m.buckets m.B++ \/\/ \u0440\u0430\u0441\u0442\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435 m.buckets = make([]bucket[K, V], bucketsNum(m.B)) m.oldbuckets = &amp;oldBuckets m.numEvacuated = 0 }<\/code><\/pre>\n<p>\u0422\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f \u0438 \u0442\u0440\u0438\u0433\u0433\u0435\u0440 \u0440\u043e\u0441\u0442\u0430 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435\u00a0<code>Put<\/code>:<\/p>\n<pre><code class=\"go\">func (h *hmap[K, V]) Put(key K, value V) { tophash, targetBucket := h.locateBucket(key)      \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \"\u0442\u0440\u0438\u0433\u0433\u0435\u0440\" \u0440\u043e\u0441\u0442\u0430 \u0435\u0441\u043b\u0438 \u043a\u043e\u043b-\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u0441\u044f if !h.isGrowing() &amp;&amp; overLoadFactor(h.len+1, h.B) { h.startGrowth() }  \/\/ \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u0443\u0435\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 if h.isGrowing() { h.growWork(targetBucket) }  if h.buckets[targetBucket].Put(key, tophash, value) { h.len++ } }<\/code><\/pre>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u043e\u0441\u0442\u0430 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f \u043b\u0438 \u0431\u0430\u043a\u0435\u0442 \u043f\u0435\u0440\u0435\u0434 \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0442\u0442\u0443\u0434\u0430:<\/p>\n<pre><code class=\"go\">func (h *hmap[K, V]) Get2(key K) (V, bool) { tophash, targetBucket := h.locateBucket(key)  b := &amp;h.buckets[targetBucket]  if h.isGrowing() { oldB := &amp;(*h.oldbuckets)[targetBucket&amp;h.oldBucketMask()] \/\/ \u0431\u0435\u0440\u0435\u043c \u0441\u0442\u0430\u0440\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 if !oldB.isEvacuated() { \/\/ \u0435\u0441\u043b\u0438 \u043e\u043d \u0435\u0449\u0435 \u043d\u0435 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f, \u0442\u043e \u0438\u0449\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u043c b = oldB } }  return b.Get(key, tophash) }<\/code><\/pre>\n<h3>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f<\/h3>\n<p>\u0421\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u044b\u0439 (\u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438) &#8212; \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u043f\u043e \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c \u0432 \u0431\u0430\u043a\u0435\u0442\u0435, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u0438 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u043c \u043a\u043b\u044e\u0447, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438 \u0442\u043e\u043f\u0445\u0435\u0448. <\/p>\n<h4>\u041a\u0443\u0434\u0430 \u043f\u0435\u0440\u0435\u0435\u0437\u0436\u0430\u0442\u044c<\/h4>\n<p>\u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043c\u0430\u043f\u044b \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432\u0434\u0432\u043e\u0435. \u0415\u0441\u043b\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u0441\u043b\u0430\u0439\u0441 \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043d\u0430 \u0434\u0432\u0435 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b, \u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432\u043d\u0443\u0442\u0440\u0438 \u0441\u0442\u0430\u0440\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u043f\u0443\u0442\u0438 <s>this is the way<\/s> &#8212; \u043b\u0438\u0431\u043e \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043b\u0438\u0431\u043e \u0432\u043e \u0432\u0442\u043e\u0440\u0443\u044e. \u0410 \u0435\u0441\u043b\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 <em>\u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c<\/em> \u0441\u043b\u0430\u0439\u0441\u043e\u043c, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0447\u0442\u043e \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0430\u043a\u0435\u0442\u0430 \u0434\u043b\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0440\u0438\u043c\u0435\u0440<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0411\u044b\u043b\u043e 8 \u0431\u0430\u043a\u0435\u0442\u043e\u0432, \u043c\u044b \u043d\u0430\u0447\u0430\u043b\u0438 \u0440\u043e\u0441\u0442, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0443\u0434\u0432\u043e\u0438\u043b\u043e\u0441\u044c \u0438 \u0441\u0442\u0430\u043b\u043e 16. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u0430\u043a\u0435\u0442\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 3(\u0447\u0435\u0442\u0432\u0435\u0440\u0442\u044b\u0439 \u0431\u0430\u043a\u0435\u0442) \u043f\u0435\u0440\u0435\u043d\u0435\u0441\u0435\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u0432 \u0431\u0430\u043a\u0435\u0442 \u0432 \u043f\u0435\u0440\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 3, \u043b\u0438\u0431\u043e \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 11 (3+8). \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0431\u0430\u043a\u0435\u0442 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 7 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u0432 7\u043e\u0439 \u043b\u0438\u0431\u043e \u0432 15\u0439(7+8).<\/p>\n<\/div>\n<\/details>\n<p>\u0411\u0430\u043a\u0435\u0442\u044b \u0438\u0437 \u0440\u0430\u0437\u043d\u044b\u0445 \u043f\u043e\u043b\u043e\u0432\u0438\u043d \u0445\u0440\u0430\u043d\u0438\u043c \u0432\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u0422\u0430\u043c \u0436\u0435 \u0434\u0435\u0440\u0436\u0438\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430.<\/p>\n<pre><code class=\"go\">\/\/ evacDst \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u043b\u044f \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 type evacDst[K comparable, V any] struct { b *bucket[K, V] \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u043e \u043d\u043e\u0432\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 i uint          \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 }  \/\/ \u0445\u0440\u0430\u043d\u0438\u043c \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u0434\u0432\u0430 \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u0434\u0430\u043d\u043d\u044b\u0435 \u0438\u0437 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e halfs := [2]evacDst[K, V]{     {b: &amp;m.buckets[oldbucket]}, \/\/ oldBucket \u0440\u0430\u0432\u0435\u043d \u043d\u043e\u043c\u0435\u0440\u0443 \u0441\u0442\u0430\u0440\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0445\u043e\u0442\u0438\u043c \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u0442\u044c     {b: &amp;m.buckets[oldbucket+newBit]}, \/\/ newBit \u0440\u0430\u0432\u0435\u043d \u043a\u043e\u043b-\u0432\u0443 \u0441\u0442\u0430\u0440\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 }<\/code><\/pre>\n<p>\u0412\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0445\u0435\u0448\u0430 \u043e\u0442 \u043a\u043b\u044e\u0447\u0430 \u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u043c\u0430\u0441\u043a\u0438. \u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043a \u043d\u043e\u0432\u043e\u0439 \u043c\u0430\u0441\u043a\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0431\u0438\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438 \u0440\u0435\u0448\u0430\u0435\u0442 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u0441\u044f \u043b\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>hash&amp;mask<\/code> \u0438\u043b\u0438 \u043d\u0435\u0442.<\/p>\n<pre><code class=\"go\">newBit := m.numOldBuckets() hash := m.hasher.Hash(*key) var useSecond uint8 if hash&amp;newBit != 0 {     useSecond = 1 }<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u041f\u043e\u0447\u0435\u043c\u0443 newBit<\/summary>\n<div class=\"spoiler__content\">\n<p>newBit &#8212; \u0441\u0442\u0430\u0440\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0412 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u044d\u0442\u043e \u043e\u0434\u0438\u043d \u043d\u0435 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0431\u0438\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043d\u043e\u0432\u0430\u044f \u043c\u0430\u0441\u043a\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0441\u0442\u0430\u0440\u043e\u0439.<br \/>\u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u0441 8 \u0434\u043e 16 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 <br \/>newBit == 8 (1000)<br \/>mask == 15 (1111)<br \/>oldMask == 7 (0111)<br \/>\u041e\u0442 \u0441\u044e\u0434\u0430 \u0438 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439.<\/p>\n<\/div>\n<\/details>\n<p>\u041f\u043e\u043b\u043d\u044b\u0439 \u0446\u0438\u043a\u043b \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438:<\/p>\n<pre><code class=\"go\">newBit := m.numOldBuckets() \/* ... *\/ for ; b != nil; b = b.overflow {     \/\/ \u0438\u0442\u0435\u0440\u0438\u0440\u0443\u0435\u043c\u0441\u044f \u043f\u043e \u0441\u0442\u0430\u0440\u043e\u043c\u0443 \u0431\u0430\u043a\u0435\u0442\u0443     for i := 0; i &lt; bucketSize; i++ {         top := b.tophash[i]          \/\/ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0444\u043b\u0430\u0433\u0438 tophash \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0443\u0441\u0442\u044b\u0445 \u044f\u0447\u0435\u0435\u043a         if isCellEmpty(top) {             b.tophash[i] = evacuatedEmpty             continue         }          key := &amp;b.keys[i]         value := &amp;b.values[i]          \/\/ \u043e\u043f\u044f\u0442\u044c \u0431\u0435\u0440\u0435\u043c \u0445\u044d\u0448 \u043e\u0442 \u043a\u043b\u044e\u0447\u0430         hash := m.hasher.Hash(*key)          \/\/ \u0444\u043b\u0430\u0433 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432         var useSecond uint8          \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043b\u0438 \u043c\u0435\u0441\u0442\u043e\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u0442 \u043d\u043e\u0432\u043e\u0433\u043e \u0431\u0438\u0442\u0430         if hash&amp;newBit != 0 {             useSecond = 1         }          \/\/ evacuatedFirst, evacuatedSecond - \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u044b\u0435 \u0444\u043b\u0430\u0433\u0438 \u0434\u043b\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430 tophash \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u0432 \u043a\u0430\u043a\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043f\u0435\u0440\u0435\u0435\u0445\u0430\u043b \u044d\u043b\u0435\u043c\u0435\u043d\u0442         \/\/ evacuatedFirst + useSecond == evaluatedSecond         b.tophash[i] = evacuatedFirst + useSecond          \/\/\u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442         dst := &amp;halfs[useSecond]         \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043a\u043e\u043b-\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432         if dst.i == bucketSize {             dst.b = newOverflow(dst.b) \/\/ \u0435\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u043c overflow             dst.i = 0         }         \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443         dst.b.putAt(*key, top, *value, dst.i)         dst.i++     } }<\/code><\/pre>\n<p>\u0412 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0435\u0441\u0442\u044c \u0442\u0430\u043a\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430:<\/p>\n<pre><code class=\"go\">if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {     throw(\"bad evacuatedN\") }<\/code><\/pre>\n<p>\u041e\u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u041d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u044d\u0442\u043e \u0441\u0442\u0440\u0430\u043d\u043d\u043e, \u0442\u0430\u043a \u043a\u0430\u043a \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b \u043d\u0435\u043b\u044c\u0437\u044f \u043f\u0435\u0440\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c, \u0438 \u0445\u0432\u0430\u0442\u0438\u043b\u043e \u0431\u044b \u043e\u0434\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0446\u0438\u0438. \u042f \u0437\u0430\u043c\u0435\u043d\u0438\u043b \u044d\u0442\u043e \u043d\u0430 \u0442\u0430\u043a\u0443\u044e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443:<\/p>\n<pre><code class=\"go\">func _() { var x [1]struct{} _ = x[evacuatedFirst-2] _ = x[evacuatedSecond-3] }<\/code><\/pre>\n<h3>\u0418\u0442\u0435\u0440\u0430\u0446\u0438\u044f<\/h3>\n<p>\u041f\u043b\u044e\u0441\u044b \u0442\u0430\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u043e\u0441\u0442\u0430 &#8212; \u043d\u0435\u0442 \u043f\u0440\u043e\u0441\u0430\u0434\u043e\u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u0438 \u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u0430\u043a \u0435\u0441\u043b\u0438 \u0431\u044b \u043c\u044b \u044d\u0442\u043e \u0434\u0435\u043b\u0430\u043b\u0438 \u043e\u0434\u043d\u0438\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u043c. \u0418\u0437 \u043c\u0438\u043d\u0443\u0441\u043e\u0432 &#8212; \u043d\u0443\u0436\u043d\u043e \u044d\u0442\u043e \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u043f\u0440\u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0435\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438\/\u043f\u043e\u0438\u0441\u043a\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0430 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043f\u0440\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438.<\/p>\n<p>\u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0445\u0440\u0430\u043d\u0438\u0442 \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438:<\/p>\n<pre><code class=\"go\">type hiter[K comparable, V any] struct { key           *K   \/\/ \u043a\u043b\u044e\u0447 elem          *V   \/\/ \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 m             *hmap[K, V]  \/\/ \u0441\u0430\u043c\u0430 \u043c\u0430\u043f\u0430 buckets       *[]bucket[K, V] \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0438\u0442\u0435\u0440\u0438\u0440\u0443\u0435\u043c\u0441\u044f currBktPtr    *bucket[K, V]   \/\/ \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0431\u0430\u043a\u0435\u0442 startBucket   uint64          \/\/ \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0439 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 offset        uint8           \/\/ \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u044b\u0439 \u043e\u0444\u0444\u0441\u0435\u0442, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 wrapped       bool            \/\/ \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u043a\u0440\u0443\u0433 \u043f\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0443 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 B             uint8  \/\/ log_2 \u043e\u0442 \u043a\u043e\u043b-\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043d\u0430 \u043c\u043e\u043c\u0435\u043d\u0442 \u0441\u0442\u0430\u0440\u0442\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 i             uint8  \/\/ \u043f\u043e\u0437\u0438\u0446\u0438\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u0431\u0430\u043a\u0435\u0442\u0435 currBucketNum uint64  \/\/ \u043d\u043e\u043c\u0435\u0440 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 checkBucket   uint64  \/\/ \u043d\u043e\u043c\u0435\u0440 \u0431\u0430\u043a\u0435\u0442\u0430 \u0434\u043b\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438. todo \u0438\u0437-\u0437\u0430 \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438 \u0438\u043d\u043e\u0433\u0434\u0430 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u0441\u0440\u0430\u0437\u0443 \u0432 \u0434\u0432\u0443\u0445 \u0431\u0430\u043a\u0435\u0442\u0430\u0445 } <\/code><\/pre>\n<p>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c. \u0417\u0434\u0435\u0441\u044c \u0436\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043c\u0430\u0433\u0438\u044f &#171;\u0440\u0430\u043d\u0434\u043e\u043c\u043d\u043e\u0439&#187; \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u043d\u043e\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438: \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430\u0447\u043d\u0435\u0442\u0441\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f, \u0438 \u043e\u0442\u0441\u0442\u0443\u043f, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0443\u0442 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u043d\u0443\u0442\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430.<\/p>\n<pre><code class=\"go\">func iterInit[K comparable, V any](m *hmap[K, V]) *hiter[K, V] { h := hiter[K, V]{}  if m == nil || m.len == 0 { return &amp;h }  h.m = m h.B = m.B h.buckets = &amp;m.buckets \/\/ \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 h.startBucket = rand.Uint64() &amp; bucketMask(m.B) \/\/ \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043f\u043e\u0437\u0438\u0446\u0438\u044e, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 h.offset = uint8(uint8(h.startBucket) >> h.B &amp; (bucketSize - 1)) h.currBucketNum = h.startBucket  \/\/ \u0441\u0440\u0430\u0437\u0443 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043e\u0434\u043d\u0443 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e h.next()  return &amp;h }<\/code><\/pre>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438:<\/p>\n<ul>\n<li>\n<p>\u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 &#8212; \u043a\u043e\u0433\u0434\u0430 \u043c\u0430\u043f\u0430 \u043d\u0435 \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430;<\/p>\n<\/li>\n<li>\n<p>\u0441\u043b\u043e\u0436\u043d\u044b\u0439 &#8212; \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438.<\/p>\n<\/li>\n<\/ul>\n<p>\u0412 \u043f\u0435\u0440\u0432\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0431\u0430\u043a\u0435\u0442\u0430\u043c. \u0417\u0430\u043d\u043e\u0441\u0438\u043c \u0432 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u0431\u0430\u043a\u0435\u0442:<\/p>\n<pre><code class=\"go\">b := it.currBktPtr bucketNum := it.currBucketNum i := it.i checkBucket := it.checkBucket next: \/\/ \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0431\u0430\u043a\u0435\u0442 if b == nil { if bucketNum == it.startBucket &amp;&amp; it.wrapped { \/\/ \u043a\u043e\u043d\u0435\u0446 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 it.key = nil it.elem = nil return } checkBucket = noCheck \/\/ b = &amp;it.m.buckets[bucketNum] \/\/ \u0431\u0430\u043a\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043a\u0430\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435  bucketNum++ \/\/ \u043d\u043e\u043c\u0435\u0440 \u0441\u043b\u0435\u0434. \u0431\u0430\u043a\u0435\u0442\u0430 if bucketNum == bucketsNum(it.B) { \/\/ \u0435\u0441\u043b\u0438 \"\u0437\u0430\u043c\u043a\u043d\u0443\u043b\u0438 \u043a\u0440\u0443\u0433\" \u0442\u043e \u043f\u0440\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0444\u043b\u0430\u0433 bucketNum = 0 it.wrapped = true } i = 0 }<\/code><\/pre>\n<p>\u0418\u0442\u0435\u0440\u0438\u0440\u0443\u0435\u043c\u0441\u044f:<\/p>\n<pre><code class=\"go\">\/\/ bucketSize - \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 for ; i &lt; bucketSize; i++ { \/\/ \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u044c, \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u043e\u0444\u0444\u0441\u0435\u0442\u043e\u043c offI := (i + it.offset) &amp; (bucketSize - 1) top := b.tophash[offI] \/\/ \u0435\u0441\u043b\u0438 \u044f\u0447\u0435\u0439\u043a\u0430 \u043f\u0443\u0441\u0442\u0430\u044f if isCellEmpty(top) || top == evacuatedEmpty { continue } key := &amp;b.keys[offI] elem := &amp;b.values[offI]  \/\/ \u043f\u0440\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 it.key = key it.elem = elem \/\/ \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0441\u0442\u0435\u0439\u0442 it.currBucketNum = bucketNum if it.currBktPtr != b { it.currBktPtr = b } it.i = i + 1 return } \/\/ \u0438\u0434\u0435\u043c \u0432 overflow b = b.overflow i = 0 goto next \/\/ \u043a \u0432\u044b\u0431\u043e\u0440\u0443 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430<\/code><\/pre>\n<p>\u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u043c\u0430\u043f\u044b \u0434\u043e\u0431\u0430\u0432\u0438\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041f\u0440\u0438 \u0432\u044b\u0431\u043e\u0440\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 <code>x<\/code> \u0431\u0443\u0434\u0435\u043c \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0447\u0442\u043e \u0434\u0430\u043d\u043d\u044b\u0435 \u0438\u0437 \u0441\u0442\u0430\u0440\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 <code>oldX<\/code> \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0435\u0449\u0435 \u043d\u0435 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0438\u0441\u044c, \u0438 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0447\u0430\u0442\u044c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u043f\u043e <code>oldX<\/code>.<\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u0437 \u0431\u0430\u043a\u0435\u0442\u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0430, \u0442\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0434\u0435 \u043f\u043e \u0441\u0442\u0430\u0440\u043e\u043d\u0443 (\u043d\u0435 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c\u0443) <code>oldX<\/code> \u0431\u0430\u043a\u0435\u0442\u0443, \u0431\u0443\u0434\u0435\u043c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0435\u0440\u0435\u0439\u0434\u0443\u0442 \u0432 \u0431\u0430\u043a\u0435\u0442 <code>x<\/code>.<\/p>\n<p>\u0418\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0432 \u043c\u0435\u0441\u0442\u0435 \u0432\u044b\u0431\u043e\u0440\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430:<\/p>\n<pre><code class=\"go\">\/\/ \u0435\u0441\u043b\u0438 \u0440\u043e\u0441\u0442 \u0435\u0449\u0435 \u043d\u0435 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d, \u0442\u043e \u0441\u0442\u0430\u0440\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b \u0442\u043e\u0436\u0435 \u043d\u0443\u0436\u043d\u043e \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c if it.m.isGrowing() &amp;&amp; it.B == it.m.B { \/\/ runtime\/map.go:890 \/\/ \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u043d\u0430\u0447\u0430\u043b\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u043e\u0441\u0442\u0430. \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u0442\u0430\u0440\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \/\/ \u0435\u0441\u043b\u0438 \u043e\u043d \u0435\u0449\u0435 \u043d\u0435 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f, \u0442\u043e \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u043f\u043e \u043d\u0435\u043c\u0443, \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \/\/ \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u0438\u0433\u0440\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0432 \u0442\u0435\u043a\u0443\u0449\u0438\u0439 \u0431\u0430\u043a\u0435\u0442 oldBucketNum := bucketNum &amp; it.m.oldBucketMask() b = &amp;(*it.m.oldbuckets)[oldBucketNum] if !b.isEvacuated() { checkBucket = bucketNum } else { \/\/ \u0438\u043d\u0430\u0447\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u0442\u0435\u0440\u0438\u0440\u0443\u0435\u043c\u0441\u044f \u043f\u043e bucketNum checkBucket = noCheck b = &amp;it.m.buckets[bucketNum] } } else { checkBucket = noCheck b = &amp;it.m.buckets[bucketNum] } bucketNum++ if bucketNum == bucketsNum(it.B) {   \/\/ \u0435\u0441\u043b\u0438 \"\u0437\u0430\u043c\u043a\u043d\u0443\u043b\u0438 \u043a\u0440\u0443\u0433\" \u0442\u043e \u043f\u0440\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0444\u043b\u0430\u0433   bucketNum = 0   it.wrapped = true } i = 0 <\/code><\/pre>\n<p>\u0423\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u043c\u044b \u0432 \u0441\u0442\u0430\u0440\u043e\u043c \u0431\u0430\u043a\u0435\u0442\u0435, \u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0443\u0436\u043d\u043e \u043b\u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u044d\u043b\u0435\u043c\u0435\u043d\u0442. <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0436\u0435 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430\u00a0<code>key<\/code>\u00a0!=\u00a0<code>key<\/code>\u00a0(NaN). \u0422\u0430\u043a \u043a\u0430\u043a \u0445\u0435\u0448 \u043e\u0442 NaN \u0431\u0443\u0434\u0435\u0442 \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043d\u043e\u0432\u044b\u0439, \u0442\u043e \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u0441\u043f\u043e\u0441\u043e\u0431 &#171;\u0440\u0430\u043d\u0434\u043e\u043c\u043d\u043e\u0433\u043e&#187; \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0430. \u041a \u0442\u043e\u043c\u0443 \u0436\u0435 \u043d\u0443\u0436\u043d\u043e \u0443\u043c\u0435\u0442\u044c \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u0432\u044b\u0431\u043e\u0440. \u041f\u043e-\u044d\u0442\u043e\u043c\u0443 \u0434\u043b\u044f \u0442\u0430\u043a\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432\u043c\u0435\u0441\u0442\u043e \u0445\u0435\u0448\u0430 \u043a\u043b\u044e\u0447\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f tophash, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u0435\u0433\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0431\u0438\u0442, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0438\u0439 \u0432 \u043a\u0430\u043a\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043f\u0435\u0440\u0435\u043d\u0435\u0441\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435.<\/p>\n<pre><code class=\"go\">if checkBucket != noCheck &amp;&amp; !it.m.sameSizeGrow() { \/\/ runtime\/map.go:925 \/\/ \u0441\u043b\u0443\u0447\u0430\u0439 \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043d\u0430\u0447\u0430\u043b\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u043e\u0441\u0442\u0430 \u0438 \u043e\u043d \u0435\u0449\u0435 \u043d\u0435 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u043b\u0441\u044f \/\/ oldbucket \u0441\u043b\u0430\u0439\u0441 \u0435\u0449\u0435 \u043d\u0435 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f. \u0438\u043b\u0438, \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0443\u043c, \u043e\u043d \u043d\u0435 \u0431\u044b\u043b \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043d \/\/ \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043d\u0430\u0447\u0430\u043b\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e. \/\/ \u043f\u043e-\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u043d\u0430\u0432\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u043d\u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \/\/ (\u043f\u0440\u0438 \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u0430\u043a\u0435\u0442\u0430 \u043b\u0438\u0431\u043e \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 \u043f\u043e \u0441\u0442\u0430\u0440\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u043b\u0438\u0431\u043e \u043f\u043e \u043d\u043e\u0432\u043e\u043c\u0443) if key == key { hash := it.m.hasher.Hash(*key) if hash&amp;bucketMask(it.B) != checkBucket { continue } } else { \/\/ runtime\/map.go:941 \/\/ \u0435\u0441\u043b\u0438 \u043a\u043b\u044e\u0447 \u043d\u0435 \u0440\u0430\u0432\u0435\u043d \u0441\u0435\u0431\u0435(NaN) \u043c\u044b \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \"\u0440\u0430\u043d\u0434\u043e\u043c\u043d\u043e\u0435\" \u043c\u0435\u0441\u0442\u043e \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0430 if checkBucket>>(it.B-1) != uint64(b.tophash[offI]&amp;1) { continue } } }<\/code><\/pre>\n<p>\u0418 \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 &#8212; \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0447\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0435 \u043f\u0435\u0440\u0435\u0435\u0445\u0430\u043b \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u0431\u0430\u043a\u0435\u0442, \u0442\u043e \u0435\u0441\u0442\u044c \u0435\u0433\u043e tophash \u043d\u0435 \u0440\u0430\u0432\u0435\u043d \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0435\u0441\u043b\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432\u0441\u0435 \u0442\u0430\u043a\u0438 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f, \u0442\u043e \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043e\u0431\u044b\u0447\u043d\u044b\u043c \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u0447\u0435\u0440\u0435\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u044e\u00a0<code>Get()<\/code>.<\/p>\n<pre><code class=\"go\">if (top != evacuatedFirst &amp;&amp; top != evacuatedSecond) || key != key { \/\/ \u043d\u0430\u0448\u043b\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u0448\u0430\u0433\u0435 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 it.key = key it.elem = elem } else { \/\/ \u043c\u0430\u043f\u0430 \u0432\u044b\u0440\u043e\u0441\u043b\u0430 \u0441 \u043c\u043e\u043c\u0435\u043d\u0442\u0430 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \/\/ \u043d\u0443\u0436\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u0433\u0434\u0435-\u0442\u043e \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \/\/ \u044d\u0442\u043e\u0442 \u043a\u0435\u0439\u0441 \u0434\u043b\u044f \u0441\u043b\u0443\u0447\u0430\u0439 \u043a\u043e\u0433\u0434\u0430 \u043a\u043b\u044e\u0447 \u0431\u044b\u043b \u0443\u0434\u0430\u043b\u0435\u043d\/\u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d \u0435\u0449\u0435 \u0440\u0430\u0437.  re, ok := it.m.Get2(*key) if !ok { continue \/\/ \u043a\u043b\u044e\u0447 \u0431\u044b\u043b \u0443\u0434\u0430\u043b\u0435\u043d } it.key = key it.elem = &amp;re }<\/code><\/pre>\n<p>\u041a\u043e\u043d\u0441\u0438\u0441\u0442\u0435\u043d\u0442\u043d\u043e\u0441\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0445 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0430\u043c \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u0449\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u0438\u00a0<code>next()<\/code>. \u041e\u043d\u0430 \u0441\u043f\u0430\u0441\u0430\u0435\u0442 \u043e\u0442 \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0433\u043e \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u043a \u043c\u0430\u043f\u0435 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438, \u0447\u0442\u043e \u043f\u0440\u0438\u0432\u0435\u043b\u043e \u0431\u044b \u043a \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432.<\/p>\n<pre><code class=\"go\">if it.m.flags&amp;hashWriting != 0 { panic(\"concurrent map iteration and map write\") }<\/code><\/pre>\n<p>\u0417\u0430\u043f\u0443\u0441\u0442\u0438\u043c \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a \u0438\u0437 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0447\u0430\u0441\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442 N \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u043f\u0443 \u0441 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 1000. \u0421\u0442\u0430\u043b \u043f\u043e\u0445\u043e\u0436 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0435\u0441\u0442\u044c \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c:<\/p>\n<pre><code class=\"bash\">go test . -run=^$ -bench ^BenchmarkPutWithOverflow$ -benchmem goos: darwin goarch: arm64 pkg: github.com\/w1kend\/go-map BenchmarkPutWithOverflow\/gen-map__(string_key)10000-8           37374638                29.77 ns\/op            0 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/STD______(string_key)10000-8           41619038                27.21 ns\/op            0 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/gen-map__(string_key)100000-8          29636793                34.50 ns\/op            0 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/STD______(string_key)100000-8          30507568                34.89 ns\/op            0 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/gen-map__(string_key)1000000-8         14918946                79.41 ns\/op            0 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/STD______(string_key)1000000-8         19115414                63.17 ns\/op            0 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/gen-map__(string_key)10000000-8         6472369               267.0 ns\/op           212 B\/op          0 allocs\/op BenchmarkPutWithOverflow\/STD______(string_key)10000000-8         6640574               248.4 ns\/op           211 B\/op          0 allocs\/op <\/code><\/pre>\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438 \u0434\u043b\u044f \u043f\u043e\u0438\u0433\u0440\u0430\u0442\u044c\u0441\u044f\u00a0<a href=\"https:\/\/github.com\/w1kend\/go-map\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a>. \u0417\u0430\u0447\u0435\u043c? \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0430\u0440\u0435\u043d\u044b \u0438\u0437 Go 1.20 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u043e \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0443 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u0438\u043b\u0430\u0441\u044c (\u0441\u0442\u0430\u043b\u043e \u043b\u0443\u0447\u0448\u0435 \u043f\u0440\u0438 10\u043a\u043a+ \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432).<\/p>\n<p>\u041d\u0430 \u044d\u0442\u043e\u043c \u0432\u0441\u0435, \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 (:<\/p>\n<h2>\u0421\u0441\u044b\u043b\u043a\u0438<\/h2>\n<p><a href=\"https:\/\/github.com\/w1kend\/go-map\" rel=\"noopener noreferrer nofollow\">Source code<\/a><\/p>\n<p><a href=\"https:\/\/github.com\/w1kend\/gophers\" rel=\"noopener noreferrer nofollow\">\u041a\u0430\u0440\u0442\u0438\u043d\u043a\u0438 \u0433\u043e\u0444\u0435\u0440\u043e\u0432<\/a><\/p>\n<p><a href=\"https:\/\/www.dolthub.com\/blog\/2022-12-19-maphash\" rel=\"noopener noreferrer nofollow\">Hacking Go&#8217;s Runtime with Generics<\/a><\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p> <!----> <!----><\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/717724\/\"> https:\/\/habr.com\/ru\/post\/717724\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><figcaption>github.com\/w1kend\/gophers<\/figcaption><\/figure>\n<p>\u0412\u0441\u0435\u043c \u043f\u0440\u0438\u0432\u0435\u0442. \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u0442\u044c hashmap \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u043e\u0432 Go 1.19. \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c generic \u043a\u043b\u044e\u0447\u0438 \u0438 \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b. \u0423\u0437\u043d\u0430\u0435\u043c \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u043d\u0435\u0440\u0435\u0444\u043b\u0435\u043a\u0441\u0438\u0432\u043d\u044b\u0435 \u043a\u043b\u044e\u0447\u0438, \u043a\u0430\u043a \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u043e\u0441\u0442\u0430 \u0438 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043f\u0440\u043e \u043a\u043e\u0440\u043e\u0431\u043e\u0447\u043d\u043e\u0435 \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435.<\/p>\n<p><a href=\"https:\/\/habr.com\/ru\/post\/704796\" rel=\"noopener noreferrer nofollow\">\u0427\u0430\u0441\u0442\u044c 1<\/a><\/p>\n<h3>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0438\u0437 \u043f\u0440\u043e\u0448\u043b\u043e\u0439 \u0447\u0430\u0441\u0442\u0438:<\/h3>\n<ul>\n<li>\n<p>\u0431\u0430\u043a\u0435\u0442 &#8212; \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u043a\u043b\u044e\u0447\u0438, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438 \u0442\u043e\u043f\u0445\u0435\u0448;<\/p>\n<\/li>\n<li>\n<p>\u0440\u043e\u0441\u0442 &#8212; \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u043e\u0433\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 (\u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c) \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0440\u043e\u0441\u0442 \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u0443\u044e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441 \u043c\u0430\u043f\u043e\u0439. \u0412\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u04452 \u0431\u0430\u043a\u0435\u0442\u043e\u0432;<\/p>\n<\/li>\n<li>\n<p>\u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f &#8212; \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u0441\u0442\u0430\u0440\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b &#171;\u044d\u0432\u0430\u043a\u0443\u0438\u0440\u0443\u044e\u0442\u0441\u044f&#187; \u0432 \u043d\u043e\u0432\u043e\u0435 \u043c\u0435\u0441\u0442\u043e.<\/p>\n<\/li>\n<\/ul>\n<h2>Generic \u043a\u043b\u044e\u0447\u0438<\/h2>\n<p>\u0425\u044d\u0448\u0438\u0440\u0443\u0435\u043c \u0432\u0441\u0435 \u0447\u0442\u043e <s>\u0434\u0432\u0438\u0436\u0435\u0442\u0441\u044f<\/s> comparable:<\/p>\n<p>\u0418\u0437 \u043a\u043e\u0440\u043e\u0431\u043a\u0438 Go \u043d\u0435 \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0444\u0443\u043d\u043a\u0446\u0438\u044f\u043c \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0432 map. \u041e\u0434\u043d\u0430\u043a\u043e \u0435\u0441\u0442\u044c \u043f\u0440\u043e\u0434\u0432\u0438\u0436\u0435\u043d\u0438\u044f \u0432 \u044d\u0442\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438 &#8212; \u0432 go 1.19 \u0432 \u043f\u0430\u043a\u0435\u0442\u0435 maphash \u0431\u044b\u043b\u0438\u00a0<a href=\"https:\/\/pkg.go.dev\/hash\/maphash#Bytes\" rel=\"noopener noreferrer nofollow\">\u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u044b<\/a>\u00a0\u0444\u0443\u043d\u043a\u0446\u0438\u0438\u00a0<code>Bytes<\/code>\u00a0\u0438\u00a0<code>String<\/code>\u00a0\u0434\u043b\u044f \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0431\u0430\u0439\u0442 \u0438 \u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u041d\u043e \u0434\u043b\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f generic \u043a\u043b\u044e\u0447\u0435\u0439 \u0432 \u043d\u0430\u0448\u0435\u0439 map&#8217;\u0435 \u044d\u0442\u043e\u0433\u043e \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e. \u0411\u0443\u0434\u0435\u043c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043c\u0430\u0433\u0438\u0435\u0439, \u043f\u0440\u043e \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c\u00a0<a href=\"https:\/\/www.dolthub.com\/blog\/2022-12-19-maphash\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<h3>dolthub\/maphash \u0438\u043b\u0438 \u043a\u0430\u043a \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437 runtime<\/h3>\n<p>\u041a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 Go \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0432 \u043d\u0430\u0448\u0435\u043c \u043a\u043e\u0434\u0435. \u041d\u0430\u0439\u0442\u0438 \u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435\u00a0<code>maptype<\/code>:<\/p>\n<p><a href=\"https:\/\/github.com\/golang\/go\/blob\/ba913774543d7388b7bb1843fc7c1b935aebedda\/src\/runtime\/type.go#L356\" rel=\"noopener noreferrer nofollow\"><em>runtime\/type.go<\/em><\/a><\/p>\n<pre><code class=\"go\">type maptype struct {     \/* ... *\/ \/\/ function for hashing keys (ptr to key, seed) -> hash hasher     func(unsafe.Pointer, uintptr) uintptr     \/* ... *\/ }<\/code><\/pre>\n<p>\u0414\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u043d\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u0442\u0438\u043f\u043e\u0432 \u0438 \u043f\u0430\u043a\u0435\u0442\u0430\u00a0<code>unsafe<\/code>:<\/p>\n<p><a href=\"https:\/\/github.com\/dolthub\/maphash\/blob\/74e1e1ea1577958fc17c2c43d2b6baba8f2243a5\/runtime.go#L31\" rel=\"noopener noreferrer nofollow\"><em>dolthub\/maphash\/runtime.go<\/em><\/a><\/p>\n<pre><code class=\"go\">func getRuntimeHasher[K comparable]() (h hashfn, seed uintptr) { a := any(make(map[K]struct{})) \/\/ \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043c\u0430\u043f\u0443 \u0441 \u043d\u0443\u0436\u043d\u044b\u043c \u0442\u0438\u043f\u043e\u043c \u043a\u043b\u044e\u0447\u0430 i := (*mapiface)(unsafe.Pointer(&amp;a)) \/\/ \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u043c \u043a \u043d\u0430\u0448\u0435\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u0430 \u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c h, seed = i.typ.hasher, uintptr(i.val.hash0) \/\/ \u0437\u0430\u0431\u0438\u0440\u0430\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u0443 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430 return }  type mapiface struct { typ *maptype val *hmap }  \/\/ go\/src\/runtime\/type.go type maptype struct {     \/* ... *\/ hasher func(unsafe.Pointer, uintptr) uintptr \/\/ \u0437\u0430\u0432\u0435\u0442\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f     \/* ... *\/ }  \/\/ go\/src\/runtime\/map.go type hmap struct {     \/* ... *\/ }<\/code><\/pre>\n<p>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0445\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f\u00a0 \u0434\u043b\u044f <code>comparable<\/code>\u00a0\u0442\u0438\u043f\u043e\u0432:<\/p>\n<pre><code class=\"go\">func (h Hasher[K]) Hash(key K) uint64 \/\/ K - comparable<\/code><\/pre>\n<h4>\u0417\u0430\u0447\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0430\u0433\u0438\u044e?<\/h4>\n<p>\u0425\u0435\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u043f\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/AES_instruction_set\" rel=\"noopener noreferrer nofollow\">AES<\/a>\u00a0\u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430. \u042d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 (\u0432 \u0442\u0435\u043e\u0440\u0438\u0438) \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0438 \u043e\u0442 \u043a\u043e\u0434\u0430 \u043d\u0430 \u0447\u0438\u0441\u0442\u043e\u043c Go.<\/p>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0441\u0435\u0431\u0435. \u0422\u0435\u043f\u0435\u0440\u044c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043c\u0430\u043f\u044b \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a:<\/p>\n<pre><code class=\"go\">type hmap[K comparable, V any] struct {     \/* ... *\/ hasher  maphash.Hasher[K]     \/* ... *\/ }  func New[K comparable, V any](size int) Hashmap[K, V] { h := new(hmap[K, V])  B := uint8(0) for overLoadFactor(size, B) { B++ } h.B = B  h.buckets = make([]bucket[K, V], bucketsNum(h.B))      \/* \u043d\u043e\u0432\u044b\u0439 \u043a\u043e\u0434 *\/ h.hasher = maphash.NewHasher[K]() \/\/ \u043d\u043e\u0432\u044b\u0439 \u0445\u044d\u0448\u0435\u0440 \u0434\u043b\u044f comparable \u0442\u0438\u043f\u043e\u0432  return h }  \/\/ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435  func (h *hmap[K, V]) locateBucket(key K) (tophash uint8, targetBucket uint64) { hash := h.hasher.Hash(key)     \/* ... *\/ }<\/code><\/pre>\n<h4>\u041f\u0440\u043e \u043d\u0435\u0440\u0435\u0444\u043b\u0435\u043a\u0441\u0438\u0432\u043d\u044b\u0435 \u043a\u043b\u044e\u0447\u0438<\/h4>\n<p>\u0422\u0430\u043a\u0438\u043c\u0438 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u043b\u044e\u0447\u0438 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u0440\u0430\u0432\u043d\u044b \u0441\u0430\u043c\u0438 \u0441\u0435\u0431\u0435 &#8212;\u00a0<code>x != x<\/code>. \u0418\u0445 \u0432 Go \u0435\u0441\u0442\u044c.<\/p>\n<p>\u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u00a0<code>NaN<\/code>\u00a0\u043a\u0430\u043a \u043a\u043b\u044e\u0447 \u0432 \u043c\u0430\u043f\u0435 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0438 \u043e\u0433\u043e\u0432\u043e\u0440\u043a\u0430\u043c\u0438:<\/p>\n<ul>\n<li>\n<p>\u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0441 \u0442\u0430\u043a\u0438\u043c \u043a\u043b\u044e\u0447\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442;<\/p>\n<\/li>\n<li>\n<p>\u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u0442\u0430\u043a\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438;<\/p>\n<\/li>\n<li>\n<p>\u043d\u0435\u043b\u044c\u0437\u044f \u0443\u0434\u0430\u043b\u0438\u0442\u044c;<\/p>\n<\/li>\n<li>\n<p>\u0445\u044d\u0448 \u043e\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u043a\u043b\u044e\u0447\u0430 \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0437\u043d\u044b\u0439, \u043f\u043e-\u044d\u0442\u043e\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0437\u0431\u0440\u043e\u0441\u0430\u043d\u044b \u043f\u043e \u0440\u0430\u0437\u043d\u044b\u043c \u0431\u0430\u043a\u0435\u0442\u0430\u043c.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"go\">  m := make(map[float64]int)   for i := 0; i &lt; 4; i++ {       m[math.NaN()] = i   }   fmt.Println(m)             \/\/ map[NaN:1 NaN:0 NaN:3 NaN:2]   fmt.Println(m[math.NaN()]) \/\/ 0<\/code><\/pre>\n<h3>\u042d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f<\/h3>\n<p>\u0420\u043e\u0441\u0442 \u043c\u0430\u043f\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0443\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445:<\/p>\n<ul>\n<li>\n<p>\u0431\u0430\u043a\u0435\u0442\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u043d\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c ~80%. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432\u0434\u0432\u043e\u0435;<\/p>\n<\/li>\n<li>\n<p>\u0438 \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 (\u043d\u0435 \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d) &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e overflow \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0441\u0430\u043c\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. <\/p>\n<\/li>\n<\/ul>\n<details class=\"spoiler\">\n<summary>\u041a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0412 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043c\u0430\u043f\u044b \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c N \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0438 \u043a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u043d\u0438\u0445 (\u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0438\u043d\u0430\u0447\u0435 \u0441\u0440\u0430\u0431\u043e\u0442\u0430\u043b \u0431\u044b \u0442\u0440\u0438\u0433\u0435\u0440 \u043d\u0430 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u0440\u043e\u0441\u0442) \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u044f\u043b\u0441\u044f \u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043b\u043e\u0441\u044c \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u0432 overflow \u0431\u0430\u043a\u0435\u0442\u0430\u0445. \u0414\u0430\u043b\u0435\u0435 \u0443\u0434\u0430\u043b\u044f\u043b\u0438\u0441\u044c \u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u043b\u0438\u0441\u044c \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u0430\u0445. \u0417\u0430\u043f\u043e\u043b\u043d\u0438\u0432 \u0442\u0430\u043a \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044e \u043a\u043e\u0433\u0434\u0430 \u0441\u0430\u043c\u0438 \u0431\u0430\u043a\u0435\u0442\u044b \u043f\u043e\u043b\u0443\u043f\u0443\u0441\u0442\u044b\u0435, \u0430 \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u043b\u0435\u0436\u0438\u0442 \u0432 overflow. <\/p>\n<p>\u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432 \u0442\u043e\u043c \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435\/\u0432\u0441\u0442\u0430\u0432\u043a\u0435\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0438 \u043d\u0443\u0436\u043d\u043e \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c\u0443 \u0431\u0430\u043a\u0435\u0442\u0443, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u043e overflow.<\/p>\n<\/div>\n<\/details>\n<p>\u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043e\u0442\u00a0<a href=\"https:\/\/github.com\/python\/cpython\/blob\/7b20a0f55a16b3e2d274cc478e4d04bd8a836a9f\/Python\/hashtable.c#L295\" rel=\"noopener noreferrer nofollow\">Python<\/a>\u00a0\u0438\u00a0<a href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/dcf1523bf2dba234371190a70a41cfcb77907196\/src\/java.base\/share\/classes\/java\/util\/HashMap.java#L713\" rel=\"noopener noreferrer nofollow\">Java<\/a>\u00a0\u0432 Go \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e. \u041a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0435\u0440\u0435\u0434 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0438\u043b\u0438 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u044f\u0442\u0441\u044f \u0434\u0430\u043d\u043d\u044b\u0435 \u0438\u0437 1-2 \u0431\u0430\u043a\u0435\u0442\u043e\u0432.<\/p>\n<p>\u0414\u043b\u044f \u0440\u043e\u0441\u0442\u0430 \u043d\u0430\u043c \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u043e\u0432\u044b\u0445 \u043f\u043e\u043b\u0435\u0439:<\/p>\n<pre><code class=\"go\">type hmap[K comparable, V any] struct { len int \/\/ \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u043c\u0430\u043f\u0435 B   uint8 \/\/ log_2 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 buckets []bucket[K, V] \/\/ \u0441\u043b\u0430\u0439\u0441 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 hasher  maphash.Hasher[K] \/\/ \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0437 \u0440\u0430\u043d\u0442\u0430\u0439\u043c\u0430      \/* \u043d\u043e\u0432\u044b\u0435 \u043f\u043e\u043b\u044f *\/ oldbuckets   *[]bucket[K, V] \/\/ \u0441\u043b\u0430\u0439\u0441 \u0441\u0442\u0430\u0440\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 numEvacuated uint64 \/\/ \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0430 \u0440\u043e\u0441\u0442\u0430. \u0432\u0441\u0435 \u0431\u0430\u043a\u0435\u0442\u044b \u043c\u0435\u043d\u044c\u0448\u0435 \u044d\u0442\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u044b }<\/code><\/pre>\n<p>\u041f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430 \u0432 \u0440\u043e\u0441\u0442\u0443:<\/p>\n<pre><code class=\"go\">\/\/ \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u0441\u0447\u0435\u0442\u0447\u0438\u043a \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 func (m *hmap[K, V]) startGrowth() { oldBuckets := m.buckets m.B++ \/\/ \u0440\u0430\u0441\u0442\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u043d\u0430 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435 m.buckets = make([]bucket[K, V], bucketsNum(m.B)) m.oldbuckets = &amp;oldBuckets m.numEvacuated = 0 }<\/code><\/pre>\n<p>\u0422\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f \u0438 \u0442\u0440\u0438\u0433\u0433\u0435\u0440 \u0440\u043e\u0441\u0442\u0430 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435\u00a0<code>Put<\/code>:<\/p>\n<pre><code class=\"go\">func (h *hmap[K, V]) Put(key K, value V) { tophash, targetBucket := h.locateBucket(key)      \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \"\u0442\u0440\u0438\u0433\u0433\u0435\u0440\" \u0440\u043e\u0441\u0442\u0430 \u0435\u0441\u043b\u0438 \u043a\u043e\u043b-\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u0441\u044f if !h.isGrowing() &amp;&amp; overLoadFactor(h.len+1, h.B) { h.startGrowth() }  \/\/ \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u0443\u0435\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 if h.isGrowing() { h.growWork(targetBucket) }  if h.buckets[targetBucket].Put(key, tophash, value) { h.len++ } }<\/code><\/pre>\n<p>\u0422\u0430\u043a\u0436\u0435 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0440\u043e\u0441\u0442\u0430 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f \u043b\u0438 \u0431\u0430\u043a\u0435\u0442 \u043f\u0435\u0440\u0435\u0434 \u043f\u043e\u0438\u0441\u043a\u043e\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u0442\u0442\u0443\u0434\u0430:<\/p>\n<pre><code class=\"go\">func (h *hmap[K, V]) Get2(key K) (V, bool) { tophash, targetBucket := h.locateBucket(key)  b := &amp;h.buckets[targetBucket]  if h.isGrowing() { oldB := &amp;(*h.oldbuckets)[targetBucket&amp;h.oldBucketMask()] \/\/ \u0431\u0435\u0440\u0435\u043c \u0441\u0442\u0430\u0440\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 if !oldB.isEvacuated() { \/\/ \u0435\u0441\u043b\u0438 \u043e\u043d \u0435\u0449\u0435 \u043d\u0435 \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043b\u0441\u044f, \u0442\u043e \u0438\u0449\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043d\u0435\u043c b = oldB } }  return b.Get(key, tophash) }<\/code><\/pre>\n<h3>\u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u044f<\/h3>\n<p>\u0421\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u044b\u0439 (\u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438) &#8212; \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u043f\u043e \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c \u0432 \u0431\u0430\u043a\u0435\u0442\u0435, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u043e\u0432\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u0438 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u043c \u043a\u043b\u044e\u0447, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438 \u0442\u043e\u043f\u0445\u0435\u0448. <\/p>\n<h4>\u041a\u0443\u0434\u0430 \u043f\u0435\u0440\u0435\u0435\u0437\u0436\u0430\u0442\u044c<\/h4>\n<p>\u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043c\u0430\u043f\u044b \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432\u0434\u0432\u043e\u0435. \u0415\u0441\u043b\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u0441\u043b\u0430\u0439\u0441 \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u043d\u0430 \u0434\u0432\u0435 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b, \u0442\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432\u043d\u0443\u0442\u0440\u0438 \u0441\u0442\u0430\u0440\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u043f\u0443\u0442\u0438 <s>this is the way<\/s> &#8212; \u043b\u0438\u0431\u043e \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043b\u0438\u0431\u043e \u0432\u043e \u0432\u0442\u043e\u0440\u0443\u044e. \u0410 \u0435\u0441\u043b\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 <em>\u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c<\/em> \u0441\u043b\u0430\u0439\u0441\u043e\u043c, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c \u0447\u0442\u043e \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0430\u043a\u0435\u0442\u0430 \u0434\u043b\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u0440\u0438\u043c\u0435\u0440<\/summary>\n<div class=\"spoiler__content\">\n<p>\u0411\u044b\u043b\u043e 8 \u0431\u0430\u043a\u0435\u0442\u043e\u0432, \u043c\u044b \u043d\u0430\u0447\u0430\u043b\u0438 \u0440\u043e\u0441\u0442, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 \u0443\u0434\u0432\u043e\u0438\u043b\u043e\u0441\u044c \u0438 \u0441\u0442\u0430\u043b\u043e 16. \u0412 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u0430\u043a\u0435\u0442\u0430 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 3(\u0447\u0435\u0442\u0432\u0435\u0440\u0442\u044b\u0439 \u0431\u0430\u043a\u0435\u0442) \u043f\u0435\u0440\u0435\u043d\u0435\u0441\u0435\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u0432 \u0431\u0430\u043a\u0435\u0442 \u0432 \u043f\u0435\u0440\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 3, \u043b\u0438\u0431\u043e \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 11 (3+8). \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0431\u0430\u043a\u0435\u0442 \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c 7 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043b\u0438\u0431\u043e \u0432 7\u043e\u0439 \u043b\u0438\u0431\u043e \u0432 15\u0439(7+8).<\/p>\n<\/div>\n<\/details>\n<p>\u0411\u0430\u043a\u0435\u0442\u044b \u0438\u0437 \u0440\u0430\u0437\u043d\u044b\u0445 \u043f\u043e\u043b\u043e\u0432\u0438\u043d \u0445\u0440\u0430\u043d\u0438\u043c \u0432\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435. \u0422\u0430\u043c \u0436\u0435 \u0434\u0435\u0440\u0436\u0438\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430.<\/p>\n<pre><code class=\"go\">\/\/ evacDst \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u043b\u044f \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 type evacDst[K comparable, V any] struct { b *bucket[K, V] \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u043e \u043d\u043e\u0432\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 i uint          \/\/ \u0438\u043d\u0434\u0435\u043a\u0441 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 }  \/\/ \u0445\u0440\u0430\u043d\u0438\u043c \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u0434\u0432\u0430 \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u0434\u0430\u043d\u043d\u044b\u0435 \u0438\u0437 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e halfs := [2]evacDst[K, V]{     {b: &amp;m.buckets[oldbucket]}, \/\/ oldBucket \u0440\u0430\u0432\u0435\u043d \u043d\u043e\u043c\u0435\u0440\u0443 \u0441\u0442\u0430\u0440\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0445\u043e\u0442\u0438\u043c \u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u0442\u044c     {b: &amp;m.buckets[oldbucket+newBit]}, \/\/ newBit \u0440\u0430\u0432\u0435\u043d \u043a\u043e\u043b-\u0432\u0443 \u0441\u0442\u0430\u0440\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 }<\/code><\/pre>\n<p>\u0412\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0445\u0435\u0448\u0430 \u043e\u0442 \u043a\u043b\u044e\u0447\u0430 \u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u0431\u0438\u0442\u0430 \u043c\u0430\u0441\u043a\u0438. \u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043a \u043d\u043e\u0432\u043e\u0439 \u043c\u0430\u0441\u043a\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0431\u0438\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438 \u0440\u0435\u0448\u0430\u0435\u0442 \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u0441\u044f \u043b\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 <code>hash&amp;mask<\/code> \u0438\u043b\u0438 \u043d\u0435\u0442.<\/p>\n<pre><code class=\"go\">newBit := m.numOldBuckets() hash := m.hasher.Hash(*key) var useSecond uint8 if hash&amp;newBit != 0 {     useSecond = 1 }<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u041f\u043e\u0447\u0435\u043c\u0443 newBit<\/summary>\n<div class=\"spoiler__content\">\n<p>newBit &#8212; \u0441\u0442\u0430\u0440\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0412 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u044d\u0442\u043e \u043e\u0434\u0438\u043d \u043d\u0435 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0431\u0438\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043d\u043e\u0432\u0430\u044f \u043c\u0430\u0441\u043a\u0430 \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u043e\u0442 \u0441\u0442\u0430\u0440\u043e\u0439.<br \/>\u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u0441 8 \u0434\u043e 16 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 <br \/>newBit == 8 (1000)<br \/>mask == 15 (1111)<br \/>oldMask == 7 (0111)<br \/>\u041e\u0442 \u0441\u044e\u0434\u0430 \u0438 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439.<\/p>\n<\/div>\n<\/details>\n<p>\u041f\u043e\u043b\u043d\u044b\u0439 \u0446\u0438\u043a\u043b \u044d\u0432\u0430\u043a\u0443\u0430\u0446\u0438\u0438:<\/p>\n<pre><code class=\"go\">newBit := m.numOldBuckets() \/* ... *\/ for ; b != nil; b = b.overflow {     \/\/ \u0438\u0442\u0435\u0440\u0438\u0440\u0443\u0435\u043c\u0441\u044f \u043f\u043e \u0441\u0442\u0430\u0440\u043e\u043c\u0443 \u0431\u0430\u043a\u0435\u0442\u0443     for i := 0; i &lt; bucketSize; i++ {         top := b.tophash[i]          \/\/ \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0444\u043b\u0430\u0433\u0438 tophash \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043f\u0443\u0441\u0442\u044b\u0445 \u044f\u0447\u0435\u0435\u043a         if isCellEmpty(top) {             b.tophash[i] = evacuatedEmpty             continue         }          key := &amp;b.keys[i]         value := &amp;b.values[i]          \/\/ \u043e\u043f\u044f\u0442\u044c \u0431\u0435\u0440\u0435\u043c \u0445\u044d\u0448 \u043e\u0442 \u043a\u043b\u044e\u0447\u0430         hash := m.hasher.Hash(*key)          \/\/ \u0444\u043b\u0430\u0433 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b \u043d\u043e\u0432\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432         var useSecond uint8          \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043b\u0438 \u043c\u0435\u0441\u0442\u043e\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043e\u0442 \u043d\u043e\u0432\u043e\u0433\u043e \u0431\u0438\u0442\u0430         if hash&amp;newBit != 0 {             useSecond = 1         }          \/\/ evacuatedFirst, evacuatedSecond - \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u044b\u0435 \u0444\u043b\u0430\u0433\u0438 \u0434\u043b\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u0430 tophash \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u0432 \u043a\u0430\u043a\u0443\u044e \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0443 \u043f\u0435\u0440\u0435\u0435\u0445\u0430\u043b \u044d\u043b\u0435\u043c\u0435\u043d\u0442         \/\/ evacuatedFirst + useSecond == evaluatedSecond         b.tophash[i] = evacuatedFirst + useSecond          \/\/\u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043d\u0443\u0436\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442         dst := &amp;halfs[useSecond]         \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043a\u043e\u043b-\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432         if dst.i == bucketSize {             dst.b = newOverflow(dst.b) \/\/ \u0435\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0435\u043c overflow             dst.i = 0         }         \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443         dst.b.putAt(*key, top, *value, dst.i)         dst.i++     } }<\/code><\/pre>\n<p>\u0412 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u0435\u0441\u0442\u044c \u0442\u0430\u043a\u0430\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430:<\/p>\n<pre><code class=\"go\">if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {     throw(\"bad evacuatedN\") }<\/code><\/pre>\n<p>\u041e\u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0435 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u041d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u044d\u0442\u043e \u0441\u0442\u0440\u0430\u043d\u043d\u043e, \u0442\u0430\u043a \u043a\u0430\u043a \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u044b \u043d\u0435\u043b\u044c\u0437\u044f \u043f\u0435\u0440\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c, \u0438 \u0445\u0432\u0430\u0442\u0438\u043b\u043e \u0431\u044b \u043e\u0434\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0446\u0438\u0438. \u042f \u0437\u0430\u043c\u0435\u043d\u0438\u043b \u044d\u0442\u043e \u043d\u0430 \u0442\u0430\u043a\u0443\u044e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443:<\/p>\n<pre><code class=\"go\">func _() { var x [1]struct{} _ = x[evacuatedFirst-2] _ = x[evacuatedSecond-3] }<\/code><\/pre>\n<h3>\u0418\u0442\u0435\u0440\u0430\u0446\u0438\u044f<\/h3>\n<p>\u041f\u043b\u044e\u0441\u044b \u0442\u0430\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u043e\u0441\u0442\u0430 &#8212; \u043d\u0435\u0442<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-345611","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/345611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=345611"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/345611\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=345611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=345611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=345611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}