{"id":252378,"date":"2015-03-04T11:12:02","date_gmt":"2015-03-04T07:12:02","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=252378"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=252378","title":{"rendered":"Lock-free \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. Concurrent maps: rehash, no rebuild"},"content":{"rendered":"<p>     \t<img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/4e3\/317\/fa0\/4e3317fa037748138cb0ed6e90a788a6.png\" align=\"right\"\/><br \/>  \u041f\u0440\u043e\u0439\u0434\u0435\u043c \u043f\u043e \u0441\u043b\u0435\u0434\u0430\u043c <a href=\"http:\/\/meetingcpp.ru\/\">C++ 2015 Russia<\/a> \u0434\u0430\u043b\u0435\u0435.<br \/>  \u0412 <a href=\"http:\/\/habrahabr.ru\/post\/250383\/\">\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439<\/a> \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f lock-free ordered list \u0438 \u043d\u0430 \u0435\u0433\u043e \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 lock-free hash map. \u0423 \u044d\u0442\u043e\u0433\u043e hash map \u0435\u0441\u0442\u044c \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u043a: \u0440\u0430\u0437\u043c\u0435\u0440 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0435\u043d \u0438 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u0447\u0438\u0441\u043b\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0435. \u042d\u0442\u043e \u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u0435\u0441\u043b\u0438 \u043c\u044b \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u0439 \u043e\u0431\u044a\u0435\u043c \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430. \u0410 \u0435\u0441\u043b\u0438 \u043d\u0435\u0442?<br \/>  <a name=\"habracut\"><\/a><br \/>  \u041f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u0443\u0432\u0435\u043b\u0438\u0447\u0435\u043d\u0438\u044f, \u0440\u0430\u0432\u043d\u043e \u043a\u0430\u043a \u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f, \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b (rehashing) \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0442\u044f\u0436\u0435\u043b\u0430\u044f<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/600\/095\/c59\/600095c5933d4fca8b6a95d12738e34c.png\"\/><br \/>  \u041a\u0430\u043a \u0432\u0438\u0434\u043d\u043e \u0434\u0430\u0436\u0435 \u0438\u0437 \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438, \u043f\u0440\u0438 rehasing&#8217;\u0435 \u043a\u043b\u044e\u0447\u0438 \u043f\u0435\u0440\u0435\u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u043e \u0434\u0440\u0443\u0433\u0438\u043c \u0441\u043b\u043e\u0442\u0430\u043c \u043d\u043e\u0432\u043e\u0439 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u2014 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 <i>\u043f\u043e\u043b\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u0441\u0442\u0440\u043e\u0439\u043a\u0430<\/i> hash map. \u042d\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0442\u0440\u0443\u0434\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e \u0438\u043b\u0438 \u0445\u043e\u0442\u044f \u0431\u044b \u0431\u0435\u0437 \u0431\u043b\u043e\u043a\u0438\u0440\u043e\u0432\u043e\u043a.<br \/>  \u041c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e \u043c\u043d\u043e\u044e \u0443\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u043c\u044b\u0439 Nir Shavit \u0441\u043e\u0432\u043c\u0435\u0441\u0442\u043d\u043e \u0441 Ori Shalev \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b \u043d\u0430 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u0441 \u0434\u0440\u0443\u0433\u043e\u0439 \u0441\u0442\u043e\u0440\u043e\u043d\u044b: \u0445\u043e\u0440\u043e\u0448\u043e, \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e \u043f\u0435\u0440\u0435\u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u043b\u044e\u0447\u0438 \u043f\u043e \u043d\u043e\u0432\u044b\u043c \u0441\u043b\u043e\u0442\u0430\u043c (bucket&#8217;\u0430\u043c), \u043d\u043e, \u0431\u044b\u0442\u044c \u043c\u043e\u0436\u0435\u0442, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 bucket \u0432 \u0443\u0436\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u044f (splitting) \u0435\u0433\u043e \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438? \u042d\u0442\u0430 \u0438\u0434\u0435\u044f \u043b\u0435\u0433\u043b\u0430 \u0432 \u043e\u0441\u043d\u043e\u0432\u0443 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u043e\u0433\u043e \u0438\u043c\u0438 \u0432 2003 \u0433\u043e\u0434\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 <a href=\"http:\/\/www.cs.ucf.edu\/~dcm\/Teaching\/COT4810-Spring2011\/Literature\/SplitOrderedLists.pdf\">split-ordered list<\/a>.<\/p>\n<h2>Split-ordered list<\/h2>\n<p>  <a href=\"https:\/\/www.google.com\/search?q=%D0%BD%D0%B5%D0%BB%D1%8C%D0%B7%D1%8F+%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE+%D1%82%D0%B0%D0%BA+%D0%B2%D0%B7%D1%8F%D1%82%D1%8C&amp;sa=X&amp;biw=1168&amp;bih=677&amp;tbm=isch&amp;tbo=u&amp;source=univ\">\u041d\u0435\u043b\u044c\u0437\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u0442\u0430\u043a \u0432\u0437\u044f\u0442\u044c<\/a> \u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 bucket, \u2013 \u0441\u043c. \u0440\u0438\u0441\u0443\u043d\u043e\u043a \u0432\u044b\u0448\u0435: \u043a\u043b\u044e\u0447\u0438 \u043f\u0440\u0438 rehashing&#8217;\u0435 \u043f\u0435\u0440\u0435\u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u043c\u0435\u0436\u0434\u0443 bucket&#8217;\u0430\u043c, \u0430 \u043d\u0430\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e\u0431\u044b \u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u044f\u043b\u0438\u0441\u044c. \u041c\u044b \u0445\u043e\u0442\u0438\u043c \u0447\u0435\u0433\u043e-\u0442\u043e <s>\u0441\u0442\u0440\u0430\u043d\u043d\u043e\u0433\u043e<\/s> \u0442\u0430\u043a\u043e\u0433\u043e:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/968\/330\/491\/96833049100d4067a91ddafaa8c7bd4d.png\"\/><br \/>  \u0412 \u043e\u0441\u043d\u043e\u0432\u0435 \u043b\u0435\u0436\u0438\u0442 \u0443\u0436\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043d\u044b\u0439 \u043d\u0430\u043c\u0438 lock-free ordered list. \u0412 \u043d\u0435\u043c \u043f\u043e\u044f\u0432\u0438\u043b\u043e\u0441\u044c \u0434\u0432\u0430 \u0442\u0438\u043f\u0430 \u0443\u0437\u043b\u043e\u0432: \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0443\u0437\u043b\u044b (\u043e\u0432\u0430\u043b\u044c\u043d\u044b\u0435) \u0438 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 (sentinel) \u0443\u0437\u043b\u044b (\u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0435). \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0438\u0433\u0440\u0430\u044e\u0442 \u0440\u043e\u043b\u044c \u043c\u0435\u0442\u043e\u043a \u043d\u0430\u0447\u0430\u043b\u0430 bucket&#8217;\u043e\u0432 \u0438 \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f; \u0432 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u043d\u0430 \u044d\u0442\u0438 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0437\u043b\u044b. <br \/>  \u0413\u043b\u044f\u0434\u044f \u043d\u0430 \u044d\u0442\u043e\u0442 \u0440\u0438\u0441\u0443\u043d\u043e\u043a, \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0441\u043f\u0440\u043e\u0441\u0438\u0442\u044c: \u0441\u043f\u0438\u0441\u043e\u043a \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439, \u043d\u043e \u044d\u0442\u043e\u0433\u043e \u043d\u0435 \u0432\u0438\u0434\u043d\u043e, \u2014 \u043a\u043b\u044e\u0447\u0438 \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u044b \u0445\u0430\u043e\u0442\u0438\u0447\u043d\u043e, \u0432 \u0447\u0435\u043c \u0434\u0435\u043b\u043e? \u041e\u0442\u0432\u0435\u0442: \u0441\u043f\u0438\u0441\u043e\u043a <i>\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439<\/i>, \u043d\u043e \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u043c\u044b \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0435\u043c \u0447\u0443\u0442\u044c \u043f\u043e\u0437\u0436\u0435.<br \/>  \u0418\u0442\u0430\u043a, \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0441 \u0434\u0432\u0443\u043c\u044f \u0441\u043b\u043e\u0442\u0430\u043c\u0438, \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u043c\u0438 \u043d\u0430 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0437\u043b\u044b. \u0420\u0430\u0437\u043c\u0435\u0440 \u0441\u043f\u0438\u0441\u043a\u0430 \u0440\u0430\u0432\u0435\u043d 4 (\u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0435 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u0438 \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432), load factor \u0440\u0430\u0432\u0435\u043d 2 (\u044d\u0442\u043e \u043c\u043e\u0435 \u0432\u043e\u043b\u044e\u043d\u0442\u0430\u0440\u0438\u0441\u0442\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435). \u041c\u044b \u0445\u043e\u0442\u0438\u043c \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c 10:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/915\/a94\/8b8\/915a948b8b7b4e2ebb6f2e730ca9e506.png\"\/><br \/>  \u041f\u0440\u0438 \u043f\u043e\u043f\u044b\u0442\u043a\u0435 \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u043d\u043e\u0432\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u043c\u044b \u0432\u044b\u044f\u0441\u043d\u044f\u0435\u043c, \u0447\u0442\u043e \u043d\u0430\u0448 \u0441\u043f\u0438\u0441\u043e\u043a \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d \u2013 \u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f 5, \u0447\u0438\u0441\u043b\u043e bucket&#8217;\u043e\u0432 \u0440\u0430\u0432\u043d\u043e 2, <code>5\/2 &gt; load factor<\/code>, \u2014 \u043d\u0430\u0434\u043e \u0440\u0430\u0441\u0448\u0438\u0440\u044f\u0442\u044c \u0442\u0430\u0431\u043b\u0438\u0446\u0443 <code>T[]<\/code>. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u043c\u044b \u043a\u0430\u043a\u0438\u043c-\u0442\u043e \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0435\u0451 \u0440\u0430\u0441\u0448\u0438\u0440\u0438\u043b\u0438 \u2014 \u0432 \u043d\u0435\u0439 \u0441\u0442\u0430\u043b\u043e 4 bucket&#8217;\u0430, \u0434\u0432\u0430 \u043f\u0435\u0440\u0432\u044b\u0445 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u044b, \u0434\u0432\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0445 \u2014 \u043d\u0435\u0442. \u041d\u043e\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 10 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u043e\u043f\u0430\u0441\u0442\u044c \u0432 bucket 2 ( <code>10 mod 4 = 2<\/code>, \u0437\u0434\u0435\u0441\u044c \u0438 \u0434\u0430\u043b\u0435\u0435 \u044f \u0441\u0447\u0438\u0442\u0430\u044e \u0434\u043b\u044f \u043d\u0430\u0433\u043b\u044f\u0434\u043d\u043e\u0441\u0442\u0438, \u0447\u0442\u043e <code>hash(key) == key<\/code>), \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0435\u0449\u0451 \u043d\u0435 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d. \u0417\u043d\u0430\u0447\u0438\u0442, \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0443\u0436\u043d\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 2, \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c <i>\u0440\u0430\u0441\u0449\u0435\u043f\u043b\u0435\u043d\u0438\u0435<\/i> \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0433\u043e bucket&#8217;\u0430. \u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0430\u0434\u043e \u043d\u0430\u0439\u0442\u0438 \u044d\u0442\u043e\u0442 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 bucket, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0439 <i>\u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u043c<\/i> (parent):<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/2ed\/729\/421\/2ed7294211ea4df7874d39c3b037af02.png\"\/><br \/>  \u0420\u0430\u0441\u0449\u0435\u043f\u043b\u0435\u043d\u0438\u0435 bucket&#8217;\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u044b\u0439 \u0442\u043e\u043d\u043a\u0438\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435. \u0420\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 bucket, \u043f\u043e\u043a\u0430 \u043d\u0430\u043c \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439, \u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u043f\u0435\u0440\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u0442\u043e \u0435\u0441\u0442\u044c \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e bucket 0 \u0438\u043b\u0438 1. <br \/>  Bucket \u2013 \u044d\u0442\u043e <code>hash(key) mod 2**(m+1)<\/code>, \u0433\u0434\u0435 <code>2**(m+1)<\/code> \u2014 \u0440\u0430\u0437\u043c\u0435\u0440 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b. \u041d\u043e\u0432\u044b\u0439 bucket \u0440\u0430\u0441\u0449\u0435\u043f\u043b\u044f\u0435\u0442 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439, \u0442\u043e \u0435\u0441\u0442\u044c \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e bucket&#8217;\u0430 \u043d\u0430 \u0434\u0432\u0430 \u043b\u0430\u0433\u0435\u0440\u044f: \u043e\u0434\u043d\u0438 \u0432\u0445\u043e\u0434\u044f\u0442 \u0432 parent bucket, \u0430 \u0432\u0442\u043e\u0440\u044b\u0435 \u2014 \u0432 <code>parent_bucket + 2**m<\/code>. \u041e\u0442\u0441\u044e\u0434\u0430 \u0441\u043b\u0435\u0434\u0443\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043d\u043e\u0432\u043e\u0433\u043e bucket 2 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u2014 \u044d\u0442\u043e bucket 0.<br \/>  \u041d\u0430 C++ \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e bucket&#8217;\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e:  <\/p>\n<pre><code>        size_t parent_bucket( size_t nBucket )         {             assert( nBucket &gt; 0 );             return nBucket & ~( 1 &lt;&lt; MSB( nBucket ) );         }  <\/code><\/pre>\n<p>  \u0433\u0434\u0435 <code>MSB<\/code> \u2013 most significant bit \u2013 \u043d\u043e\u043c\u0435\u0440 \u0441\u0442\u0430\u0440\u0448\u0435\u0433\u043e \u0435\u0434\u0438\u043d\u0438\u0447\u043d\u043e\u0433\u043e \u0431\u0438\u0442\u0430.  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">Recursive split-ordering<\/b><\/p>\n<div class=\"spoiler_text\">\u0412\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u043c\u0435\u0442\u0438\u0442, \u0447\u0442\u043e \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044f, \u043a\u043e\u0433\u0434\u0430 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 bucket \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442, \u2014 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u0435\u043c\u0443 \u0441\u043b\u043e\u0442 \u0432 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043f\u0443\u0441\u0442. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430 \u043f\u043e\u043c\u043e\u0449\u044c \u043d\u0430\u043c \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044f: \u043c\u044b \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 bucket \u0434\u043b\u044f \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u043e\u0433\u043e bucket&#8217;\u0430 \u0438 \u0442.\u0434. \u0427\u0442\u043e\u0431\u044b \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044f \u0431\u044b\u043b\u0430 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430, bucket 0 \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 split-ordered list, \u0442\u043e \u0435\u0441\u0442\u044c bucket 0 \u0441\u043e\u0437\u0434\u0430\u0435\u0442\u0441\u044f \u0432 \u043c\u043e\u043c\u0435\u043d\u0442 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0441\u043f\u0438\u0441\u043a\u0430.  <\/div>\n<\/div>\n<p>  \u0418\u0442\u0430\u043a, \u0434\u043b\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 10 \u043f\u0440\u0435\u0436\u0434\u0435 \u0432\u0441\u0435\u0433\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 bucket 2 \u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0435\u0433\u043e \u0432 bucket 0. \u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0433\u043e\u0442\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <i>\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u043e\u0433\u043e<\/i> \u0441\u043f\u0438\u0441\u043a\u0430, \u0442\u0430\u043a \u0447\u0442\u043e \u0441\u0430\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c\u0441\u044f, \u043a\u0430\u043a \u0436\u0435 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d \u043d\u0430\u0448 split-ordered list.<br \/>  \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0432\u0441\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0434\u043e \u0441\u0438\u0445 \u043f\u043e\u0440 \u0434\u0435\u043b\u0430\u043b\u0438, \u0431\u044b\u043b\u0438 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0435 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043a\u043b\u044e\u0447\u0435\u0439:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/f6a\/779\/962\/f6a779962e724b6693b318a9ac7d6cfc.png\"\/><br \/>  \u0410 \u0442\u0435\u043f\u0435\u0440\u044c \u2014 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435: \u0435\u0441\u043b\u0438 \u043f\u0440\u043e\u0447\u0435\u0441\u0442\u044c \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043a\u043b\u044e\u0447\u0435\u0439 <i>\u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e<\/i>, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/954\/4b0\/03f\/9544b003f8b644be9cbc997cbeb35435.png\"\/><br \/>  \u0422\u0430\u043a\u0438\u0435 \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u043d\u044b\u0435 \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044f \u043d\u0430\u0437\u044b\u0432\u0430\u044e shah.<br \/>  \u0418\u0442\u0430\u043a, \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u0441\u043f\u0438\u0441\u043a\u0430 \u2014 \u043f\u043e \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u043d\u044b\u043c (\u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043d\u043d\u044b\u043c \u0441\u043f\u0440\u0430\u0432\u0430 \u043d\u0430\u043b\u0435\u0432\u043e) \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c \u043a\u043b\u044e\u0447\u0435\u0439.   <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0431\u0438\u0442<\/b><\/p>\n<div class=\"spoiler_text\">\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u0447\u0442\u043e \u043d\u0438 \u043e\u0434\u043d\u0430 \u0438\u0437 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u043c\u043d\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043d\u044b\u0445 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440 \u043d\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0431\u0438\u0442 \u0432 \u0441\u043b\u043e\u0432\u0435, \u0445\u043e\u0442\u044f, \u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0431\u044b, \u0442\u0430\u043a\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0438 \u0431\u0435\u0437 \u043e\u0441\u043e\u0431\u044b\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u0432 \u0436\u0435\u043b\u0435\u0437\u0435. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0431\u0438\u0442 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u043e, \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u0442\u0430\u043f\u043e\u0432, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a:  <\/p>\n<pre><code>        uint32_t reverse_bit_order( uint32_t x )         {             \/\/ swap odd and even bits             x = ((x &gt;&gt; 1) & 0x55555555) | ((x & 0x55555555) &lt;&lt; 1);             \/\/ swap consecutive pairs             x = ((x &gt;&gt; 2) & 0x33333333) | ((x & 0x33333333) &lt;&lt; 2);             \/\/ swap nibbles ...             x = ((x &gt;&gt; 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) &lt;&lt; 4);             \/\/ swap bytes             x = ((x &gt;&gt; 8) & 0x00FF00FF) | ((x & 0x00FF00FF) &lt;&lt; 8);             \/\/ swap 2-byte long pairs             return ( x &gt;&gt; 16 ) | ( x &lt;&lt; 16 );         } <\/code><\/pre>\n<p>  \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 \u0434\u0432\u0430 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f, \u043e\u0431\u0440\u0430\u0449\u0430\u044e\u0449\u0438\u0435 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0431\u0430\u0439\u0442, \u0438\u043d\u043e\u0433\u0434\u0430 \u0432 \u0436\u0435\u043b\u0435\u0437\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u044b.  <\/div>\n<\/div>\n<p>  \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e: bucket&#8217;\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u043e \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c \u043a\u043b\u044e\u0447\u0435\u0439, \u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u2014 \u043f\u043e \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u043d\u044b\u043c \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c. \u0413\u043b\u0430\u0432\u043d\u043e\u0435 \u2014 \u043d\u0435 \u0437\u0430\u043f\u0443\u0442\u0430\u0442\u044c\u0441\u044f.<br \/>  \u041d\u043e \u0438 \u044d\u0442\u043e \u0435\u0449\u0451 \u043d\u0435 \u0432\u0441\u0435. \u0412\u0437\u0433\u043b\u044f\u043d\u0443\u0432 \u043d\u0430 \u0440\u0438\u0441\u0443\u043d\u043e\u043a \u0435\u0449\u0451 \u0440\u0430\u0437, \u043c\u044b \u0443\u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0443\u0437\u0435\u043b \u0441 \u043a\u043b\u044e\u0447\u043e\u043c 2 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0432 \u0441\u043f\u0438\u0441\u043a\u0435, \u2014 \u044d\u0442\u043e \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0439 \u0443\u0437\u0435\u043b, \u0430 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0441 \u0442\u0435\u043c \u0436\u0435 \u0441\u0430\u043c\u044b\u043c \u043a\u043b\u044e\u0447\u043e\u043c. \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0438 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u2014 \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u0440\u0430\u0437\u043d\u044b\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b, \u0434\u0430\u0436\u0435 \u043f\u043e \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u043c\u0443 \u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044e: \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u043a\u043b\u044e\u0447 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 (value), \u0430 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435, \u0441\u043b\u0443\u0436\u0430\u0449\u0438\u0435 \u043c\u0435\u0442\u043a\u0430\u043c\u0438 \u043d\u0430\u0447\u0430\u043b\u0430 bucket&#8217;\u043e\u0432, \u2014 \u0442\u043e\u043b\u044c\u043a\u043e \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0420\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0439 \u0443\u0437\u0435\u043b \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0443\u0434\u0430\u043b\u0435\u043d \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430, \u0430 \u0432\u043e\u0442 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u2014 \u043d\u0438\u043a\u043e\u0433\u0434\u0430. \u0421\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u043a\u0430\u043a-\u0442\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u0430\u0442\u044c \u044d\u0442\u0438 \u0434\u0432\u0430 \u0442\u0438\u043f\u0430 \u0443\u0437\u043b\u043e\u0432. \u0410\u0432\u0442\u043e\u0440\u044b \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u0442\u0430\u0440\u0448\u0438\u0439 \u0431\u0438\u0442 \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f (\u0432 \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u043d\u043e\u043c \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0438 \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043c\u043b\u0430\u0434\u0448\u0438\u0439 \u0431\u0438\u0442): \u0432 \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0443\u0437\u043b\u043e\u0432 \u0441\u0442\u0430\u0440\u0448\u0438\u0439 \u0431\u0438\u0442 \u0432\u044b\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432 1, \u0430 \u0432\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u2014 \u0432 0:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/b4e\/206\/f2b\/b4e206f2b2fd4461b0c21be75a97b191.png\"\/><br \/>  \u042d\u0442\u043e\u0442 \u0431\u0438\u0442 \u0442\u0430\u043a\u0436\u0435 \u0438\u0433\u0440\u0430\u0435\u0442 \u0440\u043e\u043b\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0442\u0435\u043b\u044f \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u043a\u043b\u044e\u0447\u0430 \u0432 bucket&#8217;\u0435, \u2014 \u043c\u044b \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u0432\u044b\u043b\u0435\u0437\u0435\u043c \u0437\u0430 \u0433\u0440\u0430\u043d\u0438\u0446\u044b bucket&#8217;\u0430.<\/p>\n<p>  \u041f\u043e\u0434\u0432\u0435\u0434\u0435\u043c \u0438\u0442\u043e\u0433 \u0432\u0441\u0435\u043c\u0443 \u0432\u044b\u0448\u0435\u0441\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c\u0443. \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u043a\u043b\u044e\u0447\u0430 10 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u0432 \u0434\u0432\u0430 \u044d\u0442\u0430\u043f\u0430: \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0443\u0437\u0435\u043b 2 \u0432 \u0440\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 bucket 0:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/d5f\/5b7\/101\/d5f5b7101e4345b6a73ddbe8ae69f695.png\"\/><br \/>  \u0417\u0430\u0442\u0435\u043c \u0432 bucket 2 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441 \u043a\u043b\u044e\u0447\u043e\u043c 10:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/eb4\/91b\/57e\/eb491b57e1b34cb49f44e72a93654275.png\"\/><br \/>  \u0412 \u043e\u0441\u043d\u043e\u0432\u0435 split-ordered list \u043b\u0435\u0436\u0438\u0442 lock-free ordered list, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u043b\u0438 \u0432 <a href=\"http:\/\/habrahabr.ru\/post\/250383\/\">\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435<\/a>, \u0442\u0430\u043a \u0447\u0442\u043e \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0442\u0440\u0443\u0434\u043d\u043e\u0441\u0442\u0435\u0439 \u0441\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u043e\u0439\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435\u043c \u0431\u044b\u0442\u044c \u043d\u0435 \u0434\u043e\u043b\u0436\u043d\u043e. \u041a\u0441\u0442\u0430\u0442\u0438, \u043f\u0440\u043e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435, \u2014 \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u0437 split-ordered list \u043d\u0435 \u0438\u043c\u0435\u0435\u0442, \u043c\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043f\u043e \u043a\u043b\u044e\u0447\u0443 bucket \u0438 \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u0437 lock-free list \u0441 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0432\u043e \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u043c \u0443\u0437\u043b\u0435 \u044d\u0442\u043e\u0433\u043e bucket&#8217;\u0430. \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0437\u043b\u044b \u043d\u0435 \u0443\u0434\u0430\u043b\u044f\u044e\u0442\u0441\u044f \u043d\u0438\u043a\u043e\u0433\u0434\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0432 split-ordered list \u043c\u043e\u0436\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438 \u0440\u0430\u0441\u0442\u0438, \u043d\u043e \u043d\u0435 \u0441\u0436\u0438\u043c\u0430\u0442\u044c\u0441\u044f.<\/p>\n<p>  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c split-ordered list \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0435\u043d \u0442\u0435\u043c, \u0447\u0442\u043e \u043e\u043d \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u0442 \u0432\u0441\u0435\u043c \u043a\u0430\u043d\u043e\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u043c \u043e \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u0430\u0445. \u0412\u0441\u043f\u043e\u043c\u043d\u0438\u043c, \u041a\u043d\u0443\u0442 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043c\u043e\u043d\u043e\u0433\u0440\u0430\u0444\u0438\u0438 \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0445\u043e\u0440\u043e\u0448\u0435\u0439 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0435\u0451 \u0440\u0430\u0437\u043c\u0435\u0440 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043f\u0440\u043e\u0441\u0442\u044b\u043c \u0447\u0438\u0441\u043b\u043e\u043c, \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u0432\u0441\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u0414\u043b\u044f split-ordered list \u0432\u0441\u0435 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442: \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u0432\u0441\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0430 \u0432\u0435\u0434\u0435\u0442\u0441\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0434\u0432\u043e\u0439\u043a\u0438. \u0422\u0430\u043a\u0430\u044f \u0437\u0430\u0442\u043e\u0447\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u0434 <code>2**N<\/code> \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u043b\u043e\u0436\u0438\u0442\u0441\u044f \u043d\u0430 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435, \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441, \u0432\u0441\u0451 \u0435\u0449\u0451 \u0442\u0443\u043f\u044f\u0442 \u043d\u0430 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u043c \u0434\u0435\u043b\u0435\u043d\u0438\u0438, \u0430 \u0432\u043e\u0442 \u0437\u0430\u043c\u0435\u043d\u0430 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 \u0441\u0434\u0432\u0438\u0433\u0438 \u0438\u043c \u043e\u0447\u0435\u043d\u044c \u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f.<\/p>\n<p>  \u041e\u0441\u0442\u0430\u043b\u0441\u044f \u043e\u0434\u0438\u043d \u043d\u0435\u0432\u044b\u044f\u0441\u043d\u0435\u043d\u043d\u044b\u0439 \u0432\u043e\u043f\u0440\u043e\u0441 \u2014 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b. \u0410\u0432\u0442\u043e\u0440\u044b \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e\u0442 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043d\u0443\u044e \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u0430\u0446\u0438\u044e \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b:<br \/>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/1e8\/f0b\/9ba\/1e8f0b9bac1541ca9cdbaf2c8063f8b3.png\"\/><br \/>  \u0412\u043c\u0435\u0441\u0442\u043e \u0435\u0434\u0438\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 <code>T[N]<\/code> \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043e\u0432 <code>Segment[M]<\/code>, \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0435\u043c\u044b\u0439 \u043f\u0440\u0438 \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 split-ordered list. \u0417\u0434\u0435\u0441\u044c <code>M<\/code> \u2014 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u0434\u0432\u043e\u0439\u043a\u0438. \u041d\u043e\u043c\u0435\u0440 \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u0430 \u2014 \u044d\u0442\u043e \u0441\u0442\u0430\u0440\u0448\u0438\u0435 \u0431\u0438\u0442\u044b \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u041a\u0430\u0436\u0434\u044b\u0439 \u0441\u0435\u0433\u043c\u0435\u043d\u0442 \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 <code>T[N]<\/code>, \u044d\u0442\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0441\u043e\u0437\u0434\u0430\u044e\u0442\u0441\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u043a\u0440\u043e\u043c\u0435 \u0442\u0430\u0431\u043b\u0438\u0446\u044b <code>Segment[0]<\/code>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 split-ordered list (\u043f\u043e\u043c\u043d\u0438\u0442\u0435, \u044f \u043e\u0442\u043c\u0435\u0447\u0430\u043b, \u0447\u0442\u043e bucket 0 \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c).<br \/>  \u041f\u0440\u0438 \u0442\u0430\u043a\u043e\u0439 \u043e\u0440\u0433\u0430\u043d\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 \u043c\u043e\u043c\u0435\u043d\u0442 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043e\u0431\u044a\u0435\u043a\u0442\u0430-\u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u0441\u0435 \u0436\u0435 \u043d\u0443\u0436\u043d\u043e \u0437\u043d\u0430\u0442\u044c \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0441\u0435\u0433\u043c\u0435\u043d\u0442\u043e\u0432 <code>M<\/code> (\u043d\u0438\u043a\u0430\u043a\u043e\u0433\u043e \u043e\u0441\u043e\u0431\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u044d\u0442\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u0442 \u2014 \u043c\u043d\u043e\u044e \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u043d\u044b \u043d\u0435\u043a\u0438\u0435 \u0433\u0440\u0430\u043d\u0438\u0446\u044b, \u0447\u0442\u043e\u0431\u044b \u043a\u0430\u043a <code>Segment[]<\/code>, \u0442\u0430\u043a \u0438 \u043a\u0430\u0436\u0434\u0430\u044f <code>T[]<\/code> \u0431\u044b\u043b\u0438 \u0441\u043e\u0438\u0437\u043c\u0435\u0440\u0438\u043c\u044b \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443). \u041d\u043e \u0432\u0441\u0435 \u0436\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043e\u043f\u0443\u0441\u043a\u0430\u0435\u0442 <i>\u0440\u043e\u0441\u0442<\/i> \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u043f\u0443\u0441\u0442\u044c \u0438 \u0432 \u0442\u0430\u043a\u043e\u043c \u043d\u0435\u043f\u0440\u0438\u0432\u044b\u0447\u043d\u043e\u043c \u0432\u0438\u0434\u0435.<\/p>\n<h2>\u0418\u0442\u043e\u0433\u0438<\/h2>\n<p>  <img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/7f5\/9f6\/d67\/7f59f6d676904ab5818ceed4936ddf6a.png\" align=\"right\"\/><br \/>  \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d \u0432\u0435\u0441\u044c\u043c\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c lock-free split-ordered list, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0439 \u0434\u0435\u043b\u0430\u0442\u044c rehash \u0431\u0435\u0437 rebuild, \u0442\u043e \u0435\u0441\u0442\u044c \u0431\u0435\u0437 \u043f\u0435\u0440\u0435\u0441\u0442\u0440\u043e\u0439\u043a\u0438 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a\u0436\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0435\u043d \u0442\u0435\u043c, \u0447\u0442\u043e \u0432 \u0441\u0432\u043e\u0435\u0439 \u043e\u0441\u043d\u043e\u0432\u0435 \u0438\u043c\u0435\u0435\u0442 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 lock-free ordered list \u0438 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d \u043a\u0430\u043a \u043f\u043e\u043b\u0438\u0433\u043e\u043d \u0434\u043b\u044f \u043e\u0442\u043b\u0430\u0434\u043a\u0438 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0439 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0445 \u0441\u043f\u0438\u0441\u043a\u043e\u0432.<br \/>   \u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0432 <a href=\"https:\/\/github.com\/khizmax\/libcds\">libcds<\/a> \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u043d\u0435\u043f\u043b\u043e\u0445\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0432 \u0442\u0435\u0441\u0442\u0430\u0445, \u043d\u043e \u0432\u0441\u0435 \u0436\u0435 \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0445\u0443\u0436\u0435, \u0447\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 hash map, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435. \u042d\u0442\u043e\u043c\u0443 \u0435\u0441\u0442\u044c \u0434\u0432\u0435 \u043f\u0440\u0438\u0447\u0438\u043d\u044b:  <\/p>\n<ul>\n<li>\u044d\u0442\u043e \u043f\u043b\u0430\u0442\u0430 \u0437\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438 \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0435\u043c\u044b\u0435 bucket&#8217;\u044b<\/li>\n<li>\u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u043f\u043e\u0440\u044f\u0434\u043a\u0430 \u0431\u0438\u0442 \u0445\u0435\u0448-\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432\u0441\u0435-\u0442\u0430\u043a\u0438 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0442\u044f\u0436\u0435\u043b\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f, \u0435\u0441\u043b\u0438 \u043e\u043d\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u043e. \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b \u0438\u043c\u0435\u0442\u044c \u0434\u0430\u043d\u043d\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0432 \u0436\u0435\u043b\u0435\u0437\u0435<\/li>\n<\/ul>\n<p>  \u0421 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f, \u043e\u0447\u0435\u043d\u044c \u0443\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u043b\u043e \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0437\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c ordered list \u043a\u0430\u043a \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044e \u0434\u043b\u044f split-ordered list.<\/p>\n<p>  \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e\u0431 \u0435\u0449\u0451 \u043e\u0434\u043d\u043e\u0439 \u0440\u0435\u0438\u043d\u043a\u0430\u0440\u043d\u0430\u0446\u0438\u0438 lock-free ordered list. \u041d\u0430 \u0441\u0435\u0439 \u0440\u0430\u0437 \u0431\u0443\u0434\u0435\u043c \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043d\u0435 hash map, \u0430 <i>\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439<\/i> map.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">Lock-free \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445<\/b><\/p>\n<div class=\"spoiler_text\"><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/195770\/\">\u041d\u0430\u0447\u0430\u043b\u043e<\/a><br \/>  \u041e\u0441\u043d\u043e\u0432\u044b:  <\/p>\n<ul>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/195948\/\">\u0410\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u0438 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u0435 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u044b<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/196548\/\">\u041e\u0442\u043a\u0443\u0434\u0430 \u043f\u043e\u0448\u043b\u0438 \u0431\u044b\u0442\u044c \u0431\u0430\u0440\u044c\u0435\u0440\u044b \u043f\u0430\u043c\u044f\u0442\u0438<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/197520\/\">\u041c\u043e\u0434\u0435\u043b\u044c \u043f\u0430\u043c\u044f\u0442\u0438<\/a><\/li>\n<\/ul>\n<p>  \u0412\u043d\u0443\u0442\u0440\u0438:  <\/p>\n<ul>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/202190\/\">\u0421\u0445\u0435\u043c\u044b \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u0430\u043c\u044f\u0442\u044c\u044e<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/206984\/\">RCU<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/216013\/\">\u042d\u0432\u043e\u043b\u044e\u0446\u0438\u044f \u0441\u0442\u0435\u043a\u0430<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/219201\/\">\u041e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0442\u0440\u0430\u043a\u0442\u0430\u0442<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/post\/230349\/\">\u0414\u0438\u0441\u0441\u0435\u043a\u0446\u0438\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u0438<\/a><\/li>\n<li><a href=\"http:\/\/habrahabr.ru\/post\/250383\/\">Concurrent maps: \u0440\u0430\u0437\u043c\u0438\u043d\u043a\u0430<\/a><\/li>\n<\/ul>\n<p>  \u0418\u0437\u0432\u043d\u0435:  <\/p>\n<ul>\n<li><a href=\"http:\/\/habrahabr.ru\/company\/ifree\/blog\/196834\/\">\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 libcds<\/a><\/li>\n<\/ul>\n<p>  <\/div>\n<\/div>\n<div class=\"clear\"><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/250523\/\"> http:\/\/habrahabr.ru\/post\/250523\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>     \t<img decoding=\"async\" src=\"\/\/habrastorage.org\/files\/4e3\/317\/fa0\/4e3317fa037748138cb0ed6e90a788a6.png\" align=\"right\"\/><br \/>  \u041f\u0440\u043e\u0439\u0434\u0435\u043c \u043f\u043e \u0441\u043b\u0435\u0434\u0430\u043c <a href=\"http:\/\/meetingcpp.ru\/\">C++ 2015 Russia<\/a> \u0434\u0430\u043b\u0435\u0435.<br \/>  \u0412 <a href=\"http:\/\/habrahabr.ru\/post\/250383\/\">\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439<\/a> \u0441\u0442\u0430\u0442\u044c\u0435 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f lock-free ordered list \u0438 \u043d\u0430 \u0435\u0433\u043e \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u0434\u0435\u043b\u0430\u043b\u0438 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 lock-free hash map. \u0423 \u044d\u0442\u043e\u0433\u043e hash map \u0435\u0441\u0442\u044c \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u043a: \u0440\u0430\u0437\u043c\u0435\u0440 \u0445\u0435\u0448-\u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0435\u043d \u0438 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0440\u043e\u0441\u0442\u0430 \u0447\u0438\u0441\u043b\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0435. \u042d\u0442\u043e \u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b, \u0435\u0441\u043b\u0438 \u043c\u044b \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u044b\u0439 \u043e\u0431\u044a\u0435\u043c \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430. \u0410 \u0435\u0441\u043b\u0438 \u043d\u0435\u0442?  <\/p>\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-252378","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/252378","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=252378"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/252378\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=252378"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=252378"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=252378"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}