{"id":5380,"date":"2023-09-09T16:10:26","date_gmt":"2023-09-09T08:10:26","guid":{"rendered":"https:\/\/www.xttblog.com\/?p=5380"},"modified":"2023-09-09T17:21:26","modified_gmt":"2023-09-09T09:21:26","slug":"%e5%a6%82%e4%bd%95%e8%ae%be%e8%ae%a1%e5%b9%b6%e5%ae%9e%e7%8e%b0%e4%b8%80%e4%b8%aa%e7%ba%bf%e7%a8%8b%e5%ae%89%e5%85%a8%e7%9a%84-map%ef%bc%9f","status":"publish","type":"post","link":"https:\/\/www.xttblog.com\/?p=5380","title":{"rendered":"\u5982\u4f55\u8bbe\u8ba1\u5e76\u5b9e\u73b0\u4e00\u4e2a\u7ebf\u7a0b\u5b89\u5168\u7684 Map\uff1f"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Map \u662f\u4e00\u79cd\u5f88\u5e38\u89c1\u7684\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u5b58\u50a8\u4e00\u4e9b\u65e0\u5e8f\u7684\u952e\u503c\u5bf9\u3002\u5728\u4e3b\u6d41\u7684\u7f16\u7a0b\u8bed\u8a00\u4e2d\uff0c\u9ed8\u8ba4\u5c31\u81ea\u5e26\u5b83\u7684\u5b9e\u73b0\u3002C\u3001C++ \u4e2d\u7684 STL \u5c31\u5b9e\u73b0\u4e86 Map\uff0cJavaScript \u4e2d\u4e5f\u6709 Map\uff0cJava \u4e2d\u6709 HashMap\uff0cSwift \u548c Python \u4e2d\u6709 Dictionary\uff0cGo \u4e2d\u6709 Map\uff0cObjective-C \u4e2d\u6709 NSDictionary\u3001NSMutableDictionary\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u9762\u8fd9\u4e9b Map \u90fd\u662f\u7ebf\u7a0b\u5b89\u5168\u7684\u4e48\uff1f\u7b54\u6848\u662f\u5426\u5b9a\u7684\uff0c\u5e76\u975e\u5168\u662f\u7ebf\u7a0b\u5b89\u5168\u7684\u3002\u90a3\u5982\u4f55\u80fd\u5b9e\u73b0\u4e00\u4e2a\u7ebf\u7a0b\u5b89\u5168\u7684 Map \u5462\uff1f\u60f3\u56de\u7b54\u8fd9\u4e2a\u95ee\u9898\uff0c\u9700\u8981\u5148\u4ece\u5982\u4f55\u5b9e\u73b0\u4e00\u4e2a Map \u8bf4\u8d77\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u9009\u7528\u4ec0\u4e48\u6570\u636e\u7ed3\u6784\u5b9e\u73b0 Map \uff1f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Map \u662f\u4e00\u4e2a\u975e\u5e38\u5e38\u7528\u7684\u6570\u636e\u7ed3\u6784\uff0c\u4e00\u4e2a\u65e0\u5e8f\u7684 key\/value \u5bf9\u7684\u96c6\u5408\uff0c\u5176\u4e2d Map \u6240\u6709\u7684 key \u90fd\u662f\u4e0d\u540c\u7684\uff0c\u7136\u540e\u901a\u8fc7\u7ed9\u5b9a\u7684 key \u53ef\u4ee5\u5728\u5e38\u6570\u65f6\u95f4 O(1) \u590d\u6742\u5ea6\u5185\u67e5\u627e\u3001\u66f4\u65b0\u6216\u5220\u9664\u5bf9\u5e94\u7684 value\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8981\u60f3\u5b9e\u73b0\u5e38\u6570\u7ea7\u7684\u67e5\u627e\uff0c\u5e94\u8be5\u7528\u4ec0\u4e48\u6765\u5b9e\u73b0\u5462\uff1f\u8bfb\u8005\u5e94\u8be5\u5f88\u5feb\u4f1a\u60f3\u5230\u54c8\u5e0c\u8868\u3002\u786e\u5b9e\uff0cMap \u5e95\u5c42\u4e00\u822c\u90fd\u662f\u4f7f\u7528\u6570\u7ec4\u6765\u5b9e\u73b0\uff0c\u4f1a\u501f\u7528\u54c8\u5e0c\u7b97\u6cd5\u8f85\u52a9\u3002\u5bf9\u4e8e\u7ed9\u5b9a\u7684 key\uff0c\u4e00\u822c\u5148\u8fdb\u884c hash \u64cd\u4f5c\uff0c\u7136\u540e\u76f8\u5bf9\u54c8\u5e0c\u8868\u7684\u957f\u5ea6\u53d6\u6a21\uff0c\u5c06 key \u6620\u5c04\u5230\u6307\u5b9a\u7684\u5730\u65b9\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/0.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u54c8\u5e0c\u7b97\u6cd5\u6709\u5f88\u591a\u79cd\uff0c\u9009\u54ea\u4e00\u79cd\u66f4\u52a0\u9ad8\u6548\u5462\uff1f<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u54c8\u5e0c\u51fd\u6570<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/1.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">MD5 \u548c SHA1 \u53ef\u4ee5\u8bf4\u662f\u76ee\u524d\u5e94\u7528\u6700\u5e7f\u6cdb\u7684 Hash \u7b97\u6cd5\uff0c\u800c\u5b83\u4eec\u90fd\u662f\u4ee5 MD4 \u4e3a\u57fa\u7840\u8bbe\u8ba1\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">MD4(RFC 1320) \u662f MIT \u7684Ronald L. Rivest \u5728 1990 \u5e74\u8bbe\u8ba1\u7684\uff0cMD \u662f Message Digest\uff08\u6d88\u606f\u6458\u8981\uff09 \u7684\u7f29\u5199\u3002\u5b83\u9002\u7528\u572832\u4f4d\u5b57\u957f\u7684\u5904\u7406\u5668\u4e0a\u7528\u9ad8\u901f\u8f6f\u4ef6\u5b9e\u73b0\u2014\u2014\u5b83\u662f\u57fa\u4e8e 32\u4f4d\u64cd\u4f5c\u6570\u7684\u4f4d\u64cd\u4f5c\u6765\u5b9e\u73b0\u7684\u3002<br>\nMD5(RFC 1321) \u662f Rivest \u4e8e1991\u5e74\u5bf9 MD4 \u7684\u6539\u8fdb\u7248\u672c\u3002\u5b83\u5bf9\u8f93\u5165\u4ecd\u4ee5512\u4f4d\u5206\u7ec4\uff0c\u5176\u8f93\u51fa\u662f4\u4e2a32\u4f4d\u5b57\u7684\u7ea7\u8054\uff0c\u4e0e MD4 \u76f8\u540c\u3002MD5 \u6bd4 MD4 \u6765\u5f97\u590d\u6742\uff0c\u5e76\u4e14\u901f\u5ea6\u8f83\u4e4b\u8981\u6162\u4e00\u70b9\uff0c\u4f46\u66f4\u5b89\u5168\uff0c\u5728\u6297\u5206\u6790\u548c\u6297\u5dee\u5206\u65b9\u9762\u8868\u73b0\u66f4\u597d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">SHA1 \u662f\u7531 NIST NSA \u8bbe\u8ba1\u4e3a\u540c DSA \u4e00\u8d77\u4f7f\u7528\u7684\uff0c\u5b83\u5bf9\u957f\u5ea6\u5c0f\u4e8e264\u7684\u8f93\u5165\uff0c\u4ea7\u751f\u957f\u5ea6\u4e3a160bit \u7684\u6563\u5217\u503c\uff0c\u56e0\u6b64\u6297\u7a77\u4e3e (brute-force)<br>\n\u6027\u66f4\u597d\u3002SHA-1 \u8bbe\u8ba1\u65f6\u57fa\u4e8e\u548c MD4 \u76f8\u540c\u539f\u7406,\u5e76\u4e14\u6a21\u4eff\u4e86\u8be5\u7b97\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5e38\u7528\u7684 hash \u51fd\u6570\u6709 SHA-1\uff0cSHA-256\uff0cSHA-512\uff0cMD5 \u3002\u8fd9\u4e9b\u90fd\u662f\u7ecf\u5178\u7684 hash \u7b97\u6cd5\u3002\u5728\u73b0\u4ee3\u5316\u751f\u4ea7\u4e2d\uff0c\u8fd8\u4f1a\u7528\u5230\u73b0\u4ee3\u7684 hash \u7b97\u6cd5\u3002\u4e0b\u9762\u5217\u4e3e\u51e0\u4e2a\uff0c\u8fdb\u884c\u6027\u80fd\u5bf9\u6bd4\uff0c\u6700\u540e\u518d\u9009\u5176\u4e2d\u4e00\u4e2a\u6e90\u7801\u5206\u6790\u4e00\u4e0b\u5b9e\u73b0\u8fc7\u7a0b\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Jenkins Hash \u548c SpookyHash<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/2.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">1997\u5e74 Bob Jenkins<code>http:\/\/burtleburtle.net\/bob\/<\/code> \u5728\u300a Dr. Dobbs Journal\u300b\u6742\u5fd7\u4e0a\u53d1\u8868\u4e86\u4e00\u7247\u5173\u4e8e\u6563\u5217\u51fd\u6570\u7684\u6587\u7ae0\u300aA hash function for hash Table lookup\u300b<code>http:\/\/www.burtleburtle.net\/bob\/hash\/doobs.html<\/code>\u3002\u8fd9\u7bc7\u6587\u7ae0\u4e2d\uff0cBob \u5e7f\u6cdb\u6536\u5f55\u4e86\u5f88\u591a\u5df2\u6709\u7684\u6563\u5217\u51fd\u6570\uff0c\u8fd9\u5176\u4e2d\u4e5f\u5305\u62ec\u4e86\u4ed6\u81ea\u5df1\u6240\u8c13\u7684\u201clookup2\u201d\u3002\u968f\u540e\u57282006\u5e74\uff0cBob \u53d1\u5e03\u4e86 lookup3<code>http:\/\/burtleburtle.net\/bob\/c\/lookup3.c<\/code>\u3002lookup3 \u5373\u4e3a Jenkins Hash\u3002\u66f4\u591a\u6709\u5173 Bob\u2019s \u6563\u5217\u51fd\u6570\u7684\u5185\u5bb9\u8bf7\u53c2\u9605\u7ef4\u57fa\u767e\u79d1\uff1aJenkins hash <code>http:\/\/en.wikipedia.org\/wiki\/Jenkins_hash_function<\/code>\u3002memcached\u7684 hash \u7b97\u6cd5\uff0c\u652f\u6301\u4e24\u79cd\u7b97\u6cd5\uff1ajenkins, murmur3\uff0c\u9ed8\u8ba4\u662f jenkins\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2011\u5e74 Bob Jenkins \u53d1\u5e03\u4e86\u4ed6\u81ea\u5df1\u7684\u4e00\u4e2a\u65b0\u6563\u5217\u51fd\u6570<br>\nSpookyHash\uff08\u8fd9\u6837\u547d\u540d\u662f\u56e0\u4e3a\u5b83\u662f\u5728\u4e07\u5723\u8282\u53d1\u5e03\u7684\uff09\u3002\u5b83\u4eec\u90fd\u62e5\u67092\u500d\u4e8e MurmurHash \u7684\u901f\u5ea6\uff0c\u4f46\u4ed6\u4eec\u90fd\u53ea\u4f7f\u7528\u4e8664\u4f4d\u6570\u5b66\u51fd\u6570\u800c\u6ca1\u670932\u4f4d\u7248\u672c\uff0cSpookyHash \u7ed9\u51fa128\u4f4d\u8f93\u51fa\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">MurmurHash<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/3.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">MurmurHash \u662f\u4e00\u79cd\u975e\u52a0\u5bc6<code>https:\/\/zh.wikipedia.org\/wiki\/\u52a0\u5bc6<\/code>\u578b\u54c8\u5e0c\u51fd\u6570<code>https:\/\/zh.wikipedia.org\/wiki\/\u54c8\u5e0c\u51fd\u6570<\/code>\uff0c\u9002\u7528\u4e8e\u4e00\u822c\u7684\u54c8\u5e0c\u68c0\u7d22\u64cd\u4f5c\u3002<br>\nAustin Appleby \u57282008\u5e74\u53d1\u5e03\u4e86\u4e00\u4e2a\u65b0\u7684\u6563\u5217\u51fd\u6570\u2014\u2014MurmurHash<code>https:\/\/en.wikipedia.org\/wiki\/MurmurHash<\/code>\u3002\u5176\u6700\u65b0\u7248\u672c\u5927\u7ea6\u662f lookup3 \u901f\u5ea6\u76842\u500d\uff08\u5927\u7ea6\u4e3a1 byte\/cycle\uff09\uff0c\u5b83\u670932\u4f4d\u548c64\u4f4d\u4e24\u4e2a\u7248\u672c\u300232\u4f4d\u7248\u672c\u53ea\u4f7f\u752832\u4f4d\u6570\u5b66\u51fd\u6570\u5e76\u7ed9\u51fa\u4e00\u4e2a32\u4f4d\u7684\u54c8\u5e0c\u503c\uff0c\u800c64\u4f4d\u7248\u672c\u4f7f\u7528\u4e8664\u4f4d\u7684\u6570\u5b66\u51fd\u6570\uff0c\u5e76\u7ed9\u51fa64\u4f4d\u54c8\u5e0c\u503c\u3002\u6839\u636eAustin\u7684\u5206\u6790\uff0cMurmurHash\u5177\u6709\u4f18\u5f02\u7684\u6027\u80fd\uff0c\u867d\u7136 Bob Jenkins \u5728\u300aDr. Dobbs article\u300b\u6742\u5fd7\u4e0a\u58f0\u79f0\u201c\u6211\u9884\u6d4b MurmurHash \u6bd4\u8d77lookup3\u8981\u5f31\uff0c\u4f46\u662f\u6211\u4e0d\u77e5\u9053\u5177\u4f53\u503c\uff0c\u56e0\u4e3a\u6211\u8fd8\u6ca1\u6d4b\u8bd5\u8fc7\u5b83\u201d\u3002MurmurHash\u80fd\u591f\u8fc5\u901f\u8d70\u7ea2\u5f97\u76ca\u4e8e\u5176\u51fa\u8272\u7684\u901f\u5ea6\u548c\u7edf\u8ba1\u7279\u6027\u3002\u5f53\u524d\u7684\u7248\u672c\u662fMurmurHash3\uff0cRedis\u3001Memcached\u3001Cassandra\u3001HBase\u3001Lucene\u90fd\u5728\u4f7f\u7528\u5b83\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0b\u9762\u662f\u7528 C \u5b9e\u73b0 MurmurHash \u7684\u7248\u672c\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed) {\n        static const uint32_t c1 = 0xcc9e2d51;\n        static const uint32_t c2 = 0x1b873593;\n        static const uint32_t r1 = 15;\n        static const uint32_t r2 = 13;\n        static const uint32_t m = 5;\n        static const uint32_t n = 0xe6546b64;\n\n        uint32_t hash = seed;\n\n        const int nblocks = len \/ 4;\n        const uint32_t *blocks = (const uint32_t *) key;\n        int i;\n        for (i = 0; i &lt; nblocks; i++) {\n                uint32_t k = blocks[i];\n                k *= c1;\n                k = (k &lt;&lt; r1) | (k &gt;&gt; (32 - r1));\n                k *= c2;\n\n                hash ^= k;\n                hash = ((hash &lt;&lt; r2) | (hash &gt;&gt; (32 - r2))) * m + n;\n        }\n\n        const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);\n        uint32_t k1 = 0;\n\n        switch (len &amp; 3) {\n        case 3:\n                k1 ^= tail[2] &lt;&lt; 16;\n        case 2:\n                k1 ^= tail[1] &lt;&lt; 8;\n        case 1:\n                k1 ^= tail[0];\n\n                k1 *= c1;\n                k1 = (k1 &lt;&lt; r1) | (k1 &gt;&gt; (32 - r1));\n                k1 *= c2;\n                hash ^= k1;\n        }\n\n        hash ^= len;\n        hash ^= (hash &gt;&gt; 16);\n        hash *= 0x85ebca6b;\n        hash ^= (hash &gt;&gt; 13);\n        hash *= 0xc2b2ae35;\n        hash ^= (hash &gt;&gt; 16);\n\n        return hash;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">CityHash \u548c FramHash<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/4.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u4e24\u79cd\u7b97\u6cd5\u90fd\u662f Google \u53d1\u5e03\u7684\u5b57\u7b26\u4e32\u7b97\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">CityHash<code>https:\/\/github.com\/google\/cityhash<\/code>\u662f2011\u5e74 Google \u53d1\u5e03\u7684\u5b57\u7b26\u4e32\u6563\u5217\u7b97\u6cd5\uff0c\u548c murmurhash \u4e00\u6837\uff0c\u5c5e\u4e8e\u975e\u52a0\u5bc6\u578b hash \u7b97\u6cd5\u3002CityHash \u7b97\u6cd5\u7684\u5f00\u53d1\u662f\u53d7\u5230\u4e86 MurmurHash \u7684\u542f\u53d1\u3002\u5176\u4e3b\u8981\u4f18\u70b9\u662f\u5927\u90e8\u5206\u6b65\u9aa4\u5305\u542b\u4e86\u81f3\u5c11\u4e24\u6b65\u72ec\u7acb\u7684\u6570\u5b66\u8fd0\u7b97\u3002\u73b0\u4ee3 CPU \u901a\u5e38\u80fd\u4ece\u8fd9\u79cd\u4ee3\u7801\u83b7\u5f97\u6700\u4f73\u6027\u80fd\u3002CityHash \u4e5f\u6709\u5176\u7f3a\u70b9\uff1a\u4ee3\u7801\u8f83\u540c\u7c7b\u6d41\u884c\u7b97\u6cd5\u590d\u6742\u3002Google \u5e0c\u671b\u4e3a\u901f\u5ea6\u800c\u4e0d\u662f\u4e3a\u4e86\u7b80\u5355\u800c\u4f18\u5316\uff0c\u56e0\u6b64\u6ca1\u6709\u7167\u987e\u8f83\u77ed\u8f93\u5165\u7684\u7279\u4f8b\u3002Google\u53d1\u5e03\u7684\u6709\u4e24\u79cd\u7b97\u6cd5\uff1acityhash64 \u4e0e cityhash128\u3002\u5b83\u4eec\u5206\u522b\u6839\u636e\u5b57\u4e32\u8ba1\u7b97 64 \u548c 128 \u4f4d\u7684\u6563\u5217\u503c\u3002\u8fd9\u4e9b\u7b97\u6cd5\u4e0d\u9002\u7528\u4e8e\u52a0\u5bc6\uff0c\u4f46\u9002\u5408\u7528\u5728\u6563\u5217\u8868\u7b49\u5904\u3002CityHash \u7684\u901f\u5ea6\u53d6\u51b3\u4e8eCRC32 \u6307\u4ee4\uff0c\u76ee\u524d\u4e3aSSE 4.2\uff08Intel Nehalem\u53ca\u4ee5\u540e\u7248\u672c\uff09\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u76f8\u6bd4 Murmurhash \u652f\u630132\u300164\u3001128bit\uff0c Cityhash \u652f\u630164\u3001128\u3001256bit \u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">2014\u5e74 Google \u53c8\u53d1\u5e03\u4e86 FarmHash<code>https:\/\/github.com\/google\/farmhash<\/code>\uff0c\u4e00\u4e2a\u65b0\u7684\u7528\u4e8e\u5b57\u7b26\u4e32\u7684\u54c8\u5e0c\u51fd\u6570\u7cfb\u5217\u3002FarmHash \u4ece CityHash \u7ee7\u627f\u4e86\u8bb8\u591a\u6280\u5de7\u548c\u6280\u672f\uff0c\u662f\u5b83\u7684\u540e\u7ee7\u3002FarmHash \u6709\u591a\u4e2a\u76ee\u6807\uff0c\u58f0\u79f0\u4ece\u591a\u4e2a\u65b9\u9762\u6539\u8fdb\u4e86 CityHash\u3002\u4e0e CityHash \u76f8\u6bd4\uff0cFarmHash \u7684\u53e6\u4e00\u9879\u6539\u8fdb\u662f\u5728\u591a\u4e2a\u7279\u5b9a\u4e8e\u5e73\u53f0\u7684\u5b9e\u73b0\u4e4b\u4e0a\u63d0\u4f9b\u4e86\u4e00\u4e2a\u63a5\u53e3\u3002\u8fd9\u6837\uff0c\u5f53\u5f00\u53d1\u4eba\u5458\u53ea\u662f\u60f3\u8981\u4e00\u4e2a\u7528\u4e8e\u54c8\u5e0c\u8868\u7684\u3001\u5feb\u901f\u5065\u58ee\u7684\u54c8\u5e0c\u51fd\u6570\uff0c\u800c\u4e0d\u9700\u8981\u5728\u6bcf\u4e2a\u5e73\u53f0\u4e0a\u90fd\u4e00\u6837\u65f6\uff0cFarmHash \u4e5f\u80fd\u6ee1\u8db3\u8981\u6c42\u3002\u76ee\u524d\uff0cFarmHash \u53ea\u5305\u542b\u572832\u300164\u548c128\u4f4d\u5e73\u53f0\u4e0a\u7528\u4e8e\u5b57\u8282\u6570\u7ec4\u7684\u54c8\u5e0c\u51fd\u6570\u3002\u672a\u6765\u5f00\u53d1\u8ba1\u5212\u5305\u542b\u4e86\u5bf9\u6574\u6570\u3001\u5143\u7ec4\u548c\u5176\u5b83\u6570\u636e\u7684\u652f\u6301\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">xxHash<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/5.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">xxHash \u662f\u7531 Yann Collet \u521b\u5efa\u7684\u975e\u52a0\u5bc6\u54c8\u5e0c\u51fd\u6570\u3002\u5b83\u6700\u521d\u7528\u4e8e LZ4 \u538b\u7f29\u7b97\u6cd5\uff0c\u4f5c\u4e3a\u6700\u7ec8\u7684\u9519\u8bef\u68c0\u67e5\u7b7e\u540d\u7684\u3002\u8be5 hash \u7b97\u6cd5\u7684\u901f\u5ea6\u63a5\u8fd1\u4e8e RAM \u7684\u6781\u9650\u3002\u5e76\u7ed9\u51fa\u4e8632\u4f4d\u548c64\u4f4d\u7684\u4e24\u4e2a\u7248\u672c\u3002\u73b0\u5728\u5b83\u88ab\u5e7f\u6cdb\u4f7f\u7528\u5728<code>PrestoDB<\/code>\uff1a<code>http:\/\/prestodb.io\/<\/code>\u3001RocksDB<code>https:\/\/rocksdb.org\/<\/code>\u3001MySQL<code>https:\/\/www.mysql.com\/<\/code>\u3001ArangoDB<code>https:\/\/www.arangodb.org\/<\/code>\u3001PGroonga<code>https:\/\/pgroonga.github.io\/<\/code>\u3001Spark<code>http:\/\/spark.apache.org\/<\/code> \u8fd9\u4e9b\u6570\u636e\u5e93\u4e2d\uff0c\u8fd8\u7528\u5728\u4e86 Cocos2D<code>http:\/\/www.cocos2d.org\/<\/code>\u3001Dolphin<code>https:\/\/dolphin-emu.org\/<\/code>\u3001Cxbx-reloaded<code>http:\/\/cxbx-reloaded.co.uk\/<\/code> \u8fd9\u4e9b\u6e38\u620f\u6846\u67b6\u4e2d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0b\u9762\u8fd9\u6709\u4e00\u4e2a\u6027\u80fd\u5bf9\u6bd4\u7684\u5b9e\u9a8c\u3002\u6d4b\u8bd5\u73af\u5883\u662f Open-Source SMHasher program by Austin Appleby<code>http:\/\/code.google.com\/p\/smhasher\/wiki\/SMHasher<\/code>\uff0c\u5b83\u662f\u5728 Windows 7 \u4e0a\u901a\u8fc7 Visual C \u7f16\u8bd1\u51fa\u6765\u7684\uff0c\u5e76\u4e14\u5b83\u53ea\u6709\u552f\u4e00\u4e00\u4e2a\u7ebf\u7a0b\u3002CPU \u5185\u6838\u662f Core 2 Duo @3.0GHz\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/6.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u8868\u91cc\u9762\u7684 hash \u51fd\u6570\u5e76\u4e0d\u662f\u6240\u6709\u7684 hash \u51fd\u6570\uff0c\u53ea\u5217\u4e3e\u4e86\u4e00\u4e9b\u5e38\u89c1\u7684\u7b97\u6cd5\u3002\u7b2c\u4e8c\u680f\u662f\u901f\u5ea6\u7684\u5bf9\u6bd4\uff0c\u53ef\u4ee5\u770b\u51fa\u6765\u901f\u5ea6\u6700\u5feb\u7684\u662f xxHash \u3002\u7b2c\u4e09\u680f\u662f\u54c8\u5e0c\u7684\u8d28\u91cf\uff0c\u54c8\u5e0c\u8d28\u91cf\u6700\u9ad8\u7684\u67095\u4e2a\uff0c\u5168\u662f5\u661f\uff0cxxHash\u3001MurmurHash 3a\u3001CityHash64\u3001MD5-32\u3001SHA1-32 \u3002\u4ece\u8868\u91cc\u7684\u6570\u636e\u770b\uff0c\u54c8\u5e0c\u8d28\u91cf\u6700\u9ad8\uff0c\u901f\u5ea6\u6700\u5feb\u7684\u8fd8\u662f xxHash\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">memhash<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/7.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u4e2a\u54c8\u5e0c\u7b97\u6cd5\u7b14\u8005\u6ca1\u6709\u5728\u7f51\u4e0a\u627e\u5230\u5f88\u660e\u786e\u7684\u4f5c\u8005\u4fe1\u606f\u3002\u53ea\u5728 Google \u7684 Go \u7684\u6587\u6863\u4e0a\u6709\u8fd9\u4e48\u51e0\u884c\u6ce8\u91ca\uff0c\u8bf4\u660e\u4e86\u5b83\u7684\u7075\u611f\u6765\u6e90\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ Hashing algorithm inspired by\n\/\/   xxhash: https:\/\/code.google.com\/p\/xxhash\/\n\/\/ cityhash: https:\/\/code.google.com\/p\/cityhash\/<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5b83\u8bf4 memhash \u7684\u7075\u611f\u6765\u6e90\u4e8e xxhash \u548c cityhash\u3002\u90a3\u4e48\u63a5\u4e0b\u6765\u5c31\u6765\u770b\u770b memhash \u662f\u600e\u4e48\u5bf9\u5b57\u7b26\u4e32\u8fdb\u884c\u54c8\u5e0c\u7684\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>const (\n    \/\/ Constants for multiplication: four random odd 32-bit numbers.\n    m1 = 3168982561\n    m2 = 3339683297\n    m3 = 832293441\n    m4 = 2336365089\n)\n\nfunc memhash(p unsafe.Pointer, seed, s uintptr) uintptr {\n    if GOARCH == \"386\" &amp;&amp; GOOS != \"nacl\" &amp;&amp; useAeshash {\n        return aeshash(p, seed, s)\n    }\n    h := uint32(seed + s*hashkey[0])\ntail:\n    switch {\n    case s == 0:\n    case s &lt; 4:\n        h ^= uint32(*(*byte)(p))\n        h ^= uint32(*(*byte)(add(p, s&gt;&gt;1))) &lt;&lt; 8\n        h ^= uint32(*(*byte)(add(p, s-1))) &lt;&lt; 16\n        h = rotl_15(h*m1) * m2\n    case s == 4:\n        h ^= readUnaligned32(p)\n        h = rotl_15(h*m1) * m2\n    case s &lt;= 8:\n        h ^= readUnaligned32(p)\n        h = rotl_15(h*m1) * m2\n        h ^= readUnaligned32(add(p, s-4))\n        h = rotl_15(h*m1) * m2\n    case s &lt;= 16:\n        h ^= readUnaligned32(p)\n        h = rotl_15(h*m1) * m2\n        h ^= readUnaligned32(add(p, 4))\n        h = rotl_15(h*m1) * m2\n        h ^= readUnaligned32(add(p, s-8))\n        h = rotl_15(h*m1) * m2\n        h ^= readUnaligned32(add(p, s-4))\n        h = rotl_15(h*m1) * m2\n    default:\n        v1 := h\n        v2 := uint32(seed * hashkey[1])\n        v3 := uint32(seed * hashkey[2])\n        v4 := uint32(seed * hashkey[3])\n        for s &gt;= 16 {\n            v1 ^= readUnaligned32(p)\n            v1 = rotl_15(v1*m1) * m2\n            p = add(p, 4)\n            v2 ^= readUnaligned32(p)\n            v2 = rotl_15(v2*m2) * m3\n            p = add(p, 4)\n            v3 ^= readUnaligned32(p)\n            v3 = rotl_15(v3*m3) * m4\n            p = add(p, 4)\n            v4 ^= readUnaligned32(p)\n            v4 = rotl_15(v4*m4) * m1\n            p = add(p, 4)\n            s -= 16\n        }\n        h = v1 ^ v2 ^ v3 ^ v4\n        goto tail\n    }\n    h ^= h &gt;&gt; 17\n    h *= m3\n    h ^= h &gt;&gt; 13\n    h *= m4\n    h ^= h &gt;&gt; 16\n    return uintptr(h)\n}\n\n\/\/ Note: in order to get the compiler to issue rotl instructions, we\n\/\/ need to constant fold the shift amount by hand.\n\/\/ TODO: convince the compiler to issue rotl instructions after inlining.\nfunc rotl_15(x uint32) uint32 {\n    return (x &lt;&lt; 15) | (x &gt;&gt; (32 - 15))\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">m1\u3001m2\u3001m3\u3001m4 \u662f4\u4e2a\u968f\u673a\u9009\u7684\u5947\u6570\uff0c\u4f5c\u4e3a\u54c8\u5e0c\u7684\u4e58\u6cd5\u56e0\u5b50\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ used in hash{32,64}.go to seed the hash function\nvar hashkey [4]uintptr\n\nfunc alginit() {\n    \/\/ Install aes hash algorithm if we have the instructions we need\n    if (GOARCH == \"386\" || GOARCH == \"amd64\") &amp;&amp;\n        GOOS != \"nacl\" &amp;&amp;\n        cpuid_ecx&amp;(1&lt;&lt;25) != 0 &amp;&amp; \/\/ aes (aesenc)\n        cpuid_ecx&amp;(1&lt;&lt;9) != 0 &amp;&amp; \/\/ sse3 (pshufb)\n        cpuid_ecx&amp;(1&lt;&lt;19) != 0 { \/\/ sse4.1 (pinsr{d,q})\n        useAeshash = true\n        algarray[alg_MEM32].hash = aeshash32\n        algarray[alg_MEM64].hash = aeshash64\n        algarray[alg_STRING].hash = aeshashstr\n        \/\/ Initialize with random data so hash collisions will be hard to engineer.\n        getRandomData(aeskeysched[:])\n        return\n    }\n    getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&amp;hashkey))[:])\n    hashkey[0] |= 1 \/\/ make sure these numbers are odd\n    hashkey[1] |= 1\n    hashkey[2] |= 1\n    hashkey[3] |= 1\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u8fd9\u4e2a\u521d\u59cb\u5316\u7684\u51fd\u6570\u4e2d\uff0c\u521d\u59cb\u5316\u4e862\u4e2a\u6570\u7ec4\uff0c\u6570\u7ec4\u91cc\u9762\u88c5\u7684\u90fd\u662f\u968f\u673a\u7684 hashkey\u3002\u5728 386\u3001 amd64\u3001\u975e nacl \u7684\u5e73\u53f0\u4e0a\uff0c\u4f1a\u7528 aeshash \u3002\u8fd9\u91cc\u4f1a\u628a\u968f\u673a\u7684 key \u751f\u6210\u597d\uff0c\u5b58\u5165\u5230 aeskeysched \u6570\u7ec4\u4e2d\u3002\u540c\u7406\uff0chashkey \u6570\u7ec4\u91cc\u9762\u4e5f\u4f1a\u968f\u673a\u597d4\u4e2a\u6570\u5b57\u3002\u6700\u540e\u90fd\u6309\u4f4d\u4e0e\u4e86\u4e00\u4e2a1\uff0c\u5c31\u662f\u4e3a\u4e86\u4fdd\u8bc1\u751f\u6210\u51fa\u6765\u7684\u968f\u673a\u6570\u90fd\u662f\u5947\u6570\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u6765\u770b\u770b memhash \u7a76\u7adf\u662f\u5982\u4f55\u8ba1\u7b97\u54c8\u5e0c\u503c\u7684\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func main() {\n    r := [8]byte{'h', 'a', 'l', 'f', 'r', 'o', 's', 't'}\n    pp := memhashpp(unsafe.Pointer(&amp;r), 3, 7)\n    fmt.Println(pp)\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3a\u4e86\u7b80\u5355\u8d77\u89c1\uff0c\u8fd9\u91cc\u7528\u7b14\u8005\u7684\u540d\u5b57\u4e3a\u4f8b\u7b97\u51fa\u54c8\u5e0c\u503c\uff0c\u79cd\u5b50\u7b80\u5355\u4e00\u70b9\u8bbe\u7f6e\u62103\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7b2c\u4e00\u6b65\u8ba1\u7b97 h \u7684\u503c\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>h\u00a0:=\u00a0uint32(seed\u00a0+\u00a0s*hashkey[0])<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u91cc\u5047\u8bbe hashkey[0] = 1\uff0c\u90a3\u4e48 h \u7684\u503c\u4e3a 3 + 7 * 1 = 10 \u3002\u7531\u4e8e s &lt; 8\uff0c\u90a3\u4e48\u5c31\u4f1a\u8fdb\u884c\u4ee5\u4e0b\u7684\u5904\u7406\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>case s &lt;= 8:\n    h ^= readUnaligned32(p)\n    h = rotl_15(h*m1) * m2\n    h ^= readUnaligned32(add(p, s-4))\n    h = rotl_15(h*m1) * m2<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/8.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">readUnaligned32()\u51fd\u6570\u4f1a\u628a\u4f20\u5165\u7684 unsafe.Pointer \u6307\u9488\u8fdb\u884c2\u6b21\u8f6c\u6362\uff0c\u5148\u8f6c\u6210 *uint32 \u7c7b\u578b\uff0c\u7136\u540e\u518d\u8f6c\u6210 *(*uint32) \u7c7b\u578b\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u7740\u8fdb\u884c\u5f02\u6216\u64cd\u4f5c\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/9.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u7740\u7b2c\u4e8c\u6b65 h * m1 = 1718378850 * 3168982561 = 3185867170<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/10.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u7531\u4e8e\u662f32\u4f4d\u7684\u4e58\u6cd5\uff0c\u6700\u7ec8\u7ed3\u679c\u662f64\u4f4d\u7684\uff0c\u9ad832\u4f4d\u6ea2\u51fa\uff0c\u76f4\u63a5\u820d\u5f03\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e58\u51fa\u6765\u7684\u7ed3\u679c\u5f53\u505a rotl_15() \u5165\u53c2\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func rotl_15(x uint32) uint32 {\n    return (x &lt;&lt; 15) | (x &gt;&gt; (32 - 15))\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u4e2a\u51fd\u6570\u91cc\u9762\u5bf9\u5165\u53c2\u8fdb\u884c\u4e86\u4e24\u6b21\u4f4d\u79fb\u64cd\u4f5c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/11.png\" alt=\"\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/12.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u540e\u5c06\u4e24\u6b21\u4f4d\u79fb\u7684\u7ed3\u679c\u8fdb\u884c\u903b\u8f91\u6216\u8fd0\u7b97\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/13.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u7740\u518d\u8fdb\u884c\u4e00\u6b21 readUnaligned32() \u8f6c\u6362\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/14.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u8f6c\u6362\u5b8c\u518d\u8fdb\u884c\u4e00\u6b21\u5f02\u6216\u3002\u6b64\u65f6 h = 2615762644\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7136\u540e\u8fd8\u8981\u518d\u8fdb\u884c\u4e00\u6b21 rotl_15() \u53d8\u6362\u3002\u8fd9\u91cc\u5c31\u4e0d\u753b\u56fe\u6f14\u793a\u4e86\u3002\u53d8\u6362\u5b8c\u6210\u4ee5\u540e h = 2932930721\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u540e\u6267\u884c hash \u7684\u6700\u540e\u4e00\u6b65\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>h ^= h &gt;&gt; 17\nh *= m3\nh ^= h &gt;&gt; 13\nh *= m4\nh ^= h &gt;&gt; 16<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5148\u53f3\u79fb17\u4f4d\uff0c\u7136\u540e\u5f02\u6216\uff0c\u518d\u4e58\u4ee5m3\uff0c\u518d\u53f3\u79fb13\u4f4d\uff0c\u518d\u5f02\u6216\uff0c\u518d\u4e58\u4ee5m4\uff0c\u518d\u53f3\u79fb16\u4f4d\uff0c\u6700\u540e\u518d\u5f02\u6216\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u901a\u8fc7\u8fd9\u6837\u4e00\u7cfb\u5217\u7684\u64cd\u4f5c\uff0c\u6700\u540e\u5c31\u80fd\u751f\u6210\u51fa hash \u503c\u4e86\u3002\u6700\u540e h = 1870717864\u3002\u611f\u5174\u8da3\u7684\u540c\u5b66\u53ef\u4ee5\u7b97\u4e00\u7b97\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">AES Hash<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u4e0a\u9762\u5206\u6790 Go \u7684 hash \u7b97\u6cd5\u7684\u65f6\u5019\uff0c\u6211\u4eec\u53ef\u4ee5\u770b\u5230\u5b83\u5bf9 CPU \u662f\u5426\u652f\u6301 AES \u6307\u4ee4\u96c6\u8fdb\u884c\u4e86\u5224\u65ad\uff0c\u5f53 CPU \u652f\u6301 AES \u6307\u4ee4\u96c6\u7684\u65f6\u5019\uff0c\u5b83\u4f1a\u9009\u7528 AES Hash \u7b97\u6cd5\uff0c\u5f53 CPU \u4e0d\u652f\u6301 AES \u6307\u4ee4\u96c6\u7684\u65f6\u5019\uff0c\u6362\u6210 memhash \u7b97\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">AES \u6307\u4ee4\u96c6\u5168\u79f0\u662f<strong>\u300c\u9ad8\u7ea7\u52a0\u5bc6\u6807\u51c6\u6307\u4ee4\u96c6\u300d<\/strong>\uff08\u6216\u79f0\u82f1\u7279\u5c14<strong>\u300c\u9ad8\u7ea7\u52a0\u5bc6\u6807\u51c6\u65b0\u6307\u4ee4\u300d<\/strong>\uff0c\u7b80\u79f0<strong>\u300cAES-NI\u300d<\/strong>\uff09\u662f\u4e00\u4e2a x86<code>https:\/\/zh.wikipedia.org\/wiki\/X86<\/code>\u6307\u4ee4\u96c6\u67b6\u69cb<code>https:\/\/zh.wikipedia.org\/wiki\/\u6307\u4ee4\u96c6\u67b6\u69cb<\/code> \u7684\u6269\u5c55\uff0c\u7528\u4e8e Intel<code>https:\/\/zh.wikipedia.org\/wiki\/\u82f1\u7279\u5c14<\/code>\u548c AMD<code>https:\/\/zh.wikipedia.org\/wiki\/\u8d85\u5a01\u534a\u5bfc\u4f53<\/code>\u5fae\u5904\u7406\u5668<code>https:\/\/zh.wikipedia.org\/wiki\/\u5fae\u5904\u7406\u5668<\/code>\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5229\u7528 AES \u5b9e\u73b0 Hash \u7b97\u6cd5\u6027\u80fd\u4f1a\u5f88\u4f18\u79c0\uff0c\u56e0\u4e3a\u5b83\u80fd\u63d0\u4f9b\u786c\u4ef6\u52a0\u901f\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5177\u4f53\u4ee3\u7801\u5b9e\u73b0\u5982\u4e0b\uff0c\u6c47\u7f16\u7a0b\u5e8f\uff0c\u6ce8\u91ca\u89c1\u4e0b\u9762\u7a0b\u5e8f\u4e2d\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ aes hash \u7b97\u6cd5\u901a\u8fc7 AES \u786c\u4ef6\u6307\u4ee4\u96c6\u5b9e\u73b0\nTEXT runtime\u00b7aeshash(SB),NOSPLIT,$0-32\n    MOVQ    p+0(FP), AX \/\/ \u628aptr\u79fb\u52a8\u5230data\u6570\u636e\u6bb5\u4e2d\n    MOVQ    s+16(FP), CX    \/\/ \u957f\u5ea6\n    LEAQ    ret+24(FP), DX\n    JMP runtime\u00b7aeshashbody(SB)\n\nTEXT runtime\u00b7aeshashstr(SB),NOSPLIT,$0-24\n    MOVQ    p+0(FP), AX \/\/ \u628aptr\u79fb\u52a8\u5230\u5b57\u7b26\u4e32\u7684\u7ed3\u6784\u4f53\u4e2d\n    MOVQ    8(AX), CX   \/\/ \u5b57\u7b26\u4e32\u957f\u5ea6\n    MOVQ    (AX), AX    \/\/ \u5b57\u7b26\u4e32\u7684\u6570\u636e\n    LEAQ    ret+16(FP), DX\n    JMP runtime\u00b7aeshashbody(SB)<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u7ec8\u7684 hash \u7684\u5b9e\u73b0\u90fd\u5728 aeshashbody \u4e2d\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/ AX: \u6570\u636e\n\/\/ CX: \u957f\u5ea6\n\/\/ DX: \u8fd4\u56de\u7684\u5730\u5740\nTEXT runtime\u00b7aeshashbody(SB),NOSPLIT,$0-0\n    \/\/ SSE \u5bc4\u5b58\u5668\u4e2d\u88c5\u586b\u5165\u6211\u4eec\u7684\u968f\u673a\u6570\u79cd\u5b50\n    MOVQ    h+8(FP), X0         \/\/ \u6bcf\u4e2atable\u4e2dhash\u79cd\u5b50\u670964 \u4f4d\n    PINSRW  $4, CX, X0          \/\/ \u957f\u5ea6\u536016\u4f4d\n    PSHUFHW $0, X0, X0          \/\/ \u538b\u7f29\u9ad8\u4f4d\u5b57\u4e71\u5e8f\uff0c\u91cd\u590d\u957f\u5ea64\u6b21\n    MOVO    X0, X1              \/\/ \u4fdd\u5b58\u52a0\u5bc6\u524d\u7684\u79cd\u5b50\n    PXOR    runtime\u00b7aeskeysched(SB), X0 \/\/ \u5bf9\u6bcf\u4e00\u4e2a\u5904\u7406\u4e2d\u7684\u79cd\u5b50\u8fdb\u884c\u903b\u8f91\u5f02\u6216\n    AESENC  X0, X0              \/\/ \u52a0\u5bc6\u79cd\u5b50\n\n    CMPQ    CX, $16\n    JB  aes0to15\n    JE  aes16\n    CMPQ    CX, $32\n    JBE aes17to32\n    CMPQ    CX, $64\n    JBE aes33to64\n    CMPQ    CX, $128\n    JBE aes65to128\n    JMP aes129plus\n\n\/\/ aes \u4ece 0 - 15\naes0to15:\n    TESTQ   CX, CX\n    JE  aes0\n\n    ADDQ    $16, AX\n    TESTW   $0xff0, AX\n    JE  endofpage\n\n    \/\/\u5f53\u524d\u52a0\u8f7d\u768416\u4f4d\u5b57\u8282\u7684\u5730\u5740\u4e0d\u4f1a\u8d8a\u8fc7\u4e00\u4e2a\u9875\u9762\u8fb9\u754c\uff0c\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u76f4\u63a5\u52a0\u8f7d\u5b83\u3002\n    MOVOU   -16(AX), X1\n    ADDQ    CX, CX\n    MOVQ    $masks&lt;&gt;(SB), AX\n    PAND    (AX)(CX*8), X1\nfinal1:\n    PXOR    X0, X1  \/\/ \u5f02\u6216\u6570\u636e\u548c\u79cd\u5b50\n    AESENC  X1, X1  \/\/ \u8fde\u7eed\u52a0\u5bc63\u6b21\n    AESENC  X1, X1\n    AESENC  X1, X1\n    MOVQ    X1, (DX)\n    RET\n\nendofpage:\n    \/\/ \u5730\u5740\u7ed3\u5c3e\u662f1111xxxx\u3002 \u8fd9\u6837\u5c31\u53ef\u80fd\u8d85\u8fc7\u4e00\u4e2a\u9875\u9762\u8fb9\u754c\uff0c\u6240\u4ee5\u5728\u52a0\u8f7d\u5b8c\u6700\u540e\u4e00\u4e2a\u5b57\u8282\u540e\u505c\u6b62\u52a0\u8f7d\u3002\u7136\u540e\u4f7f\u7528pshufb\u5c06\u5b57\u8282\u5411\u4e0b\u79fb\u52a8\u3002\n    MOVOU   -32(AX)(CX*1), X1\n    ADDQ    CX, CX\n    MOVQ    $shifts&lt;&gt;(SB), AX\n    PSHUFB  (AX)(CX*8), X1\n    JMP final1\n\naes0:\n    \/\/ \u8fd4\u56de\u8f93\u5165\u7684\u5e76\u4e14\u5df2\u7ecf\u52a0\u5bc6\u8fc7\u7684\u79cd\u5b50\n    AESENC  X0, X0\n    MOVQ    X0, (DX)\n    RET\n\naes16:\n    MOVOU   (AX), X1\n    JMP final1\n\naes17to32:\n    \/\/ \u5f00\u59cb\u5904\u7406\u7b2c\u4e8c\u4e2a\u8d77\u59cb\u79cd\u5b50\n    PXOR    runtime\u00b7aeskeysched+16(SB), X1\n    AESENC  X1, X1\n    \n    \/\/ \u52a0\u8f7d\u8981\u88ab\u54c8\u5e0c\u7b97\u6cd5\u5904\u7406\u7684\u6570\u636e\n    MOVOU   (AX), X2\n    MOVOU   -16(AX)(CX*1), X3\n\n    \/\/ \u5f02\u6216\u79cd\u5b50\n    PXOR    X0, X2\n    PXOR    X1, X3\n\n    \/\/ \u8fde\u7eed\u52a0\u5bc63\u6b21\n    AESENC  X2, X2\n    AESENC  X3, X3\n    AESENC  X2, X2\n    AESENC  X3, X3\n    AESENC  X2, X2\n    AESENC  X3, X3\n\n    \/\/ \u62fc\u63a5\u5e76\u751f\u6210\u7ed3\u679c\n    PXOR    X3, X2\n    MOVQ    X2, (DX)\n    RET\n\naes33to64:\n    \/\/ \u5904\u7406\u7b2c\u4e09\u4e2a\u4ee5\u4e0a\u7684\u8d77\u59cb\u79cd\u5b50\n    MOVO    X1, X2\n    MOVO    X1, X3\n    PXOR    runtime\u00b7aeskeysched+16(SB), X1\n    PXOR    runtime\u00b7aeskeysched+32(SB), X2\n    PXOR    runtime\u00b7aeskeysched+48(SB), X3\n    AESENC  X1, X1\n    AESENC  X2, X2\n    AESENC  X3, X3\n    \n    MOVOU   (AX), X4\n    MOVOU   16(AX), X5\n    MOVOU   -32(AX)(CX*1), X6\n    MOVOU   -16(AX)(CX*1), X7\n\n    PXOR    X0, X4\n    PXOR    X1, X5\n    PXOR    X2, X6\n    PXOR    X3, X7\n    \n    AESENC  X4, X4\n    AESENC  X5, X5\n    AESENC  X6, X6\n    AESENC  X7, X7\n    \n    AESENC  X4, X4\n    AESENC  X5, X5\n    AESENC  X6, X6\n    AESENC  X7, X7\n    \n    AESENC  X4, X4\n    AESENC  X5, X5\n    AESENC  X6, X6\n    AESENC  X7, X7\n\n    PXOR    X6, X4\n    PXOR    X7, X5\n    PXOR    X5, X4\n    MOVQ    X4, (DX)\n    RET\n\naes65to128:\n    \/\/ \u5904\u7406\u7b2c\u4e03\u4e2a\u4ee5\u4e0a\u7684\u8d77\u59cb\u79cd\u5b50\n    MOVO    X1, X2\n    MOVO    X1, X3\n    MOVO    X1, X4\n    MOVO    X1, X5\n    MOVO    X1, X6\n    MOVO    X1, X7\n    PXOR    runtime\u00b7aeskeysched+16(SB), X1\n    PXOR    runtime\u00b7aeskeysched+32(SB), X2\n    PXOR    runtime\u00b7aeskeysched+48(SB), X3\n    PXOR    runtime\u00b7aeskeysched+64(SB), X4\n    PXOR    runtime\u00b7aeskeysched+80(SB), X5\n    PXOR    runtime\u00b7aeskeysched+96(SB), X6\n    PXOR    runtime\u00b7aeskeysched+112(SB), X7\n    AESENC  X1, X1\n    AESENC  X2, X2\n    AESENC  X3, X3\n    AESENC  X4, X4\n    AESENC  X5, X5\n    AESENC  X6, X6\n    AESENC  X7, X7\n\n    \/\/ \u52a0\u8f7d\u6570\u636e\n    MOVOU   (AX), X8\n    MOVOU   16(AX), X9\n    MOVOU   32(AX), X10\n    MOVOU   48(AX), X11\n    MOVOU   -64(AX)(CX*1), X12\n    MOVOU   -48(AX)(CX*1), X13\n    MOVOU   -32(AX)(CX*1), X14\n    MOVOU   -16(AX)(CX*1), X15\n\n    \/\/ \u5f02\u6216\u79cd\u5b50\n    PXOR    X0, X8\n    PXOR    X1, X9\n    PXOR    X2, X10\n    PXOR    X3, X11\n    PXOR    X4, X12\n    PXOR    X5, X13\n    PXOR    X6, X14\n    PXOR    X7, X15\n\n    \/\/ \u8fde\u7eed\u52a0\u5bc63\u6b21\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n\n    \/\/ \u62fc\u88c5\u7ed3\u679c\n    PXOR    X12, X8\n    PXOR    X13, X9\n    PXOR    X14, X10\n    PXOR    X15, X11\n    PXOR    X10, X8\n    PXOR    X11, X9\n    PXOR    X9, X8\n    MOVQ    X8, (DX)\n    RET\n\naes129plus:\n    \/\/ \u5904\u7406\u7b2c\u4e03\u4e2a\u4ee5\u4e0a\u7684\u8d77\u59cb\u79cd\u5b50\n    MOVO    X1, X2\n    MOVO    X1, X3\n    MOVO    X1, X4\n    MOVO    X1, X5\n    MOVO    X1, X6\n    MOVO    X1, X7\n    PXOR    runtime\u00b7aeskeysched+16(SB), X1\n    PXOR    runtime\u00b7aeskeysched+32(SB), X2\n    PXOR    runtime\u00b7aeskeysched+48(SB), X3\n    PXOR    runtime\u00b7aeskeysched+64(SB), X4\n    PXOR    runtime\u00b7aeskeysched+80(SB), X5\n    PXOR    runtime\u00b7aeskeysched+96(SB), X6\n    PXOR    runtime\u00b7aeskeysched+112(SB), X7\n    AESENC  X1, X1\n    AESENC  X2, X2\n    AESENC  X3, X3\n    AESENC  X4, X4\n    AESENC  X5, X5\n    AESENC  X6, X6\n    AESENC  X7, X7\n    \n    \/\/ \u9006\u5e8f\u5f00\u59cb\uff0c\u4ece\u6700\u540e\u7684block\u5f00\u59cb\u5904\u7406\uff0c\u56e0\u4e3a\u53ef\u80fd\u4f1a\u51fa\u73b0\u91cd\u53e0\u7684\u60c5\u51b5\n    MOVOU   -128(AX)(CX*1), X8\n    MOVOU   -112(AX)(CX*1), X9\n    MOVOU   -96(AX)(CX*1), X10\n    MOVOU   -80(AX)(CX*1), X11\n    MOVOU   -64(AX)(CX*1), X12\n    MOVOU   -48(AX)(CX*1), X13\n    MOVOU   -32(AX)(CX*1), X14\n    MOVOU   -16(AX)(CX*1), X15\n\n    \/\/ \u5f02\u6216\u79cd\u5b50\n    PXOR    X0, X8\n    PXOR    X1, X9\n    PXOR    X2, X10\n    PXOR    X3, X11\n    PXOR    X4, X12\n    PXOR    X5, X13\n    PXOR    X6, X14\n    PXOR    X7, X15\n    \n    \/\/ \u8ba1\u7b97\u5269\u4f59128\u5b57\u8282\u5757\u7684\u6570\u91cf\n    DECQ    CX\n    SHRQ    $7, CX\n    \naesloop:\n    \/\/ \u52a0\u5bc6\u72b6\u6001\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n\n    \/\/ \u5728\u540c\u4e00\u4e2ablock\u5757\u4e2d\u52a0\u5bc6\u72b6\u6001\uff0c\u8fdb\u884c\u5f02\u6216\u8fd0\u7b97\n    MOVOU   (AX), X0\n    MOVOU   16(AX), X1\n    MOVOU   32(AX), X2\n    MOVOU   48(AX), X3\n    AESENC  X0, X8\n    AESENC  X1, X9\n    AESENC  X2, X10\n    AESENC  X3, X11\n    MOVOU   64(AX), X4\n    MOVOU   80(AX), X5\n    MOVOU   96(AX), X6\n    MOVOU   112(AX), X7\n    AESENC  X4, X12\n    AESENC  X5, X13\n    AESENC  X6, X14\n    AESENC  X7, X15\n\n    ADDQ    $128, AX\n    DECQ    CX\n    JNE aesloop\n\n    \/\/ \u6700\u540e\u4e00\u6b65\uff0c\u8fdb\u884c3\u6b21\u4ee5\u4e0a\u7684\u52a0\u5bc6\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n    AESENC  X8, X8\n    AESENC  X9, X9\n    AESENC  X10, X10\n    AESENC  X11, X11\n    AESENC  X12, X12\n    AESENC  X13, X13\n    AESENC  X14, X14\n    AESENC  X15, X15\n\n    PXOR    X12, X8\n    PXOR    X13, X9\n    PXOR    X14, X10\n    PXOR    X15, X11\n    PXOR    X10, X8\n    PXOR    X11, X9\n    PXOR    X9, X8\n    MOVQ    X8, (DX)\n    RET<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u54c8\u5e0c\u51b2\u7a81\u5904\u7406<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u94fe\u8868\u6570\u7ec4\u6cd5<\/h3>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/15.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u94fe\u8868\u6570\u7ec4\u6cd5\u6bd4\u8f83\u7b80\u5355\uff0c\u6bcf\u4e2a\u952e\u503c\u5bf9\u8868\u957f\u53d6\u6a21\uff0c\u5982\u679c\u7ed3\u679c\u76f8\u540c\uff0c\u7528\u94fe\u8868\u7684\u65b9\u5f0f\u4f9d\u6b21\u5f80\u540e\u63d2\u5165\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5047\u8bbe\u5f85\u63d2\u5165\u7684\u952e\u503c\u96c6\u5408\u662f{ 2\uff0c3\uff0c5\uff0c7\uff0c11\uff0c13\uff0c19}\uff0c\u8868\u957f MOD 8\u3002\u5047\u8bbe\u54c8\u5e0c\u51fd\u6570\u5728[0,9)\u4e0a\u5747\u5300\u5206\u5e03\u3002\u5982\u4e0a\u56fe\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765\u91cd\u70b9\u8fdb\u884c\u6027\u80fd\u5206\u6790\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u67e5\u627e\u952e\u503c k\uff0c\u5047\u8bbe\u952e\u503c k \u4e0d\u5728\u54c8\u5e0c\u8868\u4e2d\uff0ch(k) \u5728 [0\uff0cM) \u4e2d\u5747\u5300\u5206\u5e03\uff0c\u5373 P(h(k) = i) = 1\/M \u3002\u4ee4 Xi \u4e3a\u54c8\u5e0c\u8868 ht[ i ] \u4e2d\u5305\u542b\u952e\u503c\u7684\u4e2a\u6570\u3002\u5982\u679c h(k) = i \uff0c\u5219\u4e0d\u6210\u529f\u67e5\u627e k \u7684\u952e\u503c\u6bd4\u8f83\u6b21\u6570\u662f Xi\uff0c\u4e8e\u662f\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/16.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6210\u529f\u67e5\u627e\u7684\u5206\u6790\u7a0d\u5fae\u590d\u6742\u4e00\u70b9\u3002\u8981\u8003\u8651\u6dfb\u52a0\u54c8\u5e0c\u8868\u7684\u6b21\u5e8f\uff0c\u4e0d\u8003\u8651\u6709\u76f8\u540c\u952e\u503c\u7684\u60c5\u51b5\uff0c\u5047\u8bbe K = {k1,k2,\u2026\u2026kn}\uff0c\u5e76\u4e14\u5047\u8bbe\u4ece\u7a7a\u54c8\u5e0c\u8868\u5f00\u59cb\u6309\u7167\u8fd9\u4e2a\u6b21\u5e8f\u6dfb\u52a0\u5230\u54c8\u5e0c\u8868\u4e2d\u3002\u5f15\u5165\u968f\u673a\u53d8\u91cf\uff0c\u5982\u679c h(ki) = h(kj)\uff0c\u90a3\u4e48 Xij = 1\uff1b\u5982\u679c h(ki) \uff01= h(kj)\uff0c\u90a3\u4e48 Xij = 0 \u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7531\u4e8e\u4e4b\u524d\u7684\u5047\u8bbe\u54c8\u5e0c\u8868\u662f\u5747\u5300\u5206\u5e03\u7684\uff0c\u6240\u4ee5 P(Xij = i) = E(Xij) = 1\/M \uff0c\u8fd9\u91cc\u7684 E(X) \u8868\u793a\u968f\u673a\u53d8\u91cf X \u7684\u6570\u5b66\u671f\u671b\u3002\u518d\u5047\u8bbe\u6bcf\u6b21\u6dfb\u52a0\u952e\u503c\u7684\u65f6\u5019\u90fd\u662f\u628a\u6dfb\u52a0\u5728\u94fe\u8868\u672b\u7aef\u3002\u4ee4 Ci \u4e3a\u67e5\u627e Ki \u6240\u9700\u7684\u952e\u503c\u6bd4\u8f83\u6b21\u6570\uff0c\u7531\u4e8e\u4e0d\u80fd\u4e8b\u5148\u786e\u5b9a\u67e5\u627e Ki \u7684\u6982\u7387\uff0c\u6240\u4ee5\u5047\u5b9a\u67e5\u627e\u4e0d\u540c\u952e\u503c\u7684\u6982\u7387\u90fd\u662f\u76f8\u540c\u7684\uff0c\u90fd\u662f 1\/n \uff0c\u5219\u6709\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/17.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u7531\u6b64\u6211\u4eec\u53ef\u4ee5\u770b\u51fa\uff0c\u54c8\u5e0c\u8868\u7684\u6027\u80fd\u548c\u8868\u4e2d\u5143\u7d20\u7684\u591a\u5c11\u5173\u7cfb\u4e0d\u5927\uff0c\u800c\u548c\u586b\u5145\u56e0\u5b50 \u03b1 \u6709\u5173\u3002<strong>\u300c\u5982\u679c\u54c8\u5e0c\u8868\u957f\u548c\u54c8\u5e0c\u8868\u4e2d\u5143\u7d20\u4e2a\u6570\u6210\u6b63\u6bd4\uff0c\u5219\u54c8\u5e0c\u8868\u67e5\u627e\u7684\u590d\u6742\u5ea6\u4e3a O(1) \u3002\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7efc\u4e0a\u6240\u8ff0\uff0c\u94fe\u8868\u6570\u7ec4\u7684\u6210\u529f\u4e0e\u4e0d\u6210\u529f\u7684\u5e73\u5747\u952e\u503c\u6bd4\u8f83\u6b21\u6570\u5982\u4e0b\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/18.png\" alt=\"\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">\u5f00\u653e\u5730\u5740\u6cd5 \u2014\u2014 \u7ebf\u6027\u63a2\u6d4b<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ebf\u6027\u63a2\u6d4b\u7684\u89c4\u5219\u662f hi = ( h(k) + i ) MOD M\u3002\u4e3e\u4e2a\u4f8b\u5b50\uff0ci = 1\uff0cM = 9\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u79cd\u5904\u7406\u51b2\u7a81\u7684\u65b9\u6cd5\uff0c\u4e00\u65e6\u53d1\u751f\u51b2\u7a81\uff0c\u5c31\u628a\u4f4d\u7f6e\u5f80\u540e\u52a01\uff0c\u76f4\u5230\u627e\u5230\u4e00\u4e2a\u7a7a\u7684\u4f4d\u7f6e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3e\u4f8b\u5982\u4e0b\uff0c\u5047\u8bbe\u5f85\u63d2\u5165\u7684\u952e\u503c\u96c6\u5408\u662f{2\uff0c3\uff0c5\uff0c7\uff0c11\uff0c13\uff0c19}\uff0c\u7ebf\u6027\u63a2\u6d4b\u7684\u53d1\u751f\u51b2\u7a81\u4ee5\u540e\u6dfb\u52a0\u7684\u503c\u4e3a1\uff0c\u90a3\u4e48\u6700\u7ec8\u7ed3\u679c\u5982\u4e0b\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/19.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ebf\u6027\u63a2\u6d4b\u54c8\u5e0c\u8868\u7684\u6027\u80fd\u5206\u6790\u6bd4\u8f83\u590d\u6742\uff0c\u8fd9\u91cc\u5c31\u4ec5\u7ed9\u51fa\u7ed3\u679c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/20.png\" alt=\"\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">\u5f00\u653e\u5730\u5740\u6cd5 \u2014\u2014 \u5e73\u65b9\u63a2\u6d4b<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ebf\u6027\u63a2\u6d4b\u7684\u89c4\u5219\u662f h0 = h(k) \uff0chi = ( h0 + i * i ) MOD M\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3e\u4f8b\u5982\u4e0b\uff0c\u5047\u8bbe\u5f85\u63d2\u5165\u7684\u952e\u503c\u96c6\u5408\u662f{2\uff0c3\uff0c5\uff0c7\uff0c11\uff0c13\uff0c20}\uff0c\u5e73\u65b9\u63a2\u6d4b\u7684\u53d1\u751f\u51b2\u7a81\u4ee5\u540e\u6dfb\u52a0\u7684\u503c\u4e3a\u67e5\u627e\u6b21\u6570\u7684\u5e73\u65b9\uff0c\u90a3\u4e48\u6700\u7ec8\u7ed3\u679c\u5982\u4e0b\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/21.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5e73\u65b9\u63a2\u6d4b\u5728\u7ebf\u6027\u63a2\u6d4b\u7684\u57fa\u7840\u4e0a\uff0c\u52a0\u4e86\u4e00\u4e2a\u4e8c\u6b21\u66f2\u7ebf\u3002\u5f53\u53d1\u751f\u51b2\u7a81\u4ee5\u540e\uff0c\u4e0d\u518d\u662f\u52a0\u4e00\u4e2a\u7ebf\u6027\u7684\u53c2\u6570\uff0c\u800c\u662f\u52a0\u4e0a\u63a2\u6d4b\u6b21\u6570\u7684\u5e73\u65b9\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5e73\u65b9\u63a2\u6d4b\u6709\u4e00\u4e2a\u9700\u8981\u6ce8\u610f\u7684\u662f\uff0cM\u7684\u5927\u5c0f\u6709\u8bb2\u7a76\u3002\u5982\u679cM\u4e0d\u662f\u5947\u7d20\u6570\uff0c\u90a3\u4e48\u5c31\u53ef\u80fd\u51fa\u73b0\u4e0b\u9762\u8fd9\u6837\u7684\u95ee\u9898\uff0c\u5373\u4f7f\u54c8\u5e0c\u8868\u91cc\u9762\u8fd8\u6709\u7a7a\u7684\u4f4d\u7f6e\uff0c\u4f46\u662f\u5374\u6709\u5143\u7d20\u627e\u4e0d\u5230\u8981\u63d2\u5165\u7684\u4f4d\u7f6e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3e\u4f8b\uff0c\u5047\u8bbe M = 10\uff0c\u5f85\u63d2\u5165\u7684\u952e\u503c\u96c6\u5408\u662f{0\uff0c1\uff0c4\uff0c5\uff0c6\uff0c9\uff0c10}\uff0c\u5f53\u524d\u97626\u4e2a\u952e\u503c\u63d2\u5165\u54c8\u5e0c\u8868\u4e2d\u4ee5\u540e\uff0c10\u5c31\u518d\u4e5f\u65e0\u6cd5\u63d2\u5165\u4e86\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/22.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6240\u4ee5\u5728\u5e73\u65b9\u63a2\u6d4b\u4e2d\uff0c\u5b58\u5728\u4e0b\u9762\u8fd9\u5219\u89c4\u5f8b\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u5982\u679c M \u4e3a\u5947\u7d20\u6570\uff0c\u5219\u4e0b\u9762\u7684 \u2308M \/ 2\u2309 \u4f4d\u7f6e h0\uff0ch1\uff0ch2 \u2026\u2026 h\u230aM\/2\u230b \u4e92\u4e0d\u76f8\u540c\u3002\u5176\u4e2d\uff0chi = (h0 + i * i ) MOD M\u3002\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u9762\u8fd9\u5219\u89c4\u5f8b\u53ef\u4ee5\u7528\u53cd\u8bc1\u6cd5\u8bc1\u660e\u3002\u5047\u8bbe hi = hj\uff0ci &gt; j\uff1b0&lt;=i\uff0cj&lt;= \u230aM\/2\u230b\uff0c\u5219 h0 + i* i = ( h0 + j * j ) MOD M\uff0c\u4ece\u800c M \u53ef\u4ee5\u6574\u9664 ( i + j )( i &#8211; j )\u3002\u7531\u4e8e M \u4e3a\u7d20\u6570\uff0c\u5e76\u4e14 0 &lt; i + j\uff0ci &#8211; j &lt; M\uff0c\u5f53\u4e14\u4ec5\u5f53 i = j \u7684\u65f6\u5019\u624d\u80fd\u6ee1\u8db3\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u8ff0\u89c4\u5219\u4e5f\u5c31\u8bf4\u660e\u4e86\u4e00\u70b9\uff0c<strong>\u300c\u53ea\u8981 M \u4e3a\u5947\u7d20\u6570\uff0c\u5e73\u65b9\u63a2\u6d4b\u81f3\u5c11\u53ef\u4ee5\u904d\u5386\u54c8\u5e0c\u8868\u4e00\u822c\u7684\u4f4d\u7f6e\u3002\u6240\u4ee5\u53ea\u8981\u54c8\u5e0c\u8868\u7684\u586b\u5145\u56e0\u5b50 \u03b1 &lt;= 1 \/ 2 \uff0c\u5e73\u65b9\u63a2\u6d4b\u603b\u80fd\u627e\u5230\u53ef\u63d2\u5165\u7684\u4f4d\u7f6e\u3002\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u8ff0\u4e3e\u7684\u4f8b\u5b50\uff0c\u4e4b\u6240\u4ee5\u952e\u503c10\u65e0\u6cd5\u63d2\u5165\uff0c\u539f\u56e0\u4e5f\u56e0\u4e3a \u03b1 &gt; 1 \/ 2\u4e86\uff0c\u6240\u4ee5\u4e0d\u80fd\u4fdd\u8bc1\u6709\u53ef\u63d2\u5165\u7684\u4f4d\u7f6e\u4e86\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u5f00\u653e\u5730\u5740\u6cd5 \u2014\u2014 \u53cc\u54c8\u5e0c\u63a2\u6d4b<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u53cc\u54c8\u5e0c\u63a2\u6d4b\u662f\u4e3a\u4e86\u89e3\u51b3\u805a\u96c6\u7684\u73b0\u8c61\u3002\u65e0\u8bba\u662f\u7ebf\u6027\u63a2\u6d4b\u8fd8\u662f\u5e73\u65b9\u63a2\u6d4b\uff0c\u5982\u679c h(k1) \u548c h(k2) \u76f8\u90bb\uff0c\u5219\u5b83\u4eec\u7684\u63a2\u6d4b\u5e8f\u5217\u4e5f\u90fd\u662f\u76f8\u90bb\u7684\uff0c\u8fd9\u5c31\u662f\u6240\u8c13\u7684\u805a\u96c6\u73b0\u8c61\u3002\u4e3a\u4e86\u907f\u514d\u8fd9\u79cd\u73b0\u8c61\uff0c\u6240\u4ee5\u5f15\u5165\u4e86\u53cc\u54c8\u5e0c\u51fd\u6570 h2\uff0c\u4f7f\u5f97\u4e24\u6b21\u63a2\u6d4b\u4e4b\u95f4\u7684\u8ddd\u79bb\u4e3a h2(k)\u3002\u6240\u4ee5\u63a2\u6d4b\u5e8f\u5217\u4e3a h0 = h1(k)\uff0chi = ( h0 + i * h2(k) ) MOD M \u3002\u5b9e\u9a8c\u8868\u660e\uff0c\u53cc\u54c8\u5e0c\u63a2\u6d4b\u7684\u6027\u80fd\u7c7b\u4f3c\u4e8e\u968f\u673a\u63a2\u6d4b\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5173\u4e8e\u53cc\u54c8\u5e0c\u63a2\u6d4b\u548c\u5e73\u65b9\u63a2\u6d4b\u7684\u5e73\u5747\u67e5\u627e\u957f\u5ea6\u6bd4\u7ebf\u6027\u63a2\u6d4b\u66f4\u52a0\u56f0\u96be\u3002\u6240\u4ee5\u5f15\u5165\u968f\u673a\u63a2\u6d4b\u7684\u6982\u5ff5\u6765\u8fd1\u4f3c\u8fd9\u4e24\u79cd\u63a2\u6d4b\u3002\u968f\u673a\u63a2\u6d4b\u662f\u6307\u63a2\u6d4b\u5e8f\u5217 { hi } \u5728\u533a\u95f4 [0\uff0cM]\u4e2d\u7b49\u6982\u7387\u72ec\u7acb\u968f\u673a\u9009\u53d6\uff0c\u8fd9\u6837 P(hi = j) = 1\/M \u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5047\u8bbe\u63a2\u6d4b\u5e8f\u5217\u4e3a h0\uff0ch1\uff0c\u2026\u2026\uff0chi\u3002\u5728\u54c8\u5e0c\u8868\u7684 hi \u4f4d\u7f6e\u4e3a\u7a7a\uff0c\u5728 h0\uff0ch1\uff0c\u2026\u2026\uff0chi-1 \u7684\u4f4d\u7f6e\u4e0a\u54c8\u5e0c\u8868\u4e0d\u662f\u7a7a\uff0c\u6b64\u6b21\u67e5\u627e\u7684\u952e\u503c\u6bd4\u8f83\u6b21\u6570\u4e3a i\u3002\u4ee4\u968f\u673a\u53d8\u91cf X \u4e3a\u4e00\u6b21\u4e0d\u6210\u529f\u67e5\u627e\u6240\u9700\u7684\u952e\u503c\u6bd4\u8f83\u6b21\u6570\u3002\u7531\u4e8e\u54c8\u5e0c\u8868\u7684\u586b\u5145\u56e0\u5b50\u4e3a \u03b1\uff0c\u6240\u4ee5\u5728\u4e00\u4e2a\u4f4d\u7f6e\u4e0a\u54c8\u5e0c\u8868\u4e3a\u7a7a\u503c\u7684\u6982\u7387\u4e3a 1 &#8211; \u03b1 \uff0c\u4e3a\u975e\u7a7a\u503c\u7684\u6982\u7387\u4e3a \u03b1\uff0c\u6240\u4ee5 P( X = i ) = \u03b1^i * ( 1 &#8211; \u03b1 ) \u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/23.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u6982\u7387\u8bba\u4e2d\uff0c\u4e0a\u8ff0\u7684\u5206\u5e03\u53eb\u51e0\u4f55\u5206\u5e03\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5047\u5b9a\u54c8\u5e0c\u8868\u5143\u7d20\u7684\u6dfb\u52a0\u987a\u5e8f\u4e3a {k1\uff0ck2\uff0c\u2026\u2026 \uff0ckn}\uff0c\u4ee4 Xi \u4e3a\u5f53\u54c8\u5e0c\u8868\u53ea\u5305\u542b {k1\uff0ck2\uff0c\u2026\u2026 \uff0cki} \u65f6\u5019\u4e00\u6b21\u4e0d\u6210\u529f\u67e5\u627e\u7684\u952e\u503c\u6bd4\u8f83\u6b21\u6570\uff0c\u6ce8\u610f\uff0c\u8fd9\u4e2a\u65f6\u5019\u54c8\u5e0c\u8868\u7684\u586b\u5145\u56e0\u5b50\u4e3a i\/M \uff0c\u5219\u67e5\u627e k(i+1) \u7684\u952e\u503c\u6b21\u6570\u4e3a Yi = 1 + Xi\u3002\u5047\u5b9a\u67e5\u627e\u4efb\u610f\u4e00\u4e2a\u952e\u503c\u7684\u6982\u7387\u4e3a 1\/n\uff0c\u5219\u4e00\u6b21\u6210\u529f\u67e5\u627e\u7684\u5e73\u5747\u952e\u503c\u6bd4\u8f83\u6b21\u6570\u4e3a\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/24.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u7efc\u4e0a\u6240\u8ff0\uff0c\u5e73\u65b9\u63a2\u6d4b\u548c\u53cc\u54c8\u5e0c\u63a2\u6d4b\u7684\u6210\u529f\u4e0e\u4e0d\u6210\u529f\u7684\u5e73\u5747\u952e\u503c\u6bd4\u8f83\u6b21\u6570\u5982\u4e0b\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/25.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u603b\u7684\u6765\u8bf4\uff0c\u5728\u6570\u636e\u91cf\u975e\u5e38\u5927\u7684\u60c5\u51b5\u4e0b\uff0c\u7b80\u5355\u7684 hash \u51fd\u6570\u4e0d\u53ef\u907f\u514d\u4e0d\u4ea7\u751f\u78b0\u649e\uff0c\u5373\u4f7f\u91c7\u7528\u4e86\u5408\u9002\u7684\u5904\u7406\u78b0\u649e\u7684\u65b9\u6cd5\uff0c\u4f9d\u65e7\u6709\u4e00\u5b9a\u65f6\u95f4\u590d\u6742\u5ea6\u3002\u6240\u4ee5\u60f3\u5c3d\u53ef\u80fd\u7684\u907f\u514d\u78b0\u649e\uff0c\u8fd8\u662f\u8981\u9009\u62e9\u9ad8\u6027\u80fd\u7684 hash \u51fd\u6570\uff0c\u6216\u8005\u589e\u52a0 hash \u7684\u4f4d\u6570\uff0c\u6bd4\u598264\u4f4d\uff0c128\u4f4d\uff0c256\u4f4d\uff0c\u8fd9\u6837\u78b0\u649e\u7684\u51e0\u7387\u4f1a\u5c0f\u5f88\u591a\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u54c8\u5e0c\u8868\u7684\u6269\u5bb9\u7b56\u7565<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u968f\u7740\u54c8\u5e0c\u8868\u88c5\u8f7d\u56e0\u5b50\u7684\u53d8\u5927\uff0c\u53d1\u751f\u78b0\u649e\u7684\u6b21\u6570\u53d8\u5f97\u8d8a\u6765\u4e5f\u591a\uff0c\u54c8\u5e0c\u8868\u7684\u6027\u80fd\u53d8\u5f97\u8d8a\u6765\u8d8a\u5dee\u3002\u5bf9\u4e8e\u5355\u72ec\u94fe\u8868\u6cd5\u5b9e\u73b0\u7684\u54c8\u5e0c\u8868\uff0c\u5c1a\u53ef\u4ee5\u5bb9\u5fcd\uff0c\u4f46\u662f\u5bf9\u4e8e\u5f00\u653e\u5bfb\u5740\u6cd5\uff0c\u8fd9\u79cd\u6027\u80fd\u7684\u4e0b\u964d\u662f\u4e0d\u80fd\u63a5\u53d7\u7684\uff0c\u56e0\u6b64\u5bf9\u4e8e\u5f00\u653e\u5bfb\u5740\u6cd5\u9700\u8981\u5bfb\u627e\u4e00\u79cd\u65b9\u6cd5\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u5b9e\u9645\u5e94\u7528\u4e2d\uff0c\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u7684\u529e\u6cd5\u662f\u52a8\u6001\u7684\u589e\u5927\u54c8\u5e0c\u8868\u7684\u957f\u5ea6\uff0c\u5f53\u88c5\u8f7d\u56e0\u5b50\u8d85\u8fc7\u67d0\u4e2a\u9608\u503c\u65f6\u589e\u52a0\u54c8\u5e0c\u8868\u7684\u957f\u5ea6\uff0c\u81ea\u52a8\u6269\u5bb9\u3002\u6bcf\u5f53\u54c8\u5e0c\u8868\u7684\u957f\u5ea6\u53d1\u751f\u53d8\u5316\u4e4b\u540e\uff0c\u6240\u6709 key \u5728\u54c8\u5e0c\u8868\u4e2d\u5bf9\u5e94\u7684\u4e0b\u6807\u7d22\u5f15\u9700\u8981\u5168\u90e8\u91cd\u65b0\u8ba1\u7b97\uff0c\u4e0d\u80fd\u76f4\u63a5\u4ece\u539f\u6765\u7684\u54c8\u5e0c\u8868\u4e2d\u62f7\u8d1d\u5230\u65b0\u7684\u54c8\u5e0c\u8868\u4e2d\u3002\u5fc5\u987b\u4e00\u4e2a\u4e00\u4e2a\u8ba1\u7b97\u539f\u6765\u54c8\u5e0c\u8868\u4e2d\u7684 key \u7684\u54c8\u5e0c\u503c\u5e76\u63d2\u5165\u5230\u65b0\u7684\u54c8\u5e0c\u8868\u4e2d\u3002\u8fd9\u79cd\u65b9\u5f0f\u80af\u5b9a\u662f\u8fbe\u4e0d\u5230\u751f\u4ea7\u73af\u5883\u7684\u8981\u6c42\u7684\uff0c\u56e0\u4e3a\u65f6\u95f4\u590d\u6742\u5ea6\u592a\u9ad8\u4e86\uff0cO(n)\uff0c\u6570\u636e\u91cf\u4e00\u65e6\u5927\u4e86\uff0c\u6027\u80fd\u5c31\u4f1a\u5f88\u5dee\u3002Redis \u60f3\u4e86\u4e00\u79cd\u65b9\u6cd5\uff0c\u5c31\u7b97\u662f\u89e6\u53d1\u589e\u957f\u65f6\u4e5f\u53ea\u9700\u8981\u5e38\u6570\u65f6\u95f4 O(1) \u5373\u53ef\u5b8c\u6210\u63d2\u5165\u64cd\u4f5c\u3002\u89e3\u51b3\u529e\u6cd5\u662f\u5206\u591a\u6b21\u3001\u6e10\u8fdb\u5f0f\u5730\u5b8c\u6210\u7684\u65e7\u54c8\u5e0c\u8868\u5230\u65b0\u54c8\u5e0c\u8868\u7684\u62f7\u8d1d\u800c\u4e0d\u662f\u4e00\u6b21\u62f7\u8d1d\u5b8c\u6210\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765\u4ee5 Redis \u4e3a\u4f8b\uff0c\u6765\u8c08\u8c08\u5b83\u662f\u54c8\u5e0c\u8868\u662f\u5982\u4f55\u8fdb\u884c\u6269\u5bb9\u5e76\u4e14\u4e0d\u592a\u5f71\u54cd\u6027\u80fd\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Redis \u5bf9\u5b57\u5178\u7684\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/*\n * \u5b57\u5178\n *\n * \u6bcf\u4e2a\u5b57\u5178\u4f7f\u7528\u4e24\u4e2a\u54c8\u5e0c\u8868\uff0c\u7528\u4e8e\u5b9e\u73b0\u6e10\u8fdb\u5f0f rehash\n *\/\ntypedef struct dict {\n    \/\/ \u7279\u5b9a\u4e8e\u7c7b\u578b\u7684\u5904\u7406\u51fd\u6570\n    dictType *type;\n    \/\/ \u7c7b\u578b\u5904\u7406\u51fd\u6570\u7684\u79c1\u6709\u6570\u636e\n    void *privdata;\n    \/\/ \u54c8\u5e0c\u8868\uff082 \u4e2a\uff09\n    dictht ht[2];\n    \/\/ \u8bb0\u5f55 rehash \u8fdb\u5ea6\u7684\u6807\u5fd7\uff0c\u503c\u4e3a -1 \u8868\u793a rehash \u672a\u8fdb\u884c\n    int rehashidx;\n    \/\/ \u5f53\u524d\u6b63\u5728\u8fd0\u4f5c\u7684\u5b89\u5168\u8fed\u4ee3\u5668\u6570\u91cf\n    int iterators;\n} dict;<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ece\u5b9a\u4e49\u4e0a\u6211\u4eec\u53ef\u4ee5\u770b\u5230\uff0cRedis \u5b57\u5178\u4fdd\u5b58\u4e862\u4e2a\u54c8\u5e0c\u8868\uff0c\u54c8\u5e0c\u8868ht[1]\u5c31\u662f\u7528\u6765 rehash \u7684\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/26.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Redis \u4e2d\u5b9a\u4e49\u4e86\u5982\u4e0b\u7684\u54c8\u5e0c\u8868\u7684\u6570\u636e\u7ed3\u6784\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/*\n * \u54c8\u5e0c\u8868\n *\/\ntypedef struct dictht {\n    \/\/ \u54c8\u5e0c\u8868\u8282\u70b9\u6307\u9488\u6570\u7ec4\uff08\u4fd7\u79f0\u6876\uff0cbucket\uff09\n    dictEntry **table;\n    \/\/ \u6307\u9488\u6570\u7ec4\u7684\u5927\u5c0f\n    unsigned long size;\n    \/\/ \u6307\u9488\u6570\u7ec4\u7684\u957f\u5ea6\u63a9\u7801\uff0c\u7528\u4e8e\u8ba1\u7b97\u7d22\u5f15\u503c\n    unsigned long sizemask;\n    \/\/ \u54c8\u5e0c\u8868\u73b0\u6709\u7684\u8282\u70b9\u6570\u91cf\n    unsigned long used;\n\n} dictht;<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">table \u5c5e\u6027\u662f\u4e2a\u6570\u7ec4\uff0c \u6570\u7ec4\u7684\u6bcf\u4e2a\u5143\u7d20\u90fd\u662f\u4e2a\u6307\u5411 dictEntry \u7ed3\u6784\u7684\u6307\u9488\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/27.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6bcf\u4e2a dictEntry \u90fd\u4fdd\u5b58\u7740\u4e00\u4e2a\u952e\u503c\u5bf9\uff0c \u4ee5\u53ca\u4e00\u4e2a\u6307\u5411\u53e6\u4e00\u4e2a dictEntry \u7ed3\u6784\u7684\u6307\u9488\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/*\n * \u54c8\u5e0c\u8868\u8282\u70b9\n *\/\ntypedef struct dictEntry {\n    \/\/ \u952e\n    void *key;\n    \/\/ \u503c\n    union {\n        void *val;\n        uint64_t u64;\n        int64_t s64;\n    } v;\n    \/\/ \u94fe\u5f80\u540e\u7ee7\u8282\u70b9\n    struct dictEntry *next;\n\n} dictEntry;<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">next \u5c5e\u6027\u6307\u5411\u53e6\u4e00\u4e2a dictEntry \u7ed3\u6784\uff0c \u591a\u4e2a dictEntry \u53ef\u4ee5\u901a\u8fc7 next \u6307\u9488\u4e32\u8fde\u6210\u94fe\u8868\uff0c \u4ece\u8fd9\u91cc\u53ef\u4ee5\u770b\u51fa\uff0c dictht \u4f7f\u7528\u94fe\u5730\u5740\u6cd5\u6765\u5904\u7406\u952e\u78b0\u649e\u95ee\u9898\u7684\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/030996e0-d012-4919-83a6-68fb1426fca9.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">dictAdd \u5728\u6bcf\u6b21\u5411\u5b57\u5178\u6dfb\u52a0\u65b0\u952e\u503c\u5bf9\u4e4b\u524d\uff0c \u90fd\u4f1a\u5bf9\u54c8\u5e0c\u8868 ht[0] \u8fdb\u884c\u68c0\u67e5\uff0c \u5bf9\u4e8e ht[0] \u7684 size \u548c used \u5c5e\u6027\uff0c \u5982\u679c\u5b83\u4eec\u4e4b\u95f4\u7684\u6bd4\u7387 ratio = used \/ size \u6ee1\u8db3\u4ee5\u4e0b\u4efb\u4f55\u4e00\u4e2a\u6761\u4ef6\u7684\u8bdd\uff0crehash \u8fc7\u7a0b\u5c31\u4f1a\u88ab\u6fc0\u6d3b\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u81ea\u7136 rehash \uff1a ratio &gt;= 1 \uff0c\u4e14\u53d8\u91cf dict_can_resize \u4e3a\u771f\u3002<br>\n\u5f3a\u5236 rehash \uff1a ratio \u5927\u4e8e\u53d8\u91cf dict_force_resize_ratio \uff08\u76ee\u524d\u7248\u672c\u4e2d\uff0c dict_force_resize_ratio \u7684\u503c\u4e3a 5 \uff09\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/8cca7ff1-4363-4419-b815-cdf35d7b4ccd.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5047\u8bbe\u5f53\u524d\u7684\u5b57\u5178\u9700\u8981\u6269\u5bb9 rehash\uff0c\u90a3\u4e48 Redis \u4f1a\u5148\u8bbe\u7f6e\u5b57\u5178\u7684 rehashidx \u4e3a 0 \uff0c\u6807\u8bc6\u7740 rehash \u7684\u5f00\u59cb\uff1b\u518d\u4e3a ht[1]-&gt;table \u5206\u914d\u7a7a\u95f4\uff0c\u5927\u5c0f\u81f3\u5c11\u4e3a ht[0]-&gt;used \u7684\u4e24\u500d\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/30.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u4e0a\u56fe\uff0c ht[1]-&gt;table \u5df2\u7ecf\u5206\u914d\u7a7a\u95f4\u4e868\u4e2a\u7a7a\u95f4\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u7740\uff0c\u5f00\u59cb rehash \u3002\u5c06 ht[0]-&gt;table \u5185\u7684\u952e\u503c\u79fb\u52a8\u5230 ht[1]-&gt;table \u4e2d\uff0c\u952e\u503c\u7684\u79fb\u52a8\u4e0d\u662f\u4e00\u6b21\u5b8c\u6210\u7684\uff0c\u5206\u591a\u6b21\u8fdb\u884c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/31.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u56fe\u53ef\u4ee5\u770b\u51fa\u6765\uff0c ht[0] \u4e2d\u7684\u4e00\u90e8\u5206\u952e\u503c\u5df2\u7ecf\u8fc1\u79fb\u5230 ht[1] \u4e2d\u4e86\uff0c\u5e76\u4e14\u6b64\u65f6\u8fd8\u6709\u65b0\u7684\u952e\u503c\u63d2\u5165\u8fdb\u6765\uff0c\u662f\u76f4\u63a5\u63d2\u5165\u5230 ht[1] \u4e2d\u7684\uff0c\u4e0d\u4f1a\u518d\u63d2\u5165\u5230 ht[0] \u4e2d\u4e86\u3002\u4fdd\u8bc1\u4e86 ht[0] \u53ea\u51cf\u4e0d\u589e\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/32.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 rehash \u8fdb\u884c\u7684\u8fc7\u7a0b\u4e2d\uff0c\u4e0d\u65ad\u7684\u6709\u65b0\u7684\u952e\u503c\u63d2\u5165\u8fdb\u6765\uff0c\u4e5f\u4e0d\u65ad\u7684\u628a ht[0] \u4e2d\u7684\u952e\u503c\u90fd\u8fc1\u79fb\u8fc7\u6765\uff0c\u76f4\u5230 ht[0] \u4e2d\u7684\u952e\u503c\u90fd\u8fc1\u79fb\u8fc7\u6765\u4e3a\u6b62\u3002\u6ce8\u610f Redis \u7528\u7684\u662f\u5934\u63d2\u6cd5\uff0c\u65b0\u503c\u6c38\u8fdc\u90fd\u63d2\u5728\u94fe\u8868\u7684\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\uff0c\u8fd9\u6837\u4e5f\u4e0d\u7528\u904d\u5386\u5230\u94fe\u8868\u7684\u6700\u540e\uff0c\u7701\u53bb\u4e86 O(n) \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u3002\u8fdb\u884c\u5230\u4e0a\u56fe\u8fd9\u79cd\u60c5\u51b5\uff0c\u6240\u6709\u7684\u8282\u70b9\u4e5f\u5c31\u8fc1\u79fb\u5b8c\u6bd5\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">rehash \u5728\u7ed3\u675f\u4e4b\u524d\u4f1a\u8fdb\u884c\u6e05\u7406\u5de5\u4f5c\uff0c\u91ca\u653e ht[0] \u7684\u7a7a\u95f4\uff1b\u7528 ht[1] \u6765\u4ee3\u66ff ht[0] \uff0c\u4f7f\u539f\u6765\u7684 ht[1] \u6210\u4e3a\u65b0\u7684 ht[0] \uff1b\u521b\u5efa\u4e00\u4e2a\u65b0\u7684\u7a7a\u54c8\u5e0c\u8868\uff0c\u5e76\u5c06\u5b83\u8bbe\u7f6e\u4e3a ht[1] \uff1b\u5c06\u5b57\u5178\u7684 rehashidx \u5c5e\u6027\u8bbe\u7f6e\u4e3a -1 \uff0c\u6807\u8bc6 rehash \u5df2\u505c\u6b62\uff1b<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/33.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u7ec8 rehash \u7ed3\u675f\u4ee5\u540e\u60c5\u51b5\u5982\u4e0a\u56fe\u3002\u5982\u679c\u8fd8\u4e0b\u6b21\u8fd8\u9700\u8981 rehash \uff0c\u91cd\u590d\u4e0a\u8ff0\u8fc7\u7a0b\u5373\u53ef\u3002\u8fd9\u79cd\u5206\u591a\u6b21\uff0c\u6e10\u8fdb\u5f0f rehash \u7684\u65b9\u5f0f\u4e5f\u6210\u5c31\u4e86 Redis \u7684\u9ad8\u6027\u80fd\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u503c\u5f97\u4e00\u63d0\u7684\u662f\uff0cRedis \u662f\u652f\u6301\u5b57\u5178\u7684 reshrink \u64cd\u4f5c\u7684\u3002\u64cd\u4f5c\u6b65\u9aa4\u5c31\u662f<br>\nrehash \u7684\u9006\u8fc7\u7a0b\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7ea2\u9ed1\u6811\u4f18\u5316<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8bfb\u5230\u8fd9\u91cc\uff0c\u8bfb\u8005\u5e94\u8be5\u5df2\u7ecf\u660e\u767d\u4e86\u5230\u5e95\u7528\u4ec0\u4e48\u65b9\u5f0f\u6765\u63a7\u5236 map \u4f7f\u5f97<br>\nHash \u78b0\u649e\u7684\u6982\u7387\u53c8\u5c0f\uff0c\u54c8\u5e0c\u6876\u6570\u7ec4\u5360\u7528\u7a7a\u95f4\u53c8\u5c11\u4e86\u5427\uff0c\u7b54\u6848\u5c31\u662f\u9009\u62e9\u597d\u7684 Hash \u7b97\u6cd5\u548c\u589e\u52a0\u6269\u5bb9\u673a\u5236\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Java \u5728 JDK1.8 \u5bf9 HashMap \u5e95\u5c42\u7684\u5b9e\u73b0\u518d\u6b21\u8fdb\u884c\u4e86\u4f18\u5316\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/631d82ed-bc29-41f4-8958-2d59b14acec6.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u56fe\u662f\u6765\u81ea\u7f8e\u56e2\u535a\u5ba2\u603b\u7ed3\u7684\u3002\u4ece\u8fd9\u91cc\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Java \u5e95\u5c42\u521d\u59cb\u6876\u7684\u4e2a\u6570\u662f16\u4e2a\uff0c\u8d1f\u8f7d\u56e0\u5b50\u9ed8\u8ba4\u662f0.75\uff0c\u4e5f\u5c31\u662f\u8bf4\u5f53\u952e\u503c\u7b2c\u4e00\u6b21\u8fbe\u523012\u4e2a\u7684\u65f6\u5019\u5c31\u4f1a\u8fdb\u884c\u6269\u5bb9 resize\u3002\u6269\u5bb9\u7684\u4e34\u754c\u503c\u572864\uff0c\u5f53\u8d85\u8fc7\u4e8664\u4ee5\u540e\uff0c\u5e76\u4e14\u51b2\u7a81\u8282\u70b9\u4e3a8\u6216\u8005\u5927\u4e8e8\uff0c\u8fd9\u4e2a\u65f6\u5019\u5c31\u4f1a\u89e6\u53d1\u7ea2\u9ed1\u6811\u8f6c\u6362\u3002\u4e3a\u4e86\u9632\u6b62\u5e95\u5c42\u94fe\u8868\u8fc7\u957f\uff0c\u94fe\u8868\u5c31\u8f6c\u6362\u4e3a\u7ea2\u9ed1\u6811\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6362\u53e5\u8bdd\u8bf4\uff0c\u5f53\u6876\u7684\u603b\u4e2a\u6570\u6ca1\u6709\u523064\u4e2a\u7684\u65f6\u5019\uff0c\u5373\u4f7f\u94fe\u8868\u957f\u4e3a8\uff0c\u4e5f\u4e0d\u4f1a\u8fdb\u884c\u7ea2\u9ed1\u6811\u8f6c\u6362\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c\u8282\u70b9\u5c0f\u4e8e6\u4e2a\uff0c\u7ea2\u9ed1\u6811\u53c8\u4f1a\u91cd\u65b0\u9000\u5316\u6210\u94fe\u8868\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5f53\u7136\u8fd9\u91cc\u4e4b\u6240\u4ee5\u9009\u62e9\u7528\u7ea2\u9ed1\u6811\u6765\u8fdb\u884c\u4f18\u5316\uff0c\u4fdd\u8bc1\u6700\u574f\u60c5\u51b5\u4e0d\u4f1a\u9000\u5316\u6210<br>\nO(n)\uff0c\u7ea2\u9ed1\u6811\u80fd\u4fdd\u8bc1\u6700\u574f\u65f6\u95f4\u590d\u6742\u5ea6\u4e5f\u4e3a O(log n)\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u7f8e\u56e2\u535a\u5ba2\u4e2d\u4e5f\u63d0\u5230\u4e86\uff0cJava \u5728 JDK1.8 \u4e2d\u8fd8\u6709\u4e00\u4e2a\u503c\u5f97\u5b66\u4e60\u7684\u4f18\u5316\u3002Java \u5728 rehash \u7684\u952e\u503c\u8282\u70b9\u8fc1\u79fb\u8fc7\u7a0b\u4e2d\uff0c\u4e0d\u9700\u8981\u518d\u6b21\u8ba1\u7b97\u4e00\u6b21 hash \u8ba1\u7b97\uff01<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7531\u4e8e\u4f7f\u7528\u4e862\u6b21\u5e42\u7684\u6269\u5c55(\u6307\u957f\u5ea6\u6269\u4e3a\u539f\u67652\u500d)\uff0c\u6240\u4ee5\uff0c\u5143\u7d20\u7684\u4f4d\u7f6e\u8981\u4e48\u662f\u5728\u539f\u4f4d\u7f6e\uff0c\u8981\u4e48\u662f\u5728\u539f\u4f4d\u7f6e\u518d\u79fb\u52a82\u6b21\u5e42\u7684\u4f4d\u7f6e\u3002\u770b\u4e0b\u56fe\u53ef\u4ee5\u660e\u767d\u8fd9\u53e5\u8bdd\u7684\u610f\u601d\uff0cn \u4e3a table \u7684\u957f\u5ea6\uff0c\u56fe\uff08a\uff09\u8868\u793a\u6269\u5bb9\u524d\u7684 key1 \u548c<br>\nkey2 \u4e24\u79cd key \u786e\u5b9a\u7d22\u5f15\u4f4d\u7f6e\u7684\u793a\u4f8b\uff0c\u56fe\uff08b\uff09\u8868\u793a\u6269\u5bb9\u540e key1 \u548c<br>\nkey2 \u4e24\u79cd key \u786e\u5b9a\u7d22\u5f15\u4f4d\u7f6e\u7684\u793a\u4f8b\uff0c\u5176\u4e2d hash1 \u662f key1 \u5bf9\u5e94\u7684\u54c8\u5e0c\u4e0e\u9ad8\u4f4d\u8fd0\u7b97\u7ed3\u679c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/6cb03437-75cc-4e4a-bcb7-8a33fbd8e817.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5143\u7d20\u5728\u91cd\u65b0\u8ba1\u7b97 hash \u4e4b\u540e\uff0c\u56e0\u4e3a n \u53d8\u4e3a2\u500d\uff0c\u90a3\u4e48 n-1 \u7684 mask \u8303\u56f4\u5728\u9ad8\u4f4d\u591a1bit(\u7ea2\u8272)\uff0c\u56e0\u6b64\u65b0\u7684 index \u5c31\u4f1a\u53d1\u751f\u8fd9\u6837\u7684\u53d8\u5316\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/93378144-0a7b-45a1-ae37-ba045d3f5692.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6240\u4ee5\u5728\u6269\u5bb9\u4ee5\u540e\uff0c\u5c31\u53ea\u9700\u8981\u770b\u6269\u5bb9\u5bb9\u91cf\u4ee5\u540e\u90a3\u4e2a\u4f4d\u4e0a\u7684\u503c\u4e3a0\uff0c\u8fd8\u662f\u4e3a1\uff0c\u5982\u679c\u662f0\uff0c\u4ee3\u8868\u7d22\u5f15\u4e0d\u53d8\uff0c\u5982\u679c\u662f1\uff0c\u4ee3\u8868\u7684\u662f\u65b0\u7684\u7d22\u5f15\u503c\u7b49\u4e8e\u539f\u6765\u7684\u7d22\u5f15\u503c\u52a0\u4e0a oldCap \u5373\u53ef\uff0c\u8fd9\u6837\u5c31\u4e0d\u9700\u8981\u518d\u6b21\u8ba1\u7b97\u4e00\u6b21 hash \u4e86\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/37.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u56fe\u662f\u628a16\u6269\u5bb9\u523032\u7684\u60c5\u51b5\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Go \u4e2d Map \u7684\u5177\u4f53\u5b9e\u73b0\u4e3e\u4f8b<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8bfb\u5230\u8fd9\u91cc\uff0c\u8bfb\u8005\u5bf9\u5982\u4f55\u8bbe\u8ba1\u4e00\u4e2a Map \u5e94\u8be5\u6709\u4e00\u4e9b\u81ea\u5df1\u7684\u60f3\u6cd5\u4e86\u3002\u9009\u62e9\u4e00\u4e2a\u4f18\u79c0\u7684\u54c8\u5e0c\u7b97\u6cd5\uff0c\u7528\u94fe\u8868 + \u6570\u7ec4 \u4f5c\u4e3a\u5e95\u5c42\u6570\u636e\u7ed3\u6784\uff0c\u5982\u4f55\u6269\u5bb9\u548c\u4f18\u5316\uff0c\u8fd9\u4e9b\u5e94\u8be5\u90fd\u6709\u4e86\u89e3\u4e86\u3002\u8bfb\u5230\u8fd9\u91cc\u4e5f\u8bb8\u8bfb\u8005\u8ba4\u4e3a\u672c\u7bc7\u6587\u7ae0\u5185\u5bb9\u5df2\u7ecf\u8fc7\u534a\u4e86\uff0c\u4e0d\u8fc7\u524d\u9762\u8fd9\u4e9b\u90fd\u662f\u504f\u7406\u8bba\uff0c\u63a5\u4e0b\u6765\u4e5f\u8bb8\u624d\u5230\u4e86\u672c\u6587\u7684\u91cd\u70b9\u90e8\u5206 \u2014\u2014 \u4ece\u96f6\u5f00\u59cb\u5206\u6790\u4e00\u4e0b\u5b8c\u6574\u7684 Map \u5b9e\u73b0\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765\u7b14\u8005\u5bf9 Go \u4e2d\u7684 Map \u7684\u5e95\u5c42\u5b9e\u73b0\u8fdb\u884c\u5206\u6790\uff0c\u4e5f\u7b97\u662f\u5bf9\u4e00\u4e2a Map \u7684\u5177\u4f53\u5b9e\u73b0\u548c\u91cd\u8981\u7684\u51e0\u4e2a\u64cd\u4f5c\uff0c\u6dfb\u52a0\u952e\u503c\uff0c\u5220\u9664\u952e\u503c\uff0c\u6269\u5bb9\u7b56\u7565\u8fdb\u884c\u4e3e\u4f8b\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Go \u7684 map \u5b9e\u73b0\u5728 \/src\/runtime\/hashmap.go \u8fd9\u4e2a\u6587\u4ef6\u4e2d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">map \u5e95\u5c42\u5b9e\u8d28\u8fd8\u662f\u4e00\u4e2a hash table\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5148\u6765\u770b\u770b Go \u5b9a\u4e49\u4e86\u4e00\u4e9b\u5e38\u91cf\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>const (\n    \/\/ \u4e00\u4e2a\u6876\u91cc\u9762\u6700\u591a\u53ef\u4ee5\u88c5\u7684\u952e\u503c\u5bf9\u7684\u4e2a\u6570\uff0c8\u5bf9\u3002\n    bucketCntBits = 3\n    bucketCnt     = 1 &lt;&lt; bucketCntBits\n\n    \/\/ \u89e6\u53d1\u6269\u5bb9\u64cd\u4f5c\u7684\u6700\u5927\u88c5\u8f7d\u56e0\u5b50\u7684\u4e34\u754c\u503c\n    loadFactor = 6.5\n\n    \/\/ \u4e3a\u4e86\u4fdd\u6301\u5185\u8054\uff0c\u952e \u548c \u503c \u7684\u6700\u5927\u957f\u5ea6\u90fd\u662f128\u5b57\u8282\uff0c\u5982\u679c\u8d85\u8fc7\u4e86128\u4e2a\u5b57\u8282\uff0c\u5c31\u5b58\u50a8\u5b83\u7684\u6307\u9488\n    maxKeySize   = 128\n    maxValueSize = 128\n\n    \/\/ \u6570\u636e\u504f\u79fb\u5e94\u8be5\u662f bmap \u7684\u6574\u6570\u500d\uff0c\u4f46\u662f\u9700\u8981\u6b63\u786e\u7684\u5bf9\u9f50\u3002\n    dataOffset = unsafe.Offsetof(struct {\n        b bmap\n        v int64\n    }{}.v)\n\n    \/\/ tophash \u7684\u4e00\u4e9b\u503c\n    empty          = 0 \/\/ \u6ca1\u6709\u952e\u503c\u5bf9\n    evacuatedEmpty = 1 \/\/ \u6ca1\u6709\u952e\u503c\u5bf9\uff0c\u5e76\u4e14\u6876\u5185\u7684\u952e\u503c\u88ab\u8fc1\u79fb\u8d70\u4e86\u3002\n    evacuatedX     = 2 \/\/ \u952e\u503c\u5bf9\u6709\u6548\uff0c\u5e76\u4e14\u5df2\u7ecf\u8fc1\u79fb\u4e86\u4e00\u4e2a\u8868\u7684\u524d\u534a\u6bb5\n    evacuatedY     = 3 \/\/ \u952e\u503c\u5bf9\u6709\u6548\uff0c\u5e76\u4e14\u5df2\u7ecf\u8fc1\u79fb\u4e86\u4e00\u4e2a\u8868\u7684\u540e\u534a\u6bb5\n    minTopHash     = 4 \/\/ \u6700\u5c0f\u7684 tophash\n\n    \/\/ \u6807\u8bb0\n    iterator     = 1 \/\/ \u5f53\u524d\u6876\u7684\u8fed\u4ee3\u5b50\n    oldIterator  = 2 \/\/ \u65e7\u6876\u7684\u8fed\u4ee3\u5b50\n    hashWriting  = 4 \/\/ \u4e00\u4e2agoroutine\u6b63\u5728\u5199\u5165map\n    sameSizeGrow = 8 \/\/ \u5f53\u524d\u5b57\u5178\u589e\u957f\u5230\u65b0\u5b57\u5178\u5e76\u4e14\u4fdd\u6301\u76f8\u540c\u7684\u5927\u5c0f\n\n    \/\/ \u8fed\u4ee3\u5b50\u68c0\u67e5\u6876ID\u7684\u54e8\u5175\n    noCheck = 1&lt;&lt;(8*sys.PtrSize) - 1\n)<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u91cc\u503c\u5f97\u8bf4\u660e\u7684\u4e00\u70b9\u662f\u89e6\u53d1\u6269\u5bb9\u64cd\u4f5c\u7684\u4e34\u754c\u503c6.5\u662f\u600e\u4e48\u5f97\u6765\u7684\u3002\u8fd9\u4e2a\u503c\u592a\u5927\u4f1a\u5bfc\u81f4overflow buckets\u8fc7\u591a\uff0c\u67e5\u627e\u6548\u7387\u964d\u4f4e\uff0c\u8fc7\u5c0f\u4f1a\u6d6a\u8d39\u5b58\u50a8\u7a7a\u95f4\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u636e Google \u5f00\u53d1\u4eba\u5458\u79f0\uff0c\u8fd9\u4e2a\u503c\u662f\u4e00\u4e2a\u6d4b\u8bd5\u7684\u7a0b\u5e8f\uff0c\u6d4b\u91cf\u51fa\u6765\u9009\u62e9\u7684\u4e00\u4e2a\u7ecf\u9a8c\u503c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/38.png\" alt=\"\" \/><\/figure>\n\n\n\n<ul class=\"wp-block-list\"><li>%overflow \uff1a\u6ea2\u51fa\u7387\uff0c\u5e73\u5747\u4e00\u4e2a bucket \u6709\u591a\u5c11\u4e2a \u952e\u503ckv \u7684\u65f6\u5019\u4f1a\u6ea2\u51fa\u3002<\/li><li>bytes\/entry \uff1a\u5e73\u5747\u5b58\u4e00\u4e2a \u952e\u503ckv \u9700\u8981\u989d\u5916\u5b58\u50a8\u591a\u5c11\u5b57\u8282\u7684\u6570\u636e\u3002<\/li><li>hitprobe \uff1a\u67e5\u627e\u4e00\u4e2a\u5b58\u5728\u7684 key \u5e73\u5747\u67e5\u627e\u6b21\u6570\u3002<\/li><li>missprobe \uff1a\u67e5\u627e\u4e00\u4e2a\u4e0d\u5b58\u5728\u7684 key \u5e73\u5747\u67e5\u627e\u6b21\u6570\u3002<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ecf\u8fc7\u8fd9\u51e0\u7ec4\u6d4b\u8bd5\u6570\u636e\uff0c\u6700\u7ec8\u9009\u5b9a 6.5 \u4f5c\u4e3a\u4e34\u754c\u7684\u88c5\u8f7d\u56e0\u5b50\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u7740\u770b\u770b Go \u4e2d map header \u7684\u5b9a\u4e49\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>type hmap struct {\n    count     int \/\/ map \u7684\u957f\u5ea6\n    flags     uint8\n    B         uint8  \/\/ log\u4ee52\u4e3a\u5e95\uff0c\u6876\u4e2a\u6570\u7684\u5bf9\u6570 (\u603b\u5171\u80fd\u5b58 6.5 * 2^B \u4e2a\u5143\u7d20)\n    noverflow uint16 \/\/ \u8fd1\u4f3c\u6ea2\u51fa\u6876\u7684\u4e2a\u6570\n    hash0     uint32 \/\/ \u54c8\u5e0c\u79cd\u5b50\n\n    buckets    unsafe.Pointer \/\/ \u6709 2^B \u4e2a\u6876\u7684\u6570\u7ec4. count==0 \u7684\u65f6\u5019\uff0c\u8fd9\u4e2a\u6570\u7ec4\u4e3a nil.\n    oldbuckets unsafe.Pointer \/\/ \u65e7\u7684\u6876\u6570\u7ec4\u4e00\u534a\u7684\u5143\u7d20\n    nevacuate  uintptr        \/\/ \u6269\u5bb9\u589e\u957f\u8fc7\u7a0b\u4e2d\u7684\u8ba1\u6570\u5668\n\n    extra *mapextra \/\/ \u53ef\u9009\u5b57\u6bb5\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Go \u7684 map header \u7ed3\u6784\u4e2d\uff0c\u4e5f\u5305\u542b\u4e862\u4e2a\u6307\u5411\u6876\u6570\u7ec4\u7684\u6307\u9488\uff0cbuckets \u6307\u5411\u65b0\u7684\u6876\u6570\u7ec4\uff0coldbuckets \u6307\u5411\u65e7\u7684\u6876\u6570\u7ec4\u3002\u8fd9\u70b9\u548c Redis \u5b57\u5178\u4e2d\u4e5f\u6709\u4e24\u4e2a dictht \u6570\u7ec4\u7c7b\u4f3c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/39.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">hmap \u7684\u6700\u540e\u4e00\u4e2a\u5b57\u6bb5\u662f\u4e00\u4e2a\u6307\u5411 mapextra \u7ed3\u6784\u7684\u6307\u9488\uff0c\u5b83\u7684\u5b9a\u4e49\u5982\u4e0b\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>type mapextra struct {\n    overflow [2]*[]*bmap\n    nextOverflow *bmap\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c\u4e00\u4e2a\u952e\u503c\u5bf9\u6ca1\u6709\u627e\u5230\u5bf9\u5e94\u7684\u6307\u9488\uff0c\u90a3\u4e48\u5c31\u4f1a\u628a\u5b83\u4eec\u5148\u5b58\u5230\u6ea2\u51fa\u6876<br>\noverflow \u91cc\u9762\u3002\u5728 mapextra \u4e2d\u8fd8\u6709\u4e00\u4e2a\u6307\u5411\u4e0b\u4e00\u4e2a\u53ef\u7528\u7684\u6ea2\u51fa\u6876\u7684\u6307\u9488\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/40.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6ea2\u51fa\u6876 overflow \u662f\u4e00\u4e2a\u6570\u7ec4\uff0c\u91cc\u9762\u5b58\u4e862\u4e2a\u6307\u5411 *bmap \u6570\u7ec4\u7684\u6307\u9488\u3002overflow[0] \u91cc\u9762\u88c5\u7684\u662f hmap.buckets \u3002overflow[1] \u91cc\u9762\u88c5\u7684\u662f hmap.oldbuckets\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u518d\u770b\u770b\u6876\u7684\u6570\u636e\u7ed3\u6784\u7684\u5b9a\u4e49\uff0cbmap \u5c31\u662f Go \u4e2d map \u91cc\u9762\u6876\u5bf9\u5e94\u7684\u7ed3\u6784\u4f53\u7c7b\u578b\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>type bmap struct {\n    tophash [bucketCnt]uint8\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u6876\u7684\u5b9a\u4e49\u6bd4\u8f83\u7b80\u5355\uff0c\u91cc\u9762\u5c31\u53ea\u662f\u5305\u542b\u4e86\u4e00\u4e2a uint8 \u7c7b\u578b\u7684\u6570\u7ec4\uff0c\u91cc\u9762\u5305\u542b8\u4e2a\u5143\u7d20\u3002\u8fd98\u4e2a\u5143\u7d20\u5b58\u50a8\u7684\u662f hash \u503c\u7684\u9ad88\u4f4d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 tophash \u4e4b\u540e\u7684\u5185\u5b58\u5e03\u5c40\u91cc\u8fd8\u67092\u5757\u5185\u5bb9\u3002\u7d27\u63a5\u7740 tophash \u4e4b\u540e\u7684\u662f8\u5bf9 \u952e\u503c key- value \u5bf9\u3002\u5e76\u4e14\u6392\u5217\u65b9\u5f0f\u662f 8\u4e2a key \u548c 8\u4e2a value \u653e\u5728\u4e00\u8d77\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">8\u5bf9 \u952e\u503c key- value \u5bf9\u7ed3\u675f\u4ee5\u540e\u7d27\u63a5\u7740\u4e00\u4e2a overflow \u6307\u9488\uff0c\u6307\u5411\u4e0b\u4e00\u4e2a bmap\u3002\u4ece\u6b64\u4e5f\u53ef\u4ee5\u770b\u51fa Go \u4e2d map\u662f\u7528\u94fe\u8868\u7684\u65b9\u5f0f\u5904\u7406 hash \u51b2\u7a81\u7684\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/28ea641b-725b-4cc6-b6f1-e0a28c58d692.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3a\u4f55 Go \u5b58\u50a8\u952e\u503c\u5bf9\u7684\u65b9\u5f0f\u4e0d\u662f\u666e\u901a\u7684 key\/value\u3001key\/value\u3001key\/value\u2026\u2026\u8fd9\u6837\u5b58\u50a8\u7684\u5462\uff1f\u5b83\u662f\u952e key \u90fd\u5b58\u50a8\u5728\u4e00\u8d77\uff0c\u7136\u540e\u7d27\u63a5\u7740\u662f \u503cvalue \u90fd\u5b58\u50a8\u5728\u4e00\u8d77\uff0c\u4e3a\u4ec0\u4e48\u4f1a\u8fd9\u6837\u5462\uff1f<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/80a836f7-5ca4-4277-94e1-ac9c31033e03.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Redis \u4e2d\uff0c\u5f53\u4f7f\u7528 REDIS_ENCODING_ZIPLIST \u7f16\u7801\u54c8\u5e0c\u8868\u65f6\uff0c \u7a0b\u5e8f\u901a\u8fc7\u5c06\u952e\u548c\u503c\u4e00\u540c\u63a8\u5165\u538b\u7f29\u5217\u8868\uff0c \u4ece\u800c\u5f62\u6210\u4fdd\u5b58\u54c8\u5e0c\u8868\u6240\u9700\u7684\u952e-\u503c\u5bf9\u7ed3\u6784\uff0c\u5982\u4e0a\u56fe\u3002\u65b0\u6dfb\u52a0\u7684 key-value \u5bf9\u4f1a\u88ab\u6dfb\u52a0\u5230\u538b\u7f29\u5217\u8868\u7684\u8868\u5c3e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u79cd\u7ed3\u6784\u6709\u4e00\u4e2a\u5f0a\u7aef\uff0c\u5982\u679c\u5b58\u50a8\u7684\u952e\u548c\u503c\u7684\u7c7b\u578b\u4e0d\u540c\uff0c\u5728\u5185\u5b58\u4e2d\u5e03\u5c40\u4e2d\u6240\u5360\u5b57\u8282\u4e0d\u540c\u7684\u8bdd\uff0c\u5c31\u9700\u8981\u5bf9\u9f50\u3002\u6bd4\u5982\u8bf4\u5b58\u50a8\u4e00\u4e2a map[int64]int8 \u7c7b\u578b\u7684\u5b57\u5178\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Go \u4e3a\u4e86\u8282\u7ea6\u5185\u5b58\u5bf9\u9f50\u7684\u5185\u5b58\u6d88\u8017\uff0c\u4e8e\u662f\u628a\u5b83\u8bbe\u8ba1\u6210\u4e0a\u56fe\u6240\u793a\u90a3\u6837\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c map \u91cc\u9762\u5b58\u50a8\u4e86\u4e0a\u4e07\u4ebf\u7684\u5927\u6570\u636e\uff0c\u8fd9\u91cc\u8282\u7ea6\u51fa\u6765\u7684\u5185\u5b58\u7a7a\u95f4\u8fd8\u662f\u6bd4\u8f83\u53ef\u89c2\u7684\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u65b0\u5efa Map<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">makemap \u65b0\u5efa\u4e86\u4e00\u4e2a Map\uff0c\u5982\u679c\u5165\u53c2 h \u4e0d\u4e3a\u7a7a\uff0c\u90a3\u4e48 map \u7684 hmap \u5c31\u662f\u5165\u53c2\u7684\u8fd9\u4e2a hmap\uff0c\u5982\u679c\u5165\u53c2 bucket \u4e0d\u4e3a\u7a7a\uff0c\u90a3\u4e48\u8fd9\u4e2a bucket \u6876\u5c31\u4f5c\u4e3a\u7b2c\u4e00\u4e2a\u6876\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {\n    \/\/ hmap \u7684 size \u5927\u5c0f\u7684\u503c\u975e\u6cd5\n    if sz := unsafe.Sizeof(hmap{}); sz &gt; 48 || sz != t.hmap.size {\n        println(\"runtime: sizeof(hmap) =\", sz, \", t.hmap.size =\", t.hmap.size)\n        throw(\"bad hmap size\")\n    }\n\n    \/\/ \u8d85\u8fc7\u8303\u56f4\u7684 hint \u503c\u90fd\u4e3a0\n    if hint &lt; 0 || hint &gt; int64(maxSliceCap(t.bucket.size)) {\n        hint = 0\n    }\n\n    \/\/ key \u503c\u7684\u7c7b\u578b\u4e0d\u662f Go \u6240\u652f\u6301\u7684\n    if !ismapkey(t.key) {\n        throw(\"runtime.makemap: unsupported map key type\")\n    }\n\n    \/\/ \u901a\u8fc7\u7f16\u8bd1\u5668\u548c\u53cd\u5c04\u68c0\u8f66 key \u503c\u7684 size \u662f\u5426\u5408\u6cd5\n    if t.key.size &gt; maxKeySize &amp;&amp; (!t.indirectkey || t.keysize != uint8(sys.PtrSize)) ||\n        t.key.size &lt;= maxKeySize &amp;&amp; (t.indirectkey || t.keysize != uint8(t.key.size)) {\n        throw(\"key size wrong\")\n    }\n    \/\/ \u901a\u8fc7\u7f16\u8bd1\u5668\u548c\u53cd\u5c04\u68c0\u8f66 value \u503c\u7684 size \u662f\u5426\u5408\u6cd5\n    if t.elem.size &gt; maxValueSize &amp;&amp; (!t.indirectvalue || t.valuesize != uint8(sys.PtrSize)) ||\n        t.elem.size &lt;= maxValueSize &amp;&amp; (t.indirectvalue || t.valuesize != uint8(t.elem.size)) {\n        throw(\"value size wrong\")\n    }\n\n    \/\/ \u867d\u7136\u4ee5\u4e0b\u7684\u53d8\u91cf\u6211\u4eec\u4e0d\u4f9d\u8d56\uff0c\u800c\u4e14\u53ef\u4ee5\u5728\u7f16\u8bd1\u9636\u6bb5\u68c0\u67e5\u4e0b\u9762\u8fd9\u4e9b\u503c\u7684\u5408\u6cd5\u6027\uff0c\n    \/\/ \u4f46\u662f\u6211\u4eec\u8fd8\u662f\u5728\u8fd9\u91cc\u68c0\u6d4b\u3002\n\n    \/\/ key \u503c\u5bf9\u9f50\u8d85\u8fc7\u6876\u7684\u4e2a\u6570\n    if t.key.align &gt; bucketCnt {\n        throw(\"key align too big\")\n    }\n    \/\/ value \u503c\u5bf9\u9f50\u8d85\u8fc7\u6876\u7684\u4e2a\u6570\n    if t.elem.align &gt; bucketCnt {\n        throw(\"value align too big\")\n    }\n    \/\/ key \u503c\u7684 size \u4e0d\u662f key \u503c\u5bf9\u9f50\u7684\u500d\u6570\n    if t.key.size%uintptr(t.key.align) != 0 {\n        throw(\"key size not a multiple of key align\")\n    }\n    \/\/ value \u503c\u7684 size \u4e0d\u662f value \u503c\u5bf9\u9f50\u7684\u500d\u6570\n    if t.elem.size%uintptr(t.elem.align) != 0 {\n        throw(\"value size not a multiple of value align\")\n    }\n    \/\/ \u6876\u4e2a\u6570\u592a\u5c0f\uff0c\u65e0\u6cd5\u6b63\u786e\u5bf9\u9f50\n    if bucketCnt &lt; 8 {\n        throw(\"bucketsize too small for proper alignment\")\n    }\n    \/\/ \u6570\u636e\u504f\u79fb\u91cf\u4e0d\u662f key \u503c\u5bf9\u9f50\u7684\u6574\u6570\u500d\uff0c\u8bf4\u660e\u9700\u8981\u5728\u6876\u4e2d\u586b\u5145 key\n    if dataOffset%uintptr(t.key.align) != 0 {\n        throw(\"need padding in bucket (key)\")\n    }\n    \/\/ \u6570\u636e\u504f\u79fb\u91cf\u4e0d\u662f value \u503c\u5bf9\u9f50\u7684\u6574\u6570\u500d\uff0c\u8bf4\u660e\u9700\u8981\u5728\u6876\u4e2d\u586b\u5145 value\n    if dataOffset%uintptr(t.elem.align) != 0 {\n        throw(\"need padding in bucket (value)\")\n    }\n\n    B := uint8(0)\n    for ; overLoadFactor(hint, B); B++ {\n    }\n\n    \/\/ \u5206\u914d\u5185\u5b58\u5e76\u521d\u59cb\u5316\u54c8\u5e0c\u8868\n    \/\/ \u5982\u679c\u6b64\u65f6 B = 0\uff0c\u90a3\u4e48 hmap \u4e2d\u7684 buckets \u5b57\u6bb5\u7a0d\u540e\u5206\u914d\n    \/\/ \u5982\u679c hint \u503c\u5f88\u5927\uff0c\u521d\u59cb\u5316\u8fd9\u5757\u5185\u5b58\u9700\u8981\u4e00\u6bb5\u65f6\u95f4\u3002\n    buckets := bucket\n    var extra *mapextra\n    if B != 0 {\n        var nextOverflow *bmap\n        \/\/ \u521d\u59cb\u5316 bucket \u548c nextOverflow \n        buckets, nextOverflow = makeBucketArray(t, B)\n        if nextOverflow != nil {\n            extra = new(mapextra)\n            extra.nextOverflow = nextOverflow\n        }\n    }\n\n    \/\/ \u521d\u59cb\u5316 hmap\n    if h == nil {\n        h = (*hmap)(newobject(t.hmap))\n    }\n    h.count = 0\n    h.B = B\n    h.extra = extra\n    h.flags = 0\n    h.hash0 = fastrand()\n    h.buckets = buckets\n    h.oldbuckets = nil\n    h.nevacuate = 0\n    h.noverflow = 0\n\n    return h\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u65b0\u5efa\u4e00\u4e2a map \u6700\u91cd\u8981\u7684\u5c31\u662f\u5206\u914d\u5185\u5b58\u5e76\u521d\u59cb\u5316\u54c8\u5e0c\u8868\uff0c\u5728 B \u4e0d\u4e3a0\u7684\u60c5\u51b5\u4e0b\uff0c\u8fd8\u4f1a\u521d\u59cb\u5316 mapextra \u5e76\u4e14\u4f1a buckets \u4f1a\u88ab\u91cd\u65b0\u751f\u6210\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func makeBucketArray(t *maptype, b uint8) (buckets unsafe.Pointer, nextOverflow *bmap) {\n    base := uintptr(1 &lt;&lt; b)\n    nbuckets := base\n    if b &gt;= 4 {\n        nbuckets += 1 &lt;&lt; (b - 4)\n        sz := t.bucket.size * nbuckets\n        up := roundupsize(sz)\n        \/\/ \u5982\u679c\u7533\u8bf7 sz \u5927\u5c0f\u7684\u6876\uff0c\u7cfb\u7edf\u53ea\u80fd\u8fd4\u56de up \u5927\u5c0f\u7684\u5185\u5b58\u7a7a\u95f4\uff0c\u90a3\u4e48\u6876\u7684\u4e2a\u6570\u4e3a up \/ t.bucket.size\n        if up != sz {\n            nbuckets = up \/ t.bucket.size\n        }\n    }\n    buckets = newarray(t.bucket, int(nbuckets))\n    \/\/ \u5f53 b &gt; 4 \u5e76\u4e14\u8ba1\u7b97\u51fa\u6765\u6876\u7684\u4e2a\u6570\u4e0e 1 &lt;&lt; b \u4e2a\u6570\u4e0d\u7b49\u7684\u65f6\u5019\uff0c\n    if base != nbuckets {\n        \/\/ \u6b64\u65f6 nbuckets \u6bd4 base \u5927\uff0c\u90a3\u4e48\u4f1a\u9884\u5148\u5206\u914d nbuckets - base \u4e2a nextOverflow \u6876\n        nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))\n        last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))\n        last.setoverflow(t, (*bmap)(buckets))\n    }\n    return buckets, nextOverflow\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u91cc\u7684 newarray \u5c31\u5df2\u7ecf\u662f mallocgc \u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ece\u4e0a\u8ff0\u4ee3\u7801\u91cc\u9762\u53ef\u4ee5\u770b\u51fa\uff0c\u53ea\u6709\u5f53 B &gt;=4 \u7684\u65f6\u5019\uff0cmakeBucketArray \u624d\u4f1a\u751f\u6210 nextOverflow \u6307\u9488\u6307\u5411 bmap\uff0c\u4ece\u800c\u5728 Map \u751f\u6210 hmap \u7684\u65f6\u5019\u624d\u4f1a\u751f\u6210 mapextra \u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5f53 B = 3 ( B &lt; 4 ) \u7684\u65f6\u5019\uff0c\u521d\u59cb\u5316 hmap \u53ea\u4f1a\u751f\u62108\u4e2a\u6876\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/43.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5f53 B = 4 ( B &gt;= 4 ) \u7684\u65f6\u5019\uff0c\u521d\u59cb\u5316 hmap \u7684\u65f6\u5019\u8fd8\u4f1a\u989d\u5916\u751f\u6210 mapextra \uff0c\u5e76\u521d\u59cb\u5316 nextOverflow\u3002mapextra \u7684 nextOverflow \u6307\u9488\u4f1a\u6307\u5411\u7b2c16\u4e2a\u6876\u7ed3\u675f\uff0c\u7b2c17\u4e2a\u6876\u7684\u9996\u5730\u5740\u3002\u7b2c17\u4e2a\u6876\uff08\u4ece0\u5f00\u59cb\uff0c\u4e5f\u5c31\u662f\u4e0b\u6807\u4e3a16\u7684\u6876\uff09\u7684 bucketsize &#8211; sys.PtrSize \u5730\u5740\u5f00\u59cb\u5b58\u4e00\u4e2a\u6307\u9488\uff0c\u8fd9\u4e2a\u6307\u9488\u6307\u5411\u5f53\u524d\u6574\u4e2a\u6876\u7684\u9996\u5730\u5740\u3002\u8fd9\u4e2a\u6307\u9488\u5c31\u662f bmap \u7684 overflow \u6307\u9488\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/44.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5f53 B = 5 ( B &gt;= 4 ) \u7684\u65f6\u5019\uff0c\u521d\u59cb\u5316 hmap \u7684\u65f6\u5019\u8fd8\u4f1a\u989d\u5916\u751f\u6210 mapextra \uff0c\u5e76\u521d\u59cb\u5316 nextOverflow\u3002\u8fd9\u4e2a\u65f6\u5019\u5c31\u4f1a\u751f\u6210\u603b\u517134\u4e2a\u6876\u4e86\u3002\u540c\u7406\uff0c\u6700\u540e\u4e00\u4e2a\u6876\u5927\u5c0f\u51cf\u53bb\u4e00\u4e2a\u6307\u9488\u7684\u5927\u5c0f\u7684\u5730\u5740\u5f00\u59cb\u5b58\u50a8\u4e00\u4e2a overflow \u6307\u9488\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/45.png\" alt=\"\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">\u67e5\u627e Key<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Go \u4e2d\uff0c\u5982\u679c\u5b57\u5178\u91cc\u9762\u67e5\u627e\u4e00\u4e2a\u4e0d\u5b58\u5728\u7684 key \uff0c\u67e5\u627e\u4e0d\u5230\u5e76\u4e0d\u4f1a\u8fd4\u56de\u4e00\u4e2a nil \uff0c\u800c\u662f\u8fd4\u56de\u5f53\u524d\u7c7b\u578b\u7684\u96f6\u503c\u3002\u6bd4\u5982\uff0c\u5b57\u7b26\u4e32\u5c31\u8fd4\u56de\u7a7a\u5b57\u7b26\u4e32\uff0cint \u7c7b\u578b\u5c31\u8fd4\u56de 0 \u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {\n    if raceenabled &amp;&amp; h != nil {\n        \/\/ \u83b7\u53d6 caller \u7684 \u7a0b\u5e8f\u8ba1\u6570\u5668 program counter\n        callerpc := getcallerpc(unsafe.Pointer(&amp;t))\n        \/\/ \u83b7\u53d6 mapaccess1 \u7684\u7a0b\u5e8f\u8ba1\u6570\u5668 program counter\n        pc := funcPC(mapaccess1)\n        racereadpc(unsafe.Pointer(h), callerpc, pc)\n        raceReadObjectPC(t.key, key, callerpc, pc)\n    }\n    if msanenabled &amp;&amp; h != nil {\n        msanread(key, t.key.size) \n    }\n    if h == nil || h.count == 0 {\n        return unsafe.Pointer(&amp;zeroVal[0])\n    }\n    \/\/ \u5982\u679c\u591a\u7ebf\u7a0b\u8bfb\u5199\uff0c\u76f4\u63a5\u629b\u51fa\u5f02\u5e38\n    \/\/ \u5e76\u53d1\u68c0\u67e5 go hashmap \u4e0d\u652f\u6301\u5e76\u53d1\u8bbf\u95ee\n    if h.flags&amp;hashWriting != 0 {\n        throw(\"concurrent map read and map write\")\n    }\n    alg := t.key.alg\n    \/\/ \u8ba1\u7b97 key \u7684 hash \u503c\n    hash := alg.hash(key, uintptr(h.hash0))\n    m := uintptr(1)&lt;&lt;h.B - 1\n    \/\/ hash % (1&lt;&lt;B - 1) \u6c42\u51fa key \u5728\u54ea\u4e2a\u6876\n    b := (*bmap)(add(h.buckets, (hash&amp;m)*uintptr(t.bucketsize)))\n    \/\/ \u5982\u679c\u5f53\u524d\u8fd8\u5b58\u5728 oldbuckets \u6876\n    if c := h.oldbuckets; c != nil {\n        \/\/ \u5f53\u524d\u6269\u5bb9\u4e0d\u662f\u7b49\u91cf\u6269\u5bb9\n        if !h.sameSizeGrow() {\n            \/\/ \u5982\u679c oldbuckets \u672a\u8fc1\u79fb\u5b8c\u6210 \u5219\u627e\u627e oldbuckets \u4e2d\u5bf9\u5e94\u7684 bucket(\u4f4e B-1 \u4f4d)\n            \/\/ \u5426\u5219\u4e3a buckets \u4e2d\u7684 bucket(\u4f4e B \u4f4d)\n            \/\/ \u628a mask \u7f29\u5c0f 1 \u500d\n            m &gt;&gt;= 1\n        }\n        \n        oldb := (*bmap)(add(c, (hash&amp;m)*uintptr(t.bucketsize)))\n        if !evacuated(oldb) {\n            \/\/ \u5982\u679c oldbuckets \u6876\u5b58\u5728\uff0c\u5e76\u4e14\u8fd8\u6ca1\u6709\u6269\u5bb9\u8fc1\u79fb\uff0c\u5c31\u5728\u8001\u7684\u6876\u91cc\u9762\u67e5\u627e key \n            b = oldb\n        }\n    }\n    \/\/ \u53d6\u51fa hash \u503c\u7684\u9ad8 8 \u4f4d\n    top := uint8(hash &gt;&gt; (sys.PtrSize*8 - 8))\n    \/\/ \u5982\u679c top \u5c0f\u4e8e minTopHash\uff0c\u5c31\u8ba9\u5b83\u52a0\u4e0a minTopHash \u7684\u504f\u79fb\u3002\n    \/\/ \u56e0\u4e3a 0 - minTopHash \u8fd9\u533a\u95f4\u7684\u6570\u90fd\u5df2\u7ecf\u7528\u6765\u4f5c\u4e3a\u6807\u8bb0\u4f4d\u4e86\n    if top &lt; minTopHash {\n        top += minTopHash\n    }\n    for {\n        for i := uintptr(0); i &lt; bucketCnt; i++ {\n            \/\/ \u5982\u679c hash \u7684\u9ad88\u4f4d\u548c\u5f53\u524d key \u8bb0\u5f55\u7684\u4e0d\u4e00\u6837\uff0c\u5c31\u627e\u4e0b\u4e00\u4e2a\n            \/\/ \u8fd9\u6837\u6bd4\u8f83\u5f88\u9ad8\u6548\uff0c\u56e0\u4e3a\u53ea\u7528\u6bd4\u8f83\u9ad88\u4f4d\uff0c\u4e0d\u7528\u6bd4\u8f83\u6240\u6709\u7684 hash \u503c\n            \/\/ \u5982\u679c\u9ad88\u4f4d\u90fd\u4e0d\u76f8\u540c\uff0chash \u503c\u80af\u5b9a\u4e0d\u540c\uff0c\u4f46\u662f\u9ad88\u4f4d\u5982\u679c\u76f8\u540c\uff0c\u90a3\u4e48\u5c31\u8981\u6bd4\u8f83\u6574\u4e2a hash \u503c\u4e86\n            if b.tophash[i] != top {\n                continue\n            }\n            \/\/ \u53d6\u51fa key \u503c\u7684\u65b9\u5f0f\u662f\u7528\u504f\u79fb\u91cf\uff0cbmap \u9996\u5730\u5740 + i \u4e2a key \u503c\u5927\u5c0f\u7684\u504f\u79fb\u91cf\n            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\n            if t.indirectkey {\n                k = *((*unsafe.Pointer)(k))\n            }\n            \/\/ \u6bd4\u8f83 key \u503c\u662f\u5426\u76f8\u7b49\n            if alg.equal(key, k) {\n                \/\/ \u5982\u679c\u627e\u5230\u4e86 key\uff0c\u90a3\u4e48\u53d6\u51fa value \u503c\n                \/\/ \u53d6\u51fa value \u503c\u7684\u65b9\u5f0f\u662f\u7528\u504f\u79fb\u91cf\uff0cbmap \u9996\u5730\u5740 + 8 \u4e2a key \u503c\u5927\u5c0f\u7684\u504f\u79fb\u91cf + i \u4e2a value \u503c\u5927\u5c0f\u7684\u504f\u79fb\u91cf\n                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\n                if t.indirectvalue {\n                    v = *((*unsafe.Pointer)(v))\n                }\n                return v\n            }\n        }\n        \/\/ \u5982\u679c\u5f53\u524d\u6876\u91cc\u9762\u6ca1\u6709\u627e\u5230\u76f8\u5e94\u7684 key \uff0c\u90a3\u4e48\u5c31\u53bb\u4e0b\u4e00\u4e2a\u6876\u53bb\u627e\n        b = b.overflow(t)\n        \/\/ \u5982\u679c b == nil\uff0c\u8bf4\u660e\u6876\u5df2\u7ecf\u90fd\u627e\u5b8c\u4e86\uff0c\u8fd4\u56de\u5bf9\u5e94type\u7684\u96f6\u503c\n        if b == nil {\n            return unsafe.Pointer(&amp;zeroVal[0])\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u5982\u4e0a\uff0c\u8be6\u7ec6\u89e3\u91ca\u89c1\u4ee3\u7801\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/87fd6e1d-b91c-4266-8fb5-4390b369e237.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u4e0a\u56fe\uff0c\u8fd9\u662f\u4e00\u4e2a\u67e5\u627e key \u7684\u5168\u8fc7\u7a0b\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u9996\u5148\u8ba1\u7b97\u51fa key \u5bf9\u5e94\u7684 hash \u503c\uff0chash \u503c\u5bf9 B \u53d6\u4f59\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u91cc\u6709\u4e00\u4e2a\u4f18\u5316\u70b9\u3002m % n \u8fd9\u6b65\u8ba1\u7b97\uff0c\u5982\u679c n \u662f2\u7684\u500d\u6570\uff0c\u90a3\u4e48\u53ef\u4ee5\u7701\u53bb\u8fd9\u4e00\u6b65\u53d6\u4f59\u64cd\u4f5c\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>m\u00a0%\u00a0n\u00a0=\u00a0m\u00a0&amp;\u00a0(\u00a0n\u00a0-\u00a01\u00a0)\u00a0<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u6837\u4f18\u5316\u5c31\u53ef\u4ee5\u7701\u53bb\u8017\u65f6\u7684\u53d6\u4f59\u64cd\u4f5c\u4e86\u3002\u8fd9\u91cc\u4f8b\u5b50\u4e2d\u8ba1\u7b97\u5b8c\u53d6\u51fa\u6765\u662f 0010 \uff0c\u4e5f\u5c31\u662f2\uff0c\u4e8e\u662f\u5bf9\u5e94\u7684\u662f\u6876\u6570\u7ec4\u91cc\u9762\u7684\u7b2c3\u4e2a\u6876\u3002\u4e3a\u4ec0\u4e48\u662f\u7b2c3\u4e2a\u6876\u5462\uff1f\u9996\u5730\u5740\u6307\u5411\u7b2c0\u4e2a\u6876\uff0c\u5f80\u4e0b\u504f\u79fb2\u4e2a\u6876\u7684\u5927\u5c0f\uff0c\u4e8e\u662f\u504f\u79fb\u5230\u4e86\u7b2c3\u4e2a\u6876\u7684\u9996\u5730\u5740\u4e86\uff0c\u5177\u4f53\u5b9e\u73b0\u53ef\u4ee5\u770b\u4e0a\u8ff0\u4ee3\u7801\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">hash \u7684\u4f4e B \u4f4d\u51b3\u5b9a\u4e86\u6876\u6570\u7ec4\u91cc\u9762\u7684\u7b2c\u51e0\u4e2a\u6876\uff0chash \u503c\u7684\u9ad88\u4f4d\u51b3\u5b9a\u4e86\u8fd9\u4e2a\u6876\u6570\u7ec4 bmap \u91cc\u9762 key \u5b58\u5728 tophash \u6570\u7ec4\u7684\u7b2c\u51e0\u4f4d\u4e86\u3002\u5982\u4e0a\u56fe\uff0chash \u7684\u9ad88\u4f4d\u7528\u6765\u548c tophash \u6570\u7ec4\u91cc\u9762\u7684\u6bcf\u4e2a\u503c\u8fdb\u884c\u5bf9\u6bd4\uff0c\u5982\u679c\u9ad88\u4f4d\u548c tophash[i] \u4e0d\u7b49\uff0c\u5c31\u76f4\u63a5\u6bd4\u4e0b\u4e00\u4e2a\u3002\u5982\u679c\u76f8\u7b49\uff0c\u5219\u53d6\u51fa bmap \u91cc\u9762\u5bf9\u5e94\u5b8c\u6574\u7684 key\uff0c\u518d\u6bd4\u8f83\u4e00\u6b21\uff0c\u770b\u662f\u5426\u5b8c\u5168\u4e00\u81f4\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6574\u4e2a\u67e5\u627e\u8fc7\u7a0b\u4f18\u5148\u5728 oldbucket \u91cc\u9762\u627e(\u5982\u679c\u5b58\u5728 lodbucket \u7684\u8bdd)\uff0c\u627e\u5b8c\u518d\u53bb\u65b0 bmap \u91cc\u9762\u627e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6709\u4eba\u53ef\u80fd\u4f1a\u6709\u7591\u95ee\uff0c\u4e3a\u4f55\u8fd9\u91cc\u8981\u52a0\u5165 tophash \u591a\u4e00\u6b21\u6bd4\u8f83\u5462\uff1f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">tophash \u7684\u5f15\u5165\u662f\u4e3a\u4e86\u52a0\u901f\u67e5\u627e\u7684\u3002\u7531\u4e8e\u5b83\u53ea\u5b58\u4e86 hash \u503c\u7684\u9ad88\u4f4d\uff0c\u6bd4\u67e5\u627e\u5b8c\u6574\u768464\u4f4d\u8981\u5feb\u5f88\u591a\u3002\u901a\u8fc7\u6bd4\u8f83\u9ad88\u4f4d\uff0c\u8fc5\u901f\u627e\u5230\u9ad88\u4f4d\u4e00\u81f4hash \u503c\u7684\u7d22\u5f15\uff0c\u63a5\u4e0b\u6765\u518d\u8fdb\u884c\u4e00\u6b21\u5b8c\u6574\u7684\u6bd4\u8f83\uff0c\u5982\u679c\u8fd8\u4e00\u81f4\uff0c\u90a3\u4e48\u5c31\u5224\u5b9a\u627e\u5230\u8be5 key \u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c\u627e\u5230\u4e86 key \u5c31\u8fd4\u56de\u5bf9\u5e94\u7684 value\u3002\u5982\u679c\u6ca1\u6709\u627e\u5230\uff0c\u8fd8\u4f1a\u7ee7\u7eed\u53bb overflow \u6876\u7ee7\u7eed\u5bfb\u627e\uff0c\u76f4\u5230\u627e\u5230\u6700\u540e\u4e00\u4e2a\u6876\uff0c\u5982\u679c\u8fd8\u6ca1\u6709\u627e\u5230\u5c31\u8fd4\u56de\u5bf9\u5e94\u7c7b\u578b\u7684\u96f6\u503c\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u63d2\u5165 Key<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u63d2\u5165 key \u7684\u8fc7\u7a0b\u548c\u67e5\u627e key \u7684\u8fc7\u7a0b\u5927\u4f53\u4e00\u81f4\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {\n    if h == nil {\n        panic(plainError(\"assignment to entry in nil map\"))\n    }\n    if raceenabled {\n        \/\/ \u83b7\u53d6 caller \u7684 \u7a0b\u5e8f\u8ba1\u6570\u5668 program counter\n        callerpc := getcallerpc(unsafe.Pointer(&amp;t))\n        \/\/ \u83b7\u53d6 mapassign \u7684\u7a0b\u5e8f\u8ba1\u6570\u5668 program counter\n        pc := funcPC(mapassign)\n        racewritepc(unsafe.Pointer(h), callerpc, pc)\n        raceReadObjectPC(t.key, key, callerpc, pc)\n    }\n    if msanenabled {\n        msanread(key, t.key.size)\n    }\n    \/\/ \u5982\u679c\u591a\u7ebf\u7a0b\u8bfb\u5199\uff0c\u76f4\u63a5\u629b\u51fa\u5f02\u5e38\n    \/\/ \u5e76\u53d1\u68c0\u67e5 go hashmap \u4e0d\u652f\u6301\u5e76\u53d1\u8bbf\u95ee\n    if h.flags&amp;hashWriting != 0 {\n        throw(\"concurrent map writes\")\n    }\n    alg := t.key.alg\n    \/\/ \u8ba1\u7b97 key \u503c\u7684 hash \u503c\n    hash := alg.hash(key, uintptr(h.hash0))\n\n    \/\/ \u5728\u8ba1\u7b97\u5b8c hash \u503c\u4ee5\u540e\u7acb\u5373\u8bbe\u7f6e hashWriting \u53d8\u91cf\u7684\u503c\uff0c\u5982\u679c\u5728\u8ba1\u7b97 hash \u503c\u7684\u8fc7\u7a0b\u4e2d\u6ca1\u6709\u5b8c\u5168\u5199\u5b8c\uff0c\u53ef\u80fd\u4f1a\u5bfc\u81f4 panic\n    h.flags |= hashWriting\n\n    \/\/ \u5982\u679c hmap \u7684\u6876\u7684\u4e2a\u6570\u4e3a0\uff0c\u90a3\u4e48\u5c31\u65b0\u5efa\u4e00\u4e2a\u6876\n    if h.buckets == nil {\n        h.buckets = newarray(t.bucket, 1)\n    }\n\nagain:\n    \/\/ hash \u503c\u5bf9 B \u53d6\u4f59\uff0c\u6c42\u5f97\u6240\u5728\u54ea\u4e2a\u6876\n    bucket := hash &amp; (uintptr(1)&lt;&lt;h.B - 1)\n    \/\/ \u5982\u679c\u8fd8\u5728\u6269\u5bb9\u4e2d\uff0c\u7ee7\u7eed\u6269\u5bb9\n    if h.growing() {\n        growWork(t, h, bucket)\n    }\n    \/\/ \u6839\u636e hash \u503c\u7684\u4f4e B \u4f4d\u627e\u5230\u4f4d\u4e8e\u54ea\u4e2a\u6876\n    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))\n    \/\/ \u8ba1\u7b97 hash \u503c\u7684\u9ad8 8 \u4f4d\n    top := uint8(hash &gt;&gt; (sys.PtrSize*8 - 8))\n    if top &lt; minTopHash {\n        top += minTopHash\n    }\n\n    var inserti *uint8\n    var insertk unsafe.Pointer\n    var val unsafe.Pointer\n    for {\n        \/\/ \u904d\u5386\u5f53\u524d\u6876\u6240\u6709\u952e\u503c\uff0c\u67e5\u627e key \u5bf9\u5e94\u7684 value\n        for i := uintptr(0); i &lt; bucketCnt; i++ {\n            if b.tophash[i] != top {\n                if b.tophash[i] == empty &amp;&amp; inserti == nil {\n                    \/\/ \u5982\u679c\u5f80\u540e\u627e\u90fd\u6ca1\u6709\u627e\u5230\uff0c\u8fd9\u91cc\u5148\u8bb0\u5f55\u4e00\u4e2a\u6807\u8bb0\uff0c\u65b9\u4fbf\u627e\u4e0d\u5230\u4ee5\u540e\u63d2\u5165\u5230\u8fd9\u91cc\n                    inserti = &amp;b.tophash[i]\n                    \/\/ \u8ba1\u7b97\u51fa\u504f\u79fb i \u4e2a key \u503c\u7684\u4f4d\u7f6e\n                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\n                    \/\/ \u8ba1\u7b97\u51fa val \u6240\u5728\u7684\u4f4d\u7f6e\uff0c\u5f53\u524d\u6876\u7684\u9996\u5730\u5740 + 8\u4e2a key \u503c\u6240\u5360\u7684\u5927\u5c0f + i \u4e2a value \u503c\u6240\u5360\u7684\u5927\u5c0f\n                    val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\n                }\n                continue\n            }\n            \/\/ \u4f9d\u6b21\u53d6\u51fa key \u503c\n            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\n            \/\/ \u5982\u679c key \u503c\u662f\u4e00\u4e2a\u6307\u9488\uff0c\u90a3\u4e48\u5c31\u53d6\u51fa\u6539\u6307\u9488\u5bf9\u5e94\u7684 key \u503c\n            if t.indirectkey {\n                k = *((*unsafe.Pointer)(k))\n            }\n            \/\/ \u6bd4\u8f83 key \u503c\u662f\u5426\u76f8\u7b49\n            if !alg.equal(key, k) {\n                continue\n            }\n            \/\/ \u5982\u679c\u9700\u8981\u66f4\u65b0\uff0c\u90a3\u4e48\u5c31\u628a t.key \u62f7\u8d1d\u4ece k \u62f7\u8d1d\u5230 key\n            if t.needkeyupdate {\n                typedmemmove(t.key, k, key)\n            }\n            \/\/ \u8ba1\u7b97\u51fa val \u6240\u5728\u7684\u4f4d\u7f6e\uff0c\u5f53\u524d\u6876\u7684\u9996\u5730\u5740 + 8\u4e2a key \u503c\u6240\u5360\u7684\u5927\u5c0f + i \u4e2a value \u503c\u6240\u5360\u7684\u5927\u5c0f\n            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))\n            goto done\n        }\n        ovf := b.overflow(t)\n        if ovf == nil {\n            break\n        }\n        b = ovf\n    }\n\n    \/\/ \u6ca1\u6709\u627e\u5230\u5f53\u524d\u7684 key \u503c\uff0c\u5e76\u4e14\u68c0\u67e5\u6700\u5927\u8d1f\u8f7d\u56e0\u5b50\uff0c\u5982\u679c\u8fbe\u5230\u4e86\u6700\u5927\u8d1f\u8f7d\u56e0\u5b50\uff0c\u6216\u8005\u5b58\u5728\u5f88\u591a\u6ea2\u51fa\u7684\u6876\n    if !h.growing() &amp;&amp; (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {\n        \/\/ \u5f00\u59cb\u6269\u5bb9\n        hashGrow(t, h)\n        goto again \/\/ Growing the table invalidates everything, so try again\n    }\n    \/\/ \u5982\u679c\u627e\u4e0d\u5230\u4e00\u4e2a\u7a7a\u7684\u4f4d\u7f6e\u53ef\u4ee5\u63d2\u5165 key \u503c\n    if inserti == nil {\n        \/\/ all current buckets are full, allocate a new one.\n        \/\/ \u610f\u5473\u7740\u5f53\u524d\u6876\u5df2\u7ecf\u5168\u90e8\u6ee1\u4e86\uff0c\u90a3\u4e48\u5c31\u751f\u6210\u4e00\u4e2a\u65b0\u7684\n        newb := h.newoverflow(t, b)\n        inserti = &amp;newb.tophash[0]\n        insertk = add(unsafe.Pointer(newb), dataOffset)\n        val = add(insertk, bucketCnt*uintptr(t.keysize))\n    }\n\n    \/\/ store new key\/value at insert position\n    if t.indirectkey {\n        \/\/ \u5982\u679c\u662f\u5b58\u50a8 key \u503c\u7684\u6307\u9488\uff0c\u8fd9\u91cc\u5c31\u7528 insertk \u5b58\u50a8 key \u503c\u7684\u5730\u5740\n        kmem := newobject(t.key)\n        *(*unsafe.Pointer)(insertk) = kmem\n        insertk = kmem\n    }\n    if t.indirectvalue {\n        \/\/ \u5982\u679c\u662f\u5b58\u50a8 value \u503c\u7684\u6307\u9488\uff0c\u8fd9\u91cc\u5c31\u7528 val \u5b58\u50a8 key \u503c\u7684\u5730\u5740\n        vmem := newobject(t.elem)\n        *(*unsafe.Pointer)(val) = vmem\n    }\n    \/\/ \u5c06 t.key \u4ece insertk \u62f7\u8d1d\u5230 key \u7684\u4f4d\u7f6e\n    typedmemmove(t.key, insertk, key)\n    *inserti = top\n    \/\/ hmap \u4e2d\u4fdd\u5b58\u7684\u603b key \u503c\u7684\u6570\u91cf + 1\n    h.count++\n\ndone:\n    \/\/ \u7981\u6b62\u5e76\u53d1\u5199\n    if h.flags&amp;hashWriting == 0 {\n        throw(\"concurrent map writes\")\n    }\n    h.flags &amp;^= hashWriting\n    if t.indirectvalue {\n        \/\/ \u5982\u679c value \u91cc\u9762\u5b58\u50a8\u7684\u662f\u6307\u9488\uff0c\u90a3\u4e48\u53d6\u503c\u8be5\u6307\u9488\u6307\u5411\u7684 value \u503c\n        val = *((*unsafe.Pointer)(val))\n    }\n    return val\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u63d2\u5165 key \u7684\u8fc7\u7a0b\u4e2d\u548c\u67e5\u627e key \u6709\u51e0\u70b9\u4e0d\u540c\uff0c\u9700\u8981\u6ce8\u610f\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u5982\u679c\u627e\u5230\u8981\u63d2\u5165\u7684 key \uff0c\u53ea\u9700\u8981\u76f4\u63a5\u66f4\u65b0\u5bf9\u5e94\u7684 value \u503c\u5c31\u597d\u4e86\u3002 <\/li><li><ol><li>\u5982\u679c\u6ca1\u6709\u5728 bmap \u4e2d\u6ca1\u6709\u627e\u5230\u5f85\u63d2\u5165\u7684 key \uff0c\u8fd9\u4e48\u8fd9\u65f6\u5206\u51e0\u79cd\u60c5\u51b5\u3002<br> \u60c5\u51b5\u4e00: bmap \u4e2d\u8fd8\u6709\u7a7a\u4f4d\uff0c\u5728\u904d\u5386 bmap \u7684\u65f6\u5019\u9884\u5148\u6807\u8bb0\u7a7a\u4f4d\uff0c\u4e00\u65e6\u67e5\u627e\u7ed3\u675f\u4e5f\u6ca1\u6709\u627e\u5230 key\uff0c\u5c31\u628a key \u653e\u5230\u9884\u5148\u904d\u5386\u65f6\u5019\u6807\u8bb0\u7684\u7a7a\u4f4d\u4e0a\u3002<br> \u60c5\u51b5\u4e8c\uff1abmap\u4e2d\u5df2\u7ecf\u6ca1\u6709\u7a7a\u4f4d\u4e86\u3002\u8fd9\u4e2a\u65f6\u5019 bmap \u88c5\u7684\u5f88\u6ee1\u4e86\u3002\u6b64\u65f6\u9700\u8981\u68c0\u67e5\u4e00\u6b21\u6700\u5927\u8d1f\u8f7d\u56e0\u5b50\u662f\u5426\u5df2\u7ecf\u8fbe\u5230\u4e86\u3002\u5982\u679c\u8fbe\u5230\u4e86\uff0c\u7acb\u5373\u8fdb\u884c\u6269\u5bb9\u64cd\u4f5c\u3002\u6269\u5bb9\u4ee5\u540e\u5728\u65b0\u6876\u91cc\u9762\u63d2\u5165 key\uff0c\u6d41\u7a0b\u548c\u4e0a\u8ff0\u7684\u4e00\u81f4\u3002\u5982\u679c\u6ca1\u6709\u8fbe\u5230\u6700\u5927\u8d1f\u8f7d\u56e0\u5b50\uff0c\u90a3\u4e48\u5c31\u5728\u65b0\u751f\u6210\u4e00\u4e2a bmap\uff0c\u5e76\u628a\u524d\u4e00\u4e2a bmap \u7684 overflow \u6307\u9488\u6307\u5411\u65b0\u7684 bmap\u3002 <\/li><\/ol><\/li><li><ol><li>\u5728\u6269\u5bb9\u8fc7\u7a0b\u4e2d\uff0coldbucke t\u662f\u88ab\u51bb\u7ed3\u7684\uff0c\u67e5\u627e key \u65f6\u4f1a\u5728<br> oldbucket \u4e2d\u67e5\u627e\uff0c\u4f46\u4e0d\u4f1a\u5728 oldbucket \u4e2d\u63d2\u5165\u6570\u636e\u3002\u5982\u679c\u5728<br> oldbucket \u662f\u627e\u5230\u4e86\u76f8\u5e94\u7684key\uff0c\u505a\u6cd5\u662f\u5c06\u5b83\u8fc1\u79fb\u5230\u65b0 bmap \u540e\u52a0\u5165<br> evalucated \u6807\u8bb0\u3002 <\/li><\/ol><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\u5176\u4ed6\u6d41\u7a0b\u548c\u67e5\u627e key \u57fa\u672c\u4e00\u81f4\uff0c\u8fd9\u91cc\u5c31\u4e0d\u518d\u8d58\u8ff0\u4e86\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u5220\u9664 Key<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {\n    if raceenabled &amp;&amp; h != nil {\n        \/\/ \u83b7\u53d6 caller \u7684 \u7a0b\u5e8f\u8ba1\u6570\u5668 program counter\n        callerpc := getcallerpc(unsafe.Pointer(&amp;t))\n        \/\/ \u83b7\u53d6 mapdelete \u7684\u7a0b\u5e8f\u8ba1\u6570\u5668 program counter\n        pc := funcPC(mapdelete)\n        racewritepc(unsafe.Pointer(h), callerpc, pc)\n        raceReadObjectPC(t.key, key, callerpc, pc)\n    }\n    if msanenabled &amp;&amp; h != nil {\n        msanread(key, t.key.size)\n    }\n    if h == nil || h.count == 0 {\n        return\n    }\n    \/\/ \u5982\u679c\u591a\u7ebf\u7a0b\u8bfb\u5199\uff0c\u76f4\u63a5\u629b\u51fa\u5f02\u5e38\n    \/\/ \u5e76\u53d1\u68c0\u67e5 go hashmap \u4e0d\u652f\u6301\u5e76\u53d1\u8bbf\u95ee\n    if h.flags&amp;hashWriting != 0 {\n        throw(\"concurrent map writes\")\n    }\n\n    alg := t.key.alg\n    \/\/ \u8ba1\u7b97 key \u503c\u7684 hash \u503c\n    hash := alg.hash(key, uintptr(h.hash0))\n\n    \/\/ \u5728\u8ba1\u7b97\u5b8c hash \u503c\u4ee5\u540e\u7acb\u5373\u8bbe\u7f6e hashWriting \u53d8\u91cf\u7684\u503c\uff0c\u5982\u679c\u5728\u8ba1\u7b97 hash \u503c\u7684\u8fc7\u7a0b\u4e2d\u6ca1\u6709\u5b8c\u5168\u5199\u5b8c\uff0c\u53ef\u80fd\u4f1a\u5bfc\u81f4 panic\n    h.flags |= hashWriting\n\n    bucket := hash &amp; (uintptr(1)&lt;&lt;h.B - 1)\n    \/\/ \u5982\u679c\u8fd8\u5728\u6269\u5bb9\u4e2d\uff0c\u7ee7\u7eed\u6269\u5bb9\n    if h.growing() {\n        growWork(t, h, bucket)\n    }\n    \/\/ \u6839\u636e hash \u503c\u7684\u4f4e B \u4f4d\u627e\u5230\u4f4d\u4e8e\u54ea\u4e2a\u6876\n    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))\n    \/\/ \u8ba1\u7b97 hash \u503c\u7684\u9ad8 8 \u4f4d\n    top := uint8(hash &gt;&gt; (sys.PtrSize*8 - 8))\n    if top &lt; minTopHash {\n        top += minTopHash\n    }\n    for {\n        \/\/ \u904d\u5386\u5f53\u524d\u6876\u6240\u6709\u952e\u503c\uff0c\u67e5\u627e key \u5bf9\u5e94\u7684 value\n        for i := uintptr(0); i &lt; bucketCnt; i++ {\n            if b.tophash[i] != top {\n                continue\n            }\n            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))\n            \/\/ \u5982\u679c k \u662f\u6307\u5411 key \u7684\u6307\u9488\uff0c\u90a3\u4e48\u8fd9\u91cc\u9700\u8981\u53d6\u51fa key \u7684\u503c\n            k2 := k\n            if t.indirectkey {\n                k2 = *((*unsafe.Pointer)(k2))\n            }\n            if !alg.equal(key, k2) {\n                continue\n            }\n            \/\/ key \u7684\u6307\u9488\u7f6e\u7a7a\n            if t.indirectkey {\n                *(*unsafe.Pointer)(k) = nil\n            } else {\n            \/\/ \u6e05\u9664 key \u7684\u5185\u5b58\n                typedmemclr(t.key, k)\n            }\n            v := unsafe.Pointer(uintptr(unsafe.Pointer(b)) + dataOffset + bucketCnt*uintptr(t.keysize) + i*uintptr(t.valuesize))\n            \/\/ value \u7684\u6307\u9488\u7f6e\u7a7a\n            if t.indirectvalue {\n                *(*unsafe.Pointer)(v) = nil\n            } else {\n            \/\/ \u6e05\u9664 value \u7684\u5185\u5b58\n                typedmemclr(t.elem, v)\n            }\n            \/\/ \u6e05\u7a7a tophash \u91cc\u9762\u7684\u503c\n            b.tophash[i] = empty\n            \/\/ map \u91cc\u9762 key \u7684\u603b\u4e2a\u6570\u51cf1\n            h.count--\n            goto done\n        }\n        \/\/ \u5982\u679c\u6ca1\u6709\u627e\u5230\uff0c\u90a3\u4e48\u5c31\u7ee7\u7eed\u67e5\u627e overflow \u6876\uff0c\u4e00\u76f4\u904d\u5386\u5230\u6700\u540e\u4e00\u4e2a\n        b = b.overflow(t)\n        if b == nil {\n            goto done\n        }\n    }\n\ndone:\n    if h.flags&amp;hashWriting == 0 {\n        throw(\"concurrent map writes\")\n    }\n    h.flags &amp;^= hashWriting\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u5220\u9664\u64cd\u4f5c\u4e3b\u8981\u6d41\u7a0b\u548c\u67e5\u627e key \u6d41\u7a0b\u4e5f\u5dee\u4e0d\u591a\uff0c\u627e\u5230\u5bf9\u5e94\u7684 key \u4ee5\u540e\uff0c\u5982\u679c\u662f\u6307\u9488\u6307\u5411\u539f\u6765\u7684 key\uff0c\u5c31\u628a\u6307\u9488\u7f6e\u4e3a nil\u3002\u5982\u679c\u662f\u503c\u5c31\u6e05\u7a7a\u5b83\u6240\u5728\u7684\u5185\u5b58\u3002\u8fd8\u8981\u6e05\u7406 tophash \u91cc\u9762\u7684\u503c\u6700\u540e\u628a map \u7684 key \u603b\u4e2a\u6570\u8ba1\u6570\u5668\u51cf1 \u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c\u5728\u6269\u5bb9\u8fc7\u7a0b\u4e2d\uff0c\u5220\u9664\u64cd\u4f5c\u4f1a\u5728\u6269\u5bb9\u4ee5\u540e\u5728\u65b0\u7684 bmap \u91cc\u9762\u5220\u9664\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u67e5\u627e\u7684\u8fc7\u7a0b\u4f9d\u65e7\u4f1a\u4e00\u76f4\u904d\u5386\u5230\u94fe\u8868\u7684\u6700\u540e\u4e00\u4e2a bmap \u6876\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u589e\u91cf\u7ffb\u500d\u6269\u5bb9<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u90e8\u5206\u7b97\u662f\u6574\u4e2a Map \u5b9e\u73b0\u6bd4\u8f83\u6838\u5fc3\u7684\u90e8\u5206\u4e86\u3002\u6211\u4eec\u90fd\u77e5\u9053 Map \u5728\u4e0d\u65ad\u7684\u88c5\u8f7d Key \u503c\u7684\u65f6\u5019\uff0c\u67e5\u627e\u6548\u7387\u4f1a\u53d8\u7684\u8d8a\u6765\u8d8a\u4f4e\uff0c\u5982\u679c\u6b64\u65f6\u4e0d\u8fdb\u884c\u6269\u5bb9\u64cd\u4f5c\u7684\u8bdd\uff0c\u54c8\u5e0c\u51b2\u7a81\u4f7f\u5f97\u94fe\u8868\u53d8\u5f97\u8d8a\u6765\u8d8a\u957f\uff0c\u6027\u80fd\u4e5f\u5c31\u8d8a\u6765\u8d8a\u5dee\u3002\u6269\u5bb9\u52bf\u5728\u5fc5\u884c\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4f46\u662f\u6269\u5bb9\u8fc7\u7a0b\u4e2d\u5982\u679c\u963b\u65ad\u4e86 Key \u503c\u7684\u5199\u5165\uff0c\u5728\u5904\u7406\u5927\u6570\u636e\u7684\u65f6\u5019\u4f1a\u5bfc\u81f4\u6709\u4e00\u6bb5\u4e0d\u54cd\u5e94\u7684\u65f6\u95f4\uff0c\u5982\u679c\u7528\u5728\u9ad8\u5b9e\u65f6\u7684\u7cfb\u7edf\u4e2d\uff0c\u90a3\u4e48\u6bcf\u6b21\u6269\u5bb9\u90fd\u4f1a\u5361\u51e0\u79d2\uff0c\u8fd9\u6bb5\u65f6\u95f4\u90fd\u4e0d\u80fd\u76f8\u5e94\u4efb\u4f55\u8bf7\u6c42\u3002\u8fd9\u79cd\u6027\u80fd\u660e\u663e\u662f\u4e0d\u80fd\u63a5\u53d7\u7684\u3002\u6240\u4ee5\u8981\u65e2\u4e0d\u5f71\u54cd\u5199\u5165\uff0c\u4e5f\u540c\u65f6\u8981\u8fdb\u884c\u6269\u5bb9\u3002\u8fd9\u4e2a\u65f6\u5019\u5c31\u5e94\u8be5\u589e\u91cf\u6269\u5bb9\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u91cc\u589e\u91cf\u6269\u5bb9\u5176\u5b9e\u7528\u9014\u5df2\u7ecf\u5f88\u5e7f\u6cdb\u4e86\uff0c\u4e4b\u524d\u4e3e\u4f8b\u7684 Redis \u5c31\u91c7\u7528\u7684\u589e\u91cf\u6269\u5bb9\u7b56\u7565\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765\u770b\u770b Go \u662f\u600e\u4e48\u8fdb\u884c\u589e\u91cf\u6269\u5bb9\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Go \u7684 mapassign \u63d2\u5165 Key \u503c\u3001mapdelete \u5220\u9664 key \u503c\u7684\u65f6\u5019\u90fd\u4f1a\u68c0\u67e5\u5f53\u524d\u662f\u5426\u5728\u6269\u5bb9\u4e2d\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func growWork(t *maptype, h *hmap, bucket uintptr) {\n    \/\/ \u786e\u4fdd\u6211\u4eec\u8fc1\u79fb\u4e86\u6240\u6709 oldbucket\n    evacuate(t, h, bucket&amp;h.oldbucketmask())\n\n    \/\/ \u518d\u8fc1\u79fb\u4e00\u4e2a\u6807\u8bb0\u8fc7\u7684\u6876\n    if h.growing() {\n        evacuate(t, h, h.nevacuate)\n    }\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ece\u8fd9\u91cc\u6211\u4eec\u53ef\u4ee5\u770b\u5230\uff0c\u6bcf\u6b21\u6267\u884c\u4e00\u6b21 growWork \u4f1a\u8fc1\u79fb2\u4e2a\u6876\u3002\u4e00\u4e2a\u662f\u5f53\u524d\u7684\u6876\uff0c\u8fd9\u7b97\u662f\u5c40\u90e8\u8fc1\u79fb\uff0c\u53e6\u5916\u4e00\u4e2a\u662f hmap \u91cc\u9762\u6307\u5411\u7684 nevacuate \u7684\u6876\uff0c\u8fd9\u7b97\u662f\u589e\u91cf\u8fc1\u79fb\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u63d2\u5165 Key \u503c\u7684\u65f6\u5019\uff0c\u5982\u679c\u5f53\u524d\u5728\u6269\u5bb9\u8fc7\u7a0b\u4e2d\uff0coldbucket \u662f\u88ab\u51bb\u7ed3\u7684\uff0c\u67e5\u627e\u65f6\u4f1a\u5148\u5728 oldbucket \u4e2d\u67e5\u627e\uff0c\u4f46\u4e0d\u4f1a\u5728oldbucket\u4e2d\u63d2\u5165\u6570\u636e\u3002\u53ea\u6709\u5728 oldbucket \u627e\u5230\u4e86\u76f8\u5e94\u7684 key\uff0c\u90a3\u4e48\u5c06\u5b83\u8fc1\u79fb\u5230\u65b0 bucket \u540e\u52a0\u5165 evalucated \u6807\u8bb0\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u5220\u9664 Key \u503c\u7684\u65f6\u5019\uff0c\u5982\u679c\u5f53\u524d\u5728\u6269\u5bb9\u8fc7\u7a0b\u4e2d\uff0c\u4f18\u5148\u67e5\u627e bucket\uff0c\u5373\u65b0\u6876\uff0c\u627e\u5230\u4e00\u4e2a\u4ee5\u540e\u628a\u5b83\u5bf9\u5e94\u7684 Key\u3001Value \u90fd\u7f6e\u7a7a\u3002\u5982\u679c bucket \u91cc\u9762\u627e\u4e0d\u5230\uff0c\u624d\u4f1a\u53bb oldbucket \u4e2d\u53bb\u67e5\u627e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6bcf\u6b21\u63d2\u5165 Key \u503c\u7684\u65f6\u5019\uff0c\u90fd\u4f1a\u5224\u65ad\u4e00\u4e0b\u5f53\u524d\u88c5\u8f7d\u56e0\u5b50\u662f\u5426\u8d85\u8fc7\u4e86 6.5\uff0c\u5982\u679c\u8fbe\u5230\u4e86\u8fd9\u4e2a\u6781\u9650\uff0c\u5c31\u7acb\u5373\u6267\u884c\u6269\u5bb9\u64cd\u4f5c hashGrow\u3002\u8fd9\u662f\u6269\u5bb9\u4e4b\u524d\u7684\u51c6\u5907\u5de5\u4f5c\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func hashGrow(t *maptype, h *hmap) {\n    \/\/ \u5982\u679c\u8fbe\u5230\u4e86\u6700\u5927\u88c5\u8f7d\u56e0\u5b50\uff0c\u5c31\u9700\u8981\u6269\u5bb9\u3002\n    \/\/ \u4e0d\u7136\u7684\u8bdd\uff0c\u4e00\u4e2a\u6876\u540e\u9762\u94fe\u8868\u8ddf\u7740\u4e00\u5927\u5806\u7684 overflow \u6876\n    bigger := uint8(1)\n    if !overLoadFactor(int64(h.count), h.B) {\n        bigger = 0\n        h.flags |= sameSizeGrow\n    }\n    \/\/ \u628a hmap \u7684\u65e7\u6876\u7684\u6307\u9488\u6307\u5411\u5f53\u524d\u6876\n    oldbuckets := h.buckets\n    \/\/ \u751f\u6210\u65b0\u7684\u6269\u5bb9\u4ee5\u540e\u7684\u6876\uff0chmap \u7684 buckets \u6307\u9488\u6307\u5411\u6269\u5bb9\u4ee5\u540e\u7684\u6876\u3002\n    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger)\n\n    flags := h.flags &amp;^ (iterator | oldIterator)\n    if h.flags&amp;iterator != 0 {\n        flags |= oldIterator\n    }\n    \/\/ B \u52a0\u4e0a\u65b0\u7684\u503c\n    h.B += bigger\n    h.flags = flags\n    \/\/ \u65e7\u6876\u6307\u9488\u6307\u5411\u5f53\u524d\u6876\n    h.oldbuckets = oldbuckets\n    \/\/ \u65b0\u6876\u6307\u9488\u6307\u5411\u6269\u5bb9\u4ee5\u540e\u7684\u6876\n    h.buckets = newbuckets\n    h.nevacuate = 0\n    h.noverflow = 0\n\n    if h.extra != nil &amp;&amp; h.extra.overflow[0] != nil {\n        if h.extra.overflow[1] != nil {\n            throw(\"overflow is not nil\")\n        }\n        \/\/ \u4ea4\u6362 overflow[0] \u548c overflow[1] \u7684\u6307\u5411\n        h.extra.overflow[1] = h.extra.overflow[0]\n        h.extra.overflow[0] = nil\n    }\n    if nextOverflow != nil {\n        if h.extra == nil {\n            \/\/ \u751f\u6210 mapextra\n            h.extra = new(mapextra)\n        }\n        h.extra.nextOverflow = nextOverflow\n    }\n\n    \/\/ \u5b9e\u9645\u62f7\u8d1d\u952e\u503c\u5bf9\u7684\u8fc7\u7a0b\u5728 evacuate() \u4e2d\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u7528\u56fe\u8868\u793a\u51fa\u5b83\u7684\u6d41\u7a0b\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/302dd77d-ab11-4bb8-911d-27153f7b86d2.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">hashGrow \u64cd\u4f5c\u7b97\u662f\u6269\u5bb9\u4e4b\u524d\u7684\u51c6\u5907\u5de5\u4f5c\uff0c\u5b9e\u9645\u62f7\u8d1d\u7684\u8fc7\u7a0b\u5728 evacuate \u4e2d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">hashGrow \u64cd\u4f5c\u4f1a\u5148\u751f\u6210\u6269\u5bb9\u4ee5\u540e\u7684\u65b0\u7684\u6876\u6570\u7ec4\u3002\u65b0\u7684\u6876\u6570\u7ec4\u7684\u5927\u5c0f\u662f\u4e4b\u524d\u76842\u500d\u3002\u7136\u540e hmap \u7684 buckets \u4f1a\u6307\u5411\u8fd9\u4e2a\u65b0\u7684\u6269\u5bb9\u4ee5\u540e\u7684\u6876\uff0c\u800c oldbuckets \u4f1a\u6307\u5411\u5f53\u524d\u7684\u6876\u6570\u7ec4\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5904\u7406\u5b8c hmap \u4ee5\u540e\uff0c\u518d\u5904\u7406 mapextra\uff0cnextOverflow \u7684\u6307\u5411\u539f\u6765\u7684 overflow \u6307\u9488\uff0coverflow \u6307\u9488\u7f6e\u4e3a null\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5230\u6b64\u5c31\u505a\u597d\u6269\u5bb9\u4e4b\u524d\u7684\u51c6\u5907\u5de5\u4f5c\u4e86\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>func evacuate(t *maptype, h *hmap, oldbucket uintptr) {\n    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))\n    \/\/ \u5728\u51c6\u5907\u6269\u5bb9\u4e4b\u524d\u6876\u7684\u4e2a\u6570\n    newbit := h.noldbuckets()\n    alg := t.key.alg\n    if !evacuated(b) {\n        \/\/ TODO: reuse overflow buckets instead of using new ones, if there\n        \/\/ is no iterator using the old buckets.  (If !oldIterator.)\n\n        var (\n            x, y   *bmap          \/\/ \u5728\u65b0\u6876\u91cc\u9762 \u4f4e\u4f4d\u6876\u548c\u9ad8\u4f4d\u6876\n            xi, yi int            \/\/ key \u548c value \u503c\u7684\u7d22\u5f15\u503c\u5206\u522b\u4e3a xi \uff0c yi \n            xk, yk unsafe.Pointer \/\/ \u6307\u5411 x \u548c y \u7684 key \u503c\u7684\u6307\u9488 \n            xv, yv unsafe.Pointer \/\/ \u6307\u5411 x \u548c y \u7684 value \u503c\u7684\u6307\u9488  \n        )\n        \/\/ \u65b0\u6876\u4e2d\u4f4e\u4f4d\u7684\u4e00\u4e9b\u6876\n        x = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))\n        xi = 0\n        \/\/ \u6269\u5bb9\u4ee5\u540e\u7684\u65b0\u6876\u4e2d\u4f4e\u4f4d\u7684\u7b2c\u4e00\u4e2a key \u503c\n        xk = add(unsafe.Pointer(x), dataOffset)\n        \/\/ \u6269\u5bb9\u4ee5\u540e\u7684\u65b0\u6876\u4e2d\u4f4e\u4f4d\u7684\u7b2c\u4e00\u4e2a key \u503c\u5bf9\u5e94\u7684 value \u503c\n        xv = add(xk, bucketCnt*uintptr(t.keysize))\n        \/\/ \u5982\u679c\u4e0d\u662f\u7b49\u91cf\u6269\u5bb9\n        if !h.sameSizeGrow() {\n            y = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))\n            yi = 0\n            yk = add(unsafe.Pointer(y), dataOffset)\n            yv = add(yk, bucketCnt*uintptr(t.keysize))\n        }\n        \/\/ \u4f9d\u6b21\u904d\u5386\u6ea2\u51fa\u6876\n        for ; b != nil; b = b.overflow(t) {\n            k := add(unsafe.Pointer(b), dataOffset)\n            v := add(k, bucketCnt*uintptr(t.keysize))\n            \/\/ \u904d\u5386 key - value \u952e\u503c\u5bf9\n            for i := 0; i &lt; bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {\n                top := b.tophash[i]\n                if top == empty {\n                    b.tophash[i] = evacuatedEmpty\n                    continue\n                }\n                if top &lt; minTopHash {\n                    throw(\"bad map state\")\n                }\n                k2 := k\n                \/\/ key \u503c\u5982\u679c\u662f\u6307\u9488\uff0c\u5219\u53d6\u51fa\u6307\u9488\u91cc\u9762\u7684\u503c\n                if t.indirectkey {\n                    k2 = *((*unsafe.Pointer)(k2))\n                }\n                useX := true\n                if !h.sameSizeGrow() {\n                    \/\/ \u5982\u679c\u4e0d\u662f\u7b49\u91cf\u6269\u5bb9\uff0c\u5219\u9700\u8981\u91cd\u65b0\u8ba1\u7b97 hash \u503c\uff0c\u4e0d\u7ba1\u662f\u9ad8\u4f4d\u6876 x \u4e2d\uff0c\u8fd8\u662f\u4f4e\u4f4d\u6876 y \u4e2d\n                    hash := alg.hash(k2, uintptr(h.hash0))\n                    if h.flags&amp;iterator != 0 {\n                        if !t.reflexivekey &amp;&amp; !alg.equal(k2, k2) {\n                            \/\/ \u5982\u679c\u4e24\u4e2a key \u4e0d\u76f8\u7b49\uff0c\u90a3\u4e48\u4ed6\u4eec\u4fe9\u6781\u5927\u53ef\u80fd\u65e7\u7684 hash \u503c\u4e5f\u4e0d\u76f8\u7b49\u3002\n                            \/\/ tophash \u5bf9\u8981\u8fc1\u79fb\u7684 key \u503c\u4e5f\u662f\u6ca1\u6709\u591a\u5927\u610f\u4e49\u7684\uff0c\u6240\u4ee5\u6211\u4eec\u7528\u4f4e\u4f4d\u7684 tophash \u8f85\u52a9\u6269\u5bb9\uff0c\u6807\u8bb0\u4e00\u4e9b\u72b6\u6001\u3002\n                            \/\/ \u4e3a\u4e0b\u4e00\u4e2a\u7ea7 level \u91cd\u65b0\u8ba1\u7b97\u4e00\u4e9b\u65b0\u7684\u968f\u673a\u7684 hash \u503c\u3002\u4ee5\u81f3\u4e8e\u8fd9\u4e9b key \u503c\u5728\u591a\u6b21\u6269\u5bb9\u4ee5\u540e\u4f9d\u65e7\u53ef\u4ee5\u5747\u5300\u5206\u5e03\u5728\u6240\u6709\u6876\u4e2d\n                            \/\/ \u5224\u65ad top \u7684\u6700\u4f4e\u4f4d\u662f\u5426\u4e3a1\n                            if top&amp;1 != 0 {\n                                hash |= newbit\n                            } else {\n                                hash &amp;^= newbit\n                            }\n                            top = uint8(hash &gt;&gt; (sys.PtrSize*8 - 8))\n                            if top &lt; minTopHash {\n                                top += minTopHash\n                            }\n                        }\n                    }\n                    useX = hash&amp;newbit == 0\n                }\n                if useX {\n                    \/\/ \u6807\u8bb0\u4f4e\u4f4d\u6876\u5b58\u5728 tophash \u4e2d\n                    b.tophash[i] = evacuatedX\n                    \/\/ \u5982\u679c key \u7684\u7d22\u5f15\u503c\u5230\u4e86\u6876\u6700\u540e\u4e00\u4e2a\uff0c\u5c31\u65b0\u5efa\u4e00\u4e2a overflow\n                    if xi == bucketCnt {\n                        newx := h.newoverflow(t, x)\n                        x = newx\n                        xi = 0\n                        xk = add(unsafe.Pointer(x), dataOffset)\n                        xv = add(xk, bucketCnt*uintptr(t.keysize))\n                    }\n                    \/\/ \u628a hash \u7684\u9ad88\u4f4d\u518d\u6b21\u5b58\u5728 tophash \u4e2d\n                    x.tophash[xi] = top\n                    if t.indirectkey {\n                        \/\/ \u5982\u679c\u662f\u6307\u9488\u6307\u5411 key \uff0c\u90a3\u4e48\u62f7\u8d1d\u6307\u9488\u6307\u5411\n                        *(*unsafe.Pointer)(xk) = k2 \/\/ copy pointer\n                    } else {\n                        \/\/ \u5982\u679c\u662f\u6307\u9488\u6307\u5411 key \uff0c\u90a3\u4e48\u8fdb\u884c\u503c\u62f7\u8d1d\n                        typedmemmove(t.key, xk, k) \/\/ copy value\n                    }\n                    \/\/ \u540c\u7406\u62f7\u8d1d value\n                    if t.indirectvalue {\n                        *(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v)\n                    } else {\n                        typedmemmove(t.elem, xv, v)\n                    }\n                    \/\/ \u7ee7\u7eed\u8fc1\u79fb\u4e0b\u4e00\u4e2a\n                    xi++\n                    xk = add(xk, uintptr(t.keysize))\n                    xv = add(xv, uintptr(t.valuesize))\n                } else {\n                    \/\/ \u8fd9\u91cc\u662f\u9ad8\u4f4d\u6876 y\uff0c\u8fc1\u79fb\u8fc7\u7a0b\u548c\u4e0a\u8ff0\u4f4e\u4f4d\u6876 x \u4e00\u81f4\uff0c\u4e0b\u9762\u5c31\u4e0d\u518d\u8d58\u8ff0\u4e86\n                    b.tophash[i] = evacuatedY\n                    if yi == bucketCnt {\n                        newy := h.newoverflow(t, y)\n                        y = newy\n                        yi = 0\n                        yk = add(unsafe.Pointer(y), dataOffset)\n                        yv = add(yk, bucketCnt*uintptr(t.keysize))\n                    }\n                    y.tophash[yi] = top\n                    if t.indirectkey {\n                        *(*unsafe.Pointer)(yk) = k2\n                    } else {\n                        typedmemmove(t.key, yk, k)\n                    }\n                    if t.indirectvalue {\n                        *(*unsafe.Pointer)(yv) = *(*unsafe.Pointer)(v)\n                    } else {\n                        typedmemmove(t.elem, yv, v)\n                    }\n                    yi++\n                    yk = add(yk, uintptr(t.keysize))\n                    yv = add(yv, uintptr(t.valuesize))\n                }\n            }\n        }\n        \/\/ Unlink the overflow buckets &amp; clear key\/value to help GC.\n        if h.flags&amp;oldIterator == 0 {\n            b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))\n            \/\/ Preserve b.tophash because the evacuation\n            \/\/ state is maintained there.\n            if t.bucket.kind&amp;kindNoPointers == 0 {\n                memclrHasPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)\n            } else {\n                memclrNoHeapPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)\n            }\n        }\n    }\n\n    \/\/ Advance evacuation mark\n    if oldbucket == h.nevacuate {\n        h.nevacuate = oldbucket + 1\n        \/\/ Experiments suggest that 1024 is overkill by at least an order of magnitude.\n        \/\/ Put it in there as a safeguard anyway, to ensure O(1) behavior.\n        stop := h.nevacuate + 1024\n        if stop &gt; newbit {\n            stop = newbit\n        }\n        for h.nevacuate != stop &amp;&amp; bucketEvacuated(t, h, h.nevacuate) {\n            h.nevacuate++\n        }\n        if h.nevacuate == newbit { \/\/ newbit == # of oldbuckets\n            \/\/ Growing is all done. Free old main bucket array.\n            h.oldbuckets = nil\n            \/\/ Can discard old overflow buckets as well.\n            \/\/ If they are still referenced by an iterator,\n            \/\/ then the iterator holds a pointers to the slice.\n            if h.extra != nil {\n                h.extra.overflow[1] = nil\n            }\n            h.flags &amp;^= sameSizeGrow\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u8ff0\u51fd\u6570\u5c31\u662f\u8fc1\u79fb\u8fc7\u7a0b\u6700\u6838\u5fc3\u7684\u62f7\u8d1d\u5de5\u4f5c\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6574\u4e2a\u8fc1\u79fb\u8fc7\u7a0b\u5e76\u4e0d\u96be\u3002\u8fd9\u91cc\u9700\u8981\u8bf4\u660e\u7684\u662f x \uff0cy \u4ee3\u8868\u7684\u610f\u4e49\u3002\u7531\u4e8e\u6269\u5bb9\u4ee5\u540e\uff0c\u65b0\u7684\u6876\u6570\u7ec4\u662f\u539f\u6765\u6876\u6570\u7ec4\u76842\u500d\u3002\u7528 x \u4ee3\u8868\u65b0\u7684\u6876\u6570\u7ec4\u91cc\u9762\u4f4e\u4f4d\u7684\u90a3\u4e00\u534a\uff0c\u7528 y \u4ee3\u8868\u9ad8\u4f4d\u7684\u90a3\u4e00\u534a\u3002\u5176\u4ed6\u7684\u53d8\u91cf\u5c31\u662f\u4e00\u4e9b\u6807\u8bb0\u4e86\uff0c\u6e38\u6807\u548c\u6807\u8bb0 key &#8211; value \u539f\u6765\u6240\u5728\u7684\u4f4d\u7f6e\u3002\u8be6\u7ec6\u7684\u89c1\u4ee3\u7801\u6ce8\u91ca\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/www.xttblog.com\/img\/20230909\/48.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u56fe\u4e2d\u8868\u793a\u4e86\u8fc1\u79fb\u5f00\u59cb\u4e4b\u540e\u7684\u8fc7\u7a0b\u3002\u53ef\u4ee5\u770b\u5230\u65e7\u7684\u6876\u6570\u7ec4\u91cc\u9762\u7684\u6876\u5728\u8fc1\u79fb\u5230\u65b0\u7684\u6876\u4e2d\uff0c\u5e76\u4e14\u65b0\u7684\u6876\u4e5f\u5728\u4e0d\u65ad\u7684\u5199\u5165\u65b0\u7684 key \u503c\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/0aafc48a-679a-43e2-9056-f88cd0dd51fb.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e00\u76f4\u62f7\u8d1d\u952e\u503c\u5bf9\uff0c\u76f4\u5230\u65e7\u6876\u4e2d\u6240\u6709\u7684\u952e\u503c\u90fd\u62f7\u8d1d\u5230\u4e86\u65b0\u7684\u6876\u4e2d\u3002<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/files.mdnice.com\/user\/656\/b2a6909a-0c9a-4956-b177-e2283fa1a025.png\" alt=\"\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u540e\u4e00\u6b65\u5c31\u662f\u91ca\u653e\u65e7\u6876\uff0coldbuckets \u7684\u6307\u9488\u7f6e\u4e3a null\u3002\u5230\u6b64\uff0c\u4e00\u6b21\u8fc1\u79fb\u8fc7\u7a0b\u5c31\u5b8c\u5168\u7ed3\u675f\u4e86\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7b49\u91cf\u6269\u5bb9<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e25\u683c\u610f\u4e49\u4e0a\u8fd9\u79cd\u65b9\u5f0f\u5e76\u4e0d\u80fd\u7b97\u662f\u6269\u5bb9\u3002\u4f46\u662f\u51fd\u6570\u540d\u662f Grow\uff0c\u59d1\u4e14\u6682\u65f6\u5c31\u8fd9\u4e48\u53eb\u5427\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 go1.8 \u7684\u7248\u672c\u5f00\u59cb\uff0c\u6dfb\u52a0\u4e86 sameSizeGrow\uff0c\u5f53 overflow buckets<br>\n\u7684\u6570\u91cf\u8d85\u8fc7\u4e00\u5b9a\u6570\u91cf (2^B) \u4f46\u88c5\u8f7d\u56e0\u5b50\u53c8\u672a\u8fbe\u5230 6.5 \u7684\u65f6\u5019\uff0c\u6b64\u65f6\u53ef\u80fd\u5b58\u5728\u90e8\u5206\u7a7a\u7684bucket\uff0c\u5373 bucket \u7684\u4f7f\u7528\u7387\u4f4e\uff0c\u8fd9\u65f6\u4f1a\u89e6\u53d1sameSizeGrow\uff0c\u5373 B \u4e0d\u53d8\uff0c\u4f46\u8d70\u6570\u636e\u8fc1\u79fb\u6d41\u7a0b\uff0c\u5c06 oldbuckets \u7684\u6570\u636e\u91cd\u65b0\u7d27\u51d1\u6392\u5217\u63d0\u9ad8 bucket \u7684\u5229\u7528\u7387\u3002\u5f53\u7136\u5728 sameSizeGrow \u8fc7\u7a0b\u4e2d\uff0c\u4e0d\u4f1a\u89e6\u53d1 loadFactorGrow\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Map \u5b9e\u73b0\u4e2d\u7684\u4e00\u4e9b\u4f18\u5316<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8bfb\u5230\u8fd9\u91cc\uff0c\u76f8\u4fe1\u8bfb\u8005\u5fc3\u91cc\u5e94\u8be5\u5f88\u6e05\u695a\u5982\u4f55\u8bbe\u8ba1\u5e76\u5b9e\u73b0\u4e00\u4e2a Map \u4e86\u5427\u3002\u5305\u62ec Map \u4e2d\u7684\u5404\u79cd\u64cd\u4f5c\u7684\u5b9e\u73b0\u3002\u5728\u63a2\u7a76\u5982\u4f55\u5b9e\u73b0\u4e00\u4e2a\u7ebf\u7a0b\u5b89\u5168\u7684 Map \u4e4b\u524d\uff0c\u5148\u628a\u4e4b\u524d\u8bf4\u5230\u4e2a\u4e00\u4e9b\u4eae\u70b9\u4f18\u5316\u70b9\uff0c\u5c0f\u7ed3\u4e00\u4e0b\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Redis \u4e2d\uff0c\u91c7\u7528\u589e\u91cf\u5f0f\u6269\u5bb9\u7684\u65b9\u5f0f\u5904\u7406\u54c8\u5e0c\u51b2\u7a81\u3002\u5f53\u5e73\u5747\u67e5\u627e\u957f\u5ea6\u8d85\u8fc7 5 \u7684\u65f6\u5019\u5c31\u4f1a\u89e6\u53d1\u589e\u91cf\u6269\u5bb9\u64cd\u4f5c\uff0c\u4fdd\u8bc1 hash \u8868\u7684\u9ad8\u6027\u80fd\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u540c\u65f6 Redis \u91c7\u7528\u5934\u63d2\u6cd5\uff0c\u4fdd\u8bc1\u63d2\u5165 key \u503c\u65f6\u5019\u7684\u6027\u80fd\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Java \u4e2d\uff0c\u5f53\u6876\u7684\u4e2a\u6570\u8d85\u8fc7\u4e8664\u4e2a\u4ee5\u540e\uff0c\u5e76\u4e14\u51b2\u7a81\u8282\u70b9\u4e3a8\u6216\u8005\u5927\u4e8e8\uff0c\u8fd9\u4e2a\u65f6\u5019\u5c31\u4f1a\u89e6\u53d1\u7ea2\u9ed1\u6811\u8f6c\u6362\u3002\u8fd9\u6837\u80fd\u4fdd\u8bc1\u94fe\u8868\u5728\u5f88\u957f\u7684\u60c5\u51b5\u4e0b\uff0c\u67e5\u627e\u957f\u5ea6\u4f9d\u65e7\u4e0d\u4f1a\u592a\u957f\uff0c\u5e76\u4e14\u7ea2\u9ed1\u6811\u4fdd\u8bc1\u6700\u5dee\u60c5\u51b5\u4e0b\u4e5f\u652f\u6301 O(log n) \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Java \u5728\u8fc1\u79fb\u4e4b\u540e\u6709\u4e00\u4e2a\u975e\u5e38\u597d\u7684\u8bbe\u8ba1\uff0c\u53ea\u9700\u8981\u6bd4\u8f83\u8fc1\u79fb\u4e4b\u540e\u6876\u4e2a\u6570\u7684\u6700\u9ad8\u4f4d\u662f\u5426\u4e3a0\uff0c\u5982\u679c\u662f0\uff0ckey \u5728\u65b0\u6876\u5185\u7684\u76f8\u5bf9\u4f4d\u7f6e\u4e0d\u53d8\uff0c\u5982\u679c\u662f1\uff0c\u5219\u52a0\u4e0a\u6876\u7684\u65e7\u7684\u6876\u7684\u4e2a\u6570 oldCap \u5c31\u53ef\u4ee5\u5f97\u5230\u65b0\u7684\u4f4d\u7f6e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728 Go \u4e2d\u4f18\u5316\u7684\u70b9\u6bd4\u8f83\u591a\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\u54c8\u5e0c\u7b97\u6cd5\u9009\u7528\u9ad8\u6548\u7684 memhash \u7b97\u6cd5 \u548c CPU AES\u6307\u4ee4\u96c6\u3002AES \u6307\u4ee4\u96c6\u5145\u5206\u5229\u7528 CPU \u786c\u4ef6\u7279\u6027\uff0c\u8ba1\u7b97\u54c8\u5e0c\u503c\u7684\u6548\u7387\u8d85\u9ad8\u3002<\/li><li>key &#8211; value \u7684\u6392\u5217\u8bbe\u8ba1\u6210 key \u653e\u5728\u4e00\u8d77\uff0cvalue \u653e\u5728\u4e00\u8d77\uff0c\u800c\u4e0d\u662fkey\uff0cvalue\u6210\u5bf9\u6392\u5217\u3002\u8fd9\u6837\u65b9\u4fbf\u5185\u5b58\u5bf9\u9f50\uff0c\u6570\u636e\u91cf\u5927\u4e86\u4ee5\u540e\u8282\u7ea6\u5185\u5b58\u5bf9\u9f50\u9020\u6210\u7684\u4e00\u4e9b\u6d6a\u8d39\u3002<\/li><li>key\uff0cvalue \u7684\u5185\u5b58\u5927\u5c0f\u8d85\u8fc7128\u5b57\u8282\u4ee5\u540e\u81ea\u52a8\u8f6c\u6210\u5b58\u50a8\u4e00\u4e2a\u6307\u9488\u3002<\/li><li>tophash \u6570\u7ec4\u7684\u8bbe\u8ba1\u52a0\u901f\u4e86 key \u7684\u67e5\u627e\u8fc7\u7a0b\u3002tophash \u4e5f\u88ab\u590d\u7528\uff0c\u7528\u6765\u6807\u8bb0\u6269\u5bb9\u64cd\u4f5c\u65f6\u5019\u7684\u72b6\u6001\u3002<\/li><li>\u7528\u4f4d\u8fd0\u7b97\u8f6c\u6362\u6c42\u4f59\u64cd\u4f5c\uff0cm % n \uff0c\u5f53 n = 1 &lt;&lt; B \u7684\u65f6\u5019\uff0c\u53ef\u4ee5\u8f6c\u6362\u6210 m &amp; (1&lt;&lt;B &#8211; 1) \u3002<\/li><li>\u589e\u91cf\u5f0f\u6269\u5bb9\u3002<\/li><li>\u7b49\u91cf\u6269\u5bb9\uff0c\u7d27\u51d1\u64cd\u4f5c\u3002<\/li><li>Go 1.9 \u7248\u672c\u4ee5\u540e\uff0cMap \u539f\u751f\u5c31\u5df2\u7ecf\u652f\u6301\u7ebf\u7a0b\u5b89\u5168\u3002(\u5728\u4e0b\u4e00\u7ae0\u4e2d\u91cd\u70b9\u8ba8\u8bba\u8fd9\u4e2a\u95ee\u9898)<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">\u5f53\u7136 Go \u4e2d\u8fd8\u6709\u4e00\u4e9b\u9700\u8981\u518d\u4f18\u5316\u7684\u5730\u65b9\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\u5728\u8fc1\u79fb\u7684\u8fc7\u7a0b\u4e2d\uff0c\u5f53\u524d\u7248\u672c\u4e0d\u4f1a\u91cd\u7528 overflow \u6876\uff0c\u800c\u662f\u76f4\u63a5\u91cd\u65b0\u7533\u8bf7\u4e00\u4e2a\u65b0\u7684\u6876\u3002\u8fd9\u91cc\u53ef\u4ee5\u4f18\u5316\u6210\u4f18\u5148\u91cd\u7528\u6ca1\u6709\u6307\u9488\u6307\u5411\u7684 overflow \u6876\uff0c\u5f53\u6ca1\u6709\u53ef\u7528\u7684\u4e86\uff0c\u518d\u53bb\u7533\u8bf7\u4e00\u4e2a\u65b0\u7684\u3002\u8fd9\u4e00\u70b9\u4f5c\u8005\u5df2\u7ecf\u5199\u5728\u4e86 TODO \u91cc\u9762\u4e86\u3002<\/li><li>\u52a8\u6001\u5408\u5e76\u591a\u4e2a empty \u7684\u6876\u3002<\/li><li>\u5f53\u524d\u7248\u672c\u4e2d\u6ca1\u6709 shrink \u64cd\u4f5c\uff0cMap \u53ea\u80fd\u589e\u957f\u800c\u4e0d\u80fd\u6536\u7f29\u3002\u8fd9\u5757 Redis \u6709\u76f8\u5173\u7684\u5b9e\u73b0\u3002<\/li><\/ol>\n\n\n\n<hr class=\"wp-block-separator\" \/>\n\n\n\n<p class=\"wp-block-paragraph\">Reference\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u300a\u7b97\u6cd5\u4e0e\u6570\u636e\u7ed3\u6784\u300b<\/li><li>\u300aRedis \u8bbe\u8ba1\u4e0e\u5b9e\u73b0\u300b<\/li><li>xxHash<code>http:\/\/cyan4973.github.io\/xxHash\/<\/code><\/li><li>\u5b57\u7b26\u4e32hash\u51fd\u6570<code>https:\/\/www.biaodianfu.com\/hash.html<\/code><\/li><li>General Purpose Hash Function Algorithms<code>http:\/\/www.partow.net\/programming\/hashfunctions\/index.html<\/code><\/li><li>Java 8\u7cfb\u5217\u4e4b\u91cd\u65b0\u8ba4\u8bc6HashMap<code>https:\/\/tech.meituan.com\/java-hashmap.html<\/code><\/li><li>Halfrost-Field<code>https:\/\/github.com\/halfrost\/Halfrost-Field<\/code><\/li><li>halfrost \u00b7 GitHub<code>https:\/\/github.com\/halfrost<\/code><\/li><li>Source: <code>https:\/\/halfrost.com\/go_map_chapter_one\/<\/code><\/li><\/ul>\n<!-- <audio autoplay=\"autoplay\" height=\"100\" width=\"100\" hidden=\"true\"><source src=\"https:\/\/c.coka.la\/orAvPR.mp3\" type=\"audio\/mp3\"\/><\/audio><img decoding=\"async\" src=\"https:\/\/images.weserv.nl\/?url=https:\/\/ws3.sinaimg.cn\/large\/8fa5dcfcgy1g4em3rzar5j20ib089ae0.jpg\" alt=\"\u4e1a\u4f59\u8349\u516c\u4f17\u53f7\"\/> --><p><!-- <img decoding=\"async\" src=\"https:\/\/raw.githubusercontent.com\/xmt1139057136\/xttblog\/master\/8fa5dcfcgy1g4em3rzar5j20ib089ae0.jpg\" alt=\"\u4e1a\u4f59\u8349\u516c\u4f17\u53f7\"\/>--><img decoding=\"async\" src=\"https:\/\/saas.51autoparts.cn\/api\/admin\/sys-file\/oss\/file?fileName=84db51f8561e448f9a4fda2eff0811f9.jpg\" alt=\"\u4e1a\u4f59\u8349\u516c\u4f17\u53f7\"\/><\/p><p>\u6700\u540e\uff0c\u6b22\u8fce\u5173\u6ce8\u6211\u7684\u4e2a\u4eba\u5fae\u4fe1\u516c\u4f17\u53f7\uff1a\u4e1a\u4f59\u8349\uff08yyucao\uff09\uff01<b>\u53ef\u52a0\u4f5c\u8005\u5fae\u4fe1\u53f7\uff1a<font color=\"red\">xttblog2<\/font>\u3002\u5907\u6ce8\uff1a\u201c1\u201d\uff0c\u6dfb\u52a0\u535a\u4e3b\u5fae\u4fe1\u62c9\u4f60\u8fdb\u5fae\u4fe1\u7fa4\u3002\u5907\u6ce8\u9519\u8bef\u4e0d\u4f1a\u540c\u610f\u597d\u53cb\u7533\u8bf7\u3002<\/b>\u518d\u6b21\u611f\u8c22\u60a8\u7684\u5173\u6ce8\uff01\u540e\u7eed\u6709\u7cbe\u5f69\u5185\u5bb9\u4f1a\u7b2c\u4e00\u65f6\u95f4\u53d1\u7ed9\u60a8\uff01\u539f\u521b\u6587\u7ae0\u6295\u7a3f\u8bf7\u53d1\u9001\u81f3532009913@qq.com\u90ae\u7bb1\u3002\u5546\u52a1\u5408\u4f5c\u4e5f\u53ef\u6dfb\u52a0\u4f5c\u8005\u5fae\u4fe1\u8fdb\u884c\u8054\u7cfb\uff01<\/p><p>\u672c\u6587\u539f\u6587\u51fa\u5904\uff1a<a href=\"https:\/\/www.xttblog.com\">\u4e1a\u4f59\u8349<\/a>\uff1a &raquo; <a href=\"https:\/\/www.xttblog.com\/?p=5380\">\u5982\u4f55\u8bbe\u8ba1\u5e76\u5b9e\u73b0\u4e00\u4e2a\u7ebf\u7a0b\u5b89\u5168\u7684 Map\uff1f<\/a><\/p><!-- <div class=\"bd-reward-stl\"><button id=\"bdRewardBtn\"><span><\/span><\/button><\/div> -->","protected":false},"excerpt":{"rendered":"<p>Map \u662f\u4e00\u79cd\u5f88\u5e38\u89c1\u7684\u6570\u636e\u7ed3\u6784\uff0c\u7528\u4e8e\u5b58\u50a8\u4e00\u4e9b\u65e0\u5e8f\u7684\u952e\u503c\u5bf9\u3002\u5728\u4e3b\u6d41\u7684\u7f16\u7a0b\u8bed\u8a00\u4e2d\uff0c\u9ed8\u8ba4\u5c31\u81ea\u5e26\u5b83\u7684\u5b9e\u73b0\u3002C\u3001C++  [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[1164,1161,1846,1163,583],"class_list":["post-5380","post","type-post","status-publish","format-standard","hentry","category-yyzt","tag-concurrenthashmap","tag-hashmap","tag-jmap","tag-linkedhashmap","tag-mapreduce"],"_links":{"self":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/5380","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5380"}],"version-history":[{"count":2,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/5380\/revisions"}],"predecessor-version":[{"id":5382,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/5380\/revisions\/5382"}],"wp:attachment":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5380"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5380"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5380"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}