{"id":5361,"date":"2023-02-19T13:38:14","date_gmt":"2023-02-19T05:38:14","guid":{"rendered":"https:\/\/www.xttblog.com\/?p=5361"},"modified":"2023-02-19T13:38:14","modified_gmt":"2023-02-19T05:38:14","slug":"%e4%bb%8e%e5%a4%b4%e5%88%b0%e5%b0%be%e8%a7%a3%e6%9e%90hash%e8%a1%a8%e7%ae%97%e6%b3%95%ef%bc%8c%e7%99%be%e5%ba%a6top-k%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/www.xttblog.com\/?p=5361","title":{"rendered":"\u4ece\u5934\u5230\u5c3e\u89e3\u6790Hash\u8868\u7b97\u6cd5\uff0c\u767e\u5ea6Top K\u7b97\u6cd5\u8be6\u89e3"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\u4ece\u5934\u5230\u5c3e\u89e3\u6790Hash \u8868\u7b97\u6cd5<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u672c\u6587\u5206\u4e3a\u4e09\u90e8\u5206\u5185\u5bb9\uff0c\u7b2c\u4e00\u90e8\u5206\u4e3a\u4e00\u9053\u767e\u5ea6\u9762\u8bd5\u9898Top K\u7b97\u6cd5\u7684\u8be6\u89e3\uff1b\u7b2c\u4e8c\u90e8\u5206\u4e3a\u5173\u4e8eHash\u8868\u7b97\u6cd5\u7684\u8be6\u7ec6\u9610\u8ff0\uff1b\u7b2c\u4e09\u90e8\u5206\u4e3a\u6253\u9020\u4e00\u4e2a\u6700\u5feb\u7684Hash\u8868\u7b97\u6cd5\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7b2c\u4e00\u90e8\u5206\uff1aTop K \u7b97\u6cd5\u8be6\u89e3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u95ee\u9898\u63cf\u8ff0<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><code>\u767e\u5ea6\u9762\u8bd5\u9898<\/code>\uff1a\u641c\u7d22\u5f15\u64ce\u4f1a\u901a\u8fc7\u65e5\u5fd7\u6587\u4ef6\u628a\u7528\u6237\u6bcf\u6b21\u68c0\u7d22\u4f7f\u7528\u7684\u6240\u6709\u68c0\u7d22\u4e32\u90fd\u8bb0\u5f55\u4e0b\u6765\uff0c\u6bcf\u4e2a\u67e5\u8be2\u4e32\u7684\u957f\u5ea6\u4e3a1-255\u5b57\u8282\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5047\u8bbe\u76ee\u524d\u6709\u4e00\u5343\u4e07\u4e2a\u8bb0\u5f55\uff08\u8fd9\u4e9b\u67e5\u8be2\u4e32\u7684\u91cd\u590d\u5ea6\u6bd4\u8f83\u9ad8\uff0c\u867d\u7136\u603b\u6570\u662f1\u5343\u4e07\uff0c\u4f46\u5982\u679c\u9664\u53bb\u91cd\u590d\u540e\uff0c\u4e0d\u8d85\u8fc73\u767e\u4e07\u4e2a\u3002\u4e00\u4e2a\u67e5\u8be2\u4e32\u7684\u91cd\u590d\u5ea6\u8d8a\u9ad8\uff0c\u8bf4\u660e\u67e5\u8be2\u5b83\u7684\u7528\u6237\u8d8a\u591a\uff0c\u4e5f\u5c31\u662f\u8d8a\u70ed\u95e8\u3002\uff09\uff0c\u8bf7\u4f60\u7edf\u8ba1\u6700\u70ed\u95e8\u768410\u4e2a\u67e5\u8be2\u4e32\uff0c\u8981\u6c42\u4f7f\u7528\u7684\u5185\u5b58\u4e0d\u80fd\u8d85\u8fc71G\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0b\u9762\u662f\u4e00\u4e9b\u5fc5\u5907\u77e5\u8bc6\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\uff1f<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u54c8\u5e0c\u8868\uff08Hash table\uff0c\u4e5f\u53eb\u6563\u5217\u8868\uff09\uff0c\u662f\u6839\u636e\u5173\u952e\u7801\u503c(Key value)\u800c\u76f4\u63a5\u8fdb\u884c\u8bbf\u95ee\u7684\u6570\u636e\u7ed3\u6784\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u5b83\u901a\u8fc7\u628a\u5173\u952e\u7801\u503c\u6620\u5c04\u5230\u8868\u4e2d\u4e00\u4e2a\u4f4d\u7f6e\u6765\u8bbf\u95ee\u8bb0\u5f55\uff0c\u4ee5\u52a0\u5feb\u67e5\u627e\u7684\u901f\u5ea6\u3002\u8fd9\u4e2a\u6620\u5c04\u51fd\u6570\u53eb\u505a\u6563\u5217\u51fd\u6570\uff0c\u5b58\u653e\u8bb0\u5f55\u7684\u6570\u7ec4\u53eb\u505a\u6563\u5217\u8868\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u54c8\u5e0c\u8868hashtable(key\uff0cvalue) \u7684\u505a\u6cd5\u5176\u5b9e\u5f88\u7b80\u5355\uff0c\u5c31\u662f\u628aKey\u901a\u8fc7\u4e00\u4e2a\u56fa\u5b9a\u7684\u7b97\u6cd5\u51fd\u6570\u65e2\u6240\u8c13\u7684\u54c8\u5e0c\u51fd\u6570\u8f6c\u6362\u6210\u4e00\u4e2a\u6574\u578b\u6570\u5b57\uff0c\u7136\u540e\u5c31\u5c06\u8be5\u6570\u5b57\u5bf9\u6570\u7ec4\u957f\u5ea6\u8fdb\u884c\u53d6\u4f59\uff0c\u53d6\u4f59\u7ed3\u679c\u5c31\u5f53\u4f5c\u6570\u7ec4\u7684\u4e0b\u6807\uff0c\u5c06value\u5b58\u50a8\u5728\u4ee5\u8be5\u6570\u5b57\u4e3a\u4e0b\u6807\u7684\u6570\u7ec4\u7a7a\u95f4\u91cc\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u800c\u5f53\u4f7f\u7528\u54c8\u5e0c\u8868\u8fdb\u884c\u67e5\u8be2\u7684\u65f6\u5019\uff0c\u5c31\u662f\u518d\u6b21\u4f7f\u7528\u54c8\u5e0c\u51fd\u6570\u5c06key\u8f6c\u6362\u4e3a\u5bf9\u5e94\u7684\u6570\u7ec4\u4e0b\u6807\uff0c\u5e76\u5b9a\u4f4d\u5230\u8be5\u7a7a\u95f4\u83b7\u53d6value\uff0c\u5982\u6b64\u4e00\u6765\uff0c\u5c31\u53ef\u4ee5\u5145\u5206\u5229\u7528\u5230\u6570\u7ec4\u7684\u5b9a\u4f4d\u6027\u80fd\u8fdb\u884c\u6570\u636e\u5b9a\u4f4d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u95ee\u9898\u89e3\u6790\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8981\u7edf\u8ba1\u6700\u70ed\u95e8\u67e5\u8be2\uff0c\u9996\u5148\u5c31\u662f\u8981\u7edf\u8ba1\u6bcf\u4e2aQuery\u51fa\u73b0\u7684\u6b21\u6570\uff0c\u7136\u540e\u6839\u636e\u7edf\u8ba1\u7ed3\u679c\uff0c\u627e\u51faTop 10\u3002\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u57fa\u4e8e\u8fd9\u4e2a\u601d\u8def\u5206\u4e24\u6b65\u6765\u8bbe\u8ba1\u8be5\u7b97\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5373\uff0c\u6b64\u95ee\u9898\u7684\u89e3\u51b3\u5206\u4e3a\u4ee5\u4e0b<strong>\u300c\u4fe9\u4e2a\u6b65\u9aa4\u300d<\/strong>\uff1a<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7b2c\u4e00\u6b65\uff1aQuery\u7edf\u8ba1<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Query\u7edf\u8ba1\u6709\u4ee5\u4e0b\u4fe9\u4e2a\u65b9\u6cd5\uff0c\u53ef\u4f9b\u9009\u62e9\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c1\u3001\u76f4\u63a5\u6392\u5e8f\u6cd5\u300d<\/strong>&nbsp;\u9996\u5148\u6211\u4eec\u6700\u5148\u60f3\u5230\u7684\u7684\u7b97\u6cd5\u5c31\u662f\u6392\u5e8f\u4e86\uff0c\u9996\u5148\u5bf9\u8fd9\u4e2a\u65e5\u5fd7\u91cc\u9762\u7684\u6240\u6709Query\u90fd\u8fdb\u884c\u6392\u5e8f\uff0c\u7136\u540e\u518d\u904d\u5386\u6392\u597d\u5e8f\u7684Query\uff0c\u7edf\u8ba1\u6bcf\u4e2aQuery\u51fa\u73b0\u7684\u6b21\u6570\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4f46\u662f\u9898\u76ee\u4e2d\u6709\u660e\u786e\u8981\u6c42\uff0c\u90a3\u5c31\u662f\u5185\u5b58\u4e0d\u80fd\u8d85\u8fc71G\uff0c\u4e00\u5343\u4e07\u6761\u8bb0\u5f55\uff0c\u6bcf\u6761\u8bb0\u5f55\u662f255Byte\uff0c\u5f88\u663e\u7136\u8981\u5360\u636e2.375G\u5185\u5b58\uff0c\u8fd9\u4e2a\u6761\u4ef6\u5c31\u4e0d\u6ee1\u8db3\u8981\u6c42\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8ba9\u6211\u4eec\u56de\u5fc6\u4e00\u4e0b\u6570\u636e\u7ed3\u6784\u8bfe\u7a0b\u4e0a\u7684\u5185\u5bb9\uff0c\u5f53\u6570\u636e\u91cf\u6bd4\u8f83\u5927\u800c\u4e14\u5185\u5b58\u65e0\u6cd5\u88c5\u4e0b\u7684\u65f6\u5019\uff0c\u6211\u4eec\u53ef\u4ee5\u91c7\u7528\u5916\u6392\u5e8f\u7684\u65b9\u6cd5\u6765\u8fdb\u884c\u6392\u5e8f\uff0c\u8fd9\u91cc\u6211\u4eec\u53ef\u4ee5\u91c7\u7528\u5f52\u5e76\u6392\u5e8f\uff0c\u56e0\u4e3a\u5f52\u5e76\u6392\u5e8f\u6709\u4e00\u4e2a\u6bd4\u8f83\u597d\u7684\u65f6\u95f4\u590d\u6742\u5ea6O(NlgN)\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6392\u5b8c\u5e8f\u4e4b\u540e\u6211\u4eec\u518d\u5bf9\u5df2\u7ecf\u6709\u5e8f\u7684Query\u6587\u4ef6\u8fdb\u884c\u904d\u5386\uff0c\u7edf\u8ba1\u6bcf\u4e2aQuery\u51fa\u73b0\u7684\u6b21\u6570\uff0c\u518d\u6b21\u5199\u5165\u6587\u4ef6\u4e2d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7efc\u5408\u5206\u6790\u4e00\u4e0b\uff0c\u6392\u5e8f\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(NlgN)\uff0c\u800c\u904d\u5386\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(N)\uff0c\u56e0\u6b64\u8be5\u7b97\u6cd5\u7684\u603b\u4f53\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(N+NlgN)=O\uff08NlgN\uff09\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c2\u3001Hash Table\u6cd5\u300d<\/strong> \u5728\u7b2c1\u4e2a\u65b9\u6cd5\u4e2d\uff0c\u6211\u4eec\u91c7\u7528\u4e86\u6392\u5e8f\u7684\u529e\u6cd5\u6765\u7edf\u8ba1\u6bcf\u4e2aQuery\u51fa\u73b0\u7684\u6b21\u6570\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662fNlgN\uff0c\u90a3\u4e48\u80fd\u4e0d\u80fd\u6709\u66f4\u597d\u7684\u65b9\u6cd5\u6765\u5b58\u50a8\uff0c\u800c\u65f6\u95f4\u590d\u6742\u5ea6\u66f4\u4f4e\u5462\uff1f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u9898\u76ee\u4e2d\u8bf4\u660e\u4e86\uff0c\u867d\u7136\u6709\u4e00\u5343\u4e07\u4e2aQuery\uff0c\u4f46\u662f\u7531\u4e8e\u91cd\u590d\u5ea6\u6bd4\u8f83\u9ad8\uff0c\u56e0\u6b64\u4e8b\u5b9e\u4e0a\u53ea\u6709300\u4e07\u7684Query\uff0c\u6bcf\u4e2aQuery255Byte\uff0c\u56e0\u6b64\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u628a\u4ed6\u4eec\u90fd\u653e\u8fdb\u5185\u5b58\u4e2d\u53bb\uff0c\u800c\u73b0\u5728\u53ea\u662f\u9700\u8981\u4e00\u4e2a\u5408\u9002\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5728\u8fd9\u91cc\uff0cHash Table\u7edd\u5bf9\u662f\u6211\u4eec\u4f18\u5148\u7684\u9009\u62e9\uff0c\u56e0\u4e3aHash Table\u7684\u67e5\u8be2\u901f\u5ea6\u975e\u5e38\u7684\u5feb\uff0c\u51e0\u4e4e\u662fO(1)\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u90a3\u4e48\uff0c\u6211\u4eec\u7684\u7b97\u6cd5\u5c31\u6709\u4e86\uff1a\u7ef4\u62a4\u4e00\u4e2aKey\u4e3aQuery\u5b57\u4e32\uff0cValue\u4e3a\u8be5Query\u51fa\u73b0\u6b21\u6570\u7684HashTable\uff0c\u6bcf\u6b21\u8bfb\u53d6\u4e00\u4e2aQuery\uff0c\u5982\u679c\u8be5\u5b57\u4e32\u4e0d\u5728Table\u4e2d\uff0c\u90a3\u4e48\u52a0\u5165\u8be5\u5b57\u4e32\uff0c\u5e76\u4e14\u5c06Value\u503c\u8bbe\u4e3a1\uff1b\u5982\u679c\u8be5\u5b57\u4e32\u5728Table\u4e2d\uff0c\u90a3\u4e48\u5c06\u8be5\u5b57\u4e32\u7684\u8ba1\u6570\u52a0\u4e00\u5373\u53ef\u3002\u6700\u7ec8\u6211\u4eec\u5728**O(N)**\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5185\u5b8c\u6210\u4e86\u5bf9\u8be5\u6d77\u91cf\u6570\u636e\u7684\u5904\u7406\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u672c\u65b9\u6cd5\u76f8\u6bd4\u7b97\u6cd51\uff1a\u5728\u65f6\u95f4\u590d\u6742\u5ea6\u4e0a\u63d0\u9ad8\u4e86\u4e00\u4e2a\u6570\u91cf\u7ea7\uff0c\u4e3aO\uff08N\uff09\uff0c\u4f46\u4e0d\u4ec5\u4ec5\u662f\u65f6\u95f4\u590d\u6742\u5ea6\u4e0a\u7684\u4f18\u5316\uff0c\u8be5\u65b9\u6cd5\u53ea\u9700\u8981IO\u6570\u636e\u6587\u4ef6\u4e00\u6b21\uff0c\u800c\u7b97\u6cd51\u7684IO\u6b21\u6570\u8f83\u591a\u7684\uff0c\u56e0\u6b64\u8be5\u7b97\u6cd52\u6bd4\u7b97\u6cd51\u5728\u5de5\u7a0b\u4e0a\u6709\u66f4\u597d\u7684\u53ef\u64cd\u4f5c\u6027\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u7b2c\u4e8c\u6b65\uff1a\u627e\u51faTop 10<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u7b97\u6cd5\u4e00\uff1a\u666e\u901a\u6392\u5e8f\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6211\u60f3\u5bf9\u4e8e\u6392\u5e8f\u7b97\u6cd5\u5927\u5bb6\u90fd\u5df2\u7ecf\u4e0d\u964c\u751f\u4e86\uff0c\u8fd9\u91cc\u4e0d\u5728\u8d58\u8ff0\uff0c\u6211\u4eec\u8981\u6ce8\u610f\u7684\u662f\u6392\u5e8f\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662fNlgN\uff0c\u5728\u672c\u9898\u76ee\u4e2d\uff0c\u4e09\u767e\u4e07\u6761\u8bb0\u5f55\uff0c\u75281G\u5185\u5b58\u662f\u53ef\u4ee5\u5b58\u4e0b\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u7b97\u6cd5\u4e8c\uff1a\u90e8\u5206\u6392\u5e8f\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u9898\u76ee\u8981\u6c42\u662f\u6c42\u51faTop 10\uff0c\u56e0\u6b64\u6211\u4eec\u6ca1\u6709\u5fc5\u8981\u5bf9\u6240\u6709\u7684Query\u90fd\u8fdb\u884c\u6392\u5e8f\uff0c\u6211\u4eec\u53ea\u9700\u8981\u7ef4\u62a4\u4e00\u4e2a10\u4e2a\u5927\u5c0f\u7684\u6570\u7ec4\uff0c\u521d\u59cb\u5316\u653e\u516510\u4e2aQuery\uff0c\u6309\u7167\u6bcf\u4e2aQuery\u7684\u7edf\u8ba1\u6b21\u6570\u7531\u5927\u5230\u5c0f\u6392\u5e8f\uff0c\u7136\u540e\u904d\u5386\u8fd9300\u4e07\u6761\u8bb0\u5f55\uff0c\u6bcf\u8bfb\u4e00\u6761\u8bb0\u5f55\u5c31\u548c\u6570\u7ec4\u6700\u540e\u4e00\u4e2aQuery\u5bf9\u6bd4\uff0c\u5982\u679c\u5c0f\u4e8e\u8fd9\u4e2aQuery\uff0c\u90a3\u4e48\u7ee7\u7eed\u904d\u5386\uff0c\u5426\u5219\uff0c\u5c06\u6570\u7ec4\u4e2d\u6700\u540e\u4e00\u6761\u6570\u636e\u6dd8\u6c70\uff0c\u52a0\u5165\u5f53\u524d\u7684Query\u3002\u6700\u540e\u5f53\u6240\u6709\u7684\u6570\u636e\u90fd\u904d\u5386\u5b8c\u6bd5\u4e4b\u540e\uff0c\u90a3\u4e48\u8fd9\u4e2a\u6570\u7ec4\u4e2d\u768410\u4e2aQuery\u4fbf\u662f\u6211\u4eec\u8981\u627e\u7684Top10\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0d\u96be\u5206\u6790\u51fa\uff0c\u8fd9\u6837\uff0c\u7b97\u6cd5\u7684\u6700\u574f\u65f6\u95f4\u590d\u6742\u5ea6\u662f<strong>\u300cN*K\u300d<\/strong>\uff0c \u5176\u4e2dK\u662f\u6307top\u591a\u5c11\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u7b97\u6cd5\u4e09\uff1a\u5806\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5728\u7b97\u6cd5\u4e8c\u4e2d\uff0c\u6211\u4eec\u5df2\u7ecf\u5c06\u65f6\u95f4\u590d\u6742\u5ea6\u7531NlogN\u4f18\u5316\u5230NK\uff0c\u4e0d\u5f97\u4e0d\u8bf4\u8fd9\u662f\u4e00\u4e2a\u6bd4\u8f83\u5927\u7684\u6539\u8fdb\u4e86\uff0c\u53ef\u662f\u6709\u6ca1\u6709\u66f4\u597d\u7684\u529e\u6cd5\u5462\uff1f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5206\u6790\u4e00\u4e0b\uff0c\u5728\u7b97\u6cd5\u4e8c\u4e2d\uff0c\u6bcf\u6b21\u6bd4\u8f83\u5b8c\u6210\u4e4b\u540e\uff0c\u9700\u8981\u7684\u64cd\u4f5c\u590d\u6742\u5ea6\u90fd\u662fK\uff0c\u56e0\u4e3a\u8981\u628a\u5143\u7d20\u63d2\u5165\u5230\u4e00\u4e2a\u7ebf\u6027\u8868\u4e4b\u4e2d\uff0c\u800c\u4e14\u91c7\u7528\u7684\u662f\u987a\u5e8f\u6bd4\u8f83\u3002\u8fd9\u91cc\u6211\u4eec\u6ce8\u610f\u4e00\u4e0b\uff0c\u8be5\u6570\u7ec4\u662f\u6709\u5e8f\u7684\uff0c\u4e00\u6b21\u6211\u4eec\u6bcf\u6b21\u67e5\u627e\u7684\u65f6\u5019\u53ef\u4ee5\u91c7\u7528\u4e8c\u5206\u7684\u65b9\u6cd5\u67e5\u627e\uff0c\u8fd9\u6837\u64cd\u4f5c\u7684\u590d\u6742\u5ea6\u5c31\u964d\u5230\u4e86logK\uff0c\u53ef\u662f\uff0c\u968f\u4e4b\u800c\u6765\u7684\u95ee\u9898\u5c31\u662f\u6570\u636e\u79fb\u52a8\uff0c\u56e0\u4e3a\u79fb\u52a8\u6570\u636e\u6b21\u6570\u589e\u591a\u4e86\u3002\u4e0d\u8fc7\uff0c\u8fd9\u4e2a\u7b97\u6cd5\u8fd8\u662f\u6bd4\u7b97\u6cd5\u4e8c\u6709\u4e86\u6539\u8fdb\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u57fa\u4e8e\u4ee5\u4e0a\u7684\u5206\u6790\uff0c\u6211\u4eec\u60f3\u60f3\uff0c\u6709\u6ca1\u6709\u4e00\u79cd\u65e2\u80fd\u5feb\u901f\u67e5\u627e\uff0c\u53c8\u80fd\u5feb\u901f\u79fb\u52a8\u5143\u7d20\u7684\u6570\u636e\u7ed3\u6784\u5462\uff1f\u56de\u7b54\u662f\u80af\u5b9a\u7684\uff0c\u90a3\u5c31\u662f\u5806\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u501f\u52a9\u5806\u7ed3\u6784\uff0c\u6211\u4eec\u53ef\u4ee5\u5728log\u91cf\u7ea7\u7684\u65f6\u95f4\u5185\u67e5\u627e\u548c\u8c03\u6574\/\u79fb\u52a8\u3002\u56e0\u6b64\u5230\u8fd9\u91cc\uff0c\u6211\u4eec\u7684\u7b97\u6cd5\u53ef\u4ee5\u6539\u8fdb\u4e3a\u8fd9\u6837\uff0c\u7ef4\u62a4\u4e00\u4e2aK(\u8be5\u9898\u76ee\u4e2d\u662f10)\u5927\u5c0f\u7684\u5c0f\u6839\u5806\uff0c\u7136\u540e\u904d\u5386300\u4e07\u7684Query\uff0c<strong>\u300c\u5206\u522b\u548c\u6839\u5143\u7d20\u8fdb\u884c\u5bf9\u6bd4\u3002\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5177\u4f53\u8fc7\u7a0b\u662f\uff0c\u5806\u9876\u5b58\u653e\u7684\u662f\u6574\u4e2a\u5806\u4e2d\u6700\u5c0f\u7684\u6570\uff0c\u73b0\u5728\u904d\u5386N\u4e2a\u6570\uff0c\u628a\u6700\u5148\u904d\u5386\u5230\u7684k\u4e2a\u6570\u5b58\u653e\u5230\u6700\u5c0f\u5806\u4e2d\uff0c\u5e76\u5047\u8bbe\u5b83\u4eec\u5c31\u662f\u6211\u4eec\u8981\u627e\u7684\u6700\u5927\u7684k\u4e2a\u6570\uff0cX1&gt;X2&#8230;Xmin(\u5806\u9876)\uff0c\u800c\u540e\u904d\u5386\u540e\u7eed\u7684N-K\u4e2a\u6570\uff0c\u4e00\u4e00\u4e0e\u5806\u9876\u5143\u7d20\u8fdb\u884c\u6bd4\u8f83\uff0c\u5982\u679c\u904d\u5386\u5230\u7684Xi\u5927\u4e8e\u5806\u9876\u5143\u7d20Xmin\uff0c\u5219\u628aXi\u653e\u5165\u5806\u4e2d\uff0c\u800c\u540e\u66f4\u65b0\u6574\u4e2a\u5806\uff0c\u66f4\u65b0\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e3alogK\uff0c\u5982\u679cXi&lt;Xmin\uff0c\u5219\u4e0d\u66f4\u65b0\u5806\uff0c\u6574\u4e2a\u8fc7\u7a0b\u7684\u590d\u6742\u5ea6\u4e3aO(K)+O(\uff08N-K\uff09*logK)=O\uff08N*logK\uff09\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5806\u6392\u5e8f\u76843D\u52a8\u753b\u6f14\u793a\u53ef\u4ee5\u53c2\u770b\u6b64\u94fe\u63a5\uff1a<code>http:\/\/www.benfrederickson.com\/2013\/10\/10\/heap-visualization.html<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u601d\u60f3\u4e0e\u4e0a\u8ff0\u7b97\u6cd5\u4e8c\u4e00\u81f4\uff0c\u53ea\u662f\u7b97\u6cd5\u5728\u7b97\u6cd5\u4e09\uff0c\u6211\u4eec\u91c7\u7528\u4e86\u6700\u5c0f\u5806\u8fd9\u79cd\u6570\u636e\u7ed3\u6784\u4ee3\u66ff\u6570\u7ec4\uff0c\u628a\u67e5\u627e\u76ee\u6807\u5143\u7d20\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6709O\uff08K\uff09\u964d\u5230\u4e86O\uff08logK\uff09\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u90a3\u4e48\u8fd9\u6837\uff0c\u91c7\u7528\u5806\u6570\u636e\u7ed3\u6784\uff0c\u7b97\u6cd5\u4e09\uff0c\u6700\u7ec8\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u964d\u5230\u4e86<strong>\u300cN\u2018logK\u300d<\/strong>\uff0c\u548c\u7b97\u6cd5\u4e8c\u76f8\u6bd4\uff0c\u53c8\u6709\u4e86\u6bd4\u8f83\u5927\u7684\u6539\u8fdb\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u603b\u7ed3\uff1a\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u81f3\u6b64\uff0c\u7b97\u6cd5\u5c31\u5b8c\u5168\u7ed3\u675f\u4e86\uff0c\u7ecf\u8fc7\u4e0a\u8ff0\u7b2c\u4e00\u6b65\u3001\u5148\u7528Hash\u8868\u7edf\u8ba1\u6bcf\u4e2aQuery\u51fa\u73b0\u7684\u6b21\u6570\uff0cO\uff08N\uff09\uff1b\u7136\u540e\u7b2c\u4e8c\u6b65\u3001\u91c7\u7528\u5806\u6570\u636e\u7ed3\u6784\u627e\u51faTop 10\uff0cN*O\uff08logK\uff09\u3002\u6240\u4ee5\uff0c\u6211\u4eec\u6700\u7ec8\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f\uff1a<strong>\u300cO\uff08N\uff09 + N&#8217;*O\uff08logK\uff09\u3002\u300d<\/strong>\uff08N\u4e3a1000\u4e07\uff0cN\u2019\u4e3a300\u4e07\uff09\u3002\u5982\u679c\u5404\u4f4d\u6709\u4ec0\u4e48\u66f4\u597d\u7684\u7b97\u6cd5\uff0c\u6b22\u8fce\u7559\u8a00\u8bc4\u8bba\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7b2c\u4e8c\u90e8\u5206\u3001Hash\u8868 \u7b97\u6cd5\u7684\u8be6\u7ec6\u89e3\u6790<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u4ec0\u4e48\u662fHash<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Hash\uff0c\u4e00\u822c\u7ffb\u8bd1\u505a\u201c\u6563\u5217\u201d\uff0c\u4e5f\u6709\u76f4\u63a5\u97f3\u8bd1\u4e3a\u201c\u54c8\u5e0c\u201d\u7684\uff0c\u5c31\u662f\u628a\u4efb\u610f\u957f\u5ea6\u7684\u8f93\u5165\uff08\u53c8\u53eb\u505a\u9884\u6620\u5c04\uff0c pre-image\uff09\uff0c\u901a\u8fc7\u6563\u5217\u7b97\u6cd5\uff0c\u53d8\u6362\u6210\u56fa\u5b9a\u957f\u5ea6\u7684\u8f93\u51fa\uff0c\u8be5\u8f93\u51fa\u5c31\u662f\u6563\u5217\u503c\u3002\u8fd9\u79cd\u8f6c\u6362\u662f\u4e00\u79cd\u538b\u7f29\u6620\u5c04\uff0c\u4e5f\u5c31\u662f\uff0c\u6563\u5217\u503c\u7684\u7a7a\u95f4\u901a\u5e38\u8fdc\u5c0f\u4e8e\u8f93\u5165\u7684\u7a7a\u95f4\uff0c\u4e0d\u540c\u7684\u8f93\u5165\u53ef\u80fd\u4f1a\u6563\u5217\u6210\u76f8\u540c\u7684\u8f93\u51fa\uff0c\u800c\u4e0d\u53ef\u80fd\u4ece\u6563\u5217\u503c\u6765\u552f\u4e00\u7684\u786e\u5b9a\u8f93\u5165\u503c\u3002\u7b80\u5355\u7684\u8bf4\u5c31\u662f\u4e00\u79cd\u5c06\u4efb\u610f\u957f\u5ea6\u7684\u6d88\u606f\u538b\u7f29\u5230\u67d0\u4e00\u56fa\u5b9a\u957f\u5ea6\u7684\u6d88\u606f\u6458\u8981\u7684\u51fd\u6570\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">HASH\u4e3b\u8981\u7528\u4e8e\u4fe1\u606f\u5b89\u5168\u9886\u57df\u4e2d\u52a0\u5bc6\u7b97\u6cd5\uff0c\u5b83\u628a\u4e00\u4e9b\u4e0d\u540c\u957f\u5ea6\u7684\u4fe1\u606f\u8f6c\u5316\u6210\u6742\u4e71\u7684128\u4f4d\u7684\u7f16\u7801,\u8fd9\u4e9b\u7f16\u7801\u503c\u53eb\u505aHASH\u503c. \u4e5f\u53ef\u4ee5\u8bf4\uff0chash\u5c31\u662f\u627e\u5230\u4e00\u79cd\u6570\u636e\u5185\u5bb9\u548c\u6570\u636e\u5b58\u653e\u5730\u5740\u4e4b\u95f4\u7684\u6620\u5c04\u5173\u7cfb\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6570\u7ec4\u7684\u7279\u70b9\u662f\uff1a\u5bfb\u5740\u5bb9\u6613\uff0c\u63d2\u5165\u548c\u5220\u9664\u56f0\u96be\uff1b\u800c\u94fe\u8868\u7684\u7279\u70b9\u662f\uff1a\u5bfb\u5740\u56f0\u96be\uff0c\u63d2\u5165\u548c\u5220\u9664\u5bb9\u6613\u3002\u90a3\u4e48\u6211\u4eec\u80fd\u4e0d\u80fd\u7efc\u5408\u4e24\u8005\u7684\u7279\u6027\uff0c\u505a\u51fa\u4e00\u79cd\u5bfb\u5740\u5bb9\u6613\uff0c\u63d2\u5165\u5220\u9664\u4e5f\u5bb9\u6613\u7684\u6570\u636e\u7ed3\u6784\uff1f\u7b54\u6848\u662f\u80af\u5b9a\u7684\uff0c\u8fd9\u5c31\u662f\u6211\u4eec\u8981\u63d0\u8d77\u7684\u54c8\u5e0c\u8868\uff0c\u54c8\u5e0c\u8868\u6709\u591a\u79cd\u4e0d\u540c\u7684\u5b9e\u73b0\u65b9\u6cd5\uff0c\u6211\u63a5\u4e0b\u6765\u89e3\u91ca\u7684\u662f\u6700\u5e38\u7528\u7684\u4e00\u79cd\u65b9\u6cd5\u2014\u2014\u62c9\u94fe\u6cd5\uff0c\u6211\u4eec\u53ef\u4ee5\u7406\u89e3\u4e3a\u201c\u94fe\u8868\u7684\u6570\u7ec4\u201d\uff0c\u5982\u56fe\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/xmt1139057136\/xttblog\/2023\/02\/top_k.jpg\" alt=\"\u94fe\u8868\u7684\u6570\u7ec4\" \/><figcaption>\u94fe\u8868\u7684\u6570\u7ec4<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u5de6\u8fb9\u5f88\u660e\u663e\u662f\u4e2a\u6570\u7ec4\uff0c\u6570\u7ec4\u7684\u6bcf\u4e2a\u6210\u5458\u5305\u62ec\u4e00\u4e2a\u6307\u9488\uff0c\u6307\u5411\u4e00\u4e2a\u94fe\u8868\u7684\u5934\uff0c\u5f53\u7136\u8fd9\u4e2a\u94fe\u8868\u53ef\u80fd\u4e3a\u7a7a\uff0c\u4e5f\u53ef\u80fd\u5143\u7d20\u5f88\u591a\u3002\u6211\u4eec\u6839\u636e\u5143\u7d20\u7684\u4e00\u4e9b\u7279\u5f81\u628a\u5143\u7d20\u5206\u914d\u5230\u4e0d\u540c\u7684\u94fe\u8868\u4e2d\u53bb\uff0c\u4e5f\u662f\u6839\u636e\u8fd9\u4e9b\u7279\u5f81\uff0c\u627e\u5230\u6b63\u786e\u7684\u94fe\u8868\uff0c\u518d\u4ece\u94fe\u8868\u4e2d\u627e\u51fa\u8fd9\u4e2a\u5143\u7d20\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5143\u7d20\u7279\u5f81\u8f6c\u53d8\u4e3a\u6570\u7ec4\u4e0b\u6807\u7684\u65b9\u6cd5\u5c31\u662f\u6563\u5217\u6cd5\u3002\u6563\u5217\u6cd5\u5f53\u7136\u4e0d\u6b62\u4e00\u79cd\uff0c\u4e0b\u9762\u5217\u51fa\u4e09\u79cd\u6bd4\u8f83\u5e38\u7528\u7684\uff1a<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">1\uff0c\u9664\u6cd5\u6563\u5217\u6cd5<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u76f4\u89c2\u7684\u4e00\u79cd\uff0c\u4e0a\u56fe\u4f7f\u7528\u7684\u5c31\u662f\u8fd9\u79cd\u6563\u5217\u6cd5\uff0c\u516c\u5f0f\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>index = value % 16<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5b66\u8fc7\u6c47\u7f16\u7684\u90fd\u77e5\u9053\uff0c\u6c42\u6a21\u6570\u5176\u5b9e\u662f\u901a\u8fc7\u4e00\u4e2a\u9664\u6cd5\u8fd0\u7b97\u5f97\u5230\u7684\uff0c\u6240\u4ee5\u53eb\u201c\u9664\u6cd5\u6563\u5217\u6cd5\u201d\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2\uff0c\u5e73\u65b9\u6563\u5217\u6cd5<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u6c42index\u662f\u975e\u5e38\u9891\u7e41\u7684\u64cd\u4f5c\uff0c\u800c\u4e58\u6cd5\u7684\u8fd0\u7b97\u8981\u6bd4\u9664\u6cd5\u6765\u5f97\u7701\u65f6\uff08\u5bf9\u73b0\u5728\u7684CPU\u6765\u8bf4\uff0c\u4f30\u8ba1\u6211\u4eec\u611f\u89c9\u4e0d\u51fa\u6765\uff09\uff0c\u6240\u4ee5\u6211\u4eec\u8003\u8651\u628a\u9664\u6cd5\u6362\u6210\u4e58\u6cd5\u548c\u4e00\u4e2a\u4f4d\u79fb\u64cd\u4f5c\u3002\u516c\u5f0f\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>index = (value * value) &gt;&gt; 28<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\uff08<strong>\u300c\u53f3\u79fb\uff0c\u9664\u4ee52^28\u3002\u8bb0\u6cd5\uff1a\u5de6\u79fb\u53d8\u5927\uff0c\u662f\u4e58\u3002\u53f3\u79fb\u53d8\u5c0f\uff0c\u662f\u9664\u3002\u300d<\/strong>\uff09<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c\u6570\u503c\u5206\u914d\u6bd4\u8f83\u5747\u5300\u7684\u8bdd\u8fd9\u79cd\u65b9\u6cd5\u80fd\u5f97\u5230\u4e0d\u9519\u7684\u7ed3\u679c\uff0c\u4f46\u6211\u4e0a\u9762\u753b\u7684\u90a3\u4e2a\u56fe\u7684\u5404\u4e2a\u5143\u7d20\u7684\u503c\u7b97\u51fa\u6765\u7684index\u90fd\u662f0\u2014\u2014\u975e\u5e38\u5931\u8d25\u3002\u4e5f\u8bb8\u4f60\u8fd8\u6709\u4e2a\u95ee\u9898\uff0cvalue\u5982\u679c\u5f88\u5927\uff0cvalue * value\u4e0d\u4f1a\u6ea2\u51fa\u5417\uff1f\u7b54\u6848\u662f\u4f1a\u7684\uff0c\u4f46\u6211\u4eec\u8fd9\u4e2a\u4e58\u6cd5\u4e0d\u5173\u5fc3\u6ea2\u51fa\uff0c\u56e0\u4e3a\u6211\u4eec\u6839\u672c\u4e0d\u662f\u4e3a\u4e86\u83b7\u53d6\u76f8\u4e58\u7ed3\u679c\uff0c\u800c\u662f\u4e3a\u4e86\u83b7\u53d6index\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">3\uff0c\u6590\u6ce2\u90a3\u5951\uff08Fibonacci\uff09\u6563\u5217\u6cd5**<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u5e73\u65b9\u6563\u5217\u6cd5\u7684\u7f3a\u70b9\u662f\u663e\u800c\u6613\u89c1\u7684\uff0c\u6240\u4ee5\u6211\u4eec\u80fd\u4e0d\u80fd\u627e\u51fa\u4e00\u4e2a\u7406\u60f3\u7684\u4e58\u6570\uff0c\u800c\u4e0d\u662f\u62ffvalue\u672c\u8eab\u5f53\u4f5c\u4e58\u6570\u5462\uff1f\u7b54\u6848\u662f\u80af\u5b9a\u7684\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">1\uff0c\u5bf9\u4e8e16\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u8fd9\u4e2a\u4e58\u6570\u662f40503<br>\n2\uff0c\u5bf9\u4e8e32\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u8fd9\u4e2a\u4e58\u6570\u662f2654435769<br>\n3\uff0c\u5bf9\u4e8e64\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u8fd9\u4e2a\u4e58\u6570\u662f11400714819323198485<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u51e0\u4e2a\u201c\u7406\u60f3\u4e58\u6570\u201d\u662f\u5982\u4f55\u5f97\u51fa\u6765\u7684\u5462\uff1f\u8fd9\u8ddf\u4e00\u4e2a\u6cd5\u5219\u6709\u5173\uff0c\u53eb\u9ec4\u91d1\u5206\u5272\u6cd5\u5219\uff0c\u800c\u63cf\u8ff0\u9ec4\u91d1\u5206\u5272\u6cd5\u5219\u7684\u6700\u7ecf\u5178\u8868\u8fbe\u5f0f\u65e0\u7591\u5c31\u662f\u8457\u540d\u7684\u6590\u6ce2\u90a3\u5951\u6570\u5217\uff0c\u5373\u5982\u6b64\u5f62\u5f0f\u7684\u5e8f\u5217\uff1a0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610\uff0c 987, 1597, 2584, 4181, 6765, 10946\uff0c\u2026\u3002\u53e6\u5916\uff0c\u6590\u6ce2\u90a3\u5951\u6570\u5217\u7684\u503c\u548c\u592a\u9633\u7cfb\u516b\u5927\u884c\u661f\u7684\u8f68\u9053\u534a\u5f84\u7684\u6bd4\u4f8b\u51fa\u5947\u543b\u5408\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5bf9\u6211\u4eec\u5e38\u89c1\u768432\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u516c\u5f0f\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>index = (value * 2654435769) &gt;&gt; 28<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c\u7528\u8fd9\u79cd\u6590\u6ce2\u90a3\u5951\u6563\u5217\u6cd5\u7684\u8bdd\uff0c\u90a3\u4e0a\u9762\u7684\u56fe\u5c31\u53d8\u6210\u8fd9\u6837\u4e86\uff1a<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter\"><img decoding=\"async\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/xmt1139057136\/xttblog\/2023\/02\/top_hash.jpg\" alt=\"\u6590\u6ce2\u90a3\u5951\u6563\u5217\u6cd5\" \/><figcaption>\u6590\u6ce2\u90a3\u5951\u6563\u5217\u6cd5<\/figcaption><\/figure><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">\u6ce8\uff1a\u7528\u6590\u6ce2\u90a3\u5951\u6563\u5217\u6cd5\u8c03\u6574\u4e4b\u540e\u4f1a\u6bd4\u539f\u6765\u7684\u53d6\u6478\u6563\u5217\u6cd5\u597d\u5f88\u591a\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u9002\u7528\u8303\u56f4\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5feb\u901f\u67e5\u627e\uff0c\u5220\u9664\u7684\u57fa\u672c\u6570\u636e\u7ed3\u6784\uff0c\u901a\u5e38\u9700\u8981\u603b\u6570\u636e\u91cf\u53ef\u4ee5\u653e\u5165\u5185\u5b58\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u57fa\u672c\u539f\u7406\u53ca\u8981\u70b9\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">hash\u51fd\u6570\u9009\u62e9\uff0c\u9488\u5bf9\u5b57\u7b26\u4e32\uff0c\u6574\u6570\uff0c\u6392\u5217\uff0c\u5177\u4f53\u76f8\u5e94\u7684hash\u65b9\u6cd5\u3002<br>\n\u78b0\u649e\u5904\u7406\uff0c\u4e00\u79cd\u662fopen hashing\uff0c\u4e5f\u79f0\u4e3a\u62c9\u94fe\u6cd5\uff1b\u53e6\u4e00\u79cd\u5c31\u662fclosed hashing\uff0c\u4e5f\u79f0\u5f00\u5730\u5740\u6cd5\uff0copened addressing\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u6269\u5c55\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">d-left hashing\u4e2d\u7684d\u662f\u591a\u4e2a\u7684\u610f\u601d\uff0c\u6211\u4eec\u5148\u7b80\u5316\u8fd9\u4e2a\u95ee\u9898\uff0c\u770b\u4e00\u770b2-left hashing\u30022-left hashing\u6307\u7684\u662f\u5c06\u4e00\u4e2a\u54c8\u5e0c\u8868\u5206\u6210\u957f\u5ea6\u76f8\u7b49\u7684\u4e24\u534a\uff0c\u5206\u522b\u53eb\u505aT1\u548cT2\uff0c\u7ed9T1\u548cT2\u5206\u522b\u914d\u5907\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570\uff0ch1\u548ch2\u3002\u5728\u5b58\u50a8\u4e00\u4e2a\u65b0\u7684key\u65f6\uff0c\u540c \u65f6\u7528\u4e24\u4e2a\u54c8\u5e0c\u51fd\u6570\u8fdb\u884c\u8ba1\u7b97\uff0c\u5f97\u51fa\u4e24\u4e2a\u5730\u5740h1[key]\u548ch2[key]\u3002\u8fd9\u65f6\u9700\u8981\u68c0\u67e5T1\u4e2d\u7684h1[key]\u4f4d\u7f6e\u548cT2\u4e2d\u7684h2[key]\u4f4d\u7f6e\uff0c\u54ea\u4e00\u4e2a \u4f4d\u7f6e\u5df2\u7ecf\u5b58\u50a8\u7684\uff08\u6709\u78b0\u649e\u7684\uff09key\u6bd4\u8f83\u591a\uff0c\u7136\u540e\u5c06\u65b0key\u5b58\u50a8\u5728\u8d1f\u8f7d\u5c11\u7684\u4f4d\u7f6e\u3002\u5982\u679c\u4e24\u8fb9\u4e00\u6837\u591a\uff0c\u6bd4\u5982\u4e24\u4e2a\u4f4d\u7f6e\u90fd\u4e3a\u7a7a\u6216\u8005\u90fd\u5b58\u50a8\u4e86\u4e00\u4e2akey\uff0c\u5c31\u628a\u65b0key \u5b58\u50a8\u5728\u5de6\u8fb9\u7684T1\u5b50\u8868\u4e2d\uff0c2-left\u4e5f\u7531\u6b64\u800c\u6765\u3002\u5728\u67e5\u627e\u4e00\u4e2akey\u65f6\uff0c\u5fc5\u987b\u8fdb\u884c\u4e24\u6b21hash\uff0c\u540c\u65f6\u67e5\u627e\u4e24\u4e2a\u4f4d\u7f6e\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><code>\u95ee\u9898\u5b9e\u4f8b\uff08\u6d77\u91cf\u6570\u636e\u5904\u7406<\/code><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6211\u4eec\u77e5\u9053hash \u8868\u5728\u6d77\u91cf\u6570\u636e\u5904\u7406\u4e2d\u6709\u7740\u5e7f\u6cdb\u7684\u5e94\u7528\uff0c\u4e0b\u9762\uff0c\u8bf7\u770b\u53e6\u4e00\u9053\u767e\u5ea6\u9762\u8bd5\u9898\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u9898\u76ee\uff1a<code>\u6d77\u91cf\u65e5\u5fd7\u6570\u636e\uff0c\u63d0\u53d6\u51fa\u67d0\u65e5\u8bbf\u95ee\u767e\u5ea6\u6b21\u6570\u6700\u591a\u7684\u90a3\u4e2aIP<\/code>\u3002<br>\n\u65b9\u6848\uff1aIP\u7684\u6570\u76ee\u8fd8\u662f\u6709\u9650\u7684\uff0c\u6700\u591a2^32\u4e2a\uff0c\u6240\u4ee5\u53ef\u4ee5\u8003\u8651\u4f7f\u7528hash\u5c06ip\u76f4\u63a5\u5b58\u5165\u5185\u5b58\uff0c\u7136\u540e\u8fdb\u884c\u7edf\u8ba1\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u7b2c\u4e09\u90e8\u5206\u3001\u6700\u5feb\u7684Hash\u8868\u7b97\u6cd5**<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u63a5\u4e0b\u6765\uff0c\u54b1\u4eec\u6765\u5177\u4f53\u5206\u6790\u4e00\u4e0b\u4e00\u4e2a\u6700\u5feb\u7684Hasb\u8868\u7b97\u6cd5\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6211\u4eec\u7531\u4e00\u4e2a\u7b80\u5355\u7684\u95ee\u9898\u9010\u6b65\u5165\u624b\uff1a\u6709\u4e00\u4e2a\u5e9e\u5927\u7684\u5b57\u7b26\u4e32\u6570\u7ec4\uff0c\u7136\u540e\u7ed9\u4f60\u4e00\u4e2a\u5355\u72ec\u7684\u5b57\u7b26\u4e32\uff0c\u8ba9\u4f60\u4ece\u8fd9\u4e2a\u6570\u7ec4\u4e2d\u67e5\u627e\u662f\u5426\u6709\u8fd9\u4e2a\u5b57\u7b26\u4e32\u5e76\u627e\u5230\u5b83\uff0c\u4f60\u4f1a\u600e\u4e48\u505a\uff1f\u6709\u4e00\u4e2a\u65b9\u6cd5\u6700\u7b80\u5355\uff0c\u8001\u8001\u5b9e\u5b9e\u4ece\u5934\u67e5\u5230\u5c3e\uff0c\u4e00\u4e2a\u4e00\u4e2a\u6bd4\u8f83\uff0c\u76f4\u5230\u627e\u5230\u4e3a\u6b62\uff0c\u6211\u60f3\u53ea\u8981\u5b66\u8fc7\u7a0b\u5e8f\u8bbe\u8ba1\u7684\u4eba\u90fd\u80fd\u628a\u8fd9\u6837\u4e00\u4e2a\u7a0b\u5e8f\u4f5c\u51fa\u6765\uff0c\u4f46\u8981\u662f\u6709\u7a0b\u5e8f\u5458\u628a\u8fd9\u6837\u7684\u7a0b\u5e8f\u4ea4\u7ed9\u7528\u6237\uff0c\u6211\u53ea\u80fd\u7528\u65e0\u8bed\u6765\u8bc4\u4ef7\uff0c\u6216\u8bb8\u5b83\u771f\u7684\u80fd\u5de5\u4f5c\uff0c\u4f46&#8230;\u4e5f\u53ea\u80fd\u5982\u6b64\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u5408\u9002\u7684\u7b97\u6cd5\u81ea\u7136\u662f\u4f7f\u7528HashTable\uff08\u54c8\u5e0c\u8868\uff09\uff0c\u5148\u4ecb\u7ecd\u4ecb\u7ecd\u5176\u4e2d\u7684\u57fa\u672c\u77e5\u8bc6\uff0c\u6240\u8c13Hash\uff0c\u4e00\u822c\u662f\u4e00\u4e2a\u6574\u6570\uff0c\u901a\u8fc7\u67d0\u79cd\u7b97\u6cd5\uff0c\u53ef\u4ee5\u628a\u4e00\u4e2a\u5b57\u7b26\u4e32&#8221;\u538b\u7f29&#8221; \u6210\u4e00\u4e2a\u6574\u6570\u3002\u5f53\u7136\uff0c\u65e0\u8bba\u5982\u4f55\uff0c\u4e00\u4e2a32\u4f4d\u6574\u6570\u662f\u65e0\u6cd5\u5bf9\u5e94\u56de\u4e00\u4e2a\u5b57\u7b26\u4e32\u7684\uff0c\u4f46\u5728\u7a0b\u5e8f\u4e2d\uff0c\u4e24\u4e2a\u5b57\u7b26\u4e32\u8ba1\u7b97\u51fa\u7684Hash\u503c\u76f8\u7b49\u7684\u53ef\u80fd\u975e\u5e38\u5c0f\uff0c\u4e0b\u9762\u770b\u770b\u5728MPQ\u4e2d\u7684Hash\u7b97\u6cd5\uff08\u53c2\u770b\u81ea\u6b64\u6587\uff1a<code>http:\/\/sfsrealm.hopto.org\/inside_mopaq\/chapter2.htm<\/code>\uff09<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u51fd\u6570\u4e00\u3001\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ee5\u4e0b\u7684\u51fd\u6570\u751f\u6210\u4e00\u4e2a\u957f\u5ea6\u4e3a0x500\uff08\u540810\u8fdb\u5236\u6570\uff1a1280\uff09\u7684cryptTable[0x500]<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>void prepareCryptTable()  \n{  \n\u00a0\u00a0\u00a0 unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;\n\n\u00a0\u00a0\u00a0\u00a0 for( index1 = 0; index1 &lt; 0x100; index1++ )  \n\u00a0\u00a0\u00a0 {  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 for( index2 = index1, i = 0; i &lt; 5; i++, index2 += 0x100 )  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 unsigned long temp1, temp2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 seed = (seed * 125 + 3) % 0x2AAAAB;  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 temp1 = (seed &amp; 0xFFFF) &lt;&lt; 0x10;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 seed = (seed * 125 + 3) % 0x2AAAAB;  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 temp2 = (seed &amp; 0xFFFF);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 cryptTable[index2] = ( temp1 | temp2 );  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 }  \n\u00a0\u00a0 }  \n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u51fd\u6570\u4e8c\u3001\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ee5\u4e0b\u51fd\u6570\u8ba1\u7b97lpszFileName \u5b57\u7b26\u4e32\u7684hash\u503c\uff0c\u5176\u4e2ddwHashType \u4e3ahash\u7684\u7c7b\u578b\uff0c\u5728\u4e0b\u9762\u7684<strong>\u300c\u51fd\u6570\u4e09\u300d<\/strong>\u3001GetHashTablePos\u51fd\u6570\u4e2d\u8c03\u7528\u6b64\u51fd\u6570\u4e8c\uff0c\u5176\u53ef\u4ee5\u53d6\u7684\u503c\u4e3a0\u30011\u30012\uff1b\u8be5\u51fd\u6570\u8fd4\u56delpszFileName \u5b57\u7b26\u4e32\u7684hash\u503c\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>unsigned long HashString( char *lpszFileName, unsigned long dwHashType )  \n{  \n\u00a0\u00a0\u00a0 unsigned char *key\u00a0 = (unsigned char *)lpszFileName;  \nunsigned long seed1 = 0x7FED7FED;  \nunsigned long seed2 = 0xEEEEEEEE;  \n\u00a0\u00a0\u00a0 int ch;\n\n\u00a0\u00a0\u00a0\u00a0 while( *key != 0 )  \n\u00a0\u00a0\u00a0 {  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 ch = toupper(*key++);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 seed1 = cryptTable[(dwHashType &lt;&lt; 8) + ch] ^ (seed1 + seed2);  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 seed2 = ch + seed1 + seed2 + (seed2 &lt;&lt; 5) + 3;  \n\u00a0\u00a0\u00a0 }  \n\u00a0\u00a0\u00a0 return seed1;  \n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">Blizzard\u7684\u8fd9\u4e2a\u7b97\u6cd5\u662f\u975e\u5e38\u9ad8\u6548\u7684\uff0c\u88ab\u79f0\u4e3a&#8221;One-Way Hash&#8221;( A one-way hash is a an algorithm that is constructed in such a way that deriving the original string (set of strings, actually) is virtually impossible)\u3002\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5b57\u7b26\u4e32&#8221;unitneutralacritter.grp&#8221;\u901a\u8fc7\u8fd9\u4e2a\u7b97\u6cd5\u5f97\u5230\u7684\u7ed3\u679c\u662f0xA26067F3\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u662f\u4e0d\u662f\u628a\u7b2c\u4e00\u4e2a\u7b97\u6cd5\u6539\u8fdb\u4e00\u4e0b\uff0c\u6539\u6210\u9010\u4e2a\u6bd4\u8f83\u5b57\u7b26\u4e32\u7684Hash\u503c\u5c31\u53ef\u4ee5\u4e86\u5462\uff0c\u7b54\u6848\u662f\uff0c\u8fdc\u8fdc\u4e0d\u591f\uff0c\u8981\u60f3\u5f97\u5230\u6700\u5feb\u7684\u7b97\u6cd5\uff0c\u5c31\u4e0d\u80fd\u8fdb\u884c\u9010\u4e2a\u7684\u6bd4\u8f83\uff0c\u901a\u5e38\u662f\u6784\u9020\u4e00\u4e2a<strong>\u300c\u54c8\u5e0c\u8868\u300d<\/strong>(Hash Table)\u6765\u89e3\u51b3\u95ee\u9898\uff0c\u54c8\u5e0c\u8868\u662f\u4e00\u4e2a\u5927\u6570\u7ec4\uff0c\u8fd9\u4e2a\u6570\u7ec4\u7684\u5bb9\u91cf\u6839\u636e\u7a0b\u5e8f\u7684\u8981\u6c42\u6765\u5b9a\u4e49\uff0c\u4f8b\u59821024\uff0c\u6bcf\u4e00\u4e2aHash\u503c\u901a\u8fc7\u53d6\u6a21\u8fd0\u7b97 (mod) \u5bf9\u5e94\u5230\u6570\u7ec4\u4e2d\u7684\u4e00\u4e2a\u4f4d\u7f6e\uff0c\u8fd9\u6837\uff0c\u53ea\u8981\u6bd4\u8f83\u8fd9\u4e2a\u5b57\u7b26\u4e32\u7684\u54c8\u5e0c\u503c\u5bf9\u5e94\u7684\u4f4d\u7f6e\u6709\u6ca1\u6709\u88ab\u5360\u7528\uff0c\u5c31\u53ef\u4ee5\u5f97\u5230\u6700\u540e\u7684\u7ed3\u679c\u4e86\uff0c\u60f3\u60f3\u8fd9\u662f\u4ec0\u4e48\u901f\u5ea6\uff1f\u662f\u7684\uff0c\u662f\u6700\u5feb\u7684O(1)\uff0c\u73b0\u5728\u4ed4\u7ec6\u770b\u770b\u8fd9\u4e2a\u7b97\u6cd5\u5427\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>typedef struct  \n{  \n\u00a0\u00a0\u00a0 int nHashA;  \n\u00a0\u00a0\u00a0 int nHashB;  \n\u00a0\u00a0\u00a0 char bExists;  \n\u00a0\u00a0 ......  \n} SOMESTRUCTRUE; <\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e00\u79cd\u53ef\u80fd\u7684\u7ed3\u6784\u4f53\u5b9a\u4e49\uff1f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u51fd\u6570\u4e09\u3001\u300d<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0b\u8ff0\u51fd\u6570\u4e3a\u5728Hash\u8868\u4e2d\u67e5\u627e\u662f\u5426\u5b58\u5728\u76ee\u6807\u5b57\u7b26\u4e32\uff0c\u6709\u5219\u8fd4\u56de\u8981\u67e5\u627e\u5b57\u7b26\u4e32\u7684Hash\u503c\uff0c\u65e0\u5219\uff0creturn -1.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int GetHashTablePos( har *lpszString, SOMESTRUCTURE *lpTable )  \n\/\/lpszString\u8981\u5728Hash\u8868\u4e2d\u67e5\u627e\u7684\u5b57\u7b26\u4e32\uff0clpTable\u4e3a\u5b58\u50a8\u5b57\u7b26\u4e32Hash\u503c\u7684Hash\u8868\u3002  \n{  \n\u00a0\u00a0\u00a0 int nHash = HashString(lpszString);\u00a0 \n    \/\/\u8c03\u7528\u4e0a\u8ff0\u51fd\u6570\u4e8c\uff0c\u8fd4\u56de\u8981\u67e5\u627e\u5b57\u7b26\u4e32lpszString\u7684Hash\u503c\u3002  \n\u00a0\u00a0\u00a0 int nHashPos = nHash % nTableSize;\n\n\u00a0\u00a0\u00a0\u00a0 if ( lpTable[nHashPos].bExists\u00a0 &amp;&amp;\u00a0 !strcmp( lpTable[nHashPos].pString, lpszString ) )  \n\u00a0\u00a0\u00a0 {\u00a0 \/\/\u5982\u679c\u627e\u5230\u7684Hash\u503c\u5728\u8868\u4e2d\u5b58\u5728\uff0c\u4e14\u8981\u67e5\u627e\u7684\u5b57\u7b26\u4e32\u4e0e\u8868\u4e2d\u5bf9\u5e94\u4f4d\u7f6e\u7684\u5b57\u7b26\u4e32\u76f8\u540c\uff0c  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return nHashPos;\u00a0\u00a0\u00a0 \n        \/\/\u5219\u8fd4\u56de\u4e0a\u8ff0\u8c03\u7528\u51fd\u6570\u4e8c\u540e\uff0c\u627e\u5230\u7684Hash\u503c  \n\u00a0\u00a0\u00a0 }  \n\u00a0\u00a0\u00a0 else  \n\u00a0\u00a0\u00a0 {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return -1;\u00a0  \n\u00a0\u00a0\u00a0 }  \n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u770b\u5230\u6b64\uff0c\u6211\u60f3\u5927\u5bb6\u90fd\u5728\u60f3\u4e00\u4e2a\u5f88\u4e25\u91cd\u7684\u95ee\u9898\uff1a\u201c\u5982\u679c\u4e24\u4e2a\u5b57\u7b26\u4e32\u5728\u54c8\u5e0c\u8868\u4e2d\u5bf9\u5e94\u7684\u4f4d\u7f6e\u76f8\u540c\u600e\u4e48\u529e\uff1f\u201d,\u6bd5\u7adf\u4e00\u4e2a\u6570\u7ec4\u5bb9\u91cf\u662f\u6709\u9650\u7684\uff0c\u8fd9\u79cd\u53ef\u80fd\u6027\u5f88\u5927\u3002\u89e3\u51b3\u8be5\u95ee\u9898\u7684\u65b9\u6cd5\u5f88\u591a\uff0c\u6211\u9996\u5148\u60f3\u5230\u7684\u5c31\u662f\u7528\u201c<strong>\u300c\u94fe\u8868\u300d<\/strong>\u201d,\u611f\u8c22\u5927\u5b66\u91cc\u5b66\u7684\u6570\u636e\u7ed3\u6784\u6559\u4f1a\u4e86\u8fd9\u4e2a\u767e\u8bd5\u767e\u7075\u7684\u6cd5\u5b9d\uff0c\u6211\u9047\u5230\u7684\u5f88\u591a\u7b97\u6cd5\u90fd\u53ef\u4ee5\u8f6c\u5316\u6210\u94fe\u8868\u6765\u89e3\u51b3\uff0c\u53ea\u8981\u5728\u54c8\u5e0c\u8868\u7684\u6bcf\u4e2a\u5165\u53e3\u6302\u4e00\u4e2a\u94fe\u8868\uff0c\u4fdd\u5b58\u6240\u6709\u5bf9\u5e94\u7684\u5b57\u7b26\u4e32\u5c31OK\u4e86\u3002\u4e8b\u60c5\u5230\u6b64\u4f3c\u4e4e\u6709\u4e86\u5b8c\u7f8e\u7684\u7ed3\u5c40\uff0c\u5982\u679c\u662f\u628a\u95ee\u9898\u72ec\u81ea\u4ea4\u7ed9\u6211\u89e3\u51b3\uff0c\u6b64\u65f6\u6211\u53ef\u80fd\u5c31\u8981\u5f00\u59cb\u5b9a\u4e49\u6570\u636e\u7ed3\u6784\u7136\u540e\u5199\u4ee3\u7801\u4e86\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7136\u800cBlizzard\u7684\u7a0b\u5e8f\u5458\u4f7f\u7528\u7684\u65b9\u6cd5\u5219\u662f\u66f4\u7cbe\u5999\u7684\u65b9\u6cd5\u3002\u57fa\u672c\u539f\u7406\u5c31\u662f\uff1a\u4ed6\u4eec\u5728\u54c8\u5e0c\u8868\u4e2d\u4e0d\u662f\u7528\u4e00\u4e2a\u54c8\u5e0c\u503c\u800c\u662f\u7528<strong>\u300c\u4e09\u4e2a\u54c8\u5e0c\u503c\u300d<\/strong>\u6765\u6821\u9a8c\u5b57\u7b26\u4e32\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">MPQ\u4f7f\u7528\u6587\u4ef6\u540d\u54c8\u5e0c\u8868\u6765\u8ddf\u8e2a\u5185\u90e8\u7684\u6240\u6709\u6587\u4ef6\u3002\u4f46\u662f\u8fd9\u4e2a\u8868\u7684\u683c\u5f0f\u4e0e\u6b63\u5e38\u7684\u54c8\u5e0c\u8868\u6709\u4e00\u4e9b\u4e0d\u540c\u3002\u9996\u5148\uff0c\u5b83\u6ca1\u6709\u4f7f\u7528\u54c8\u5e0c\u4f5c\u4e3a\u4e0b\u6807\uff0c\u628a\u5b9e\u9645\u7684\u6587\u4ef6\u540d\u5b58\u50a8\u5728\u8868\u4e2d\u7528\u4e8e\u9a8c\u8bc1\uff0c\u5b9e\u9645\u4e0a\u5b83\u6839\u672c\u5c31\u6ca1\u6709\u5b58\u50a8\u6587\u4ef6\u540d\u3002\u800c\u662f\u4f7f\u7528\u4e863\u79cd\u4e0d\u540c\u7684\u54c8\u5e0c\uff1a\u4e00\u4e2a\u7528\u4e8e\u54c8\u5e0c\u8868\u7684\u4e0b\u6807\uff0c\u4e24\u4e2a\u7528\u4e8e\u9a8c\u8bc1\u3002\u8fd9\u4e24\u4e2a\u9a8c\u8bc1\u54c8\u5e0c\u66ff\u4ee3\u4e86\u5b9e\u9645\u6587\u4ef6\u540d\u3002<br>\n\u5f53\u7136\u4e86\uff0c\u8fd9\u6837\u4ecd\u7136\u4f1a\u51fa\u73b02\u4e2a\u4e0d\u540c\u7684\u6587\u4ef6\u540d\u54c8\u5e0c\u52303\u4e2a\u540c\u6837\u7684\u54c8\u5e0c\u3002\u4f46\u662f\u8fd9\u79cd\u60c5\u51b5\u53d1\u751f\u7684\u6982\u7387\u5e73\u5747\u662f\uff1a1:18889465931478580854784\uff0c\u8fd9\u4e2a\u6982\u7387\u5bf9\u4e8e\u4efb\u4f55\u4eba\u6765\u8bf4\u5e94\u8be5\u90fd\u662f\u8db3\u591f\u5c0f\u7684\u3002\u73b0\u5728\u518d\u56de\u5230\u6570\u636e\u7ed3\u6784\u4e0a\uff0cBlizzard\u4f7f\u7528\u7684\u54c8\u5e0c\u8868\u6ca1\u6709\u4f7f\u7528\u94fe\u8868\uff0c\u800c\u91c7\u7528&#8221;\u987a\u5ef6&#8221;\u7684\u65b9\u5f0f\u6765\u89e3\u51b3\u95ee\u9898\uff0c\u770b\u770b\u8fd9\u4e2a\u7b97\u6cd5\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u300c\u51fd\u6570\u56db\u3001\u300d<\/strong>lpszString \u4e3a\u8981\u5728hash\u8868\u4e2d\u67e5\u627e\u7684\u5b57\u7b26\u4e32\uff1blpTable \u4e3a\u5b58\u50a8\u5b57\u7b26\u4e32hash\u503c\u7684hash\u8868\uff1bnTableSize \u4e3ahash\u8868\u7684\u957f\u5ea6\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize )  \n{\n\u00a0\u00a0\u00a0 const int\u00a0 HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;\n\n\u00a0\u00a0\u00a0\u00a0 int\u00a0 nHash = HashString( lpszString, HASH_OFFSET );  \n\u00a0\u00a0\u00a0 int\u00a0 nHashA = HashString( lpszString, HASH_A );  \n\u00a0\u00a0\u00a0 int\u00a0 nHashB = HashString( lpszString, HASH_B );  \n\u00a0\u00a0\u00a0 int\u00a0 nHashStart = nHash % nTableSize;  \n\u00a0\u00a0\u00a0 int\u00a0 nHashPos = nHashStart;\n\n\u00a0\u00a0\u00a0\u00a0 while (lpTable[nHashPos].bExists )  \n\u00a0\u00a0 {\n\n\u00a0\u00a0\u00a0\u00a0 \/*\u5982\u679c\u4ec5\u4ec5\u662f\u5224\u65ad\u5728\u8be5\u8868\u4e2d\u65f6\u5019\u5b58\u5728\u8fd9\u4e2a\u5b57\u7b26\u4e32\uff0c\u5c31\u6bd4\u8f83\u8fd9\u4e24\u4e2ahash\u503c\u5c31\u53ef\u4ee5\u4e86\uff0c\u4e0d\u7528\u5bf9  \n\u00a0\u00a0\u00a0\u00a0 *\u7ed3\u6784\u4f53\u4e2d\u7684\u5b57\u7b26\u4e32\u8fdb\u884c\u6bd4\u8f83\u3002\u8fd9\u6837\u4f1a\u52a0\u5feb\u8fd0\u884c\u7684\u901f\u5ea6\uff1f\u51cf\u5c11hash\u8868\u5360\u7528\u7684\u7a7a\u95f4\uff1f\u8fd9\u79cd  \n\u00a0\u00a0\u00a0\u00a0\u00a0 *\u65b9\u6cd5\u4e00\u822c\u5e94\u7528\u5728\u4ec0\u4e48\u573a\u5408\uff1f*\/  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if ( \u3000 lpTable[nHashPos].nHashA == nHashA  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 &amp;&amp;\u00a0 lpTable[nHashPos].nHashB == nHashB )  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 return nHashPos;  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 {\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0nHashPos = (nHashPos + 1) % nTableSize;  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (nHashPos == nHashStart)  \n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 break;  \n\u00a0\u00a0\u00a0 }  \n\u00a0\u00a0\u00a0\u00a0 return -1;  \n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0a\u8ff0\u7a0b\u5e8f\u89e3\u91ca\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>\u8ba1\u7b97\u51fa\u5b57\u7b26\u4e32\u7684\u4e09\u4e2a\u54c8\u5e0c\u503c\uff08\u4e00\u4e2a\u7528\u6765\u786e\u5b9a\u4f4d\u7f6e\uff0c\u53e6\u5916\u4e24\u4e2a\u7528\u6765\u6821\u9a8c)<\/li><li>\u5bdf\u770b\u54c8\u5e0c\u8868\u4e2d\u7684\u8fd9\u4e2a\u4f4d\u7f6e<\/li><li>\u54c8\u5e0c\u8868\u4e2d\u8fd9\u4e2a\u4f4d\u7f6e\u4e3a\u7a7a\u5417\uff1f\u5982\u679c\u4e3a\u7a7a\uff0c\u5219\u80af\u5b9a\u8be5\u5b57\u7b26\u4e32\u4e0d\u5b58\u5728\uff0c\u8fd4\u56de-1\u3002<\/li><li>\u5982\u679c\u5b58\u5728\uff0c\u5219\u68c0\u67e5\u5176\u4ed6\u4e24\u4e2a\u54c8\u5e0c\u503c\u662f\u5426\u4e5f\u5339\u914d\uff0c\u5982\u679c\u5339\u914d\uff0c\u5219\u8868\u793a\u627e\u5230\u4e86\u8be5\u5b57\u7b26\u4e32\uff0c\u8fd4\u56de\u5176Hash\u503c\u3002<\/li><li>\u79fb\u5230\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\uff0c\u5982\u679c\u5df2\u7ecf\u79fb\u5230\u4e86\u8868\u7684\u672b\u5c3e\uff0c\u5219\u53cd\u7ed5\u5230\u8868\u7684\u5f00\u59cb\u4f4d\u7f6e\u8d77\u7ee7\u7eed\u67e5\u8be2<\/li><li>\u770b\u770b\u662f\u4e0d\u662f\u53c8\u56de\u5230\u4e86\u539f\u6765\u7684\u4f4d\u7f6e\uff0c\u5982\u679c\u662f\uff0c\u5219\u8fd4\u56de\u6ca1\u627e\u5230<\/li><li>\u56de\u52303<\/li><\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">ok\uff0c\u8fd9\u5c31\u662f\u672c\u6587\u4e2d\u6240\u8bf4\u7684\u6700\u5feb\u7684Hash\u8868\u7b97\u6cd5\u3002\u4ec0\u4e48?\u4e0d\u591f\u5feb?<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6b22\u8fce\uff0c\u5404\u4f4d\u6279\u8bc4\u6307\u6b63\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator\" \/>\n\n\n\n<p class=\"wp-block-paragraph\">\u8865\u51451\u3001\u4e00\u4e2a\u7b80\u5355\u7684hash\u51fd\u6570\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/*key\u4e3a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0cnTableLength\u4e3a\u54c8\u5e0c\u8868\u7684\u957f\u5ea6  \n*\u8be5\u51fd\u6570\u5f97\u5230\u7684hash\u503c\u5206\u5e03\u6bd4\u8f83\u5747\u5300*\/  \nunsigned long getHashIndex( const char *key, int nTableLength )  \n{\n\n\u00a0\u00a0\u00a0 unsigned long nHash = 0;\n\n\u00a0\u00a0 \u00a0\u00a0\u00a0 while (*key)  \n\u00a0\u00a0\u00a0 {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 nHash = (nHash&lt;&lt;5) + nHash + *key++;  \n\u00a0\u00a0\u00a0 }\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0\u00a0 return ( nHash % nTableLength );  \n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u8865\u51452\u3001\u4e00\u4e2a\u5b8c\u6574\u6d4b\u8bd5\u7a0b\u5e8f\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u54c8\u5e0c\u8868\u7684\u6570\u7ec4\u662f\u5b9a\u957f\u7684\uff0c\u5982\u679c\u592a\u5927\uff0c\u5219\u6d6a\u8d39\uff0c\u5982\u679c\u592a\u5c0f\uff0c\u4f53\u73b0\u4e0d\u51fa\u6548\u7387\u3002\u5408\u9002\u7684\u6570\u7ec4\u5927\u5c0f\u662f\u54c8\u5e0c\u8868\u7684\u6027\u80fd\u7684\u5173\u952e\u3002\u54c8\u5e0c\u8868\u7684\u5c3a\u5bf8\u6700\u597d\u662f\u4e00\u4e2a\u8d28\u6570\u3002\u5f53\u7136\uff0c\u6839\u636e\u4e0d\u540c\u7684\u6570\u636e\u91cf\uff0c\u4f1a\u6709\u4e0d\u540c\u7684\u54c8\u5e0c\u8868\u7684\u5927\u5c0f\u3002\u5bf9\u4e8e\u6570\u636e\u91cf\u65f6\u591a\u65f6\u5c11\u7684\u5e94\u7528\uff0c\u6700\u597d\u7684\u8bbe\u8ba1\u662f\u4f7f\u7528\u52a8\u6001\u53ef\u53d8\u5c3a\u5bf8\u7684\u54c8\u5e0c\u8868\uff0c\u90a3\u4e48\u5982\u679c\u4f60\u53d1\u73b0\u54c8\u5e0c\u8868\u5c3a\u5bf8\u592a\u5c0f\u4e86\uff0c\u6bd4\u5982\u5176\u4e2d\u7684\u5143\u7d20\u662f\u54c8\u5e0c\u8868\u5c3a\u5bf8\u76842\u500d\u65f6\uff0c\u6211\u4eec\u5c31\u9700\u8981\u6269\u5927\u54c8\u5e0c\u8868\u5c3a\u5bf8\uff0c\u4e00\u822c\u662f\u6269\u5927\u4e00\u500d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e0b\u9762\u662f\u54c8\u5e0c\u8868\u5c3a\u5bf8\u5927\u5c0f\u7684\u53ef\u80fd\u53d6\u503c\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/xmt1139057136\/xttblog\/2023\/02\/top_n.jpg\" alt=\"\u54c8\u5e0c\u8868\u5c3a\u5bf8\" \/><figcaption>\u54c8\u5e0c\u8868\u5c3a\u5bf8<\/figcaption><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">\u4ee5\u4e0b\u4e3a\u8be5\u7a0b\u5e8f\u7684\u5b8c\u6574\u6e90\u7801\uff0c\u5df2\u5728linux\u4e0b\u6d4b\u8bd5\u901a\u8fc7\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h&gt;\n#include &lt;ctype.h&gt;     \n\/\/\u591a\u8c22citylove\u6307\u6b63\u3002\n\/\/crytTable[]\u91cc\u9762\u4fdd\u5b58\u7684\u662fHashString\u51fd\u6570\u91cc\u9762\u5c06\u4f1a\u7528\u5230\u7684\u4e00\u4e9b\u6570\u636e\uff0c\u5728prepareCryptTable\n\/\/\u51fd\u6570\u91cc\u9762\u521d\u59cb\u5316\nunsigned long cryptTable[0x500];\n\n\/\/\u4ee5\u4e0b\u7684\u51fd\u6570\u751f\u6210\u4e00\u4e2a\u957f\u5ea6\u4e3a0x500\uff08\u540810\u8fdb\u5236\u6570\uff1a1280\uff09\u7684cryptTable[0x500]\nvoid prepareCryptTable()\n{ \n    unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;\n\n    for( index1 = 0; index1 &lt; 0x100; index1++ )\n    { \n        for( index2 = index1, i = 0; i &lt; 5; i++, index2 += 0x100 )\n        { \n            unsigned long temp1, temp2;\n\n            seed = (seed * 125 + 3) % 0x2AAAAB;\n            temp1 = (seed &amp; 0xFFFF) &lt;&lt; 0x10;\n\n            seed = (seed * 125 + 3) % 0x2AAAAB;\n            temp2 = (seed &amp; 0xFFFF);\n\n            cryptTable[index2] = ( temp1 | temp2 ); \n       } \n   } \n}\n\n\/\/\u4ee5\u4e0b\u51fd\u6570\u8ba1\u7b97lpszFileName \u5b57\u7b26\u4e32\u7684hash\u503c\uff0c\u5176\u4e2ddwHashType \u4e3ahash\u7684\u7c7b\u578b\uff0c\n\/\/\u5728\u4e0b\u9762GetHashTablePos\u51fd\u6570\u91cc\u9762\u8c03\u7528\u672c\u51fd\u6570\uff0c\u5176\u53ef\u4ee5\u53d6\u7684\u503c\u4e3a0\u30011\u30012\uff1b\u8be5\u51fd\u6570\n\/\/\u8fd4\u56delpszFileName \u5b57\u7b26\u4e32\u7684hash\u503c\uff1b\nunsigned long HashString( char *lpszFileName, unsigned long dwHashType )\n{ \n    unsigned char *key  = (unsigned char *)lpszFileName;\nunsigned long seed1 = 0x7FED7FED;\nunsigned long seed2 = 0xEEEEEEEE;\n    int ch;\n\n    while( *key != 0 )\n    { \n        ch = toupper(*key++);\n\n        seed1 = cryptTable[(dwHashType &lt;&lt; 8) + ch] ^ (seed1 + seed2);\n        seed2 = ch + seed1 + seed2 + (seed2 &lt;&lt; 5) + 3; \n    }\n    return seed1; \n}\n\n\/\/\u5728main\u4e2d\u6d4b\u8bd5argv[1]\u7684\u4e09\u4e2ahash\u503c\uff1a\n\/\/.\/hash  \"arr\/units.dat\"\n\/\/.\/hash  \"unit\/neutral\/acritter.grp\"\nint main( int argc, char **argv )\n{\n    unsigned long ulHashValue;\n    int i = 0;\n\n    if ( argc != 2 )\n    {\n        printf(\"please input two arguments\/n\");\n        return -1;\n    }\n\n     \/*\u521d\u59cb\u5316\u6570\u7ec4\uff1acrytTable[0x500]*\/\n     prepareCryptTable();\n\n     \/*\u6253\u5370\u6570\u7ec4crytTable[0x500]\u91cc\u9762\u7684\u503c*\/\n     for ( ; i &lt; 0x500; i++ )\n     {\n         if ( i % 10 == 0 )\n         {\n             printf(\"\/n\");\n         }\n\n         printf(\"%-12X\", cryptTable[i] );\n     }\n\n     ulHashValue = HashString( argv[1], 0 );\n     printf(\"\/n----%X ----\/n\", ulHashValue );\n\n     ulHashValue = HashString( argv[1], 1 );\n     printf(\"----%X ----\/n\", ulHashValue );\n\n     ulHashValue = HashString( argv[1], 2 );\n     printf(\"----%X ----\/n\", ulHashValue );\n\n     return 0;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u53c2\u8003\u8d44\u6599<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"http:\/\/blog.redfox66.com\/\">http:\/\/blog.redfox66.com\/<\/a><\/li><li><a href=\"http:\/\/blog.csdn.net\/wuliming_sc\/\">http:\/\/blog.csdn.net\/wuliming_sc\/<\/a><\/li><li><a href=\"https:\/\/blog.csdn.net\/v_JULY_v\/\">https:\/\/blog.csdn.net\/v_JULY_v\/<\/a><\/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=5361\">\u4ece\u5934\u5230\u5c3e\u89e3\u6790Hash\u8868\u7b97\u6cd5\uff0c\u767e\u5ea6Top K\u7b97\u6cd5\u8be6\u89e3<\/a><\/p><!-- <div class=\"bd-reward-stl\"><button id=\"bdRewardBtn\"><span><\/span><\/button><\/div> -->","protected":false},"excerpt":{"rendered":"<p>\u4ece\u5934\u5230\u5c3e\u89e3\u6790Hash \u8868\u7b97\u6cd5 \u672c\u6587\u5206\u4e3a\u4e09\u90e8\u5206\u5185\u5bb9\uff0c\u7b2c\u4e00\u90e8\u5206\u4e3a\u4e00\u9053\u767e\u5ea6\u9762\u8bd5\u9898Top K\u7b97\u6cd5\u7684\u8be6\u89e3\uff1b\u7b2c\u4e8c\u90e8\u5206\u4e3a\u5173\u4e8e [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[685,172,75,62,410],"class_list":["post-5361","post","type-post","status-publish","format-standard","hentry","category-java","tag-685","tag-172","tag-75","tag-62","tag-410"],"_links":{"self":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/5361","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=5361"}],"version-history":[{"count":1,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/5361\/revisions"}],"predecessor-version":[{"id":5362,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/5361\/revisions\/5362"}],"wp:attachment":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}