{"id":150,"date":"2025-07-09T19:43:11","date_gmt":"2025-07-09T11:43:11","guid":{"rendered":"http:\/\/www.tgwttt.xyz\/?p=150"},"modified":"2025-11-24T16:41:48","modified_gmt":"2025-11-24T08:41:48","slug":"%e5%93%88%e5%b8%8c%e8%a1%a8%e7%9a%84%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/www.tgwttt.xyz\/?p=150","title":{"rendered":"\u54c8\u5e0c\u8868\u7684\u5b9e\u73b0"},"content":{"rendered":"\n<p>\u4ee5\u4e0b\u4ee3\u7801\u5df2\u5728gitee\u4e0a\u5f00\u6e90\uff0c\u4ed3\u5e93\u5730\u5740\uff1a<a href=\"https:\/\/gitee.com\/tgwTTT\/c-lreant\/tree\/master\/hash\">https:\/\/gitee.com\/tgwTTT\/c-lreant\/tree\/master\/hash<\/a><\/p>\n\n\n\n<p>\u54c8\u5e0c\u8868\u662fc++\u5b66\u4e60\u4e2d\u91cd\u8981\u7684\u4e00\u90e8\u5206\uff0c\u5982c++\u91cc\u9762\u7684unordered_set\/map\u90fd\u662f\u7528hash\u5c01\u88c5\u7684\uff0c\u67e5\u627e\u6548\u7387\u8f83\u7531\u7ea2\u9ed1\u6811\u5c01\u88c5\u7684map\/set\u66f4\u52a0\u9ad8\u6548\uff0c\u4e0b\u9762\u662f\u6211\u5c06\u5e26\u9886\u5927\u5bb6\u7528\u5f00\u653e\u5b9a\u5740\u6cd5\u5efa\u7acbhash\u8868<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"124\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-23-1024x124.png\" alt=\"\" class=\"wp-image-151\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-23-1024x124.png 1024w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-23-300x36.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-23-768x93.png 768w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-23.png 1267w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u4e0b\u9762\u4f7f\u7528\u7ebf\u6027\u63a2\u6d4b\u6cd5\u5efa\u7acbhash\u8868\u7684\u8fc7\u7a0b<\/p>\n\n\n\n<p>\u9996\u5148\u4ec0\u4e48\u662f\u7ebf\u6027\u63a2\u6d4b\u6cd5\uff1f<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"187\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-24-1024x187.png\" alt=\"\" class=\"wp-image-152\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-24-1024x187.png 1024w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-24-300x55.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-24-768x140.png 768w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-24.png 1225w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u5c06\u4e0a\u9762\u7684\u6570\u636e\u6620\u5c04\u5230M=11\u7684\u8868\u4e2d\uff0c\u6211\u4eec\u9996\u5148\u9700\u8981\u5c06\u6570\u636e\u53d6\u6a21<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"68\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-25-1024x68.png\" alt=\"\" class=\"wp-image-153\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-25-1024x68.png 1024w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-25-300x20.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-25-768x51.png 768w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-25.png 1198w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u7136\u540e\u4f9d\u6b21\u586b\u5165\u8868\u4e2d\uff0c\u4f46\u662f\u6570\u636e\u6709\u76f8\u540c\u7684\uff0c\u8fd9\u5c31\u610f\u5473\u7740\u53d1\u751f\u4e86\u7ebf\u6027\u51b2\u7a81\uff0c\u9700\u8981\u4f7f\u7528\u7ebf\u6027\u63a2\u6d4b\u6cd5\uff0c\u5411\u540e\u52a0\uff0c\u6307\u5bfc\u627e\u5230\u7a7a\u4f4d<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"72\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-26-1024x72.png\" alt=\"\" class=\"wp-image-154\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-26-1024x72.png 1024w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-26-300x21.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-26-768x54.png 768w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-26.png 1079w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u53d8\u6210\u4e86\u8fd9\u4e2a\u6837\u5b50\uff0c\u5f53\u63d2\u516530\u9047\u5230\u5df2\u7ecf\u88ab19\u5360\u4e86\u7684\u60c5\u51b5\uff0c\u5411\u540e\u79fb\u52a8\u3002\u4f46\u662f\u503c\u5f97\u6211\u4eec\u6ce8\u610f\u7684\u662f \u5f53\u8d1f\u8f7d\u56e0\u5b50\uff08\u5143\u7d20\u4e2a\u6570\/\u5143\u7d20\u7a7a\u95f4\uff09>0.7,\u6211\u4eec\u5fc5\u987b\u5bf9\u5bb9\u91cf\u8fdb\u884c\u6269\u5bb9\u3002\u4e0b\u9762\u662f\u5b9e\u73b0\u8fc7\u7a0b                                                                             <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#pragma once\n#include<vector>\n#include<iostream>\n#include <utility>\nusing namespace std;\nenum State {\n\tEXIST,\n\tEMPTY,\n\tDELETE\n};\n\ntemplate<class K, class V>\nstruct HashData {\n\tpair<K, V>_kv;\n\tState _state = EMPTY;\n};\n\ntemplate<class K,class V>\nclass HashTable {\nprivate:\n\tvector<HashData<K,V>> _tables;\n\tsize_t _n;\/\/\u6570\u636e\u4e2a\u6570\npublic:\n\tHashTable()\n\t\t:_tables(11)\n\t\t,_n(0){ }\n\tbool Insert(const pair<K, V>& kv) {\n\t\tif (Find(kv.first)) {\n\t\t\treturn false;\n\t\t}\n\t\t\t\/\/\u6269\u5bb9\uff0c\u4fdd\u8bc1\u8d1f\u8f7d\u56e0\u5b50\u57280.7\u5de6\u53f3\n\t\tif (_n \/ _tables.size() >= 0.7) {\n\t\t\t\/\/vector<HashData<K, V>> newtables(_tables.size()*2);\n\t\t\t\/\/for (auto& data : _tables) {\n\t\t\t\/\/\ti = 1;\n\t\t\t\/\/\t\/\/\u65e7\u8868\u6570\u636e\u6620\u5c04\u5230\u65b0\u8868\n\t\t\t\/\/\twhile (data._state == EXIST) {\n\t\t\t\/\/\t\tsize_t hash0 = data.first % newtables.size();\n\t\t\t\/\/\t\t++i;\n\t\t\t\/\/\t}\n\t\t\t\/\/}\n\t\t\t\/\/_tables.swap(newtables);\n\t\t\tHashTable<K, V>newht;\n\t\t\tnewht._tables.resize(_tables.size() * 2);\n\t\t\tfor (auto data : _tables) {\n\t\t\t\tif(data._state==EXIST)\n\t\t\t\tnewht.Insert(data._kv);\n\t\t\t}\n\t\t\t_tables.swap(newht._tables);\n\t\t}\n\t\tsize_t hash0 = kv.first % _tables.size();\n\t\tsize_t hashi = hash0;\n\t\tsize_t i = 1;\n\t\twhile (_tables[hashi]._state ==EXIST) {\n\t\t\t\/\/\u7ebf\u6027\u63a2\u6d4b\n\t\t\thashi = (hashi + i)% _tables.size();\n\t\t\t++i;\n\t\t}\n\t\t_tables[hashi]._kv = kv;\n\t\t_tables[hashi]._state = EXIST;\n\t\t++_n;\n\t\treturn true;\n\t}\n\tHashData<K, V>* Find(const K& key) {\n\t\tsize_t hash0 = key % _tables.size();\n\t\tsize_t hashi = hash0;\n\t\tsize_t i = 1;\n\t\twhile (_tables[hashi]._state != EMPTY ) {\n\t\t\t\/\/\u7ebf\u6027\u63a2\u6d4b\n\t\t\tif (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST) {\n\t\t\t\treturn &_tables[hashi];\n\t\t\t}\n\t\t\thashi = (hashi + i) % _tables.size();\n\t\t\t++i;\n\t\t}\n\t\treturn nullptr;\n\t}\n\tbool Erase(const K& key) {\n\t\tHashData<K, V>* ret = Find(key);\n\t\tif (ret == nullptr) {\n\t\t\tcout << \"\u5220\u9664\u5931\u8d25\" << endl;\n\t\t\treturn false;\n\t\t}\n\t\telse {\n\t\t\tret->_state = DELETE;\n\t\t\treturn true;\n\t\t}\n\t}\n};<\/code><\/pre>\n\n\n\n<p>\u4e0b\u9762\u662f\u6d4b\u8bd5\u4ee3\u7801\uff1a<\/p>\n\n\n\n<p>test.cpp<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include<iostream>\n#include\"hashT.h\"\nusing namespace std;\nvoid test_hash_1() {\n    int a[] = { 19,30,52,63,11,22 };\n    HashTable<int, int>ht;\n    for (auto e : a) {\n        ht.Insert({ e,e });\n    }\n    ht.Erase(30);\n    if (ht.Find(30)) {\n        cout << \"\u627e\u5230\u4e86\" << endl;\n    }\n    else {\n        cout << \"\u6ca1\u627e\u5230\" << endl;\n    }\n}\nvoid main() {\n    test_hash_1();\n}<\/code><\/pre>\n\n\n\n<p>\u6d4b\u8bd5\u7ed3\u679c\uff1a<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"982\" height=\"110\" src=\"http:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-27.png\" alt=\"\" class=\"wp-image-155\" srcset=\"https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-27.png 982w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-27-300x34.png 300w, https:\/\/www.tgwttt.xyz\/wp-content\/uploads\/2025\/07\/image-27-768x86.png 768w\" sizes=\"auto, (max-width: 982px) 100vw, 982px\" \/><\/figure>\n\n\n\n<p>\u4eca\u5929\u7684\u66f4\u65b0\u5c31\u5230\u8fd9\u4e86\uff0c\u5982\u6709\u9519\u8bef\uff0c\u8bf7\u8bc4\u8bba\u533a\u7559\u8a00<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4ee5\u4e0b\u4ee3\u7801\u5df2\u5728gitee\u4e0a\u5f00\u6e90\uff0c\u4ed3\u5e93\u5730\u5740\uff1ahttps:\/\/gitee.com\/tgwTTT\/c-lreant\/t&#8230;<\/p>\n","protected":false},"author":1,"featured_media":151,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[4],"tags":[],"class_list":["post-150","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c"],"_links":{"self":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=150"}],"version-history":[{"count":4,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/150\/revisions"}],"predecessor-version":[{"id":877,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/posts\/150\/revisions\/877"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=\/wp\/v2\/media\/151"}],"wp:attachment":[{"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=150"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=150"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.tgwttt.xyz\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}