{"id":342430,"date":"2022-12-12T03:00:27","date_gmt":"2022-12-12T03:00:27","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=342430"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=342430","title":{"rendered":"<span>Hashmap \u043f\u043e \u0432\u0435\u0440\u0441\u0438\u0438 Golang \u0432\u043c\u0435\u0441\u0442\u0435 \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u043d\u0430 \u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u0430\u0445<\/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=\"bordered full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/b89\/101\/bad\/b89101badc588827ea9f0e815610e72c.png\" width=\"2160\" height=\"1480\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b89\/101\/bad\/b89101badc588827ea9f0e815610e72c.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u041f\u0440\u0438\u0432\u0435\u0442. \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0442\u0430\u043a\u0443\u044e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043a\u0430\u043a hashmap, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u0435\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0432 Go. \u0412\u043a\u0440\u0430\u0442\u0446\u0435 \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 hashmap, \u043a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c Go 1.19. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0442\u043b\u0438\u0447\u0438\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0441 Java \u0438 Python. \u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c hashmap \u0438\u0437-\u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u043e\u0432.<\/p>\n<h2>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 hashmap<\/h2>\n<p>\u0414\u043b\u044f \u0442\u0435\u0445, \u043a\u0442\u043e \u0435\u0449\u0435 \u043d\u0435 \u0437\u043d\u0430\u043a\u043e\u043c \u0441 hashmap, \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0438\u0437 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438<\/a>:<br \/>Hashmap &#8212; \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043f\u0430\u0440\u044b \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041a\u043b\u044e\u0447\u0438 \u0432 hashmap \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435. \u041c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043b\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043d\u043e \u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c:<\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p><strong>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f<\/strong><\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\"><strong>\u0421\u0440\u0435\u0434\u043d\u044f\u044f<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"center\"><strong>\u0425\u0443\u0434\u0448\u0430\u044f<\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0412\u0441\u0442\u0430\u0432\u043a\u0430<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/088\/734\/ec3\/088734ec333c5c1eb4efe161e42ae821.svg\" width=\"40\" height=\"22\"\/><\/p>\n<\/td>\n<td>\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/35e\/98d\/593\/35e98d593739746eb31cd57ae2a14eb9.svg\" width=\"42\" height=\"22\"\/><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041f\u043e\u0438\u0441\u043a<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/915\/97b\/af5\/91597baf534fad324a38dccf79e15b25.svg\" width=\"40\" height=\"22\"\/><\/p>\n<\/td>\n<td>\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/559\/25d\/338\/55925d3381f8260665530162ff72aa89.svg\" width=\"42\" height=\"22\"\/><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d4e\/5ae\/586\/d4e5ae58646fb33e8f8e21ea431e6337.svg\" width=\"40\" height=\"22\"\/><\/p>\n<\/td>\n<td>\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f8e\/b42\/636\/f8eb4263653916dd59a4279bdf1271c6.svg\" width=\"42\" height=\"22\"\/><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041f\u0430\u043c\u044f\u0442\u044c<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b1b\/dcf\/a0d\/b1bdcfa0d7575e3c321cbf3b4244aada.svg\" width=\"42\" height=\"22\"\/><\/p>\n<\/td>\n<td>\n<p align=\"center\"><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e46\/10c\/14d\/e4610c14d30a1c919bdd6547781afae3.svg\" width=\"42\" height=\"22\"\/><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u041f\u0440\u0438 \u0443\u0433\u043b\u0443\u0431\u043b\u0435\u043d\u0438\u0438 \u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0436\u043d\u043e \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0441\u043b\u043e\u0432\u0430: \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438, \u0431\u0430\u043a\u0435\u0442\u044b, \u0444\u0430\u043a\u0442\u043e\u0440 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438. \u0420\u0430\u0437\u0431\u0435\u0440\u0435\u043c\u0441\u044f \u0447\u0442\u043e \u043e\u043d\u0438 \u0437\u043d\u0430\u0447\u0430\u0442:<\/p>\n<ul>\n<li>\n<p><strong><em>\u0425\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f(Hash function)<\/em><\/strong>. \u041f\u043e\u0434 \u043d\u0435\u0439 \u043f\u043e\u043d\u0438\u043c\u0430\u044e\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 (\u043a\u043b\u044e\u0447) \u043d\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 c Go \u043e\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 <code>uint64<\/code>. \u041e\u0434\u043d\u043e \u0438\u0437 \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432 &#8212; \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u0414\u043b\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0438 \u0442\u043e\u0433\u043e \u0436\u0435 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442;<\/p>\n<\/li>\n<li>\n<p><strong><em>\u0411\u0430\u043a\u0435\u0442(Bucket\/Slot)<\/em><\/strong>. \u0422\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0430\u044f \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 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0430\u043f\u0435. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f\u0445 hashmap \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0430\u043a\u0435\u0442\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u043e\u0434\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0430 \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 &#8212; \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 Go \u0434\u0430\u043d\u043d\u044b\u0435 \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0438 \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0430\u043a\u0435\u0442\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043e \u0432\u043e\u0441\u044c\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432;<\/p>\n<\/li>\n<li>\n<p><strong><em>\u041a\u043e\u043b\u043b\u0438\u0437\u0438\u044f (Collision)<\/em><\/strong>. \u0422\u0430\u043a \u043a\u0430\u043a \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043d\u0435 \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u0430, \u043f\u0435\u0440\u0435\u0434\u0430\u0432 \u0432 \u043d\u0435\u0435 \u0434\u0432\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 \u0431\u0430\u043a\u0435\u0442\u0430\u043c\u0438 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u0432\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c \u0432 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0431\u0430\u043a\u0435\u0442. \u042d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0435\u0439. \u0414\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 hashmap \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u043c\u0435\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0445 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u0430\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 (\u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0439): <\/p>\n<ul>\n<li>\n<p><em>Closed addressing<\/em>. \u0425\u0440\u0430\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u0445\u044d\u0448\u0435\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a: \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u043c\u0430\u0441\u0441\u0438\u0432 \u0438 \u0434\u0440. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u044f\u0437\u044b\u043a\u0430\u0445: Go, Java, Scala;<\/p>\n<\/li>\n<li>\n<p><em>Open addressing<\/em>. \u0412 \u0431\u0430\u043a\u0435\u0442\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041f\u0440\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u043e\u0432\u0435\u043d\u0438\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u043f\u043e \u043a\u0430\u043a\u043e\u0439-\u043b\u0438\u0431\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435. \u0422\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 Python, Ruby, Rust, C++ \u0438 \u0434\u0440;<\/p>\n<\/li>\n<li>\n<p><em>Perfect hashing<\/em>. \u0412\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0430\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439. \u041f\u043e\u0434\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0441\u0442\u0430\u0442\u0438\u0447\u043d\u043e\u0433\u043e, \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043a\u043b\u044e\u0447\u0435\u0439.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p><strong><em>\u0424\u0430\u043a\u0442\u043e\u0440 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043c\u0430\u043f\u044b (Overload factor)<\/em><\/strong>. \u042d\u0442\u043e \u0447\u0438\u0441\u043b\u043e (\u043f\u043e\u0440\u043e\u0433), \u043f\u0440\u0435\u0432\u044b\u0441\u0438\u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 (\u043e\u0431\u044b\u0447\u043d\u043e \u0432\u0434\u0432\u043e\u0435) \u0434\u043b\u044f \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/26b\/12d\/dd4\/26b12ddd4077c6ba2272f906f9ba23c1.svg\" width=\"40\" height=\"22\"\/><\/p>\n<\/li>\n<\/ul>\n<h2>\u041a\u0430\u043a hashmap \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u0432 Go<\/h2>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/getpro\/habr\/upload_files\/141\/136\/940\/141136940c244e6c0d5c820a2c44cabf.jpg\" alt=\"\u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0431\u043e\u0442\u044b hashmap \u0432 Go.\" title=\"\u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0431\u043e\u0442\u044b hashmap \u0432 Go.\" width=\"2518\" height=\"1588\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/141\/136\/940\/141136940c244e6c0d5c820a2c44cabf.jpg\" data-blurred=\"true\"\/><figcaption>\u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0431\u043e\u0442\u044b hashmap \u0432 Go.<\/figcaption><\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u043e \u0448\u0430\u0433\u0430\u043c \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b hashmap. \u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0446\u0435\u043d\u043a\u0438 \u0444\u0438\u043b\u044c\u043c\u043e\u0432 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435-\u043e\u0446\u0435\u043d\u043a\u0430:<\/p>\n<ul>\n<li>\n<p>\u041f\u0435\u0440\u0435\u0434\u0430\u0435\u043c \u043a\u043b\u044e\u0447 <code>\"The Matrix\"<\/code> \u0432 \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044e. \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c <code>uint64<\/code> &#8212; 18002143618149980261;<\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043c\u0430\u0441\u043a\u0443 \u0434\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u041e\u043d\u0430 \u0440\u0430\u0432\u043d\u0430 <code>n-1<\/code>, \u0433\u0434\u0435 n &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 4 \u0431\u0430\u043a\u0435\u0442\u0430, \u0430 \u043c\u0430\u0441\u043a\u0430 \u0440\u0430\u0432\u043d\u0430 3;<\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043d\u043e\u043c\u0435\u0440 \u0431\u0430\u043a\u0435\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043c \u043d\u0430\u0448\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0431\u0438\u0442\u043e\u0432\u043e\u0435 <em>&#171;\u0438&#187;<\/em>: <code>hash &amp; mask<\/code> == <code>18002143618149980261 &amp; 3<\/code> == <code>01 &amp; 11<\/code>(\u043e\u0442\u0431\u0440\u043e\u0441\u0438\u043b\u0438 \u043d\u0443\u043b\u0438) = <code>01<\/code>, \u0447\u0442\u043e \u0440\u0430\u043d\u043e 1 \u0432 \u0434\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f;<\/p>\n<\/li>\n<li>\n<p>\u0418\u0434\u0435\u043c \u0432 \u0431\u0430\u043a\u0435\u0442 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 1 \u0438 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043d\u0430\u0448\u0435\u0433\u043e \u043a\u043b\u044e\u0447\u0430. \u0415\u0441\u043b\u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043f\u043e \u043a\u043b\u044e\u0447\u0443, \u0442\u043e \u043f\u0435\u0440\u0435\u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438\u043d\u0430\u0447\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043f\u0435\u0440\u0432\u043e\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e;<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u0430\u043f\u044b \u0438 \u0431\u0430\u043a\u0435\u0442\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u044f\u0442 \u0442\u0430\u043a:<br \/><em>runtime\/map.go<\/em><\/p>\n<pre><code class=\"go\">\/\/ A header for a Go map. type hmap struct { count     int \/\/ \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u043f\u044b. \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 len() flags     uint8 B         uint8  \/\/ log_2 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0414\u043b\u044f 8 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 B=3, \u0434\u043b\u044f 16 B=4 \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435. noverflow uint16 \/\/ \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 hash0     uint32 \/\/ seed \u0434\u043b\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043c\u0430\u043f\u044b. \u043d\u0443\u0436\u0435\u043d \u0434\u043b\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438  buckets    unsafe.Pointer \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 2^B \u0431\u0430\u043a\u0435\u0442\u043e\u0432; nil, \u0435\u0441\u043b\u0438 count==0 oldbuckets unsafe.Pointer \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u043c\u0430\u043f\u044b \u0437\u0434\u0435\u0441\u044c \u0431\u0443\u0434\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0442\u0430\u0440\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432, \u043e\u0442\u043a\u0443\u0434\u0430 \u043f\u043e\u0442\u0438\u0445\u043e\u043d\u044c\u043a\u0443 \u0431\u0443\u0434\u0443\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b. nevacuate  uintptr        \/\/ \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \"\u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445\" \u0431\u0430\u043a\u0435\u0442\u043e\u0432.  extra *mapextra \/\/ \u043e\u043f\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u043e\u043b\u044f }  \/\/ A bucket for a Go map. type bmap struct { tophash [bucketCnt]uint8 \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 tophash \/\/ \u041f\u043e\u0441\u043b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 tophash \u0438\u0434\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 bucketCnt \u043a\u043b\u044e\u0447\u0435\u0439 \u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 bucketCnt \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. }<\/code><\/pre>\n<p>\u0412 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0431\u0430\u043a\u0435\u0442\u0430 \u044f\u0432\u043d\u043e \u043d\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u043f\u043e\u043b\u044f \u043a\u043b\u044e\u0447\u0435\u0439, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 overflow \u0431\u0430\u043a\u0435\u0442. \u0414\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u044d\u0442\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0430\u0434\u0440\u0435\u0441\u043d\u0430\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u0447\u0435\u0440\u0435\u0437 <code>unsafe.Pointer<\/code>.<\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438:<\/p>\n<ul>\n<li>\n<p>\u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043b\u044e\u0447\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u0442\u0438\u043f \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0441 \u0442\u0435\u043c \u0436\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435\u043c \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0435\u0435 \u043f\u043e\u043b\u0435\u0439;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0442\u0438\u043f\u0430. \u0412\u0442\u043e\u0440\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0444\u043b\u0430\u0433 \u043d\u0430\u043b\u0438\u0447\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u043a\u043b\u044e\u0447\u0443;<\/p>\n<\/li>\n<li>\n<p>\u041d\u0435\u043b\u044c\u0437\u044f \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0430\u0434\u0440\u0435\u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u041f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043c\u0430\u043f\u044b \u043e\u043d\u043e \u043f\u0435\u0440\u0435\u0435\u0434\u0435\u0442 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u0431\u0430\u043a\u0435\u0442 \u0438 \u0430\u0434\u0440\u0435\u0441 \u0443 \u043d\u0435\u0433\u043e, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f;<\/p>\n<\/li>\n<li>\n<p>\u041c\u0430\u043f\u0430 \u043d\u0435 \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u0430 \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0431\u0435\u0440\u0442\u043a\u0443 \u0438\u0437 <code>sync.Map<\/code> \u0438\u043b\u0438 \u043c\u044c\u044e\u0442\u0435\u043a\u0441;<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0440\u044f\u0434\u043e\u043a \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f. \u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u043d\u043e\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043c\u0430\u043f\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f. \u041f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u044b\u0439 \u0431\u0430\u043a\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. \u0414\u043b\u044f \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u043a\u043b\u044e\u0447\u0438 \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438 \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u043d\u0435\u043c\u0443;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043c\u0430\u043f\u044b \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f seed \u0434\u043b\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u042d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043e \u0434\u043b\u044f \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u0437\u043d\u0430\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u043a\u043b\u044e\u0447\u0438, \u0447\u0442\u043e \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u043e\u0434\u0438\u043d \u0431\u0430\u043a\u0435\u0442 \u0438 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f <em>\u0441losed addressing.<\/em> \u041c\u044b \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0432\u0441\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 (\u0438\u0445 8) \u0438 \u0438\u0449\u0435\u043c \u043f\u0435\u0440\u0432\u043e\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e;<\/p>\n<\/li>\n<li>\n<p><em>OverloadFactor<\/em> \u0440\u0430\u0432\u0435\u043d 6.5 (~81% \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u0431\u0430\u043a\u0435\u0442\u043e\u0432). \u041a\u043e\u0433\u0434\u0430 \u0431\u0430\u043a\u0435\u0442\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u043d\u0430 6.5 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0442\u0440\u0438\u0433\u0435\u0440\u0438\u0442\u0441\u044f \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b, \u0438 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u0435.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u044f\u0442\u0441\u044f \u0432 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e, \u0430 \u043d\u0435 \u0432\u0441\u0435 \u0441\u0440\u0430\u0437\u0443;<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u044f \u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0439 \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 \u044f\u0437\u044b\u043a\u0430\u0445<\/h2>\n<p><strong><em>Python 3.6+<\/em><\/strong>. \u041f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432 \u043e\u0447\u0435\u043d\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c (\u043f\u0440\u0430\u0432\u0434\u0430) \u0434\u043e\u043a\u043b\u0430\u0434\u0435 <a href=\"https:\/\/www.youtube.com\/watch?v=npw4s1QTmPg\" rel=\"noopener noreferrer nofollow\">Raymond Hettinger Modern Python Dictionaries (2017)<\/a><\/p>\n<ul>\n<li>\n<p>\u0421\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043a\u0438;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u0445 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u0438\u0449\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 open addressing. \u0414\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 <a href=\"https:\/\/github.com\/python\/cpython\/blob\/22d91c16bb03c3d87f53b5fee10325b876262a78\/Objects\/dictobject.c#L175\" rel=\"noopener noreferrer nofollow\">\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f<\/a> \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u044b: <code>j = ((5*j) + 1) mod 2**i<\/code> \u0438 <code>j = (5*j) + 1 + perturb<\/code>;<\/p>\n<\/li>\n<li>\n<p>\u0414\u0430\u043d\u043d\u044b\u0435 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u043e\u0442 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0421\u0430\u043c\u0438 \u0431\u0430\u043a\u0435\u0442\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u0430\u043a \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 (\u0438\u043d\u0434\u0435\u043a\u0441\u044b) \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0435. \u0412\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u044d\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">  indices =  [None, 1, None, None, None, 0, None, 2]   entries =  [[-9092791511155847987, 'timmy', 'red'],               [-8522787127447073495, 'barry', 'green'],               [-6480567542315338377, 'guido', 'blue']]<\/code><\/pre>\n<ul>\n<li>\n<p>\u0420\u044f\u0434\u043e\u043c \u0441 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u044b\u0439 \u0445\u044d\u0448. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0435 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u043f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043c\u0430\u043f\u044b.<\/p>\n<\/li>\n<li>\n<p>LoadFactor &#8212; 2\/3 = ~66%<\/p>\n<\/li>\n<\/ul>\n<p><strong><em>Java<\/em><\/strong>. \u0420\u0430\u0437\u0431\u043e\u0440 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 <a href=\"https:\/\/habr.com\/ru\/post\/421179\/\" rel=\"noopener noreferrer nofollow\">\u0412\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0440\u0430\u0431\u043e\u0442\u0430 HashMap \u0432 Java<\/a>:<\/p>\n<ul>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f <em>\u0441losed addressing<\/em>, \u043d\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u0422\u0430\u043a\u0436\u0435 \u043a\u043e\u0433\u0434\u0430 \u0434\u043b\u0438\u043d\u0430 \u0441\u043f\u0438\u0441\u043a\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u043e\u0441\u044c\u043c\u0438 \u043e\u043d \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0432 TreeMap. \u042d\u0442\u043e \u0434\u0430\u0435\u0442 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(logn)\" alt=\"O(logn)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/43e\/697\/8c1\/43e6978c1e99d791b2bd09c61f44b8d7.svg\" width=\"67\" height=\"22\"\/>\u0432\u043c\u0435\u0441\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fc8\/29b\/814\/fc829b814054f79044615844ddb92b11.svg\" width=\"42\" height=\"22\"\/>\u043a\u0430\u043a \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u043c \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0438\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c;<\/p>\n<\/li>\n<li>\n<p>\u0412\u0441\u0435 \u043a\u043b\u044e\u0447\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043d\u044b\u0435 \u0442\u0438\u043f\u044b (boolean, int, char, float \u0438 \u0442.\u0434) \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0441\u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0432 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0447\u0435\u0440\u0435\u0437 <a href=\"https:\/\/docs.oracle.com\/javase\/tutorial\/java\/data\/autoboxing.html\" rel=\"noopener noreferrer nofollow\">boxing<\/a>;<\/p>\n<\/li>\n<li>\n<p><em>LoadFactor<\/em> \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e &#8212; 75%. \u041f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043c\u0430\u043f\u044b \u043c\u043e\u0436\u043d\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u0441\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430.<\/p>\n<\/li>\n<\/ul>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f\u043c\u0438 Java \u0438 C++ \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0443 <a href=\"https:\/\/dave.cheney.net\/2018\/05\/29\/how-the-go-runtime-implements-maps-efficiently-without-generics\" rel=\"noopener noreferrer nofollow\">Dave Cheney<\/a>.<\/p>\n<h2>\u041a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h2>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0431\u0430\u0437\u043e\u0432\u043e hashmap \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u043e\u0432 Go 1.19. \u041d\u0435 \u0431\u0443\u0434\u0435\u043c \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b, \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0435 \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0442\u0438\u043f\u044b \u0434\u043b\u044f \u043a\u043b\u044e\u0447\u0435\u0439.<\/p>\n<h3>\u041d\u0430\u0447\u043d\u0435\u043c \u0441 \u0432\u0435\u0434\u0435\u0440<\/h3>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/7dc\/814\/3eb\/7dc8143ebe09a53c5d8372ff5a49ff84.png\" width=\"165\" height=\"240\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/7dc\/814\/3eb\/7dc8143ebe09a53c5d8372ff5a49ff84.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0431\u0430\u043a\u0435\u0442\u0430. <\/p>\n<p>\u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0434\u043b\u044f \u043a\u043b\u044e\u0447\u0435\u0439 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0438 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0431\u0430\u043a\u0435\u0442 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e. \u0414\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0445\u0440\u0430\u043d\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0435\u0440\u0432\u044b\u0445 \u0432\u043e\u0441\u044c\u043c\u0438 \u0431\u0438\u0442 \u043e\u0442 \u0445\u044d\u0448\u0430 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f tophash.<\/p>\n<pre><code class=\"go\">const bucketSize = 8 \/\/ \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430  type bucket[T any] struct { tophash [bucketSize]uint8 \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0435\u0440\u0432\u044b\u0445 \u0432\u043e\u0441\u044c\u043c\u0438 \u0431\u0438\u0442 \u043e\u0442 \u0445\u044d\u0448\u0430 \u043a\u043b\u044e\u0447\u0430; \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043a\u0430\u043a \u0444\u043b\u0430\u0433\u0438, \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u043d\u0438\u0436\u0435.  keys   [bucketSize]string \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u044e\u0447\u0435\u0439 values [bucketSize]T \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439  overflow *bucket[T] \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0431\u0430\u043a\u0435\u0442 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e }<\/code><\/pre>\n<h4>\u041f\u0440\u043e tophash<\/h4>\n<p>\u0412 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0441 tophash \u043c\u044b \u0440\u0435\u0437\u0435\u0440\u0432\u0438\u0440\u0443\u0435\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u041a\u043e \u0432\u0441\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c tophash, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 <code>minTopHash<\/code> \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0435\u0433\u043e.<\/p>\n<pre><code class=\"go\">const ( emptyRest  = 0 \/\/ \u044d\u0442\u0430 \u0438 \u0432\u0441\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 \u0441 \u0431\u041e\u043b\u044c\u0448\u0438\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c \u043f\u0443\u0441\u0442\u044b\u0435 emptyCell  = 1 \/\/ \u044f\u0447\u0435\u0439\u043a\u0430 \u043f\u0443\u0441\u0442\u0430\u044f minTopHash = 3 \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 tophash \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0449\u0435\u0435 \u0447\u0442\u043e \u0432 \u044f\u0447\u0435\u0439\u043a\u0435 \u0435\u0441\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 )<\/code><\/pre>\n<p>\u041f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e, \u0432 Go \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d \u043d\u0443\u043b\u0435\u0432\u044b\u043c\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0434\u043b\u044f tophash \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0438\u043f\u0430 <code>uint8<\/code>, \u0431\u0443\u0434\u0443\u0442 \u043d\u0443\u043b\u0438. \u041f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u0431\u0430\u043a\u0435\u0442\u0430 \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u0443\u0435\u043c\u0441\u044f \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432 tophash, \u0430 \u043d\u0435 \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u044e\u0447\u0435\u0439. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430.<\/p>\n<h3>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043c\u0430\u043f\u0443<\/h3>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430:<\/p>\n<ul>\n<li>\n<p>\u0412 \u0446\u0438\u043a\u043b\u0435 \u0438\u0449\u0435\u043c \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f \u043f\u043e tophash \u0438 \u043a\u043b\u044e\u0447\u0443 \u0438\u043b\u0438 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e. \u0421\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0435 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0444\u043b\u0430\u0433 \u0434\u043b\u044f \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u043f\u0435.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u043d\u0435 \u043d\u0430\u0448\u043b\u0438 \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430, \u0442\u043e \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u0443\u043f\u0440\u0430\u0436\u043d\u0435\u043d\u0438\u044f \u043d\u0430 overflow \u0431\u0430\u043a\u0435\u0442\u0435.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"go\">\/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u0431\u0430\u043a\u0435\u0442. \/\/ \u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u044b\u0435 \u043a\u043b\u044e\u0447 \u0443\u0436\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u0437\u0430\u043f\u0438\u0448\u0435\u0442\u0441\u044f. \/\/ \u0415\u0441\u043b\u0438 \u0431\u0430\u043a\u0435\u0442 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 overflow. func (b *bucket[T]) Put(key string, topHash uint8, value T) (isAdded bool) { var insertIdx *int  for i := range b.tophash { \/\/ \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c tophash \u0430 \u043d\u0435 \u043a\u043b\u044e\u0447, \u0442.\u043a. \u044d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u043b\u0430\u0433\u0438 \u0438 \u044d\u0442\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 if b.tophash[i] != topHash { if b.tophash[i] == emptyRest { insertIdx = new(int) *insertIdx = i break }  if insertIdx == nil &amp;&amp; isCellEmpty(b.tophash[i]) { insertIdx = new(int) *insertIdx = i } continue }  \/\/ tophash \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043d\u0435 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b, \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438 \u0441\u0430\u043c \u043a\u043b\u044e\u0447 if b.keys[i] != key { continue }  b.values[i] = value return false }  \/\/ \u0435\u0441\u043b\u0438 \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d, \u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c overflow \u0431\u0430\u043a\u0435\u0442 if insertIdx == nil { if b.overflow == nil { b.overflow = &amp;Bucket[T]{} }  return b.overflow.Put(key, topHash, value) }  \/\/ \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u043a\u043b\u044e\u0447, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438 tophash b.keys[*insertIdx] = key b.values[*insertIdx] = value b.tophash[*insertIdx] = topHash  \/\/ \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u043f\u0440\u0438\u0437\u043d\u0430\u043a \u0443\u0441\u043f\u0435\u0445\u0430. \u043f\u043e \u043d\u0435\u043c\u0443 \u043a\u0430\u043b\u044c\u043a\u0443\u043b\u0438\u0440\u0443\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u043f\u0435. return true }  \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 tophash &lt;= \u0447\u0435\u043c \u0437\u0430\u0440\u0435\u0437\u0435\u0440\u0432\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043f\u0443\u0441\u0442\u043e\u0439 \u044f\u0447\u0435\u0439\u043a\u0438 func isCellEmpty(val uint8) bool { return val &lt;= emptyCell } <\/code><\/pre>\n<h3>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442<\/h3>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043a\u0430\u043a \u0438 \u0432 \u043c\u0435\u0442\u043e\u0434\u0435 <code>Put<\/code>. \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0444\u043b\u0430\u0433 \u043d\u0430\u043b\u0438\u0447\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435.<\/p>\n<pre><code class=\"go\">func (b bucket[T]) Get(key string, topHash uint8) (T, bool) { for i := range b.tophash { if b.tophash[i] != topHash { \/\/ \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0447\u0442\u043e \u0432\u0441\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 \u043f\u0443\u0441\u0442\u044b\u0435 -- \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u0438\u0437 \u0446\u0438\u043a\u043b\u0430. if b.tophash[i] == emptyRest { break } continue }  if !isCellEmpty(b.tophash[i]) &amp;&amp; b.keys[i] == key { return b.values[i], true } }  \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0431\u0430\u043a\u0435\u0442 overflow if b.overflow != nil { return b.overflow.Get(key, topHash) }  return *new(T), false } <\/code><\/pre>\n<h3>\u0423\u0434\u0430\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442<\/h3>\n<p>\u0412\u043c\u0435\u0441\u0442\u043e \u0444\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u043c\u0435\u0447\u0430\u0435\u043c \u044f\u0447\u0435\u0439\u043a\u0443 \u043f\u0443\u0441\u0442\u043e\u0439.<\/p>\n<pre><code class=\"go\">\/\/ Delete - \u0443\u0434\u0430\u043b\u044f\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443 func (b *bucket[T]) Delete(key string, topHash uint8) (deleted bool) { for i := range b.tophash { if b.tophash[i] != topHash { \/\/ \u0435\u0441\u043b\u0438 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u043c \u0444\u043b\u0430\u0433 \u0432\u0441\u0435 \u0441\u043b\u0435\u0434. \u044f\u0447\u0435\u0439\u043a\u0438 \u043f\u0443\u0441\u0442\u044b\u0435, \u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u0445\u043e\u0434\u0438\u043c \u0438\u0437 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 if b.tophash[i] == emptyRest { return false } continue }  \/\/ \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043f\u043e \u043a\u043b\u044e\u0447\u0443, \u0442.\u043a. tophash \u043d\u0435 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0439 if b.keys[i] == key { b.tophash[i] = emptyCell return true } }  \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c overflow \u0431\u0430\u043a\u0435\u0442 if b.overflow != nil { return b.overflow.Delete(key, topHash) }  return false } <\/code><\/pre>\n<h3>\u0421\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043c\u0430\u043f\u044b<\/h3>\n<p>\u0425\u0440\u0430\u043d\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u043f\u044b, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432, seed \u0434\u043b\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0438 \u0441\u043b\u0430\u0439\u0441 \u0441\u0430\u043c\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432.<\/p>\n<pre><code class=\"go\">\/\/ hmap - \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u043c\u0430\u043f\u044b type hmap[T 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 seed uint64 \/\/ \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0445\u044d\u0448  buckets []Bucket[T] \/\/ \u0441\u043b\u0430\u0439\u0441 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 }  \/\/ \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441 hashmap, \u043c\u0435\u0442\u043e\u0434\u044b \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c type Hashmap[T any] interface { Get(key string) T Get2(key string) (T, bool) Put(key string, value T) Delete(key string) Range(f func(k string, v T) bool) Len() int }<\/code><\/pre>\n<p>\u041f\u0440\u0438 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u043c seed \u0438 \u0441\u043e\u0437\u0434\u0430\u0435\u043c \u043d\u0443\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432.<\/p>\n<pre><code class=\"go\">const ( \/\/ \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0440\u0438\u0433\u0435\u0440\u0438\u0442 \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b - 6.5 \/\/ \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u043a\u0430\u043a loadFactorNum\/loadFactorDen, \u0434\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0447\u0435\u0440\u0435\u0437 int. loadFactorNum = 13 loadFactorDen = 2      ptrSize = 4 &lt;&lt; (^uintptr(0) >> 63) \/\/ \u0440\u0430\u0437\u043c\u0435\u0440 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f. \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f tophash )  func New[T any](size int) Hashmap[T] { h := new(hmap[T])  h.seed = generateSeed()  \/\/ \u0442\u043e\u0442 \u0441\u0430\u043c\u044b\u0439 log_2 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 B := uint8(0) \/\/ \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c B \u043f\u043e\u043a\u0430 \u0441\u0440\u0435\u0434\u043d\u044f\u044f \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u0431\u0430\u043a\u0435\u0442\u043e\u0432 > loadFactor  for overLoadFactor(size, B) { B++ } h.b = B  h.buckets = make([]bucket[T], bucketsNum(h.b))  return h }  \/\/ \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0431\u0443\u0434\u0443\u0442 \u043b\u0438 \u0431\u0430\u043a\u0435\u0442\u044b, \u0434\u043b\u044f size \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0437\u0430\u0433\u0440\u0443\u0436\u0435\u043d\u044b \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c loadFactor \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c. \/\/ \u044d\u0442\u043e\u0439 \u0436\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 \u043f\u043e\u0442\u043e\u043c \u0431\u0443\u0434\u0435\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u043d\u0443\u0436\u043d\u043e \u043b\u0438 \u043d\u0430\u0447\u0430\u0442\u044c \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b func overLoadFactor(size int, b uint8) bool { return size > bucketSize &amp;&amp; uint64(size) > loadFactorNum*(bucketsNum(b)\/loadFactorDen) }  \/\/ \u0437\u0434\u0435\u0441\u044c b - log_2 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 func bucketsNum(b uint8) uint64 { return 1 &lt;&lt; b }<\/code><\/pre>\n<h3>Get\/Set\/Delete<\/h3>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u043b\u043e\u0433\u0438\u043a\u0443 \u043c\u044b \u0437\u0430\u043b\u043e\u0436\u0438\u043b\u0438 \u0432 \u043c\u043e\u0434\u0435\u043b\u0438 \u0431\u0430\u043a\u0435\u0442\u0430. \u041e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c tophash \u0438 \u043d\u043e\u043c\u0435\u0440 \u0431\u0430\u043a\u0435\u0442\u0430. \u0414\u043b\u044f put\/delete \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0445\u0440\u0430\u043d\u0438\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<pre><code class=\"go\">\/\/ Get - \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u043a\u043b\u044e\u0447\u0443 key \/\/ \u0432\u0435\u0440\u043d\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 &lt;T> \u0435\u0441\u043b\u0438 \u043f\u043e \u043a\u043b\u044e\u0447\u0443 key \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. func (h hmap[T]) Get(key string) T { tophash, targetBucket := h.locateBucket(key)      v, _ := h.buckets[targetBucket].Get(key, tophash)     return v }  \/\/ Get2 - \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u043a\u043b\u044e\u0447\u0443 key \u0438 \u0444\u043b\u0430\u0433 \u043d\u0430\u043b\u0438\u0447\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0430\u043f\u0435 \/\/ \u0432\u0435\u0440\u043d\u0435\u0442 \u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 &lt;T> \u0438 false \u0435\u0441\u043b\u0438 \u043f\u043e \u043a\u043b\u044e\u0447\u0443 key \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. func (h hmap[T]) Get2(key string) (T, bool) { tophash, targetBucket := h.locateBucket(key)      return h.buckets[targetBucket].Get(key, tophash) }  \/\/ Put - \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043c\u0430\u043f\u0443 func (h hmap[T]) Put(key string, value T) { tophash, targetBucket := h.locateBucket(key)  if h.buckets[targetBucket].Put(key, tophash, value) { h.len++ } }  \/\/ Delete - \u0443\u0434\u0430\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0438\u0437 \u043c\u0430\u043f\u044b \u043f\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443 func (h hmap[T]) Delete(key string) { tophash, targetBucket := h.locateBucket(key) if h.buckets[targetBucket].Delete(key, tophash){ h.len-- } }<\/code><\/pre>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043d\u043e\u043c\u0435\u0440\u0430 \u0431\u0430\u043a\u0435\u0442\u0430 \u0438 tophash:<\/p>\n<pre><code class=\"go\">\/\/ locateBucket - \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0438\u043d\u0434\u0435\u043a\u0441 \u0431\u0430\u043a\u0435\u0442\u0430 \u0438 tophash func (h hmap[T]) locateBucket(key string) (tophash uint8, targetBucket uint64) { hash := hash(key, h.seed) tophash = topHash(hash) mask := bucketMask(h.b)  targetBucket = hash &amp; mask  return tophash, targetBucket }  \/\/ \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043f\u0435\u0440\u0432\u044b\u0435 8 \u0431\u0438\u0442 \u043e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f func topHash(val uint64) uint8 { tophash := uint8(val >> (ptrSize*8 - 8)) if tophash &lt; minTopHash { tophash += minTopHash } return tophash }  \/\/ bucketMask \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043c\u0430\u0441\u043a\u0443 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 func bucketMask(b uint8) uint64 { return bucketsNum(b) - 1 }  \/\/ \u0434\u043b\u044f \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c wyhash func hash(key string, seed uint64) uint64 { return wyhash.Hash([]byte(key), seed) }<\/code><\/pre>\n<h3>\u0418\u0442\u0435\u0440\u0430\u0446\u0438\u044f<\/h3>\n<p>\u0418\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0447\u0435\u0440\u0435\u0437 callback \u0444\u0443\u043d\u043a\u0446\u0438\u044e. \u0412\u043c\u0435\u0441\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0442\u043e\u0440\u0430 <code>break<\/code> \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u043b\u0430\u0433 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u044b\u0439 callback \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439. \u0414\u043b\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043f\u0440\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u043c \u0442\u0430\u043a \u0436\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0442\u044c \u0441\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430.<\/p>\n<pre><code class=\"go\">\/\/ Range - \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c \u0441 \u0432\u044b\u0437\u043e\u0432\u043e\u043c \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 func (m hmap[T]) Range(f func(key string, value T) bool) { for i := range m.randRangeSequence() { bucket := &amp;m.buckets[i] for bucket != nil { for j, th := range bucket.tophash { \/\/ \u0438\u0434\u0435\u0442 \u043a \u0441\u043b\u0435\u0434. \u0431\u0430\u043a\u0435\u0442\u0443 \u0435\u0441\u043b\u0438 \u0432\u0438\u0434\u0438\u043c \u0444\u043b\u0430\u0433 \u043e \u043f\u0443\u0441\u0442\u044b\u0445 \u044f\u0447\u0435\u0439\u043a\u0430\u0445 \u043f\u043e\u0441\u043b\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 j if th == emptyRest { continue } \/\/ \u0435\u0441\u043b\u0438 \u0432 \u044f\u0447\u0435\u0439\u043a\u0435 \u0435\u0441\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0442\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u043c \u0432 \u0444\u0443\u043d\u043a\u0446\u0438\u044e if th >= minTopHash { \/\/ \u043f\u0440\u0435\u0440\u044b\u0432\u0430\u0435\u043c \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044e \u0435\u0441\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 false if !f(bucket.keys[j], bucket.values[j]) { return } } } \/\/ \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c overflow \u0431\u0430\u043a\u0435\u0442\u044b bucket = bucket.overflow } } }  \/\/ \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u043e \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430. func (m hmap[T]) randRangeSequence() []int { i := rand.Intn(len(m.buckets))  seq := make([]int, 0, len(m.buckets)) for len(seq) != len(m.buckets) { seq = append(seq, i) i++ if i >= len(m.buckets) { i = 0 } }  return seq }<\/code><\/pre>\n<h3>\u0422\u0435\u0441\u0442\u044b, \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438<\/h3>\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438 \u0442\u0435\u0441\u0442\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u043d\u0430 <a href=\"https:\/\/github.com\/w1kend\/go-map\" rel=\"noopener noreferrer nofollow\">Github<\/a>. \u0420\u0430\u0434\u0438 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0430 \u043d\u0430\u043f\u0438\u0448\u0435\u043c \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0438 \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0441 \u043c\u0430\u043f\u043e\u0439 \u0438\u0437 \u043a\u043e\u0440\u043e\u0431\u043a\u0438.<br \/>\u041f\u0440\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u0432 <code>Put<\/code> \u0438 <code>Get<\/code> \u0432 \u043f\u0440\u0435\u0434\u0435\u043b\u0430\u0445 \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 20%:<\/p>\n<pre><code class=\"go\">var sizes = []int{128, 1024, 8192} func BenchmarkGet(b *testing.B) { for _, n := range sizes { \/\/ \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043f\u043e\u0434 n \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 mm := New[int64](n) for i := 0; i &lt; n; i++ { mm.Put(fmt.Sprintf(\"key__%d\", i), int64(i)*2) }  b.Run(fmt.Sprintf(\"generic-map_%d\", n), func(b *testing.B) { var got int64 j := 0 for i := 0; i &lt; b.N; i++ { if j > n { j = 0 } got = mm.Get(fmt.Sprintf(\"key__%d\", j)) j++ } _ = got }) } \/\/ \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043a\u043e\u0434 \u0434\u043b\u044f std \u043c\u0430\u043f\u044b  }<\/code><\/pre>\n<pre><code class=\"bash\">go test . -run=^$ -bench . -benchmem goos: darwin goarch: arm64 pkg: github.com\/w1kend\/go-map BenchmarkGet\/generic-map_128-8          12884936                85.63 ns\/op            8 B\/op          1 allocs\/op BenchmarkGet\/generic-map_1024-8         13559966                87.57 ns\/op           14 B\/op          1 allocs\/op BenchmarkGet\/generic-map_8192-8         11720404               101.1 ns\/op            22 B\/op          1 allocs\/op BenchmarkGet\/std-map_128-8              17141264                70.01 ns\/op            8 B\/op          1 allocs\/op BenchmarkGet\/std-map_1024-8             16442701                72.42 ns\/op           14 B\/op          1 allocs\/op BenchmarkGet\/std-map_8192-8             14521720                81.84 ns\/op           22 B\/op          1 allocs\/op BenchmarkPut\/generic-map_128-8          16028941                74.27 ns\/op            8 B\/op          1 allocs\/op BenchmarkPut\/generic-map_1024-8         15961150                75.22 ns\/op           14 B\/op          1 allocs\/op BenchmarkPut\/generic-map_8192-8         12941882                85.13 ns\/op           22 B\/op          1 allocs\/op BenchmarkPut\/std-map_128-8              16949132                70.37 ns\/op            8 B\/op          1 allocs\/op BenchmarkPut\/std-map_1024-8             16461930                71.99 ns\/op           14 B\/op          1 allocs\/op BenchmarkPut\/std-map_8192-8             14040560                82.28 ns\/op           22 B\/op          1 allocs\/op<\/code><\/pre>\n<p>\u041f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043c\u0430\u043f\u044b. \u0412\u044b\u0434\u0435\u043b\u044f\u0435\u043c \u043f\u0430\u043c\u044f\u0442\u044c \u043d\u0430 1000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438 \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u0434\u043e 10 000, 100 000 \u0438 1 000 000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432:<\/p>\n<pre><code class=\"go\">func BenchmarkPutWithOverflow(b *testing.B) { startSize := 1_000 targetSize := []int{10_000, 100_000, 1_000_000}  for _, n := range targetSize { mm := New[int64](startSize) b.Run(fmt.Sprintf(\"generic-map-with-overflow__%d\", n), func(b *testing.B) { j := 0 for i := 0; i &lt; b.N; i++ { if j > n { j = 0 } mm.Put(fmt.Sprintf(\"key__%d\", j), int64(j)) j++ } }) }  for _, n := range targetSize { stdm := make(map[string]int64, startSize) b.Run(fmt.Sprintf(\"std-map-with-evacuation__%d\", n), func(b *testing.B) { j := 0 for i := 0; i &lt; b.N; i++ { if j > n { j = 0 } stdm[fmt.Sprintf(\"key__%d\", j)] = int64(j) j++ } }) } }  <\/code><\/pre>\n<pre><code class=\"bash\">go test . -run=^$ -bench ^BenchmarkPutWithOverflow$ -benchmem goos: darwin goarch: arm64 pkg: github.com\/w1kend\/go-map BenchmarkPutWithOverflow\/generic-map-with-overflow__10000-8             11472094               104.9 ns\/op            23 B\/op          1 allocs\/op BenchmarkPutWithOverflow\/generic-map-with-overflow__100000-8             3440781               344.7 ns\/op            23 B\/op          1 allocs\/op BenchmarkPutWithOverflow\/generic-map-with-overflow__1000000-8            1000000              8376 ns\/op              57 B\/op          3 allocs\/op BenchmarkPutWithOverflow\/std-map-with-evacuation__10000-8               14312827                83.43 ns\/op           23 B\/op          1 allocs\/op BenchmarkPutWithOverflow\/std-map-with-evacuation__100000-8              12691999                90.62 ns\/op           23 B\/op          1 allocs\/op BenchmarkPutWithOverflow\/std-map-with-evacuation__1000000-8              7283215               168.7 ns\/op            23 B\/op          1 allocs\/op <\/code><\/pre>\n<p>\u041f\u043e\u043a\u0430 \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a \u043d\u0435 \u043e\u0441\u043e\u0431\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0442\u0438\u0432\u043d\u044b\u0439, \u0442\u0430\u043a \u043a\u0430\u043a, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0431\u0443\u0434\u0443\u0442 \u0445\u0443\u0436\u0435. \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u043d\u0430 \u0441\u043a\u043e\u043b\u044c\u043a\u043e:<\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td data-colwidth=\"291\" width=\"291\">\n<p align=\"left\"><strong>\u0423\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441 1000 \u0434\u043e<\/strong><\/p>\n<\/td>\n<td data-colwidth=\"145\" width=\"145\">\n<p align=\"left\"><strong>Std map<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>Generic map<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>\u0420\u0430\u0437\u043d\u0438\u0446\u0430<\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"291\" width=\"291\">\n<p align=\"left\">10 000<\/p>\n<\/td>\n<td data-colwidth=\"145\" width=\"145\">\n<p align=\"left\">83.43 ns\/op<\/p>\n<\/td>\n<td>\n<p align=\"left\">104.9 ns\/op<\/p>\n<\/td>\n<td>\n<p align=\"left\">1.25<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"291\" width=\"291\">\n<p align=\"left\">100 000<\/p>\n<\/td>\n<td data-colwidth=\"145\" width=\"145\">\n<p align=\"left\">90.62 ns\/op<\/p>\n<\/td>\n<td>\n<p align=\"left\">344.7 ns\/op<\/p>\n<\/td>\n<td>\n<p align=\"left\">3.8<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td data-colwidth=\"291\" width=\"291\">\n<p align=\"left\">1 000 000<\/p>\n<\/td>\n<td data-colwidth=\"145\" width=\"145\">\n<p align=\"left\">168.7 ns\/op<\/p>\n<\/td>\n<td>\n<p align=\"left\">8376 ns\/op<\/p>\n<\/td>\n<td>\n<p align=\"left\">49.65<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<hr\/>\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. \u0421\u0442\u0430\u0432\u044c\u0442\u0435 \u043b\u0430\u0439\u043a\u0438, \u043f\u043e\u0434\u043f\u0438\u0441\u044b\u0432\u0430\u0439\u0442\u0435\u0441\u044c \u043d\u0430 \u0433\u0438\u0442\u0445\u0430\u0431. <br \/>\u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u0438:<\/p>\n<ul>\n<li>\n<p>\u041d\u0430\u0443\u0447\u0438\u043c \u043c\u0430\u043f\u0443 \u0440\u0430\u0441\u0442\u0438;<\/p>\n<\/li>\n<li>\n<p>\u0417\u0430\u043c\u0435\u0440\u0438\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435;<\/p>\n<\/li>\n<li>\n<p>\u0414\u043e\u0431\u0430\u0432\u0438\u043c \u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a \u043a\u043b\u044e\u0447\u0438;<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0434\u0443\u043c\u0430\u0435\u043c \u043f\u0440\u043e \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0435 \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435.<\/p>\n<\/li>\n<\/ul>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/9a7\/2a6\/878\/9a72a6878b8d99fab243b09af2ff1222.png\" alt=\"\" title=\"\" width=\"1000\" height=\"320\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9a7\/2a6\/878\/9a72a6878b8d99fab243b09af2ff1222.png\"\/><figcaption><\/figcaption><\/figure>\n<p><em>\u0418, \u043d\u0430\u0432\u0435\u0440\u043d\u043e\u0435, \u0441\u0442\u043e\u0438\u0442 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0447\u0442\u043e \u0441\u043c\u044b\u0441\u043b \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u0438\u043c\u0435\u043d\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043a\u0430\u043a hashmap \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u0432 Go \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c, \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0447\u0438\u0442\u0430\u0435\u043c\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c Go.<\/em><\/p>\n<h3>\u0421\u0441\u044b\u043b\u043a\u0438<\/h3>\n<p><a href=\"https:\/\/github.com\/w1kend\/go-map\" rel=\"noopener noreferrer nofollow\">\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438<\/a><br \/><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><br \/><a href=\"https:\/\/github.com\/ashleymcnamara\/gophers\" rel=\"noopener noreferrer nofollow\">\u0413\u043e\u0444\u0435\u0440\u044b \u043e\u0442 Ashley McNamara<\/a><\/p>\n<p>Go:<br \/><a href=\"https:\/\/www.youtube.com\/watch?v=Tl7mi9QmLns\" rel=\"noopener noreferrer nofollow\">GopherCon 2016: Keith Randall &#8212; Inside the Map Implementation<\/a><br \/><a href=\"https:\/\/dave.cheney.net\/2018\/05\/29\/how-the-go-runtime-implements-maps-efficiently-without-generics\" rel=\"noopener noreferrer nofollow\">How the Go runtime implements maps efficiently (without generics)<\/a><\/p>\n<p>Python:<br \/><a href=\"https:\/\/www.youtube.com\/watch?v=npw4s1QTmPg\" rel=\"noopener noreferrer nofollow\">Raymond Hettinger Modern Python Dictionaries A confluence of a dozen great ideas PyCon 2017 <\/a><a href=\"https:\/\/mail.python.org\/pipermail\/python-dev\/2012-December\/123028.html\" rel=\"noopener noreferrer nofollow\">Raymond Hettinger. More compact dictionaries with faster iteration<\/a><\/p>\n<p>Java:<br \/><a href=\"https:\/\/habr.com\/ru\/post\/421179\/\" rel=\"noopener noreferrer nofollow\">\u0412\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0440\u0430\u0431\u043e\u0442\u0430 HashMap \u0432 Java<\/a><br \/><a href=\"https:\/\/www.baeldung.com\/java-hashmap-advanced\" rel=\"noopener noreferrer nofollow\">The Java HashMap Under the Hood<\/a><\/p>\n<p><a href=\"https:\/\/web.stanford.edu\/class\/archive\/cs\/cs166\/cs166.1166\/lectures\/12\/Small12.pdf\" rel=\"noopener noreferrer nofollow\">\u041b\u0435\u043a\u0446\u0438\u044f cs166 stanford \u043f\u0440\u043e Liner probing <\/a><br \/><a href=\"https:\/\/rcoh.me\/posts\/hash-map-analysis\/\" rel=\"noopener noreferrer nofollow\">An Analysis of Hash Map Implementations in Popular Languages<\/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\/704796\/\"> https:\/\/habr.com\/ru\/post\/704796\/<\/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=\"bordered full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u041f\u0440\u0438\u0432\u0435\u0442. \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0442\u0430\u043a\u0443\u044e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043a\u0430\u043a hashmap, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u0435\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0432 Go. \u0412\u043a\u0440\u0430\u0442\u0446\u0435 \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 hashmap, \u043a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c Go 1.19. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0442\u043b\u0438\u0447\u0438\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0441 Java \u0438 Python. \u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c hashmap \u0438\u0437-\u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u0436\u0435\u043d\u0435\u0440\u0438\u043a\u043e\u0432.<\/p>\n<h2>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 hashmap<\/h2>\n<p>\u0414\u043b\u044f \u0442\u0435\u0445, \u043a\u0442\u043e \u0435\u0449\u0435 \u043d\u0435 \u0437\u043d\u0430\u043a\u043e\u043c \u0441 hashmap, \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0438\u0437 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0\" rel=\"noopener noreferrer nofollow\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0438<\/a>:<br \/>Hashmap &#8212; \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043f\u0430\u0440\u044b \u043a\u043b\u044e\u0447-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041a\u043b\u044e\u0447\u0438 \u0432 hashmap \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435. \u041c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043a\u0430\u043a \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0434\u043b\u044f \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043c\u043e\u0436\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043d\u043e \u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<p>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c:<\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p><strong>\u041e\u043f\u0435\u0440\u0430\u0446\u0438\u044f<\/strong><\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\"><strong>\u0421\u0440\u0435\u0434\u043d\u044f\u044f<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"center\"><strong>\u0425\u0443\u0434\u0448\u0430\u044f<\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0412\u0441\u0442\u0430\u0432\u043a\u0430<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\">\n<\/td>\n<td>\n<p align=\"center\">\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041f\u043e\u0438\u0441\u043a<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\">\n<\/td>\n<td>\n<p align=\"center\">\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u0423\u0434\u0430\u043b\u0435\u043d\u0438\u0435<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\">\n<\/td>\n<td>\n<p align=\"center\">\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\">\u041f\u0430\u043c\u044f\u0442\u044c<\/p>\n<\/td>\n<td data-colwidth=\"265\" width=\"265\">\n<p align=\"center\">\n<\/td>\n<td>\n<p align=\"center\">\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u041f\u0440\u0438 \u0443\u0433\u043b\u0443\u0431\u043b\u0435\u043d\u0438\u0438 \u0432 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0442\u0430\u043a\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0436\u043d\u043e \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0441\u043b\u043e\u0432\u0430: \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438, \u0431\u0430\u043a\u0435\u0442\u044b, \u0444\u0430\u043a\u0442\u043e\u0440 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438. \u0420\u0430\u0437\u0431\u0435\u0440\u0435\u043c\u0441\u044f \u0447\u0442\u043e \u043e\u043d\u0438 \u0437\u043d\u0430\u0447\u0430\u0442:<\/p>\n<ul>\n<li>\n<p><strong><em>\u0425\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f(Hash function)<\/em><\/strong>. \u041f\u043e\u0434 \u043d\u0435\u0439 \u043f\u043e\u043d\u0438\u043c\u0430\u044e\u0442 \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 (\u043a\u043b\u044e\u0447) \u043d\u0435\u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 c Go \u043e\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 <code>uint64<\/code>. \u041e\u0434\u043d\u043e \u0438\u0437 \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432 &#8212; \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u0414\u043b\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0438 \u0442\u043e\u0433\u043e \u0436\u0435 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043e\u043d\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442;<\/p>\n<\/li>\n<li>\n<p><strong><em>\u0411\u0430\u043a\u0435\u0442(Bucket\/Slot)<\/em><\/strong>. \u0422\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u0430\u044f \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 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u0430\u043f\u0435. \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f\u0445 hashmap \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0430\u043a\u0435\u0442\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u043e\u0434\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0430 \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 &#8212; \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 Go \u0434\u0430\u043d\u043d\u044b\u0435 \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0438 \u0432 \u043e\u0434\u043d\u043e\u043c \u0431\u0430\u043a\u0435\u0442\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043e \u0432\u043e\u0441\u044c\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432;<\/p>\n<\/li>\n<li>\n<p><strong><em>\u041a\u043e\u043b\u043b\u0438\u0437\u0438\u044f (Collision)<\/em><\/strong>. \u0422\u0430\u043a \u043a\u0430\u043a \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043d\u0435 \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u0430, \u043f\u0435\u0440\u0435\u0434\u0430\u0432 \u0432 \u043d\u0435\u0435 \u0434\u0432\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441 \u0431\u0430\u043a\u0435\u0442\u0430\u043c\u0438 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u0432\u0430 \u0440\u0430\u0437\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c \u0432 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0431\u0430\u043a\u0435\u0442. \u042d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0435\u0439. \u0414\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 hashmap \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u043c\u0435\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0445 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0442\u0430\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 (\u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0439): <\/p>\n<ul>\n<li>\n<p><em>Closed addressing<\/em>. \u0425\u0440\u0430\u043d\u0438\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u043c \u0445\u044d\u0448\u0435\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445, \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a: \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e, \u043c\u0430\u0441\u0441\u0438\u0432 \u0438 \u0434\u0440. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u044f\u0437\u044b\u043a\u0430\u0445: Go, Java, Scala;<\/p>\n<\/li>\n<li>\n<p><em>Open addressing<\/em>. \u0412 \u0431\u0430\u043a\u0435\u0442\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u041f\u0440\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u043e\u0432\u0435\u043d\u0438\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u043f\u043e \u043a\u0430\u043a\u043e\u0439-\u043b\u0438\u0431\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435. \u0422\u0430\u043a\u0430\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0432 Python, Ruby, Rust, C++ \u0438 \u0434\u0440;<\/p>\n<\/li>\n<li>\n<p><em>Perfect hashing<\/em>. \u0412\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0430\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439. \u041f\u043e\u0434\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0441\u0442\u0430\u0442\u0438\u0447\u043d\u043e\u0433\u043e, \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043a\u043b\u044e\u0447\u0435\u0439.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p><strong><em>\u0424\u0430\u043a\u0442\u043e\u0440 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043c\u0430\u043f\u044b (Overload factor)<\/em><\/strong>. \u042d\u0442\u043e \u0447\u0438\u0441\u043b\u043e (\u043f\u043e\u0440\u043e\u0433), \u043f\u0440\u0435\u0432\u044b\u0441\u0438\u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432 (\u043e\u0431\u044b\u0447\u043d\u043e \u0432\u0434\u0432\u043e\u0435) \u0434\u043b\u044f \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 <\/p>\n<\/li>\n<\/ul>\n<h2>\u041a\u0430\u043a hashmap \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u0432 Go<\/h2>\n<figure class=\"full-width\"><figcaption>\u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0431\u043e\u0442\u044b hashmap \u0432 Go.<\/figcaption><\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u043e \u0448\u0430\u0433\u0430\u043c \u0443\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b hashmap. \u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0446\u0435\u043d\u043a\u0438 \u0444\u0438\u043b\u044c\u043c\u043e\u0432 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435-\u043e\u0446\u0435\u043d\u043a\u0430:<\/p>\n<ul>\n<li>\n<p>\u041f\u0435\u0440\u0435\u0434\u0430\u0435\u043c \u043a\u043b\u044e\u0447 <code>\"The Matrix\"<\/code> \u0432 \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044e. \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c <code>uint64<\/code> &#8212; 18002143618149980261;<\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043c\u0430\u0441\u043a\u0443 \u0434\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u041e\u043d\u0430 \u0440\u0430\u0432\u043d\u0430 <code>n-1<\/code>, \u0433\u0434\u0435 n &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0435 4 \u0431\u0430\u043a\u0435\u0442\u0430, \u0430 \u043c\u0430\u0441\u043a\u0430 \u0440\u0430\u0432\u043d\u0430 3;<\/p>\n<\/li>\n<li>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043d\u043e\u043c\u0435\u0440 \u0431\u0430\u043a\u0435\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043c \u043d\u0430\u0448\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0431\u0438\u0442\u043e\u0432\u043e\u0435 <em>&#171;\u0438&#187;<\/em>: <code>hash &amp; mask<\/code> == <code>18002143618149980261 &amp; 3<\/code> == <code>01 &amp; 11<\/code>(\u043e\u0442\u0431\u0440\u043e\u0441\u0438\u043b\u0438 \u043d\u0443\u043b\u0438) = <code>01<\/code>, \u0447\u0442\u043e \u0440\u0430\u043d\u043e 1 \u0432 \u0434\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f;<\/p>\n<\/li>\n<li>\n<p>\u0418\u0434\u0435\u043c \u0432 \u0431\u0430\u043a\u0435\u0442 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 1 \u0438 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043d\u0430 \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043d\u0430\u0448\u0435\u0433\u043e \u043a\u043b\u044e\u0447\u0430. \u0415\u0441\u043b\u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043f\u043e \u043a\u043b\u044e\u0447\u0443, \u0442\u043e \u043f\u0435\u0440\u0435\u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u0438\u043d\u0430\u0447\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043f\u0435\u0440\u0432\u043e\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e;<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u043c\u0430\u043f\u044b \u0438 \u0431\u0430\u043a\u0435\u0442\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u044f\u0442 \u0442\u0430\u043a:<br \/><em>runtime\/map.go<\/em><\/p>\n<pre><code class=\"go\">\/\/ A header for a Go map. type hmap struct { count     int \/\/ \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u043f\u044b. \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 len() flags     uint8 B         uint8  \/\/ log_2 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0414\u043b\u044f 8 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 B=3, \u0434\u043b\u044f 16 B=4 \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435. noverflow uint16 \/\/ \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432 hash0     uint32 \/\/ seed \u0434\u043b\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043c\u0430\u043f\u044b. \u043d\u0443\u0436\u0435\u043d \u0434\u043b\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438  buckets    unsafe.Pointer \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 2^B \u0431\u0430\u043a\u0435\u0442\u043e\u0432; nil, \u0435\u0441\u043b\u0438 count==0 oldbuckets unsafe.Pointer \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u043c\u0430\u043f\u044b \u0437\u0434\u0435\u0441\u044c \u0431\u0443\u0434\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0442\u0430\u0440\u044b\u0445 \u0431\u0430\u043a\u0435\u0442\u043e\u0432, \u043e\u0442\u043a\u0443\u0434\u0430 \u043f\u043e\u0442\u0438\u0445\u043e\u043d\u044c\u043a\u0443 \u0431\u0443\u0434\u0443\u0442 \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u0438\u0442\u044c\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b. nevacuate  uintptr        \/\/ \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \"\u044d\u0432\u0430\u043a\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445\" \u0431\u0430\u043a\u0435\u0442\u043e\u0432.  extra *mapextra \/\/ \u043e\u043f\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u043e\u043b\u044f }  \/\/ A bucket for a Go map. type bmap struct { tophash [bucketCnt]uint8 \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 tophash \/\/ \u041f\u043e\u0441\u043b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 tophash \u0438\u0434\u0435\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 bucketCnt \u043a\u043b\u044e\u0447\u0435\u0439 \u0438 \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 bucketCnt \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. }<\/code><\/pre>\n<p>\u0412 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0431\u0430\u043a\u0435\u0442\u0430 \u044f\u0432\u043d\u043e \u043d\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u043f\u043e\u043b\u044f \u043a\u043b\u044e\u0447\u0435\u0439, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 overflow \u0431\u0430\u043a\u0435\u0442. \u0414\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u044d\u0442\u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0430\u0434\u0440\u0435\u0441\u043d\u0430\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u0447\u0435\u0440\u0435\u0437 <code>unsafe.Pointer<\/code>.<\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438:<\/p>\n<ul>\n<li>\n<p>\u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043a\u043b\u044e\u0447\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043b\u044e\u0431\u043e\u0439 \u0442\u0438\u043f \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0441 \u0442\u0435\u043c \u0436\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435\u043c \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0435\u0435 \u043f\u043e\u043b\u0435\u0439;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u0442\u0438\u043f\u0430. \u0412\u0442\u043e\u0440\u044b\u043c \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0444\u043b\u0430\u0433 \u043d\u0430\u043b\u0438\u0447\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u043e \u043a\u043b\u044e\u0447\u0443;<\/p>\n<\/li>\n<li>\n<p>\u041d\u0435\u043b\u044c\u0437\u044f \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0430\u0434\u0440\u0435\u0441 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u041f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043c\u0430\u043f\u044b \u043e\u043d\u043e \u043f\u0435\u0440\u0435\u0435\u0434\u0435\u0442 \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u0431\u0430\u043a\u0435\u0442 \u0438 \u0430\u0434\u0440\u0435\u0441 \u0443 \u043d\u0435\u0433\u043e, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f;<\/p>\n<\/li>\n<li>\n<p>\u041c\u0430\u043f\u0430 \u043d\u0435 \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u0430 \u0434\u043b\u044f \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0431\u0435\u0440\u0442\u043a\u0443 \u0438\u0437 <code>sync.Map<\/code> \u0438\u043b\u0438 \u043c\u044c\u044e\u0442\u0435\u043a\u0441;<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0440\u044f\u0434\u043e\u043a \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043d\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f. \u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u043d\u043e\u0432\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043c\u0430\u043f\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u043e\u0436\u0435\u0442 \u043e\u0442\u043b\u0438\u0447\u0430\u0442\u044c\u0441\u044f. \u041f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u044b\u0439 \u0431\u0430\u043a\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. \u0414\u043b\u044f \u0441\u043e\u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u043a\u043b\u044e\u0447\u0438 \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0438 \u0438\u0442\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u043d\u0435\u043c\u0443;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u0430\u0436\u0434\u043e\u043c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043c\u0430\u043f\u044b \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f seed \u0434\u043b\u044f \u0440\u0430\u043d\u0434\u043e\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u042d\u0442\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043e \u0434\u043b\u044f \u0431\u0435\u0437\u043e\u043f\u0430\u0441\u043d\u043e\u0441\u0442\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u0437\u043d\u0430\u044f \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u043a\u043b\u044e\u0447\u0438, \u0447\u0442\u043e \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 \u043e\u0434\u0438\u043d \u0431\u0430\u043a\u0435\u0442 \u0438 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f <em>\u0441losed addressing.<\/em> \u041c\u044b \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0432\u0441\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 \u0431\u0430\u043a\u0435\u0442\u0430 (\u0438\u0445 8) \u0438 \u0438\u0449\u0435\u043c \u043f\u0435\u0440\u0432\u043e\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e;<\/p>\n<\/li>\n<li>\n<p><em>OverloadFactor<\/em> \u0440\u0430\u0432\u0435\u043d 6.5 (~81% \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u0431\u0430\u043a\u0435\u0442\u043e\u0432). \u041a\u043e\u0433\u0434\u0430 \u0431\u0430\u043a\u0435\u0442\u044b \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u044b \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u043d\u0430 6.5 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0442\u0440\u0438\u0433\u0435\u0440\u0438\u0442\u0441\u044f \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b, \u0438 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u0435.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043f\u0435\u0440\u0435\u043d\u043e\u0441\u044f\u0442\u0441\u044f \u0432 \u043d\u043e\u0432\u044b\u0435 \u0431\u0430\u043a\u0435\u0442\u044b \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e, \u0430 \u043d\u0435 \u0432\u0441\u0435 \u0441\u0440\u0430\u0437\u0443;<\/p>\n<\/li>\n<\/ul>\n<h2>\u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u0442\u043b\u0438\u0447\u0438\u044f \u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0439 \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 \u044f\u0437\u044b\u043a\u0430\u0445<\/h2>\n<p><strong><em>Python 3.6+<\/em><\/strong>. \u041f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432 \u043e\u0447\u0435\u043d\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u043c (\u043f\u0440\u0430\u0432\u0434\u0430) \u0434\u043e\u043a\u043b\u0430\u0434\u0435 <a href=\"https:\/\/www.youtube.com\/watch?v=npw4s1QTmPg\" rel=\"noopener noreferrer nofollow\">Raymond Hettinger Modern Python Dictionaries (2017)<\/a><\/p>\n<ul>\n<li>\n<p>\u0421\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0432\u0441\u0442\u0430\u0432\u043a\u0438;<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u0445 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0431\u0430\u043a\u0435\u0442 \u0438\u0449\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 open addressing. \u0414\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0430\u043a\u0435\u0442\u0430 <a href=\"https:\/\/github.com\/python\/cpython\/blob\/22d91c16bb03c3d87f53b5fee10325b876262a78\/Objects\/dictobject.c#L175\" rel=\"noopener noreferrer nofollow\">\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f<\/a> \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u0444\u043e\u0440\u043c\u0443\u043b\u044b: <code>j = ((5*j) + 1) mod 2**i<\/code> \u0438 <code>j = (5*j) + 1 + perturb<\/code>;<\/p>\n<\/li>\n<li>\n<p>\u0414\u0430\u043d\u043d\u044b\u0435 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u043e\u0442 \u0431\u0430\u043a\u0435\u0442\u043e\u0432. \u0421\u0430\u043c\u0438 \u0431\u0430\u043a\u0435\u0442\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u0430\u043a \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 (\u0438\u043d\u0434\u0435\u043a\u0441\u044b) \u043d\u0430 \u0434\u0430\u043d\u043d\u044b\u0435. \u0412\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u044d\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0442\u0430\u043a:<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"python\">  indices =  [None, 1, None, None, None, 0, None, 2]   entries =  [[-9092791511155847987, 'timmy', 'red'],               [-8522787127447073495, 'barry', 'green'],               [-6480567542315338377, 'guido', 'blue']]<\/code><\/pre>\n<ul>\n<li>\n<p>\u0420\u044f\u0434\u043e\u043c \u0441 \u0434\u0430\u043d\u043d\u044b\u043c\u0438 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u044b\u0439 \u0445\u044d\u0448. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0435 \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0435\u0433\u043e \u043f\u0440\u0438 \u0440\u043e\u0441\u0442\u0435 \u043c\u0430\u043f\u044b.<\/p>\n<\/li>\n<li>\n<p>LoadFactor &#8212; 2\/3 = ~66%<\/p>\n<\/li>\n<\/ul>\n<p><strong><em>Java<\/em><\/strong>. \u0420\u0430\u0437\u0431\u043e\u0440 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 <a href=\"https:\/\/habr.com\/ru\/post\/421179\/\" rel=\"noopener noreferrer nofollow\">\u0412\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0440\u0430\u0431\u043e\u0442\u0430 HashMap \u0432 Java<\/a>:<\/p>\n<ul>\n<li>\n<p>\u041f\u0440\u0438 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u044f\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f <em>\u0441losed addressing<\/em>, \u043d\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0432\u044f\u0437\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a. \u0422\u0430\u043a\u0436\u0435 \u043a\u043e\u0433\u0434\u0430 \u0434\u043b\u0438\u043d\u0430 \u0441\u043f\u0438\u0441\u043a\u0430 \u0431\u043e\u043b\u044c\u0448\u0435 \u0432\u043e\u0441\u044c\u043c\u0438 \u043e\u043d \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0432 TreeMap. \u042d\u0442\u043e \u0434\u0430\u0435\u0442 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432\u043c\u0435\u0441\u0442\u043e \u043a\u0430\u043a \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e \u0441\u0432\u044f\u0437\u043d\u044b\u043c \u0441\u043f\u0438\u0441\u043a\u043e\u043c \u0438\u043b\u0438 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c;<\/p>\n<\/li>\n<li>\n<p>\u0412\u0441\u0435 \u043a\u043b\u044e\u0447\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043d\u044b\u0435 \u0442\u0438\u043f\u044b (boolean, int, char, float \u0438 \u0442.\u0434) \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0441\u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0432 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0447\u0435\u0440\u0435\u0437 <a href=\"https:\/\/docs.oracle.com\/javase\/tutorial\/java\/data\/autoboxing.html\" rel=\"noopener noreferrer nofollow\">boxing<\/a>;<\/p>\n<\/li>\n<li>\n<p><em>LoadFactor<\/em> \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e &#8212; 75%. \u041f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043c\u0430\u043f\u044b \u043c\u043e\u0436\u043d\u043e \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u0441\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430.<\/p>\n<\/li>\n<\/ul>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f\u043c\u0438 Java \u0438 C++ \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0443 <a href=\"https:\/\/dave.cheney.net\/2018\/05\/29\/how-the-go-runtime-implements-maps-efficiently-without-generics\" rel=\"noopener noreferrer nofollow\">Dave Cheney<\/a>.<\/p>\n<h2>\u041a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/h2>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0431\u0430\u0437\u043e\u0432\u043e hashmap \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u043e\u0432 Go 1.19. \u041d\u0435 \u0431\u0443\u0434\u0435\u043c \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c \u0440\u043e\u0441\u0442 \u043c\u0430\u043f\u044b, \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u043d\u043e\u0435 \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0442\u0438\u043f\u044b \u0434\u043b\u044f \u043a\u043b\u044e\u0447\u0435\u0439.<\/p>\n<h3>\u041d\u0430\u0447\u043d\u0435\u043c \u0441 \u0432\u0435\u0434\u0435\u0440<\/h3>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0431\u0430\u043a\u0435\u0442\u0430. <\/p>\n<p>\u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0434\u0432\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0434\u043b\u044f \u043a\u043b\u044e\u0447\u0435\u0439 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0438 \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0431\u0430\u043a\u0435\u0442 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e. \u0414\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u0445\u0440\u0430\u043d\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0435\u0440\u0432\u044b\u0445 \u0432\u043e\u0441\u044c\u043c\u0438 \u0431\u0438\u0442 \u043e\u0442 \u0445\u044d\u0448\u0430 \u043a\u043b\u044e\u0447\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f tophash.<\/p>\n<pre><code class=\"go\">const bucketSize = 8 \/\/ \u0440\u0430\u0437\u043c\u0435\u0440 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430  type bucket[T any] struct { tophash [bucketSize]uint8 \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0435\u0440\u0432\u044b\u0445 \u0432\u043e\u0441\u044c\u043c\u0438 \u0431\u0438\u0442 \u043e\u0442 \u0445\u044d\u0448\u0430 \u043a\u043b\u044e\u0447\u0430; \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043a\u0430\u043a \u0444\u043b\u0430\u0433\u0438, \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u043d\u0438\u0436\u0435.  keys   [bucketSize]string \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u044e\u0447\u0435\u0439 values [bucketSize]T \/\/ \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439  overflow *bucket[T] \/\/ \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u0431\u0430\u043a\u0435\u0442 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e }<\/code><\/pre>\n<h4>\u041f\u0440\u043e tophash<\/h4>\n<p>\u0412 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0441 tophash \u043c\u044b \u0440\u0435\u0437\u0435\u0440\u0432\u0438\u0440\u0443\u0435\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f. \u041a\u043e \u0432\u0441\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c tophash, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 <code>minTopHash<\/code> \u0431\u0443\u0434\u0435\u043c \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0435\u0433\u043e.<\/p>\n<pre><code class=\"go\">const ( emptyRest  = 0 \/\/ \u044d\u0442\u0430 \u0438 \u0432\u0441\u0435 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 \u0441 \u0431\u041e\u043b\u044c\u0448\u0438\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u043c \u043f\u0443\u0441\u0442\u044b\u0435 emptyCell  = 1 \/\/ \u044f\u0447\u0435\u0439\u043a\u0430 \u043f\u0443\u0441\u0442\u0430\u044f minTopHash = 3 \/\/ \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 tophash \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0449\u0435\u0435 \u0447\u0442\u043e \u0432 \u044f\u0447\u0435\u0439\u043a\u0435 \u0435\u0441\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 )<\/code><\/pre>\n<p>\u041f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e, \u0432 Go \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d \u043d\u0443\u043b\u0435\u0432\u044b\u043c\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0434\u043b\u044f tophash \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0438\u043f\u0430 <code>uint8<\/code>, \u0431\u0443\u0434\u0443\u0442 \u043d\u0443\u043b\u0438. \u041f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0438\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 \u0431\u0430\u043a\u0435\u0442\u0430 \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043e\u0440\u0438\u0435\u043d\u0442\u0438\u0440\u0443\u0435\u043c\u0441\u044f \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432 tophash, \u0430 \u043d\u0435 \u043c\u0430\u0441\u0441\u0438\u0432 \u043a\u043b\u044e\u0447\u0435\u0439. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0432\u043d\u0443\u0442\u0440\u0438 \u0431\u0430\u043a\u0435\u0442\u0430.<\/p>\n<h3>\u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043c\u0430\u043f\u0443<\/h3>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430:<\/p>\n<ul>\n<li>\n<p>\u0412 \u0446\u0438\u043a\u043b\u0435 \u0438\u0449\u0435\u043c \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f \u043f\u043e tophash \u0438 \u043a\u043b\u044e\u0447\u0443 \u0438\u043b\u0438 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e. \u0421\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0434\u0430\u043d\u043d\u044b\u0435 \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0444\u043b\u0430\u0433 \u0434\u043b\u044f \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u043f\u0435.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u043d\u0435 \u043d\u0430\u0448\u043b\u0438 \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430, \u0442\u043e \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u0443\u043f\u0440\u0430\u0436\u043d\u0435\u043d\u0438\u044f \u043d\u0430 overflow \u0431\u0430\u043a\u0435\u0442\u0435.<\/p>\n<\/li>\n<\/ul>\n<pre><code class=\"go\">\/\/ \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u0431\u0430\u043a\u0435\u0442. \/\/ \u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u044b\u0435 \u043a\u043b\u044e\u0447 \u0443\u0436\u0435 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0431\u0430\u043a\u0435\u0442\u0435, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u0437\u0430\u043f\u0438\u0448\u0435\u0442\u0441\u044f. \/\/ \u0415\u0441\u043b\u0438 \u0431\u0430\u043a\u0435\u0442 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0431\u0430\u043a\u0435\u0442\u0435 overflow. func (b *bucket[T]) Put(key string, topHash uint8, value T) (isAdded bool) { var insertIdx *int  for i := range b.tophash { \/\/ \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c tophash \u0430 \u043d\u0435 \u043a\u043b\u044e\u0447, \u0442.\u043a. \u044d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043d\u0430\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0444\u043b\u0430\u0433\u0438 \u0438 \u044d\u0442\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 if b.tophash[i] != topHash { if b.tophash[i] == emptyRest { insertIdx = new(int) *insertIdx = i break }  if insertIdx == nil &amp;&amp; isCellEmpty(b.tophash[i]) { insertIdx = new(int) *insertIdx = i } continue }  \/\/ tophash \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043d\u0435 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b, \u043f\u043e \u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438 \u0441\u0430\u043c \u043a\u043b\u044e\u0447 if b.keys[i] != key {<\/code><\/pre>\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-342430","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/342430","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=342430"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/342430\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=342430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=342430"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=342430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}