{"id":2185,"date":"2018-11-07T14:44:47","date_gmt":"2018-11-07T06:44:47","guid":{"rendered":"https:\/\/damogame.cn:15443\/wordpress\/?p=2185"},"modified":"2018-11-07T14:45:27","modified_gmt":"2018-11-07T06:45:27","slug":"%e5%93%88%e5%b8%8c%e8%a1%a8%ef%bc%88hash-table%ef%bc%89%e5%8e%9f%e7%90%86%e5%8f%8a%e5%85%b6%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/2185","title":{"rendered":"\u54c8\u5e0c\u8868\uff08Hash Table\uff09\u539f\u7406\u53ca\u5176\u5b9e\u73b0"},"content":{"rendered":"
\n
\n
<\/div>\n
\n
<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n
\n
\n
\n
\n

\u539f\u7406\u4ecb\u7ecd<\/h2>\n<\/div>\n<\/div>\n

\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

\u54c8\u5e0c\u8868hash table(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

\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

\u54c8\u5e0c\u8868\u6700\u5927\u7684\u4f18\u70b9\uff0c\u5c31\u662f\u628a\u6570\u636e\u7684\u5b58\u50a8\u548c\u67e5\u627e\u6d88\u8017\u7684\u65f6\u95f4\u5927\u5927\u964d\u4f4e\uff0c\u51e0\u4e4e\u53ef\u4ee5\u770b\u6210\u662f\u5e38\u6570\u65f6\u95f4\uff1b\u800c\u4ee3\u4ef7\u4ec5\u4ec5\u662f\u6d88\u8017\u6bd4\u8f83\u591a\u7684\u5185\u5b58\u3002\u7136\u800c\u5728\u5f53\u524d\u53ef\u5229\u7528\u5185\u5b58\u8d8a\u6765\u8d8a\u591a\u7684\u60c5\u51b5\u4e0b\uff0c\u7528\u7a7a\u95f4\u6362\u65f6\u95f4\u7684\u505a\u6cd5\u662f\u503c\u5f97\u7684\u3002\u53e6\u5916\uff0c\u7f16\u7801\u6bd4\u8f83\u5bb9\u6613\u4e5f\u662f\u5b83\u7684\u7279\u70b9\u4e4b\u4e00\u3002 \u54c8\u5e0c\u8868\u53c8\u53eb\u505a\u6563\u5217\u8868\uff0c\u5206\u4e3a\u201c\u5f00\u6563\u5217\u201d \u548c\u201c\u95ed\u6563\u5217\u201d\u3002<\/p>\n

\u6211\u4eec\u4f7f\u7528\u4e00\u4e2a\u4e0b\u6807\u8303\u56f4\u6bd4\u8f83\u5927\u7684\u6570\u7ec4\u6765\u5b58\u50a8\u5143\u7d20\u3002\u53ef\u4ee5\u8bbe\u8ba1\u4e00\u4e2a\u51fd\u6570\uff08\u54c8\u5e0c\u51fd\u6570\uff0c \u4e5f\u53eb\u505a\u6563\u5217\u51fd\u6570\uff09\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u5143\u7d20\u7684\u5173\u952e\u5b57\u90fd\u4e0e\u4e00\u4e2a\u51fd\u6570\u503c\uff08\u5373\u6570\u7ec4\u4e0b\u6807\uff09\u76f8\u5bf9\u5e94\uff0c\u4e8e\u662f\u7528\u8fd9\u4e2a\u6570\u7ec4\u5355\u5143\u6765\u5b58\u50a8\u8fd9\u4e2a\u5143\u7d20\uff1b\u4e5f\u53ef\u4ee5\u7b80\u5355\u7684\u7406\u89e3\u4e3a\uff0c\u6309\u7167\u5173\u952e\u5b57\u4e3a\u6bcf\u4e00 \u4e2a\u5143\u7d20\u201c\u5206\u7c7b\u201d\uff0c\u7136\u540e\u5c06\u8fd9\u4e2a\u5143\u7d20\u5b58\u50a8\u5728\u76f8\u5e94\u201c\u7c7b\u201d\u6240\u5bf9\u5e94\u7684\u5730\u65b9\u3002<\/p>\n

\u4f46\u662f\uff0c\u4e0d\u80fd\u591f\u4fdd\u8bc1\u6bcf\u4e2a\u5143\u7d20\u7684\u5173\u952e\u5b57\u4e0e\u51fd\u6570\u503c\u662f\u4e00\u4e00\u5bf9\u5e94\u7684\uff0c\u56e0\u6b64\u6781\u6709\u53ef\u80fd\u51fa\u73b0\u5bf9\u4e8e\u4e0d\u540c\u7684\u5143\u7d20\uff0c\u5374\u8ba1\u7b97\u51fa\u4e86\u76f8\u540c\u7684\u51fd\u6570\u503c\uff0c\u8fd9\u6837\u5c31\u4ea7\u751f\u4e86\u201c\u51b2\u7a81\u201d\uff0c\u6362\u53e5\u8bdd\u8bf4\uff0c\u5c31\u662f\u628a\u4e0d\u540c\u7684\u5143\u7d20\u5206\u5728\u4e86\u76f8\u540c\u7684\u201c\u7c7b\u201d\u4e4b\u4e2d\u3002\u540e\u9762\u6211\u4eec\u5c06\u770b\u5230\u4e00\u79cd\u89e3\u51b3\u201c\u51b2\u7a81\u201d\u7684\u7b80\u4fbf\u505a\u6cd5\u3002 \u603b\u7684\u6765\u8bf4\uff0c\u201c\u76f4\u63a5\u5b9a\u5740\u201d\u4e0e\u201c\u89e3\u51b3\u51b2\u7a81\u201d\u662f\u54c8\u5e0c\u8868\u7684\u4e24\u5927\u7279\u70b9\u3002<\/p>\n

\u54c8\u5e0c\u51fd\u6570\u6784\u9020<\/h2>\n

\u5c31\u662f\u6620\u5c04\u51fd\u6570\u6784\u9020\uff0c\u770b\u67d0\u4e2a\u5143\u7d20\u5177\u4f53\u5c5e\u4e8e\u54ea\u4e00\u4e2a\u7c7b\u522b\u3002
\n\u9664\u4f59\u6cd5\uff1a \u9009\u62e9\u4e00\u4e2a\u9002\u5f53\u7684\u6b63\u6574\u6570 p \uff0c\u4ee4 h(k ) = k mod p \uff0c\u8fd9\u91cc\uff0c p \u5982\u679c\u9009\u53d6\u7684\u662f\u6bd4\u8f83\u5927\u7684\u7d20\u6570\uff0c\u6548\u679c\u6bd4\u8f83\u597d\u3002\u800c\u4e14\u6b64\u6cd5\u975e\u5e38\u5bb9\u6613\u5b9e\u73b0\uff0c\u56e0\u6b64\u662f\u6700\u5e38\u7528\u7684\u65b9\u6cd5\u3002\u6700\u76f4\u89c2\u7684\u4e00\u79cd\uff0c\u4e0a\u56fe\u4f7f\u7528\u7684\u5c31\u662f\u8fd9\u79cd\u6563\u5217\u6cd5\uff0c\u516c\u5f0f\uff1a
\nindex = value % 16
\n\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

\u5e73\u65b9\u6563\u5217\u6cd5
\n\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
\nindex = (value * value) >> 28 \uff08 \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\uff09<\/p>\n

\u6570\u5b57\u9009\u62e9\u6cd5\uff1a \u5982\u679c\u5173\u952e\u5b57\u7684\u4f4d\u6570\u6bd4\u8f83\u591a\uff0c\u8d85\u8fc7\u957f\u6574\u578b\u8303\u56f4\u800c\u65e0\u6cd5\u76f4\u63a5\u8fd0\u7b97\uff0c\u53ef\u4ee5\u9009\u62e9\u5176\u4e2d\u6570\u5b57\u5206\u5e03\u6bd4\u8f83\u5747\u5300\u7684\u82e5\u5e72\u4f4d\uff0c\u6240\u7ec4\u6210\u7684\u65b0\u7684\u503c\u4f5c\u4e3a\u5173\u952e\u5b57\u6216\u8005\u76f4\u63a5\u4f5c\u4e3a\u51fd\u6570\u503c\u3002<\/p>\n

\u6590\u6ce2\u90a3\u5951\uff08Fibonacci\uff09\u6563\u5217\u6cd5\uff1a\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
\n1\uff0c\u5bf9\u4e8e16\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u8fd9\u4e2a\u4e58\u6570\u662f40503
\n2\uff0c\u5bf9\u4e8e32\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u8fd9\u4e2a\u4e58\u6570\u662f2654435769
\n3\uff0c\u5bf9\u4e8e64\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u8fd9\u4e2a\u4e58\u6570\u662f11400714819323198485
\n\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
\n\u5bf9\u6211\u4eec\u5e38\u89c1\u768432\u4f4d\u6574\u6570\u800c\u8a00\uff0c\u516c\u5f0f\uff1a
\nindex = (value * 2654435769) >> 28<\/p>\n

\u51b2\u7a81\u5904\u7406<\/h2>\n

\u7ebf\u6027\u91cd\u65b0\u6563\u5217\u6280\u672f\u6613\u4e8e\u5b9e\u73b0\u4e14\u53ef\u4ee5\u8f83\u597d\u7684\u8fbe\u5230\u76ee\u7684\u3002\u4ee4\u6570\u7ec4\u5143\u7d20\u4e2a\u6570\u4e3a S \uff0c\u5219\u5f53 h(k) \u5df2\u7ecf\u5b58\u50a8\u4e86\u5143\u7d20\u7684\u65f6\u5019\uff0c\u4f9d\u6b21\u63a2\u67e5 (h(k)+i) mod S , i=1,2,3\u2026\u2026 \uff0c\u76f4\u5230\u627e\u5230\u7a7a\u7684\u5b58\u50a8\u5355\u5143\u4e3a\u6b62\uff08\u6216\u8005\u4ece\u5934\u5230\u5c3e\u626b\u63cf\u4e00\u5708\u4ecd\u672a\u53d1\u73b0\u7a7a\u5355\u5143\uff0c\u8fd9\u5c31\u662f\u54c8\u5e0c\u8868\u5df2\u7ecf\u6ee1\u4e86\uff0c\u53d1\u751f\u4e86\u9519\u8bef\u3002\u5f53\u7136\u8fd9\u662f\u53ef\u4ee5\u901a\u8fc7\u6269\u5927\u6570\u7ec4\u8303\u56f4\u907f\u514d\u7684\uff09\u3002<\/p>\n

\u4e3e\u4f8b<\/h2>\n

\u54c8\u5e0c\u8868\u652f\u6301\u7684\u8fd0\u7b97\u4e3b\u8981\u6709\uff1a\u521d\u59cb\u5316(makenull)\u3001\u54c8\u5e0c\u51fd\u6570\u503c\u7684\u8fd0\u7b97(h(x))\u3001\u63d2\u5165\u5143\u7d20(insert)\u3001\u67e5\u627e\u5143\u7d20(member)\u3002 \u8bbe\u63d2\u5165\u7684\u5143\u7d20\u7684\u5173\u952e\u5b57\u4e3a x \uff0cA \u4e3a\u5b58\u50a8\u7684\u6570\u7ec4\u3002<\/p>\n

\u4f2a\u4ee3\u7801<\/strong>
\n\u521d\u59cb\u5316\uff1a<\/p>\n

const empty=maxlongint; \/\/ \u7528\u975e\u5e38\u5927\u7684\u6574\u6570\u4ee3\u8868\u8fd9\u4e2a\u4f4d\u7f6e\u6ca1\u6709\u5b58\u50a8\u5143\u7d20  \r\np=9997; \/\/ \u8868\u7684\u5927\u5c0f  \r\nprocedure makenull;  \r\nvar i:integer;  \r\nbegin  \r\nfor i:=0 to p-1 do  \r\nA[i]:=empty;  \r\nEnd;<\/pre>\n
\u54c8\u5e0c\u51fd\u6570\u503c\u7684\u8fd0\u7b97\u6839\u636e\u51fd\u6570\u7684\u4e0d\u540c\u800c\u53d8\u5316\uff0c\u4f8b\u5982\u9664\u4f59\u6cd5\u7684\u4e00\u4e2a\u4f8b\u5b50\uff1a<\/p>\n<\/div>\n
function h(x:longint):Integer;  \r\nbegin  \r\nh:= x mod p;  \r\nend;<\/pre>\n
\n
\u6211\u4eec\u6ce8\u610f\u5230\uff0c\u63d2\u5165\u548c\u67e5\u627e\u9996\u5148\u90fd\u9700\u8981\u5bf9\u8fd9\u4e2a\u5143\u7d20\u5b9a\u4f4d\uff0c\u5373\u5982\u679c\u8fd9\u4e2a\u5143\u7d20\u82e5\u5b58\u5728\uff0c\u5b83\u5e94\u8be5\u5b58\u50a8\u5728\u4ec0\u4e48\u4f4d\u7f6e\uff0c\u56e0\u6b64\u52a0\u5165\u4e00\u4e2a\u5b9a\u4f4d\u7684\u51fd\u6570 locate\uff1a<\/p>\n<\/div>\n<\/div>\n
function locate(x:longint):integer;  \r\nvar orig,i:integer;  \r\nbegin  \r\norig:=h(x);  \r\ni:=0;  \r\nwhile (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do  \r\ninc(i);  \r\n\/\/\u5f53\u8fd9\u4e2a\u5faa\u73af\u505c\u4e0b\u6765\u65f6\uff0c\u8981\u4e48\u627e\u5230\u4e00\u4e2a\u7a7a\u7684\u5b58\u50a8\u5355\u5143\uff0c\u8981\u4e48\u627e\u5230\u8fd9\u4e2a\u5143  \r\n\/\/\u7d20\u5b58\u50a8\u7684\u5355\u5143\uff0c\u8981\u4e48\u8868\u5df2\u7ecf\u6ee1\u4e86  \r\nlocate:=(orig+i) mod S;  \r\nend;<\/pre>\n
\n
\n
\u63d2\u5165\u5143\u7d20 \uff1a<\/p>\n
procedure insert(x:longint);  \r\nvar posi:integer;  \r\nbegin  \r\nposi:=locate(x); \/\/\u5b9a\u4f4d\u51fd\u6570\u7684\u8fd4\u56de\u503c  \r\nif A[posi]=empty then A[posi]:=x  \r\nelse error; \/\/error \u5373\u4e3a\u53d1\u751f\u4e86\u9519\u8bef\uff0c\u5f53\u7136\u8fd9\u662f\u53ef\u4ee5\u907f\u514d\u7684  \r\nend;<\/pre>\n
\u67e5\u627e\u5143\u7d20\u662f\u5426\u5df2\u7ecf\u5728\u8868\u4e2d\uff1a<\/p>\n
procedure member(x:longint):boolean;  \r\nvar posi:integer;  \r\nbegin  \r\nposi:=locate(x);  \r\nif A[posi]=x then member:=true  \r\nelse member:=false;  \r\nend;<\/pre>\n
\u5f53\u6570\u636e\u89c4\u6a21\u63a5\u8fd1\u54c8\u5e0c\u8868\u4e0a\u754c\u6216\u8005\u4e0b\u754c\u7684\u65f6\u5019\uff0c\u54c8\u5e0c\u8868\u5b8c\u5168\u4e0d\u80fd\u591f\u4f53\u73b0\u9ad8\u6548\u7684\u7279\u70b9\uff0c\u751a\u81f3\u8fd8\u4e0d\u5982\u4e00\u822c\u7b97\u6cd5\u3002\u4f46\u662f\u5982\u679c\u89c4\u6a21\u5728\u4e2d\u592e\uff0c\u5b83\u9ad8\u6548\u7684\u7279\u70b9\u53ef\u4ee5\u5145\u5206\u4f53\u73b0\u3002\u8bd5\u9a8c\u8868\u660e\u5f53\u5143\u7d20\u5145\u6ee1\u54c8\u5e0c\u8868\u7684 90% \u7684\u65f6\u5019\uff0c\u6548\u7387\u5c31\u5df2\u7ecf\u5f00\u59cb\u660e\u663e\u4e0b\u964d\u3002\u8fd9\u5c31\u7ed9\u4e86\u6211\u4eec\u63d0\u793a\uff1a\u5982\u679c\u786e\u5b9a\u4f7f\u7528\u54c8\u5e0c\u8868\uff0c\u5e94\u8be5\u5c3d\u91cf\u4f7f\u6570\u7ec4\u5f00\u5927\uff0c\u4f46\u5bf9\u6700\u592a\u5927\u7684\u6570\u7ec4\u8fdb\u884c\u64cd\u4f5c\u4e5f\u6bd4\u8f83\u8d39\u65f6\u95f4\uff0c\u9700\u8981\u627e\u5230\u4e00\u4e2a\u5e73\u8861\u70b9\u3002\u901a\u5e38\u4f7f\u5b83\u7684\u5bb9\u91cf\u81f3\u5c11\u662f\u9898\u76ee\u6700\u5927\u9700\u6c42\u7684 120% \uff0c\u6548\u679c\u6bd4\u8f83\u597d\uff08\u8fd9\u4e2a\u4ec5\u4ec5\u662f\u7ecf\u9a8c\uff0c\u6ca1\u6709\u4e25\u683c\u8bc1\u660e\uff09\u3002<\/p>\n
\u4ec0\u4e48\u65f6\u5019\u9002\u5408\u5e94\u7528\u54c8\u5e0c\u8868\u5462\uff1f\u5982\u679c\u53d1\u73b0\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u65f6\u7ecf\u5e38\u8981\u8be2\u95ee\uff1a\u201c\u67d0\u4e2a\u5143\u7d20\u662f\u5426\u5728\u5df2\u77e5\u96c6\u5408\u4e2d\uff1f\u201d\uff0c\u4e5f\u5c31\u662f\u9700\u8981\u9ad8\u6548\u7684\u6570\u636e\u5b58\u50a8\u548c\u67e5\u627e\uff0c\u5219\u4f7f\u7528\u54c8\u5e0c\u8868\u662f\u6700\u597d\u4e0d\u8fc7\u7684\u4e86\uff01\u90a3\u4e48\uff0c\u5728\u5e94\u7528\u54c8\u5e0c\u8868\u7684\u8fc7\u7a0b\u4e2d\uff0c\u503c\u5f97\u6ce8\u610f\u7684\u662f\u4ec0\u4e48\u5462\uff1f<\/p>\n
\u54c8\u5e0c\u51fd\u6570\u7684\u8bbe\u8ba1\u5f88\u91cd\u8981\u3002\u4e00\u4e2a\u4e0d\u597d\u7684\u54c8\u5e0c\u51fd\u6570\uff0c\u5c31\u662f\u6307\u9020\u6210\u5f88\u591a\u51b2\u7a81\u7684\u60c5\u51b5\uff0c\u4ece\u524d\u9762\u7684\u4f8b\u5b50\u5df2\u7ecf\u53ef\u4ee5\u770b\u51fa\u6765\uff0c\u89e3\u51b3\u51b2\u7a81\u4f1a\u6d6a\u8d39\u6389\u5927\u91cf\u65f6\u95f4\uff0c\u56e0\u6b64\u6211\u4eec\u7684\u76ee\u6807 \u5c31\u662f\u5c3d\u529b\u907f\u514d\u51b2\u7a81\u3002\u524d\u9762\u63d0\u5230\uff0c\u5728\u4f7f\u7528\u201c\u9664\u4f59\u6cd5\u201d\u7684\u65f6\u5019\uff0ch(k)=k mod p \uff0cp \u6700\u597d\u662f\u4e00\u4e2a\u5927\u7d20\u6570\u3002\u8fd9\u5c31\u662f\u4e3a\u4e86\u5c3d\u529b\u907f\u514d\u51b2\u7a81\u3002\u4e3a\u4ec0\u4e48\u5462\uff1f\u5047\u8bbe p=1000 \uff0c\u5219\u54c8\u5e0c\u51fd\u6570\u5206\u7c7b\u7684\u6807\u51c6\u5b9e\u9645\u4e0a\u5c31\u53d8\u6210\u4e86\u6309\u7167\u672b\u4e09\u4f4d\u6570\u5206\u7c7b\uff0c\u8fd9\u6837\u6700\u591a1000\u7c7b\uff0c\u51b2\u7a81\u4f1a\u5f88\u591a\u3002\u4e00\u822c\u5730\u8bf4\uff0c\u5982\u679c p \u7684\u7ea6\u6570\u8d8a\u591a\uff0c\u90a3\u4e48\u51b2\u7a81\u7684\u51e0\u7387\u5c31\u8d8a\u5927\u3002<\/p>\n
\u7b80\u5355\u7684\u8bc1\u660e\uff1a\u5047\u8bbe p \u662f\u4e00\u4e2a\u6709\u8f83\u591a\u7ea6\u6570\u7684\u6570\uff0c\u540c\u65f6\u5728\u6570\u636e\u4e2d\u5b58\u5728 q \u6ee1\u8db3 gcd(p,q)=d >1 \uff0c\u5373\u6709 p=a*d , q=b*d, \u5219\u6709 q mod p= q \u2013 p* [q div p] =q \u2013 p*[b div a] . \u2460 \u5176\u4e2d [b div a ] \u7684\u53d6\u503c\u8303\u56f4\u662f\u4e0d\u4f1a\u8d85\u8fc7 [0\uff0cb] \u7684\u6b63\u6574\u6570\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c [b div a] \u7684\u503c\u53ea\u6709 b+1 \u79cd\u53ef\u80fd\uff0c\u800c p \u662f\u4e00\u4e2a\u9884\u5148\u786e\u5b9a\u7684\u6570\u3002\u56e0\u6b64 \u2460 \u5f0f\u7684\u503c\u5c31\u53ea\u6709 b+1 \u79cd\u53ef\u80fd\u4e86\u3002\u8fd9\u6837\uff0c\u867d\u7136mod \u8fd0\u7b97\u4e4b\u540e\u7684\u4f59\u6570\u4ecd\u7136\u5728 [0\uff0cp-1] \u5185\uff0c\u4f46\u662f\u5b83\u7684\u53d6\u503c\u4ec5\u9650\u4e8e \u2460 \u53ef\u80fd\u53d6\u5230\u7684\u90a3\u4e9b\u503c\u3002\u4e5f\u5c31\u662f\u8bf4\u4f59\u6570\u7684\u5206\u5e03\u53d8\u5f97\u4e0d\u5747\u5300\u4e86\u3002\u5bb9\u6613\u770b\u51fa\uff0c p \u7684\u7ea6\u6570\u8d8a\u591a\uff0c\u53d1\u751f\u8fd9\u79cd\u4f59\u6570\u5206\u5e03\u4e0d\u5747\u5300\u7684\u60c5\u51b5\u5c31\u8d8a\u9891\u7e41\uff0c\u51b2\u7a81\u7684\u51e0\u7387\u8d8a\u9ad8\u3002\u800c\u7d20\u6570\u7684\u7ea6\u6570\u662f\u6700\u5c11\u7684\uff0c\u56e0\u6b64\u6211\u4eec\u9009\u7528\u5927\u7d20\u6570\u3002\u8bb0\u4f4f\u201c\u7d20\u6570\u662f\u6211\u4eec\u7684\u5f97\u529b\u52a9\u624b\u201d\u3002<\/p>\n
\u53e6\u4e00\u65b9\u9762\uff0c\u4e00\u5473\u7684\u8ffd\u6c42\u4f4e\u51b2\u7a81\u7387\u4e5f\u4e0d\u597d\u3002\u7406\u8bba\u4e0a\uff0c\u662f\u53ef\u4ee5\u8bbe\u8ba1\u51fa\u4e00\u4e2a\u51e0\u4e4e\u5b8c\u7f8e\uff0c\u51e0\u4e4e\u6ca1\u6709\u51b2\u7a81\u7684\u51fd\u6570\u7684\u3002\u7136\u800c\uff0c\u8fd9\u6837\u505a\u663e\u7136\u4e0d\u503c\u5f97\uff0c\u56e0\u4e3a\u8fd9\u6837\u7684\u51fd\u6570\u8bbe\u8ba1 \u5f88\u6d6a\u8d39\u65f6\u95f4\u800c\u4e14\u7f16\u7801\u4e00\u5b9a\u5f88\u590d\u6742\uff0c\u4e0e\u5176\u82b1\u8d39\u8fd9\u4e48\u5927\u7684\u7cbe\u529b\u53bb\u8bbe\u8ba1\u51fd\u6570\uff0c\u8fd8\u4e0d\u5982\u7528\u4e00\u4e2a\u867d\u7136\u51b2\u7a81\u591a\u4e00\u4e9b\u4f46\u662f\u7f16\u7801\u7b80\u5355\u7684\u51fd\u6570\u3002\u56e0\u6b64\uff0c\u51fd\u6570\u8fd8\u9700\u8981\u6613\u4e8e\u7f16\u7801\uff0c\u5373\u6613\u4e8e\u5b9e \u73b0\u3002\u7efc\u4e0a\u6240\u8ff0\uff0c\u8bbe\u8ba1\u4e00\u4e2a\u597d\u7684\u54c8\u5e0c\u51fd\u6570\u662f\u5f88\u5173\u952e\u7684\u3002\u800c\u201c\u597d\u201d\u7684\u6807\u51c6\uff0c\u5c31\u662f\u8f83\u4f4e\u7684\u51b2\u7a81\u7387\u548c\u6613\u4e8e\u5b9e\u73b0\u3002\u53e6\u5916\uff0c\u4f7f\u7528\u54c8\u5e0c\u8868\u5e76\u4e0d\u662f\u8bb0\u4f4f\u4e86\u524d\u9762\u7684\u57fa\u672c\u64cd\u4f5c\u5c31\u80fd\u4ee5\u4e0d\u53d8\u5e94\u4e07\u53d8\u7684\u3002\u6709\u7684\u65f6\u5019\uff0c\u9700\u8981\u6309\u7167\u9898\u76ee\u7684\u8981\u6c42\u5bf9\u54c8\u5e0c\u8868\u7684\u7ed3\u6784\u4f5c\u4e00\u4e9b\u6539\u8fdb\u3002\u5f80\u5f80\u4e00\u4e9b\u7b80\u5355\u7684\u6539\u8fdb\u5c31\u53ef\u4ee5\u5e26\u6765\u5de8\u5927\u7684\u65b9\u4fbf\u3002<\/p>\n
\u8fd9\u4e9b\u53ea\u662f\u4e00\u822c\u539f\u5219\uff0c\u771f\u6b63\u9047\u5230\u8bd5\u9898\u7684\u65f6\u5019\u5b9e\u9645\u60c5\u51b5\u5343\u53d8\u4e07\u5316\uff0c\u9700\u8981\u5177\u4f53\u95ee\u9898\u5177\u4f53\u5206\u6790\u624d\u884c\u3002<\/p>\n
\u5f53\u7136\uff0c\u4ee5\u4e0a\u8bb2\u89e3\u7684\u90fd\u662f\u95ed\u6563\u5217\uff0c\u5982\u679c\u4f7f\u7528\u94fe\u8868\uff0c\u505a\u5f00\u6563\u5217\u7684\u8bdd\u5c31\u53ef\u4ee5\u66f4\u65b9\u4fbf\u5b58\u50a8\u548c\u5220\u9664\u4e86\u3002\u5176\u5b9e\u8fd9\u4e2a\u548c\u4e4b\u524d\u505a18-600\u7684malloc\u91cc\u9762\u8bf4\u7684\u4e1c\u897f\u5f88\u7c7b\u4f3c\u3002<\/p>\n
\u62c9\u94fe\u6cd5<\/h2>\n
\u4e0a\u9762\u7684\u65b9\u6cd5\u4f7f\u7528\u6570\u7ec4\u5b9e\u73b0\u7684\uff0c\u5176\u5b9e\u5f88\u591a\u65f6\u5019\u9700\u8981\u4f7f\u7528\u6570\u7ec4\u94fe\u8868\u6765\u505a\u3002\u5f00\u4e00\u4e2a\u6570\u7ec4\uff0c\u6570\u7ec4\u6bcf\u4e2a\u5143\u7d20\u90fd\u662f\u4e00\u4e2a\u94fe\u8868\u3002\uff08hash\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 \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\uff09<\/p>\n
\u4f7f\u7528\u9664\u6cd5\u6563\u5217\uff1a<\/p>\n
\"\"<\/p>\n
\u4f7f\u7528\u6590\u6ce2\u90a3\u5951\u6563\u5217\uff1a<\/p>\n
\"\"<\/p>\n
\u4f7f\u7528\u6269\u5c55\u6cd5\uff1a
\nd-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
hash\u7d22\u5f15\u8ddfB\u6811\u7d22\u5f15\u7684\u533a\u522b\u3002<\/h2>\n
Hash \u7d22\u5f15\u7ed3\u6784\u7684\u7279\u6b8a\u6027\uff0c\u5176\u68c0\u7d22\u6548\u7387\u975e\u5e38\u9ad8\uff0c\u7d22\u5f15\u7684\u68c0\u7d22\u53ef\u4ee5\u4e00\u6b21\u5b9a\u4f4d\uff0c\u4e0d\u50cfB-Tree \u7d22\u5f15\u9700\u8981\u4ece\u6839\u8282\u70b9\u5230\u679d\u8282\u70b9\uff0c\u6700\u540e\u624d\u80fd\u8bbf\u95ee\u5230\u9875\u8282\u70b9\u8fd9\u6837\u591a\u6b21\u7684IO\u8bbf\u95ee\uff0c\u6240\u4ee5 Hash \u7d22\u5f15\u7684\u67e5\u8be2\u6548\u7387\u8981\u8fdc\u9ad8\u4e8e B-Tree \u7d22\u5f15\u3002<\/p>\n
\uff081\uff09Hash \u7d22\u5f15\u4ec5\u4ec5\u80fd\u6ee1\u8db3\u201d=\u201d,\u201dIN\u201d\u548c\u201d<=>\u201d\u67e5\u8be2\uff0c\u4e0d\u80fd\u4f7f\u7528\u8303\u56f4\u67e5\u8be2\u3002
\n\u7531\u4e8e Hash \u7d22\u5f15\u6bd4\u8f83\u7684\u662f\u8fdb\u884c Hash \u8fd0\u7b97\u4e4b\u540e\u7684 Hash \u503c\uff0c\u6240\u4ee5\u5b83\u53ea\u80fd\u7528\u4e8e\u7b49\u503c\u7684\u8fc7\u6ee4\uff0c\u4e0d\u80fd\u7528\u4e8e\u57fa\u4e8e\u8303\u56f4\u7684\u8fc7\u6ee4\uff0c\u56e0\u4e3a\u7ecf\u8fc7\u76f8\u5e94\u7684 Hash \u7b97\u6cd5\u5904\u7406\u4e4b\u540e\u7684 Hash \u503c\u7684\u5927\u5c0f\u5173\u7cfb\uff0c\u5e76\u4e0d\u80fd\u4fdd\u8bc1\u548cHash\u8fd0\u7b97\u524d\u5b8c\u5168\u4e00\u6837\u3002<\/p>\n
\uff082\uff09Hash \u7d22\u5f15\u65e0\u6cd5\u88ab\u7528\u6765\u907f\u514d\u6570\u636e\u7684\u6392\u5e8f\u64cd\u4f5c\u3002
\n\u7531\u4e8e Hash \u7d22\u5f15\u4e2d\u5b58\u653e\u7684\u662f\u7ecf\u8fc7 Hash \u8ba1\u7b97\u4e4b\u540e\u7684 Hash \u503c\uff0c\u800c\u4e14Hash\u503c\u7684\u5927\u5c0f\u5173\u7cfb\u5e76\u4e0d\u4e00\u5b9a\u548c Hash \u8fd0\u7b97\u524d\u7684\u952e\u503c\u5b8c\u5168\u4e00\u6837\uff0c\u6240\u4ee5\u6570\u636e\u5e93\u65e0\u6cd5\u5229\u7528\u7d22\u5f15\u7684\u6570\u636e\u6765\u907f\u514d\u4efb\u4f55\u6392\u5e8f\u8fd0\u7b97\uff1b<\/p>\n
\uff083\uff09Hash \u7d22\u5f15\u4e0d\u80fd\u5229\u7528\u90e8\u5206\u7d22\u5f15\u952e\u67e5\u8be2\u3002
\n\u5bf9\u4e8e\u7ec4\u5408\u7d22\u5f15\uff0cHash \u7d22\u5f15\u5728\u8ba1\u7b97 Hash \u503c\u7684\u65f6\u5019\u662f\u7ec4\u5408\u7d22\u5f15\u952e\u5408\u5e76\u540e\u518d\u4e00\u8d77\u8ba1\u7b97 Hash \u503c\uff0c\u800c\u4e0d\u662f\u5355\u72ec\u8ba1\u7b97 Hash \u503c\uff0c\u6240\u4ee5\u901a\u8fc7\u7ec4\u5408\u7d22\u5f15\u7684\u524d\u9762\u4e00\u4e2a\u6216\u51e0\u4e2a\u7d22\u5f15\u952e\u8fdb\u884c\u67e5\u8be2\u7684\u65f6\u5019\uff0cHash \u7d22\u5f15\u4e5f\u65e0\u6cd5\u88ab\u5229\u7528\u3002<\/p>\n
\uff084\uff09Hash \u7d22\u5f15\u5728\u4efb\u4f55\u65f6\u5019\u90fd\u4e0d\u80fd\u907f\u514d\u8868\u626b\u63cf\u3002
\n\u524d\u9762\u5df2\u7ecf\u77e5\u9053\uff0cHash \u7d22\u5f15\u662f\u5c06\u7d22\u5f15\u952e\u901a\u8fc7 Hash \u8fd0\u7b97\u4e4b\u540e\uff0c\u5c06 Hash\u8fd0\u7b97\u7ed3\u679c\u7684 Hash \u503c\u548c\u6240\u5bf9\u5e94\u7684\u884c\u6307\u9488\u4fe1\u606f\u5b58\u653e\u4e8e\u4e00\u4e2a Hash \u8868\u4e2d\uff0c\u7531\u4e8e\u4e0d\u540c\u7d22\u5f15\u952e\u5b58\u5728\u76f8\u540c Hash \u503c\uff0c\u6240\u4ee5\u5373\u4f7f\u53d6\u6ee1\u8db3\u67d0\u4e2a Hash \u952e\u503c\u7684\u6570\u636e\u7684\u8bb0\u5f55\u6761\u6570\uff0c\u4e5f\u65e0\u6cd5\u4ece Hash \u7d22\u5f15\u4e2d\u76f4\u63a5\u5b8c\u6210\u67e5\u8be2\uff0c\u8fd8\u662f\u8981\u901a\u8fc7\u8bbf\u95ee\u8868\u4e2d\u7684\u5b9e\u9645\u6570\u636e\u8fdb\u884c\u76f8\u5e94\u7684\u6bd4\u8f83\uff0c\u5e76\u5f97\u5230\u76f8\u5e94\u7684\u7ed3\u679c\u3002<\/p>\n
\uff085\uff09Hash \u7d22\u5f15\u9047\u5230\u5927\u91cfHash\u503c\u76f8\u7b49\u7684\u60c5\u51b5\u540e\u6027\u80fd\u5e76\u4e0d\u4e00\u5b9a\u5c31\u4f1a\u6bd4B-Tree\u7d22\u5f15\u9ad8\u3002
\n\u5bf9\u4e8e\u9009\u62e9\u6027\u6bd4\u8f83\u4f4e\u7684\u7d22\u5f15\u952e\uff0c\u5982\u679c\u521b\u5efa Hash \u7d22\u5f15\uff0c\u90a3\u4e48\u5c06\u4f1a\u5b58\u5728\u5927\u91cf\u8bb0\u5f55\u6307\u9488\u4fe1\u606f\u5b58\u4e8e\u540c\u4e00\u4e2a Hash \u503c\u76f8\u5173\u8054\u3002\u8fd9\u6837\u8981\u5b9a\u4f4d\u67d0\u4e00\u6761\u8bb0\u5f55\u65f6\u5c31\u4f1a\u975e\u5e38\u9ebb\u70e6\uff0c\u4f1a\u6d6a\u8d39\u591a\u6b21\u8868\u6570\u636e\u7684\u8bbf\u95ee\uff0c\u800c\u9020\u6210\u6574\u4f53\u6027\u80fd\u4f4e\u4e0b\u3002<\/p>\n
\u5b9e\u73b0<\/h1>\n
\u95ee\u9898\u63cf\u8ff0\uff1a\u8bbe\u8ba1\u54c8\u5e0c\u8868\u5b9e\u73b0\u7535\u8bdd\u53f7\u7801\u67e5\u8be2\u7cfb\u7edf\uff0c\u5b9e\u73b0\u4e0b\u5217\u529f\u80fd\uff1a
\n(1) \u5047\u5b9a\u6bcf\u4e2a\u8bb0\u5f55\u6709\u4e0b\u5217\u6570\u636e\u9879\uff1a\u7535\u8bdd\u53f7\u7801\u3001\u7528\u6237\u540d\u3001\u5730\u5740\u3002
\n(2) \u4e00\u662f\u4ece\u6570\u636e\u6587\u4ef6old.txt(\u81ea\u5df1\u73b0\u884c\u5efa\u597d)\u4e2d\u8bfb\u5165\u5404\u9879\u8bb0\u5f55\uff0c\u4e8c\u662f\u7531\u7cfb\u7edf\u968f\u673a\u4ea7\u751f\u5404\u8bb0\u5f55\uff0c\u5e76\u4e14\u628a\u8bb0\u5f55\u4fdd\u5b58\u5230new.txt\u6587\u4ef6\u4e2d\u4ee5\u53ca\u663e\u793a\u5230\u5c4f\u5e55\u4e0a\uff0c\u8bb0\u5f55\u6761\u6570\u4e0d\u8981\u5c11\u4e8e30\uff0c\u7136\u540e\u5206\u522b\u4ee5\u7535\u8bdd\u53f7\u7801\u548c\u7528\u6237\u540d\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u54c8\u5e0c\u8868\u3002
\n(3) \u5206\u522b\u91c7\u7528\u4f2a\u968f\u673a\u63a2\u6d4b\u518d\u6563\u5217\u6cd5\u548c\u518d\u54c8\u5e0c\u6cd5\u89e3\u51b3\u51b2\u7a81\u3002
\n(4) \u67e5\u627e\u5e76\u663e\u793a\u7ed9\u5b9a\u7535\u8bdd\u53f7\u7801\u7684\u8bb0\u5f55\uff1b\u67e5\u627e\u5e76\u663e\u793a\u7ed9\u5b9a\u7528\u6237\u540d\u7684\u8bb0\u5f55\u3002
\n(5) \u5c06\u6ca1\u6709\u67e5\u627e\u7684\u7ed3\u679c\u4fdd\u5b58\u5230\u7ed3\u679c\u6587\u4ef6Out.txt\u4e2d\uff0c\u663e\u793a\u67e5\u627e\u7ed3\u679c\u524d\uff0c\u8981\u6709\u63d0\u793a\u8bed\u53e5\u3002<\/p>\n<\/div>\n
\/\/ MyHashTable.cpp : \u5b9a\u4e49\u63a7\u5236\u53f0\u5e94\u7528\u7a0b\u5e8f\u7684\u5165\u53e3\u70b9\u3002\r\n\/\/\/\/\u8bbe\u8ba1\u54c8\u5e0c\u8868\u5b9e\u73b0\u7535\u8bdd\u53f7\u7801\u67e5\u8be2\u7cfb\u7edf\r\n\/\/\u8bf4\u660e\uff1a\u4e00\u662f\u4ece\u6587\u4ef6old.txt\u4e2d\u8bfb\u53d6\u7684\u6570\u636e\u81ea\u5df1\u5728\u7a0b\u5e8f\u8fd0\u884c\u524d\u5efa\u7acb\uff0c\r\n\/\/      \u4e8c\u662f\u7531\u7cfb\u7edf\u968f\u673a\u751f\u6210\u6570\u636e\uff0c\u5728\u7a0b\u5e8f\u8fd0\u884c\u7531\u968f\u673a\u6570\u4ea7\u751f\u5668\u751f\u6210\uff0c\u5e76\u4e14\u5c06\u4ea7\u751f\u7684\u8bb0\u5f55\u4fdd\u5b58\u5230 new.txt\u6587\u4ef6\u3002\r\n\r\n\/\/\u5b58\u5728\u7684\u95ee\u9898\uff1a\u4f7f\u7528\u968f\u673a\u4ea7\u751f\u7684\u6587\u4ef6\uff0c\u5728\u663e\u793a\u65f6\u51fa\u73b0\u4e71\u7801\r\n\r\n\r\n#include \"stdafx.h\"\r\n#include<fstream>\/\/\u6587\u4ef6\u6d41\r\n#include<iostream>\r\n#include <string>\r\nusing namespace std;\r\n\r\nconst int D[] = {3,5,8,11,13,14,19,21};\/\/\u9884\u5b9a\u518d\u968f\u673a\u6570\r\nconst int HASH_MAXSIZE = 50;\/\/\u54c8\u5e0c\u8868\u957f\u5ea6\r\n\r\n\/\/\u8bb0\u5f55\u4fe1\u606f\u7c7b\u578b\r\nclass DataInfo\r\n{\r\npublic:\r\n    DataInfo();\/\/\u9ed8\u8ba4\u6784\u9020\u51fd\u6570\r\n    friend ostream& operator<<(ostream& out, const DataInfo& dataInfo); \/\/\u91cd\u8f7d\u8f93\u51fa\u64cd\u4f5c\u7b26\r\n    \/\/friend class HashTable;\r\n\r\n\/\/private:\r\n    string name;\/\/\u59d3\u540d\r\n    string phone;\/\/\u7535\u8bdd\u53f7\u7801\r\n    string address;\/\/\u5730\u5740 \r\n    char sign;\/\/\u51b2\u7a81\u7684\u6807\u5fd7\u4f4d\uff0c'1'\u8868\u793a\u51b2\u7a81\uff0c'0'\u8868\u793a\u65e0\u51b2\u7a81\r\n};\r\n\r\nDataInfo::DataInfo():name(\"\"), phone(\"\"), address(\"\"), sign('0')\r\n{\r\n\r\n}\r\n\r\nostream& operator<<(ostream& out, const DataInfo& dataInfo) \/\/\u91cd\u8f7d\u8f93\u51fa\u64cd\u4f5c\u7b26\r\n{\r\n    cout << \"\u59d3\u540d\uff1a\" << dataInfo.name << \"   \u7535\u8bdd\uff1a\" << dataInfo.phone \r\n         << \"    \u5730\u5740\uff1a\" << dataInfo.address << endl;\r\n    return out;\r\n}\r\n\r\n\/\/\u5b58\u653e\u8bb0\u5f55\u7684\u54c8\u5e0c\u8868\u7c7b\u578b\r\nclass HashTable\r\n{\r\npublic:\r\n    HashTable();\/\/\u9ed8\u8ba4\u6784\u9020\u51fd\u6570\r\n    ~HashTable();\/\/\u6790\u6784\u51fd\u6570\r\n    int Random(int key, int i);\/\/ \u4f2a\u968f\u673a\u6570\u63a2\u6d4b\u518d\u6563\u5217\u6cd5\u5904\u7406\u51b2\u7a81\r\n    void Hashname(DataInfo *dataInfo);\/\/\u4ee5\u540d\u5b57\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u54c8\u5e0c\u8868    \r\n    int Rehash(int key, string str);\/\/ \u518d\u54c8\u5e0c\u6cd5\u5904\u7406\u51b2\u7a81   \u6ce8\u610f\u5904\u7406\u51b2\u7a81\u8fd8\u6709\u94fe\u5730\u5740\u6cd5\u7b49\r\n    void Hashphone(DataInfo *dataInfo);\/\/\u4ee5\u7535\u8bdd\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u54c8\u5e0c\u8868       \r\n    void Hash(char *fname, int n);\/\/ \u5efa\u7acb\u54c8\u5e0c\u8868\r\n    \/\/fname \u662f\u6570\u636e\u50a8\u5b58\u7684\u6587\u4ef6\u7684\u540d\u79f0\uff0c\u7528\u4e8e\u8f93\u5165\u6570\u636e\uff0cn\u662f\u7528\u6237\u9009\u62e9\u7684\u67e5\u627e\u65b9\u5f0f  \r\n\r\n    int Findname(string name);\/\/ \u6839\u636e\u59d3\u540d\u67e5\u627e\u54c8\u5e0c\u8868\u4e2d\u7684\u8bb0\u5f55\u5bf9\u5e94\u7684\u5173\u952e\u7801\r\n    int Findphone(string phone);\/\/ \u6839\u636e\u7535\u8bdd\u67e5\u627e\u54c8\u5e0c\u8868\u4e2d\u7684\u8bb0\u5f55\u5bf9\u5e94\u7684\u5173\u952e\u7801\r\n    void Outhash(int key);\/\/ \u8f93\u51fa\u54c8\u5e0c\u8868\u4e2d\u5173\u952e\u5b57\u7801\u5bf9\u5e94\u7684\u4e00\u6761\u8bb0\u5f55\r\n    void Outfile(string name, int key);\/\/ \u5728\u6ca1\u6709\u627e\u5230\u65f6\u8f93\u51fa\u672a\u627e\u5230\u7684\u8bb0\u5f55\r\n    void Rafile();\/\/ \u968f\u673a\u751f\u6210\u6587\u4ef6\uff0c\u5e76\u5c06\u6587\u4ef6\u4fdd\u5b58\u5728 new.txt\u6587\u6863\u4e2d\r\n    void WriteToOldTxt();\/\/\u5728\u8fd0\u884c\u524d\u5148\u5199\u5165\u6570\u636e    \r\n\r\n\/\/private:\r\n        DataInfo *value[HASH_MAXSIZE];\r\n    int length;\/\/\u54c8\u5e0c\u8868\u957f\u5ea6\r\n};\r\n\r\nHashTable::HashTable():length(0)\/\/\u9ed8\u8ba4\u6784\u9020\u51fd\u6570\r\n{\r\n    \/\/memset(value, NULL, HASH_MAXSIZE*sizeof(DataInfo*));\r\n    for (int i=0; i<HASH_MAXSIZE; i++)\r\n    {\r\n        value[i] = new DataInfo();\r\n    }\r\n}\r\n\r\nHashTable::~HashTable()\/\/\u6790\u6784\u51fd\u6570\r\n{\r\n    delete[] *value;\r\n}\r\n\r\nvoid HashTable::WriteToOldTxt()\r\n{\r\n    ofstream openfile(\"old.txt\");\r\n    if (openfile.fail())\r\n    {\r\n        cout << \"\u6587\u4ef6\u6253\u5f00\u9519\u8bef\uff01\" << endl;\r\n        exit(1);\r\n    }\r\n\r\n    string oldname;\r\n        string oldphone;\r\n    string oldaddress;\r\n\r\n    for (int i=0; i<30; i++)\r\n    {\r\n        cout << \"\u8bf7\u8f93\u5165\u7b2c\" << i+1 << \"\u6761\u8bb0\u5f55:\" << endl;        \r\n        cin >> oldname ;\r\n        cin >> oldphone;\r\n        cin >> oldaddress;\r\n        openfile << oldname << \"  \" << oldphone << \"  \" << oldaddress << \",\" << endl;\r\n    }\r\n    openfile.close();\r\n}\r\n\r\n\r\nint HashTable::Random(int key, int i)\/\/ \u4f2a\u968f\u673a\u6570\u63a2\u6d4b\u518d\u6563\u5217\u6cd5\u5904\u7406\u51b2\u7a81\r\n{\/\/key\u662f\u51b2\u7a81\u65f6\u7684\u54c8\u5e0c\u8868\u5173\u952e\u7801\uff0ci\u662f\u51b2\u7a81\u7684\u6b21\u6570\uff0cN\u662f\u54c8\u5e0c\u8868\u957f\u5ea6\r\n    \/\/\u6210\u529f\u5904\u7406\u51b2\u7a81\u8fd4\u56de\u65b0\u7684\u5173\u952e\u7801\uff0c\u672a\u8fdb\u884c\u51b2\u7a81\u5904\u7406\u5219\u8fd4\u56de-1\r\n    int h;\r\n    if(value[key]->sign == '1')\/\/\u6709\u51b2\u7a81\r\n    {\r\n        h = (key + D[i]) % HASH_MAXSIZE;\r\n        return h;\r\n    }\r\n    return -1;\r\n}\r\n\r\nvoid HashTable::Hashname(DataInfo *dataInfo)\/\/\u4ee5\u540d\u5b57\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u54c8\u5e0c\u8868\r\n{\/\/\u5229\u7528\u9664\u7559\u53d6\u4f59\u6cd5\u5efa\u7acb\u4ee5\u540d\u5b57\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u7684\u54c8\u5e0c\u51fd\u6570\uff0c\u5728\u53d1\u751f\u51b2\u7a81\u65f6\u8c03\u7528Random\u51fd\u6570\u5904\u7406\u51b2\u7a81\r\n    int i = 0;  \r\n    int key = 0;\r\n\r\n        for (int t=0; dataInfo->name[t]!='\\0'; t++)   \r\n    {       \r\n        key = key + dataInfo->name[t];\r\n    }\r\n    key = key % 42;\r\n    while(value[key]->sign == '1')\/\/\u6709\u51b2\u7a81\r\n    {\r\n        key = Random(key, i++);\/\/\u5904\u7406\u51b2\u7a81\r\n    }\r\n    if(key == -1) exit(1);\/\/\u65e0\u51b2\u7a81\r\n    length++;\/\/\u5f53\u524d\u6570\u636e\u4e2a\u6570\u52a0\r\n    value[key]->name = dataInfo->name;\r\n    value[key]->address = dataInfo->address;\r\n    value[key]->phone = dataInfo->phone;\r\n    value[key]->sign = '1';\/\/\u8868\u793a\u8be5\u4f4d\u7f6e\u6709\u503c\r\n    \/\/cout << value[key]->name << \"  \" << value[key]->phone << \"  \"  << value[key]->address << endl;\r\n}\r\n\r\nint HashTable::Rehash(int key, string str)\/\/ \u518d\u54c8\u5e0c\u6cd5\u5904\u7406\u51b2\u7a81\r\n{\/\/\u518d\u54c8\u5e0c\u65f6\u4f7f\u7528\u7684\u662f\u6298\u53e0\u6cd5\u5efa\u7acb\u54c8\u5e0c\u51fd\u6570    \r\n    int h;\r\n    int num1 = (str[0] - '0') * 1000 + (str[1] - '0') * 100 + (str[2] - '0') * 10 + (str[3] - '0');\r\n    int num2 = (str[4] - '0') * 1000 + (str[5] - '0') * 100 + (str[6] - '0') * 10 + (str[7] - '0');\r\n    int num3 = (str[8] - '0') * 100  + (str[9] - '0') * 10  + (str[10] - '0');\r\n    h = num1 + num2 + num3;\r\n    h = (h + key) % HASH_MAXSIZE;\r\n    return h;\r\n}\r\n\r\nvoid HashTable::Hashphone(DataInfo *dataInfo)\/\/\u4ee5\u7535\u8bdd\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u54c8\u5e0c\u8868\r\n{\/\/\u5229\u7528\u9664\u7559\u53d6\u4f59\u6cd5\u5efa\u7acb\u4ee5\u7535\u8bdd\u4e3a\u5173\u952e\u5b57\u5efa\u7acb\u7684\u54c8\u5e0c\u51fd\u6570\uff0c\u5728\u53d1\u751f\u51b2\u7a81\u65f6\u8c03\u7528Rehash\u51fd\u6570\u5904\u7406\u51b2\u7a81\r\n    int key = 0;    \r\n    int t;\r\n\r\n    for(t=0; dataInfo->phone[t] != '\\0'; t++)\r\n    {   \r\n        key = key + dataInfo->phone[t];\r\n    }\r\n    key = key % 42;\r\n    while(value[key]->sign == '1')\/\/\u6709\u51b2\u7a81\r\n    {\r\n        key = Rehash(key, dataInfo->phone);\r\n    }\r\n    length++;\/\/\u5f53\u524d\u6570\u636e\u4e2a\u6570\u52a0\r\n    value[key]->name = dataInfo->name;\r\n    value[key]->address = dataInfo->address;\r\n    value[key]->phone = dataInfo->phone;   \r\n    value[key]->sign = '1';\/\/\u8868\u793a\u8be5\u4f4d\u7f6e\u6709\u503c    \r\n}\r\n\r\nvoid HashTable::Outfile(string name, int key)\/\/\u5728\u6ca1\u6709\u627e\u5230\u65f6\u8f93\u51fa\u672a\u627e\u5230\u7684\u8bb0\u5f55\r\n{\r\n    ofstream fout;\r\n    if((key == -1)||(value[key]->sign == '0'))\/\/\u5224\u65ad\u54c8\u5e0c\u8868\u4e2d\u6ca1\u6709\u8bb0\u5f55\r\n    {\r\n        fout.open(\"out.txt\",ios::app);\/\/\u6253\u5f00\u6587\u4ef6\r\n\r\n        if(fout.fail())\r\n        {\r\n            cout << \"\u6587\u4ef6\u6253\u5f00\u5931\u8d25!\" << endl;\r\n            exit(1);\r\n        }\r\n        fout << name << endl;\/\/\u5c06\u540d\u5b57\u5199\u5165\u6587\u4ef6,\u6709\u4e2a\u95ee\u9898\uff0c\u6bcf\u6b21\u5199\u5165\u7684\u65f6\u5019\u603b\u662f\u5c06\u539f\u6765\u7684\u5185\u5bb9\u66ff\u6362\u4e86\r\n        fout.close();\r\n    }\r\n}\r\n\r\nvoid HashTable::Outhash(int key)\/\/\u8f93\u51fa\u54c8\u5e0c\u8868\u4e2d\u5173\u952e\u5b57\u7801\u5bf9\u5e94\u7684\u8bb0\u5f55\r\n{  \r\n    if((key==-1)||(value[key]->sign=='0'))\r\n        cout << \"\u6ca1\u6709\u627e\u5230\u8fd9\u6761\u8bb0\u5f55\uff01\" << endl;\r\n    else\r\n    {       \r\n        for(unsigned int i=0; value[key]->name[i]!='\\0'; i++)\r\n        {\r\n            cout << value[key]->name[i];            \r\n        }\r\n\r\n        for(unsigned int i=0; i<10; i++)\r\n        {\r\n            cout << \" \";\r\n        }\r\n\r\n        cout << value[key]->phone;\r\n\r\n        for(int i=0; i<10; i++)\r\n        {\r\n            cout << \" \";\r\n        }\r\n\r\n        cout << value[key]->address << endl;\r\n    }\r\n}\r\n\r\nvoid HashTable::Rafile()\/\/\u968f\u673a\u751f\u6210\u6587\u4ef6\uff0c\u5e76\u5c06\u6587\u4ef6\u4fdd\u5b58\u5728new.txt\u6587\u6863\u4e2d\r\n{\r\n    ofstream fout;\r\n    fout.open(\"new.txt\");\/\/\u6253\u5f00\u6587\u4ef6\uff0c\u7b49\u5f85\u5199\u5165\r\n    if(fout.fail())\r\n    {\r\n        cout << \"\u6587\u4ef6\u6253\u5f00\u5931\u8d25\uff01\" << endl;\r\n        exit(1);\r\n    }\r\n    for(int j=0; j<30; j++)\r\n    {       \r\n        string name = \"\";\r\n        for(int i=0; i<20; i++)\/\/\u968f\u673a\u751f\u6210\u957f\u4e2a\u5b57\u7684\u540d\u5b57\r\n        {\r\n            name += rand() % 26 + 'a';\/\/\u540d\u5b57\u662f\u7531\u4e2a\u5b57\u6bcd\u7ec4\u6210           \r\n        }\r\n        fout << name << \"   \";\/\/\u5c06\u540d\u5b57\u5199\u5165\u6587\u4ef6\r\n\r\n        string phone = \"\";\r\n        for(int i=0; i<11; i++)\/\/\u968f\u673a\u751f\u6210\u957f\u4f4d\u7684\u7535\u8bdd\u53f7\u7801\r\n        {\r\n            phone += rand() % 10 + '0';\/\/\u7535\u8bdd\u53f7\u7801\u662f\u7eaf\u6570\u5b57\r\n        }\r\n        fout << phone << \"      \";\/\/\u5c06\u7535\u8bdd\u53f7\u7801\u5199\u5165\u6587\u4ef6\r\n\r\n        string address = \"\";\r\n        for(int i=0; i<29; i++)\/\/\u968f\u673a\u751f\u6210\u957f\u4e2a\u5b57\u7684\u540d\u5b57\r\n        {\r\n            address += rand() % 26 + 'a';\/\/\u5730\u5740\u662f\u7531\u4e2a\u5b57\u6bcd\u7ec4\u6210\r\n        }\r\n        address += ',';\r\n        fout << address << endl;\/\/\u5c06\u5730\u5740\u5199\u5165\u6587\u4ef6\r\n    }\r\n    fout.close();\r\n}\r\n\r\nvoid HashTable::Hash(char *fname, int n)\/\/\u5efa\u7acb\u54c8\u5e0c\u8868\r\n\/\/fname\u662f\u6570\u636e\u50a8\u5b58\u7684\u6587\u4ef6\u7684\u540d\u79f0\uff0c\u7528\u4e8e\u8f93\u5165\u6570\u636e\uff0cn\u662f\u7528\u6237\u9009\u62e9\u7684\u67e5\u627e\u65b9\u5f0f\r\n\/\/\u51fd\u6570\u8f93\u5165\u6570\u636e\uff0c\u5e76\u6839\u636e\u9009\u62e9\u8c03\u7528Hashname\u6216Hashphone\u51fd\u6570\u8fdb\u884c\u54c8\u5e0c\u8868\u7684\u5efa\u7acb\r\n{\r\n    ifstream fin;       \r\n    int i;\r\n    fin.open(fname);\/\/\u8bfb\u6587\u4ef6\u6d41\u5bf9\u8c61\r\n    if(fin.fail())\r\n    {\r\n        cout << \"\u6587\u4ef6\u6253\u5f00\u5931\u8d25\uff01\" << endl;\r\n        exit(1);\r\n    }\r\n    while(!fin.eof())\/\/\u6309\u884c\u8bfb\u5165\u6570\u636e\r\n    {\r\n        DataInfo *dataInfo = new DataInfo();\r\n        char* str = new char[100];      \r\n        fin.getline(str, 100, '\\n');\/\/\u8bfb\u53d6\u4e00\u884c\u6570\u636e\r\n\r\n        if(str[0] == '*')\/\/\u5224\u65ad\u6570\u636e\u7ed3\u675f\r\n        {\r\n            break;\r\n        }\r\n\r\n        i = 0;\/\/\u8bb0\u5f55\u5b57\u7b26\u4e32\u6570\u7ec4\u7684\u4e0b\u6807\r\n        \/\/a-z:97-122     A-Z:65-90    \r\n        \/\/\u672c\u7a0b\u5e8f\u7684\u59d3\u540d\u548c\u5730\u5740\u90fd\u4f7f\u7528\u5c0f\u5199\u5b57\u6bcd\r\n        while((str[i] < 97) || (str[i] > 122))\/\/\u8bfb\u5165\u540d\u5b57\r\n        {\r\n            i++;\r\n        }\r\n\r\n        for(; str[i]!=' '; i++)\r\n        {           \r\n            dataInfo->name += str[i];           \r\n        }\r\n\r\n        while(str[i] == ' ')\r\n        {\r\n            i++;\r\n        }\r\n\r\n        for(int j=0; str[i]!=' '; j++,i++)\/\/\u8bfb\u5165\u7535\u8bdd\u53f7\u7801\r\n        {           \r\n            dataInfo->phone += str[i];\r\n        }\r\n\r\n        while(str[i] == ' ')\r\n        {\r\n            i++;\r\n        }\r\n\r\n        for(int j=0; str[i]!=','; j++,i++)\/\/\u8bfb\u5165\u5730\u5740\r\n        {           \r\n            dataInfo->address += str[i];\r\n        }\r\n\r\n        if(n == 1)\r\n        {           \r\n            Hashname(dataInfo);\r\n        }\r\n        else\r\n        {           \r\n            Hashphone(dataInfo);\/\/\u4ee5\u7535\u8bdd\u4e3a\u5173\u952e\u5b57\r\n        }\r\n\r\n        delete []str;\r\n        delete dataInfo;\r\n    }   \r\n    fin.close();\r\n}\r\n\r\nint HashTable::Findname(string name)\/\/\u6839\u636e\u59d3\u540d\u67e5\u627e\u54c8\u5e0c\u8868\u4e2d\u7684\u8bb0\u5f55\u5bf9\u5e94\u7684\u5173\u952e\u7801\r\n{\r\n    int i = 0;\r\n    int j = 1;\r\n    int t;\r\n    int key = 0;\r\n\r\n    for(key=0, t=0; name[t] != '\\0'; t++)\r\n    {\r\n        key = key + name[t];\r\n    }\r\n    key = key % 42;\r\n    while((value[key]->sign == '1') && (value[key]->name != name))\r\n    {  \r\n        key = Random(key, i++);\r\n        j++;\r\n        if(j >= length) return -1;\r\n    }\r\n    return key;\r\n}\r\n\r\nint HashTable::Findphone(string phone)\/\/\u6839\u636e\u7535\u8bdd\u67e5\u627e\u54c8\u5e0c\u8868\u4e2d\u7684\u8bb0\u5f55\u5bf9\u5e94\u7684\u5173\u952e\u7801\r\n{  \r\n    int key = 0;\r\n    int t;\r\n\r\n    for(t=0; phone[t] != '\\0' ; t++)\r\n        {\r\n                key = key + phone[t];\r\n        }\r\n    key = key % 42;\r\n    int j = 1;\r\n    while((value[key]->sign == '1') && (value[key]->phone != phone))\r\n    {\r\n        key = Rehash(key, phone);\r\n        j++;\r\n        if(j >= length) \r\n                {\r\n                    return -1;\r\n                }\r\n        }\r\n    return key;\r\n}\r\n\r\nvoid main()\r\n{\r\n    \/\/WriteToOldTxt();  \r\n    int k;\r\n    int ch; \r\n    char *Fname;\r\n    HashTable *ht = new HashTable;\r\n    while(1)\r\n    {\r\n        system(\"cls\");\/\/cls\u547d\u4ee4\u6e05\u9664\u5c4f\u5e55\u4e0a\u6240\u6709\u7684\u6587\u5b57\r\n        cout << \"\u6b22\u8fce\u4f7f\u7528\u672c\u7cfb\u7edf\uff01\" << endl << endl;\r\n        cout << \"\u8bf7\u9009\u62e9\u6570\u636e\" << endl;\r\n        cout << \"1.\u4f7f\u7528\u5df2\u6709\u6570\u636e\u6587\u4ef6\" << endl;\r\n        cout << \"2.\u968f\u673a\u751f\u6210\u6570\u636e\u6587\u4ef6\" << endl;\r\n        cout << \"0.\u7ed3\u675f\" << endl;\r\n        cout << \"\u8f93\u5165\u76f8\u5e94\u5e8f\u53f7\u9009\u62e9\u529f\u80fd\uff1a\";\r\n        cin >> k;\r\n        switch(k)\r\n        {\r\n        case 0:\r\n            return;\r\n        case 1:\r\n            Fname = \"old.txt\";\/\/\u4ece\u6570\u636e\u6587\u4ef6old.txt(\u81ea\u5df1\u73b0\u884c\u5efa\u597d)\u4e2d\u8bfb\u5165\u5404\u9879\u8bb0\u5f55\r\n            break;\r\n        case 2:\r\n            ht->Rafile();\r\n            Fname = \"new.txt\";\/\/\u7531\u7cfb\u7edf\u968f\u673a\u4ea7\u751f\u5404\u8bb0\u5f55\uff0c\u5e76\u4e14\u628a\u8bb0\u5f55\u4fdd\u5b58\u5230new.txt\u6587\u4ef6\u4e2d\r\n            break;\r\n        default:\r\n            cout << \"\u8f93\u5165\u5e8f\u53f7\u6709\u8bef\uff0c\u9000\u51fa\u7a0b\u5e8f\u3002\" << endl; \r\n            return;\r\n        }\r\n\r\n        do\r\n        {\r\n            system(\"cls\");\r\n            cout << \" \u8bf7\u9009\u62e9\u67e5\u627e\u65b9\u5f0f\" << endl;\r\n            cout << \"1.\u901a\u8fc7\u59d3\u540d\u67e5\u627e\" << endl;\r\n            cout << \"2.\u901a\u8fc7\u7535\u8bdd\u67e5\u627e\" << endl;\r\n            cout << \"\u8f93\u5165\u76f8\u5e94\u5e8f\u53f7\u9009\u62e9\u529f\u80fd\uff1a\";\r\n            cin >> ch;\r\n            if((ch != 1) && (ch != 2))\r\n                cout << \"\u8f93\u5165\u5e8f\u53f7\u6709\u8bef\uff01\" << endl;\r\n        }while((ch != 1) && (ch != 2));\r\n\r\n        ht->Hash(Fname, ch);\r\n        while(ch == 1)\r\n        {\r\n            int choice;\r\n            cout << endl << \"\u8bf7\u9009\u62e9\u529f\u80fd\" << endl;\r\n            cout << \"1.\u8f93\u5165\u59d3\u540d\u67e5\u627e\u6570\u636e\" << endl;\r\n            cout << \"2.\u663e\u793a\u54c8\u5e0c\u8868\" << endl;\r\n            cout << \"0.\u9000\u51fa\"<<endl;\r\n            cout << \"\u8f93\u5165\u76f8\u5e94\u5e8f\u53f7\u9009\u62e9\u529f\u80fd\uff1a\";\r\n            cin >> choice;\r\n            switch(choice)\r\n            {\r\n            case 1: \r\n                {\/\/\u6ce8\u610f\u6b64\u5904\u5e94\u8be5\u52a0\u4e0a\u5927\u62ec\u53f7\r\n                    int key1;                   \r\n                    string name;                    \r\n                    cout << \"\u8bf7\u8f93\u5165\u59d3\u540d\uff1a\";\r\n                    cin >> name;                    \r\n                    key1 = ht->Findname(name);\r\n                    ht->Outfile(name, key1);\r\n                    ht->Outhash(key1);  \r\n                }\r\n                break;\r\n\r\n            case 2: \r\n                {\r\n                    for(int i=0; i<HASH_MAXSIZE; i++)\r\n                    {\r\n                        if(ht->value[i]->sign!='0')\r\n                        {\r\n                            ht->Outhash(i); \r\n                        }\r\n                    }   \r\n                }                           \r\n                break;\r\n\r\n\r\n            default:\r\n                cout << endl << \"\u60a8\u7684\u8f93\u5165\u6709\u8bef\uff01\" << endl;              \r\n            }\r\n\r\n            if(choice == 0) \r\n            {\r\n                return;\r\n            }\r\n        }\r\n\r\n        while(ch == 2)\r\n        {\r\n            int choice;\r\n            cout << endl << \"\u8bf7\u9009\u62e9\u529f\u80fd\" << endl;\r\n            cout << \"1.\u8f93\u5165\u7535\u8bdd\u67e5\u627e\u6570\u636e\" << endl;\r\n            cout << \"2.\u663e\u793a\u54c8\u5e0c\u8868\"<<endl;\r\n            cout << \"0.\u9000\u51fa\"<<endl;\r\n            cout << \"\u8f93\u5165\u76f8\u5e94\u5e8f\u53f7\u9009\u62e9\u529f\u80fd\uff1a\";\r\n            cin >> choice;\r\n            switch(choice)\r\n            {\r\n            case 1: \r\n                {\r\n                    int key2;                   \r\n                    string phone;                   \r\n                    cout << \"\u8bf7\u8f93\u516511\u4f4d\u7684\u7535\u8bdd\u53f7\u7801\uff1a\";\r\n\r\n                    do\r\n                    {\r\n                        cin >> phone;                       \r\n                        if(phone.length() != 11)                    \r\n                        {\r\n                            cout << \"\u7535\u8bdd\u53f7\u7801\u5e94\u4e3a11\u4f4d\uff01\\n\u8bf7\u91cd\u65b0\u8f93\u5165\uff1a\";\r\n                        }\r\n\r\n                    }while(phone.length() != 11);\r\n\r\n                    key2 = ht->Findphone(phone);\r\n                    ht->Outfile(phone, key2);\r\n                    ht->Outhash(key2);\r\n                }\r\n                break;\r\n\r\n            case 2: \r\n                {\r\n                    for(int i=0; i<HASH_MAXSIZE; i++)\r\n                    {\r\n                        if(ht->value[i]->sign != '0') \r\n                        {\r\n                            ht->Outhash(i); \r\n                        }\r\n                    }\r\n                }               \r\n                break;\r\n\r\n            default:\r\n                 cout << endl << \"\u60a8\u7684\u8f93\u5165\u6709\u8bef\uff01\" << endl;              \r\n            }\r\n\r\n            if(choice == 0) \r\n            {\r\n                return;\r\n            }\r\n        }\r\n\r\n        while((ch != 1) && (ch != 2))\r\n        {\r\n            cout << \"\u60a8\u7684\u8f93\u5165\u6709\u8bef\uff01\u8bf7\u8f93\u5165\u76f8\u5e94\u9700\u8981\u9009\u62e9\u529f\u80fd\uff1a\";\r\n        }\r\n    }\r\n    system(\"pause\");    \r\n}<\/pre>\n
 <\/p>\n
\n
\u539f\u7406\u8bf4\u660e\u6765\u6e90\uff1a<\/p>\n
http:\/\/www.tuicool.com\/articles\/BvI3Ir<\/a>
\nhttp:\/\/blog.csdn.net\/nju_yaho\/article\/details\/7402208<\/a>
\nhttp:\/\/blog.csdn.net\/duan19920101\/article\/details\/51579136<\/a>
\nhttp:\/\/blog.sina.com.cn\/s\/blog_6776884e0100pko1.html<\/a>
\nhttp:\/\/blog.csdn.net\/v_july_v\/article\/details\/6256463<\/a><\/p>\n
\u4ee3\u7801\u5b9e\u73b0\u6765\u6e90\uff1a<\/p>\n
http:\/\/blog.csdn.net\/htyurencaotang\/article\/details\/7881427<\/a><\/p>\n<\/div>\n<\/div>\n<\/article>\n","protected":false},"excerpt":{"rendered":"
\u539f\u7406\u4ecb\u7ecd \u54c8\u5e0c\u8868\uff08Hash table\uff0c<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[119],"class_list":["post-2185","post","type-post","status-publish","format-standard","hentry","tag-03-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/2185","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=2185"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/2185\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=2185"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=2185"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=2185"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}