{"id":812,"date":"2020-10-27T12:53:19","date_gmt":"2020-10-27T04:53:19","guid":{"rendered":"http:\/\/www.wangkaixuan.tech\/?p=812"},"modified":"2020-10-27T17:53:09","modified_gmt":"2020-10-27T09:53:09","slug":"%e5%93%88%e5%b8%8cmap%e8%af%a6%e8%a7%a3%ef%bc%88%e9%99%84%e4%bb%a3%e7%a0%81%ef%bc%89","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=812","title":{"rendered":"\u54c8\u5e0cmap\u8be6\u89e3\uff08\u9644\u4ee3\u7801\uff09"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">1.\u95ee\u9898\u573a\u666f<\/h2>\n\n\n\n<p>\u6211\u4eec\u7684\u67d0\u4e2a\u7cfb\u7edf\u76ee\u524d\u662f\u5728\u4e00\u4e2a\u8001\u65e7\u7684\u5e73\u53f0\u4e0a\u8fd0\u884c\u7684\uff0c\u6700\u8fd1\u5904\u7406\u7684\u6570\u636e\u91cf\u6709\u70b9\u5927\uff0c\u5bfc\u81f4\u6570\u636e\u67e5\u627e\u6027\u80fd\u5927\u5e45\u4e0b\u964d\u3002<\/p>\n\n\n\n<p>\u7531\u4e8e\u5e73\u53f0\u6bd4\u8f83\u8001\u65e7\uff0c\u7f16\u8bd1\u5668\u7248\u672c\u5f88\u4f4e\uff0c\u4f7f\u7528\u6807\u51c6\u5e93\u4e2d\u7684hash_map\u4e5f\u5c31\u522b\u60f3\u4e86\u3002\u56e0\u6b64\u6211\u4eec\u60f3\u7740\u81ea\u5df1\u5b9e\u73b0\u4e00\u4e2a\u7b80\u6613\u7684\uff0c\u4e13\u7528\u7684hash_map\uff0c\u6765\u8fbe\u5230\u4f18\u5316\u67e5\u627e\u6027\u80fd\u7684\u76ee\u7684\u3002<\/p>\n\n\n\n<p>\u6587\u7ae0\u7684\u540e\u9762\u9644\u7684\u6709\u4ee3\u7801\uff0c\u6838\u5fc3\u4ee3\u7801\u53ea\u6709\u4e0d\u5230100\u884c\uff0c\u4f9b\u60a8\u53c2\u8003\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2.\u54c8\u5e0c\u5bb9\u5668\u7684\u4e24\u4e2a\u8981\u70b9<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">a) \u6563\u5217\u51fd\u6570<\/h3>\n\n\n\n<p>\u6563\u5217\u51fd\u6570\u7684\u4f5c\u7528\u662f\uff0c\u5c06<strong>key<\/strong>\u6620\u5c04\u4e3a\u4e00\u4e2a<strong>value\u7684\u5b58\u50a8\u5730\u5740<\/strong>\u3002<\/p>\n\n\n\n<p>\u6700\u7b80\u5355\u7684\u6620\u5c04\u65b9\u6cd5\u662f\uff0c\u5c06key\u76f4\u63a5\u6620\u5c04\u4e3a\u4e00\u4e2a\u6570\u7ec4\u4e0b\u6807\u3002<\/p>\n\n\n\n<p>\u8fd9\u79cd\u6620\u5c04\u65b9\u6cd5\u901f\u5ea6\u6781\u5feb\uff0c\u4f46\u662f\u5e76\u4e0d\u9002\u7528\u4e8e\u6240\u6709\u573a\u666f\u3002\u6bd4\u5982key\u7684\u53d6\u503c\u8303\u56f4\u7279\u522b\u5927\uff0c\u8981\u8986\u76d6\u8fd9\u4e2a\u8303\u56f4\u7684\u8bdd\u5c31\u9700\u8981\u4e00\u4e2a\u7279\u522b\u5927\u7684\u6570\u7ec4\uff0c\u5185\u5b58\u6d6a\u8d39\u5f88\u4e25\u91cd\u3002<\/p>\n\n\n\n<p>\u56e0\u6b64\uff0c\u9700\u8981\u4e00\u4e2a\u6563\u5217\u51fd\u6570\uff0c\u5c06key\u6620\u5c04\u6210\u4e00\u4e2a\u5b58\u50a8\u5730\u5740\uff0c\u964d\u4f4e\u6240\u9700\u7684\u5b58\u50a8\u7a7a\u95f4\u3002<\/p>\n\n\n\n<p>\u6563\u5217\u51fd\u6570\u901a\u5e38\u6709\u8fd9\u6837\u51e0\u79cd\u7c7b\u578b\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>\u9664\u4f59\u6cd5<\/strong>\uff1a\u5373\u5c06key\u4e0e\u5b58\u50a8\u5730\u5740\u8303\u56f4\uff08\u6bd4\u5982\u6570\u7ec4\u7684\u957f\u5ea6\uff09\u53d6\u6a21\uff0c\u7b80\u5355\u6709\u6548<\/li><li><strong>\u4e58\u4f59\u53d6\u6574\u6cd5<\/strong>\uff1a\u8ba9key\u4e58\u4ee5\u4e00\u4e2a\u5c0f\u6570D\uff080&lt;D&lt;1\uff09\u540e\uff0c\u53d6\u5c0f\u6570\u90e8\u5206\uff0c\u7136\u540e\u5728\u7528\u6574\u6570N\u4e58\u4ee5\u8fd9\u4e2a\u503c\uff0c\u53d6\u6574\u6570\u90e8\u5206<\/li><li><strong>\u5e73\u65b9\u53d6\u4e2d\u6cd5<\/strong>\uff1a\u5148\u6c42key\u7684\u5e73\u65b9\uff08\u76ee\u7684\u662f\u6269\u5927\u76f8\u8fd1\u7684\u6570\u503c\u7684\u5dee\u522b\uff09\uff0c\u7136\u540e\u6839\u636e\u5b58\u50a8\u5730\u5740\u8303\u56f4\uff0c\u53d6\u4e2d\u95f4\u7684\u51e0\u4f4d\u6570\u4f5c\u4e3a\u5b58\u50a8\u5730\u5740\uff08\u56e0\u4e3a\u4e00\u4e2a\u4e58\u79ef\u7684\u4e2d\u95f4\u51e0\u4f4d\u6570\u4e0e\u4e58\u6570\u7684\u6bcf\u4e00\u6570\u4f4d\u90fd\u76f8\u5173\uff0c\u6240\u4ee5\u7531\u6b64\u4ea7\u751f\u7684\u6563\u5217\u5730\u5740\u8f83\u4e3a\u5747\u5300\uff09<\/li><li><strong>\u6570\u503c\u5206\u6790\u6cd5<\/strong>\uff1a\u6839\u636e\u6570\u503c\u7684\u7279\u5f81\uff08\u6bd4\u5982\u5206\u5e03\u6982\u7387\uff09\u8bbe\u5b9a\u5b58\u50a8\u5730\u5740<\/li><li><strong>\u57fa\u6570\u8f6c\u6362\u6cd5<\/strong>\uff1a\u5c06key\u770b\u6210\u67d0\u4e00\u8fdb\u5236\u7684\u6570\uff0c\u8f6c\u6362\u6210\u53e6\u5916\u4e00\u4e2a\u8fdb\u5236\u7684\u6570\uff0c\u53d6\u4e2d\u95f4\u51e0\u4f4d\u4f5c\u4e3a\u6563\u5217\u5730\u5740<\/li><li><strong>\u6298\u53e0\u6cd5<\/strong>\uff1a\u5bf9\u4e8e\u4f4d\u6570\u5f88\u591a\u7684key\uff0c\u53ef\u4ee5\u5c06\u5176\u5206\u5272\u6210\u4f4d\u6570\u76f8\u540c\u7684\u51e0\u4e2a\u90e8\u5206\uff0c\u5c06\u4ed6\u4eec\u53e0\u52a0\u540e\u4f5c\u4e3a\u6563\u5217\u5730\u5740<\/li><\/ul>\n\n\n\n<p>\u6563\u5217\u51fd\u6570\u9009\u62e9\u7684\u539f\u5219\u662f\uff0c<strong>\u8ba9\u6563\u5217\u5730\u5740\u7684\u5206\u5e03\uff0c\u5c3d\u91cf\u5747\u5300<\/strong>\uff0c\u4ece\u800c\u964d\u4f4e\u51b2\u7a81\u6982\u7387\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">b)\u51b2\u7a81\u5904\u7406<\/h3>\n\n\n\n<p>\u51b2\u7a81\u662f\u6307\uff0c<strong>\u4e24\u4e2akey\u6620\u5c04\u5230\u540c\u4e00\u4e2a\u5b58\u50a8\u5730\u5740<\/strong>\u3002<\/p>\n\n\n\n<p>\u6211\u4eec\u4e0d\u559c\u6b22\u51b2\u7a81\uff0c\u56e0\u4e3a\u51b2\u7a81\u4f1a\u540e\u8981\u518d\u6b21\u8fdb\u884c\u67e5\u627e\uff0c\u76f4\u5230\u627e\u5230\u771f\u6b63\u7684\u5143\u7d20\u3002\u8fd9\u4f1a\u964d\u4f4e\u67e5\u627e\u6548\u7387\u3002<\/p>\n\n\n\n<p>\u7136\u800c\u51b2\u7a81\u53c8\u662f\u5e38\u89c1\u7684\uff0c\u5de5\u4f5c\u826f\u597d\u7684\u6563\u5217\u51fd\u6570\uff0c\u80fd\u5c3d\u91cf\u964d\u4f4e\u51b2\u7a81\u6982\u7387\uff0c\u4f46\u5f88\u96be\u6d88\u9664\u51b2\u7a81\u3002\u53ea\u6709\u5728\u67d0\u4e9b\u5f88\u7279\u6b8a\u7684\u573a\u666f\u4e0b\uff0c \u624d\u80fd\u5b9e\u73b0\u65e0\u51b2\u7a81\u3002<\/p>\n\n\n\n<p>\u5e38\u89c1\u7684\u51b2\u7a81\u5904\u7406\u65b9\u6cd5\u6709\u5982\u4e0b\u51e0\u79cd\uff1a<\/p>\n\n\n\n<p><strong>1.\u5206\u79bb\u94fe\u8868\u6cd5<\/strong><\/p>\n\n\n\n<p>\u5373\u4ece\u51b2\u7a81\u7684\u4f4d\u7f6e\u62c9\u51fa\u4e00\u4e2a\u94fe\u8868\uff0c\u5b58\u653e\u51b2\u7a81\u7684\u5143\u7d20\uff08\u5982\u4e0b\u56fe\uff09<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1319\" height=\"689\" src=\"http:\/\/www.wangkaixuan.tech\/wp-content\/uploads\/2020\/10\/image-3.png\" alt=\"\" class=\"wp-image-813\"\/><figcaption>\u56fe\uff1a\u5206\u79bb\u94fe\u8868\u6cd5<\/figcaption><\/figure>\n\n\n\n<p><strong>2.\u5f00\u653e\u5b9a\u5740\u6cd5<\/strong><\/p>\n\n\n\n<p>\u5373\u7528\u8868\u672c\u8eab\u7684\u7a7a\u95f2\u7a7a\u95f4\u6765\u5b58\u653e\u51b2\u7a81\u5143\u7d20\u3002<\/p>\n\n\n\n<p>\u5e38\u89c1\u7684\u505a\u6cd5\u6709\u56db\u79cd\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>\u7ebf\u6027\u63a2\u67e5\u6cd5<\/strong>\uff1a\u4ece\u51b2\u7a81\u4f4d\u7f6e\uff0c\u6bcf\u6b21+1\u5bfb\u627e\u4e0b\u4e00\u4e2a\u5143\u7d20\uff0c\u8be5\u65b9\u6cd5\u5bb9\u6613\u4ea7\u751f\u805a\u96c6<\/li><li><strong>\u4e8c\u6b21\u63a2\u67e5\u6cd5<\/strong>\uff1a\u4ece\u51b2\u7a81\u4f4d\u7f6e\uff0c\u6bcf\u6b21+1^2\u30012^2\u30013^2&#8230;\u5bfb\u627e\u4e0b\u4e00\u4e2a\u5143\u7d20\uff0c\u8be5\u65b9\u6cd5\u6bd4\u7ebf\u6027\u63a2\u67e5\u6cd5\u8981\u597d\u5f88\u591a\uff0c\u4f46\u662f\u8fd8\u662f\u6709\u53ef\u80fd\u4ea7\u751f\u805a\u96c6\u3002<\/li><li><strong>\u968f\u673a\u63a2\u67e5\u6cd5<\/strong>\uff1a\u51b2\u7a81\u540e\u968f\u673a\u5bfb\u627e\u5730\u5740\u7a7a\u95f4\uff0c\u8be5\u65b9\u6cd5\u4e0d\u53ef\u63a7<\/li><li><strong>\u53cc\u6563\u5217\u63a2\u67e5\u6cd5<\/strong>\uff1a\u51b2\u7a81\u540e\u4f7f\u7528\u7b2c\u4e8c\u4e2a\u6563\u5217\u51fd\u6570\u505a\u8df3\u6b65\uff0c\u5bfb\u627e\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\uff0c\u8be5\u65b9\u6cd5\u5bf9\u7b2c\u4e8c\u4e2a\u6563\u5217\u51fd\u6570\u8981\u6c42\u5f88\u9ad8\uff0c\u5426\u5219\u4f1a\u5f15\u8d77\u707e\u96be\u6027\u7684\u540e\u679c<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">3.\u53c2\u8003\u5b9e\u73b0\u65b9\u6848<\/h2>\n\n\n\n<p>\u6211\u4eec\u8fd9\u91cc\u4ec5\u8ba8\u8bba\u51b2\u7a81\u5904\u7406\u65b9\u6cd5\u3002<\/p>\n\n\n\n<p><strong>\u65b9\u68481\uff1a\u6539\u8fdb\u540e\u7684\u4e8c\u6b21\u63a2\u67e5\u6cd5<\/strong><\/p>\n\n\n\n<p>\u4e8c\u6b21\u63a2\u67e5\u6cd5\u5982\u679c\u80fd\u4fdd\u8bc1hash\u6876\u7684\u4e2a\u6570\u4e3a\u8d28\u6570\uff0c\u4e14\u5bb9\u5668\u8d1f\u8f7d\u7cfb\u6570\u57280.5\u4ee5\u4e0b\uff08\u5373\u4fdd\u8bc1\u5bb9\u5668\u5b9e\u9645\u5bb9\u7eb3\u7684\u5143\u7d20\u4e2a\u6570\u4e0d\u5230\u5bb9\u5668\u5bb9\u91cf\u7684\u4e00\u534a\uff0c\u8d85\u8fc7\u540e\u6269\u5927\u5bb9\u5668\u5bb9\u91cf\u91cd\u65b0\u6574\u7406\uff09\uff0c\u5219\u53ef\u4fdd\u8bc1\u65b0\u63d2\u5165\u5143\u7d20\u6240\u9700\u7684\u63a2\u67e5\u6b21\u6570\u4e0d\u8d85\u8fc72\uff08\u636e\u8bf4\u6570\u5b66\u4e0a\u662f\u53ef\u4ee5\u8bc1\u660e\u7684\uff09\u3002<\/p>\n\n\n\n<p>GCC\u7684STL\u4f7f\u7528\u7684\u5c31\u662f\u8fd9\u79cd\u65b9\u6cd5\u3002<\/p>\n\n\n\n<p><strong>\u65b9\u68482\uff1a\u5206\u79bb\u94fe\u8868\u6cd5<\/strong><\/p>\n\n\n\n<p>\u53ea\u8981\u6563\u5217\u591f\u5e73\u5747\uff0c\u94fe\u8868\u5c31\u80fd\u8db3\u591f\u77ed\uff0c\u6027\u80fd\u5c31\u80fd\u8db3\u591f\u9ad8\u3002<\/p>\n\n\n\n<p>SGI\u7684STL\u5c31\u662f\u91c7\u7528\u7684\u5206\u79bb\u94fe\u8868\u6cd5\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4.\u6211\u4eec\u7684\u65b9\u6848<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">a) \u65b9\u6848\u9009\u62e9<\/h3>\n\n\n\n<p>\u6211\u4eec\u7684\u5e94\u7528\u573a\u666f\u6709\u5982\u4e0b\u7279\u70b9\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>key\u7684\u8303\u56f4\u8db3\u591f\u5927\uff0c\u800c\u4e14\u8db3\u591f\u968f\u673a<\/li><li>\u80fd\u591f\u4fdd\u8bc1\u5bb9\u5668\u8d1f\u8f7d\u7cfb\u6570\u5f88\u4f4e\uff0c\u56e0\u6b64\u4e0d\u6d89\u53ca\u6574\u7406\u95ee\u9898<\/li><li>\u8981\u6c42\u4ee3\u7801\u5fc5\u987b\u7b80\u5355\u6613\u61c2<\/li><li>\u8981\u6c42\u5c3d\u91cf\u4e0d\u4f7f\u7528\u52a8\u6001\u5185\u5b58<\/li><\/ul>\n\n\n\n<p>\u5173\u4e8e<strong>\u6563\u5217\u51fd\u6570<\/strong>\uff0c\u6839\u636e\u7b2c\u4e00\u6761\u5c31\u53ef\u786e\u5b9a\uff0c<strong>\u9664\u4f59\u6cd5<\/strong>\u5c31\u80fd\u6ee1\u8db3\u8981\u6c42\u3002<\/p>\n\n\n\n<p>\u5173\u4e8e<strong>\u51b2\u7a81\u5904\u7406<\/strong>\uff0c\u4e8c\u6b21\u63a2\u67e5\u548c\u5206\u79bb\u94fe\u8868\u611f\u89c9\u5dee\u4e0d\u591a\uff0c\u4f46\u6211\u4eec\u6700\u7ec8\u6211\u4eec\u9009\u62e9\u7684\u662f\u5206\u79bb\u94fe\u8868\u6cd5\u3002\u539f\u56e0\u6709\u4e8c\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u7b80\u5355\u7684\u4e8c\u6b21\u63a2\u67e5\u6cd5\u5b9e\u6d4b\u6548\u679c\u5e76\u4e0d\u597d\uff0c\u8981\u60f3\u8ba9\u4e8c\u6b21\u63a2\u67e5\u6cd5\u53d1\u6325\u51fa\u5a01\u529b\uff0c\u8fd8\u5f97\u5bf9\u8df3\u6b65\u7b97\u6cd5\u505a\u4f18\u5316\uff0c\u5b9e\u73b0\u8d77\u6765\u6bd4\u8f83\u590d\u6742<\/li><li>\u5206\u79bb\u94fe\u8868\u6cd5\u7b80\u5355\u6613\u61c2\uff0c\u5b9e\u6d4b\u6548\u679c\u597d\uff08\u6876\u6df1\u5ea6\uff0c\u5373\u94fe\u8868\u957f\u5ea6\u4e0d\u8d85\u8fc75\uff09<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">b) \u53c2\u8003\u4ee3\u7801<\/h3>\n\n\n\n<p>x_hash_map.h<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#ifndef X_HASH_MAP_H_\n#define X_HASH_MAP_H_\n\n\/\/hash_map\u4e2d\u7684\u5143\u7d20\ntypedef struct x_hmap_elem_t_tag\n{\n\tlong key;\n\tlong val;\n\tlong next; \/\/ \u6307\u5411\u4e0b\u4e00\u4e2a\u5143\u7d20\n} x_hmap_elem_t;\n\ntypedef struct x_hash_map_t_tag\n{\n\tint bkt_size;               \/\/\u6876\u5143\u7d20\uff0c\u4e5f\u662f\u5143\u7d20\u96c6\u5408\u7684\u5bb9\u91cf\n\tx_hmap_elem_t *p_elems;     \/\/\u6240\u6709\u5143\u7d20\u96c6\u5408\uff08\u6570\u7ec4\uff0c\u987a\u5e8f\u4f7f\u7528\uff09\n\tint cur_pos;                \/\/\u4e0a\u8ff0\u96c6\u5408\u4e2d\uff0c\u4e0b\u4e00\u4e2a\u53ef\u7528\u5143\u7d20\u7684\u4e0b\u6807\n\tlong *p_bkts;               \/\/\u5404\u4e2a\u6876\u7684\u9996\u5143\u7d20\uff08\u6570\u7ec4\uff09\n} x_hash_map_t;\n\n\/\/\u65b0\u5efa\u4e00\u4e2ahash_map\uff08\u9700\u6307\u5b9a\u6700\u5927\u5bb9\u91cf\uff09\nx_hash_map_t* alloc_hash_map(long max_elems);\n\n\/\/\u5bfb\u627ekey\u5bf9\u5e94\u7684value\uff0c\u5931\u8d25\u8fd4\u56de-1\uff0c\u5426\u5219\u8fd4\u56devalue\nlong find_hmap_elem(x_hash_map_t *p_map, long key);\n\n\/\/\u63d2\u5165\u4e00\u4e2a\u5143\u7d20\uff08\u8c03\u7528\u65f6\u4fdd\u8bc1\u5143\u7d20\u4e0d\u5b58\u5728\uff09\nint insert_hmap_elem(x_hash_map_t *p_map, long key, long value);\n\n#endif<\/code><\/pre>\n\n\n\n<p>x_hash_map.c<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include \"x_hash_map.h\"\n\n#include &lt;memory.h> \/\/ for memset()\n#include &lt;stdlib.h> \/\/ for NULL\n\n\/\/\u9884\u5b9a\u4e49\u7684\u7d20\u6570\u8868\uff0c\u5b9a\u4e49\u6765\u81ea\uff1agcc-4.8.5-libstdc++-v3\/src\/shared\/hashtable-aux.cc\nconst unsigned long k_prime_list&#91;] =\n{ 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 37ul, 41ul,\n\t\t43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, 83ul, 89ul, 97ul,\n\t\t103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, 157ul, 167ul, 179ul,\n\t\t193ul, 199ul, 211ul, 227ul, 241ul, 257ul, 277ul, 293ul, 313ul, 337ul,\n\t\t359ul, 383ul, 409ul, 439ul, 467ul, 503ul, 541ul, 577ul, 619ul, 661ul,\n\t\t709ul, 761ul, 823ul, 887ul, 953ul, 1031ul, 1109ul, 1193ul, 1289ul,\n\t\t1381ul, 1493ul, 1613ul, 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul,\n\t\t2753ul, 2971ul, 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul,\n\t\t5503ul, 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,\n\t\t11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, 19183ul,\n\t\t20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, 33223ul, 35933ul,\n\t\t38873ul, 42043ul, 45481ul, 49201ul, 53201ul, 57557ul, 62233ul, 67307ul,\n\t\t72817ul, 78779ul, 85229ul, 92203ul, 99733ul, 107897ul, 116731ul,\n\t\t126271ul, 136607ul, 147793ul, 159871ul, 172933ul, 187091ul, 202409ul,\n\t\t218971ul, 236897ul, 256279ul, 277261ul, 299951ul, 324503ul, 351061ul,\n\t\t379787ul, 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,\n\t\t658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, 1056323ul,\n\t\t1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, 1693859ul,\n\t\t1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, 2716249ul,\n\t\t2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, 4355707ul,\n\t\t4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, 6984629ul,\n\t\t7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, 11200489ul,\n\t\t12117689ul, 13109983ul, 14183539ul, 15345007ul, 16601593ul, 17961079ul,\n\t\t19431899ul, 21023161ul, 22744717ul, 24607243ul, 26622317ul, 28802401ul,\n\t\t31160981ul, 33712729ul, 36473443ul, 39460231ul, 42691603ul, 46187573ul,\n\t\t49969847ul, 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,\n\t\t80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,\n\t\t118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,\n\t\t176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,\n\t\t260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,\n\t\t386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,\n\t\t573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,\n\t\t849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,\n\t\t1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul,\n\t\t1866894511ul, 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul,\n\t\t2767159799ul, 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul,\n\t\t4101556399ul, 4294967291ul, 6442450933ul, 8589934583ul, 12884901857ul,\n\t\t17179869143ul, 25769803693ul, 34359738337ul, 51539607367ul,\n\t\t68719476731ul, 103079215087ul, 137438953447ul, 206158430123ul,\n\t\t274877906899ul, 412316860387ul, 549755813881ul, 824633720731ul,\n\t\t1099511627689ul, 1649267441579ul, 2199023255531ul, 3298534883309ul,\n\t\t4398046511093ul, 6597069766607ul, 8796093022151ul, 13194139533241ul,\n\t\t17592186044399ul, 26388279066581ul, 35184372088777ul, 52776558133177ul,\n\t\t70368744177643ul, 105553116266399ul, 140737488355213ul,\n\t\t211106232532861ul, 281474976710597ul, 562949953421231ul,\n\t\t1125899906842597ul, 2251799813685119ul, 4503599627370449ul,\n\t\t9007199254740881ul, 18014398509481951ul, 36028797018963913ul,\n\t\t72057594037927931ul, 144115188075855859ul, 288230376151711717ul,\n\t\t576460752303423433ul, 1152921504606846883ul, 2305843009213693951ul,\n\t\t4611686018427387847ul, 9223372036854775783ul, 18446744073709551557ul,\n\t\t18446744073709551557ul };\n\nx_hash_map_t* alloc_hash_map(long max_elems)\n{\n\t\/\/\u627e\u4e00\u4e2a\u3010\u5927\u4e8e\u7b49\u4e8e\u5143\u7d20\u4e2a\u6570\u3011\u7684\u3010\u6700\u5c0f\u7d20\u6570\u3011\u4f5c\u4e3a\u6876\u7684\u4e2a\u6570\n\tint prim_idx = 0;\n\twhile (k_prime_list&#91;prim_idx] &lt; max_elems)\n\t\t++prim_idx;\n\n\t\/\/\u65b0\u5efa\u4e00\u4e2amap\n\tx_hash_map_t *p_map = (x_hash_map_t*) malloc(sizeof(x_hash_map_t));\n\n\tp_map->bkt_size = k_prime_list&#91;prim_idx];\n\tp_map->cur_pos = 0;\n\tp_map->p_elems = (x_hmap_elem_t*) malloc(\n\t\t\tsizeof(x_hmap_elem_t) * p_map->bkt_size);\n\tp_map->p_bkts = (long*) malloc(sizeof(long) * p_map->bkt_size);\n\n\tfor (long i = 0; i &lt; p_map->bkt_size; ++i)\n\t\tp_map->p_bkts&#91;i] = -1; \/\/-1\u8868\u793a\u6876\u662f\u7a7a\u7684\n\n\treturn p_map;\n}\n\nlong find_hmap_elem(x_hash_map_t *p_map, long key)\n{\n\t\/\/\u786e\u5b9a\u4e00\u4e2a\u6876\uff0c\u53d6\u51fa\u9996\u5143\u7d20\u6307\u9488\n\tlong cur_idx = p_map->p_bkts&#91;key % p_map->bkt_size];\n\n\twhile (cur_idx >= 0) \/\/\u904d\u5386\u67e5\u627e\u6876\u4e2d\u5143\u7d20\n\t{\n\t\tif (p_map->p_elems&#91;cur_idx].key == key) \/\/\u627e\u5230\n\t\t\treturn p_map->p_elems&#91;cur_idx].val;\n\n\t\tcur_idx = p_map->p_elems&#91;cur_idx].next;\n\t}\n\n\treturn -1;\n}\n\nint insert_hmap_elem(x_hash_map_t *p_map, long key, long value)\n{\n\t\/\/\u65b0\u5efa\u5143\u7d20\n\tlong new_idx = p_map->cur_pos;\n\n\tp_map->p_elems&#91;new_idx].key = key;\n\tp_map->p_elems&#91;new_idx].val = value;\n\n\t\/\/\u63d2\u5165\u6876\u5143\u7d20\u94fe\u8868\u7684\u5934\u90e8\n\tp_map->p_elems&#91;new_idx].next = p_map->p_bkts&#91;key % p_map->bkt_size];\n\tp_map->p_bkts&#91;key % p_map->bkt_size] = new_idx;\n\n\t++p_map->cur_pos;\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<p>test.c<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include \"x_hash_map.h\"\n\n#include &lt;assert.h>\n#include &lt;stdio.h>\n\n\/*\n\tgcc -o x_hash_map.o -c x_hash_map.c -Wall -m64 -g -O3\n\tgcc -o test.o -c test.c -Wall -m64 -g -O3\n\tgcc -o test test.o x_hash_map.o -Wall -m64 -g -O3\n*\/\n\n#define TEST_MAX 30000000\n\nint main()\n{\n    x_hash_map_t *p_map = alloc_hash_map(TEST_MAX);\n\n    for(long i=0;i&lt;TEST_MAX;++i)\n    {\n         if(i % 10000000 == 0)\n        printf(\"insert %ld\\n\", i);\n        insert_hmap_elem(p_map, i, i+1);\n    }\n\n    for(long i=0;i&lt;TEST_MAX;++i)\n    {\n        if(i % 10000000 == 0)\n        printf(\"find %ld\\n\", i);\n        long val = find_hmap_elem(p_map, i);\n        assert(val == i+1);\n    }\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">5.\u53c2\u8003\u8d44\u6599<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>\u300aSTL\u6e90\u7801\u5256\u6790\u300b-\u4faf\u6377<\/li><li>\u300a\u521d\u7b49\u6570\u8bba\u53ca\u5176\u5e94\u7528\u300b-Rosen<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>1.\u95ee\u9898\u573a\u666f \u6211\u4eec\u7684\u67d0\u4e2a\u7cfb\u7edf\u76ee\u524d\u662f\u5728\u4e00\u4e2a\u8001\u65e7\u7684\u5e73\u53f0\u4e0a\u8fd0\u884c\u7684\uff0c\u6700\u8fd1\u5904\u7406\u7684\u6570\u636e\u91cf\u6709\u70b9\u5927\uff0c\u5bfc\u81f4\u6570\u636e\u67e5\u627e\u6027\u80fd\u5927\u5e45\u4e0b\u964d\u3002 \u7531\u4e8e\u5e73\u53f0\u6bd4\u8f83\u8001\u65e7\uff0c\u7f16\u8bd1\u5668\u7248\u672c\u5f88\u4f4e\uff0c\u4f7f\u7528\u6807\u51c6\u5e93\u4e2d\u7684&#8230;<\/p>\n<p class=\"read-more\"><a class=\"btn btn-default\" href=\"http:\/\/www.wangkaixuan.tech\/?p=812\"> Read More<span class=\"screen-reader-text\">  Read More<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14],"tags":[],"class_list":["post-812","post","type-post","status-publish","format-standard","hentry","category-05-01-"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/812","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=812"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/812\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=812"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=812"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=812"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}