{"id":10006940,"date":"2022-11-30T09:58:16","date_gmt":"2022-11-30T01:58:16","guid":{"rendered":"https:\/\/ityet.com\/?p=10006940"},"modified":"2022-11-30T09:58:16","modified_gmt":"2022-11-30T01:58:16","slug":"%e6%b5%85%e5%85%a5%e6%b5%85%e5%87%ba-1-7%e5%92%8c1-8%e7%9a%84-hashmap","status":"publish","type":"post","link":"https:\/\/itmax.cn\/?p=10006940","title":{"rendered":"\u6d45\u5165\u6d45\u51fa 1.7\u548c1.8\u7684 HashMap"},"content":{"rendered":"<h2>\u524d\u8a00<\/h2>\n<p>HashMap \u662f\u6211\u4eec<strong>\u6700\u6700\u6700<\/strong>\u5e38\u7528\u7684\u4e1c\u897f\u4e86\uff0c\u5b83\u5c31\u662f\u6211\u4eec\u5728\u5927\u5b66\u4e2d\u5b66\u4e60\u6570\u636e\u7ed3\u6784\u7684\u65f6\u5019\uff0c\u5b66\u5230\u7684\u54c8\u5e0c\u8868\u8fd9\u79cd\u6570\u636e\u7ed3\u6784\u3002\u9762\u8bd5\u4e2d\uff0cHashMap \u7684\u95ee\u9898\u4e5f\u662f\u5e38\u5ba2\uff0c\u73b0\u5728\u5377\u5230\u5fc5\u987b\u7b54\u51fa\u6765\u4e86\uff0c\u662f\u5fc5\u987b\u4f1a\u7684\u77e5\u8bc6\u3002<\/p>\n<p>\u6211\u5728\u5b66\u4e60 HashMap \u7684\u8fc7\u7a0b\u4e2d\uff0c\u4e5f\u9047\u5230\u4e86\u4e0d\u5c11\u95ee\u9898\uff0c\u4ece\u6982\u5ff5\u5230\u4f7f\u7528\uff0c\u6574\u4e2a\u8fc7\u7a0b\u90fd\u5927\u5927\u5c0f\u5c0f\u6709\u4e9b\u7591\u60d1\uff0c\u7136\u800c\u6211\u8fd9\u4e9b\u7591\u60d1\u662f\u56e0\u4e3a\u6211\u5728\u67d0\u4e2a\u77e5\u8bc6\u73af\u8282\u4e0a\u51fa\u4e86\u95ee\u9898\uff0c\u5bfc\u81f4\u4e0d\u80fd\u7406\u89e3\uff0c\u5f53\u6211\u770b\u4e86\u7f51\u4e0a\u5404\u79cd\u5173\u4e8e HashMap \u7684\u6709\u5173\u535a\u5ba2\u4ee5\u53ca HashMap \u7684\u6e90\u7801\u540e\uff0c\u5927\u81f4\u662f\u7406\u89e3\u4e86\uff0c\u4f46\u662f\u6211\u53c8\u4e0d\u786e\u5b9a\u6211\u662f\u5426\u662f\u771f\u7684\u7406\u89e3\u4e86\uff0c\u51b3\u5b9a\u628a HashMap \u7684\u57fa\u672c\u5fc5\u987b\u4f1a\u7684\u77e5\u8bc6\u5168\u90e8\u68b3\u7406\u4e0b\u6765\uff0c\u52bf\u5fc5\u5f97\u641e\u5b9a\u5b83\uff01<\/p>\n<blockquote><p>\u4ece\u6700\u5f00\u59cb\u53ea\u662f\u4f1a\u4f7f\u7528\u5b83\u7684 API \u8fdb\u884c\u6570\u636e\u7684\u5b58\u53d6\uff0c\u5230\u51b3\u5b9a\u8981\u641e\u5b9a\u7591\u60d1\u3001\u641e\u61c2\u5b83\u7684\u5e95\u5c42\u539f\u7406\uff01<\/p><\/blockquote>\n<p>\u672c\u7bc7\u6587\u7ae0\uff0c\u5c06\u4ece 0 \u6d45\u5165\uff0c\u4ece\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\u8bb2\u8d77\uff0c\u7136\u540e\u518d\u8bf4 Java \u662f\u600e\u6837\u5b9e\u73b0\u54c8\u5e0c\u8868\u7684\u3002\u6574\u4e2a\u68b3\u7406\u8fc7\u7a0b\uff0c\u5c06\u901a\u8fc7\u6e90\u7801\u8fd9\u4e2a\u7b2c\u4e00\u624b\u7684\u8d44\u6599\u8fdb\u884c\u68b3\u7406\u5206\u6790\uff0c\u5438\u6536\u77e5\u8bc6\u3001\u89e3\u51b3\u7591\u95ee\uff0c\u4e00\u6b65\u4e00\u6b65\u8fdb\u884c\u68b3\u7406\uff0c\u5982\u679c\u4f60\u662f\u5bf9 HashMap \u61f5\u61f5\u61c2\u61c2\u7684\u540c\u5b66\uff0c\u90a3\u4e48\u6b22\u8fce\u8ddf\u7740\u6211\u7684\u8282\u594f\u4e00\u8d77\u6765\u68b3\u7406\uff01<\/p>\n<p><strong>\u9605\u8bfb\u5b8c\u672c\u7bc7\u6587\u7ae0\uff0c\u4f60\u5c06\u6536\u83b7<\/strong>\uff1a<\/p>\n<ul>\n<li>\u8ba4\u8bc6\u54c8\u5e0c\u8868\u3001\u54c8\u5e0c\u51b2\u7a81\u3001\u51b2\u7a81\u89e3\u51b3\u65b9\u6cd5&#8230;<\/li>\n<li>\u660e\u767d Java \u4e2d\u54c8\u5e0c\u8868\u662f\u600e\u6837\u5b9e\u73b0\u7684&#8230;<\/li>\n<li>table \u6570\u7ec4\u7684\u610f\u601d\u3001\u54c8\u5e0c\u6876\u7684\u610f\u601d\u3001Entry \u7684\u610f\u601d\u3001Node \u7684\u610f\u601d&#8230;<\/li>\n<li>1.7 \u7684 HashMap \u6e90\u7801\u5206\u6790\u6d41\u7a0b&#8230;<\/li>\n<li>\u660e\u767d\u4e3a\u4ec0\u4e48\u5df2\u7ecf\u6709\u4e86 hashCode() \u65b9\u6cd5\u4e86\uff0c\u4e3a\u4ec0\u4e48\u8fd8\u9700\u8981 hash() \u65b9\u6cd5<\/li>\n<li>\u6574\u4e2a put\u3001get\u3001\u6269\u5bb9\u7684\u8fc7\u7a0b&#8230;<\/li>\n<li>1.8 \u7684 HashMap \u4e0e 1.7 \u7684\u4e0d\u540c\u7684\u5730\u65b9&#8230;<\/li>\n<li>1.8 \u7684\u6269\u5bb9\u548c 1.7 \u7684\u6269\u5bb9\u4e0d\u4e00\u6837\u7684\u5730\u65b9&#8230;<\/li>\n<\/ul>\n<p>\u603b\u4e4b\uff0c\u6211\u76f8\u4fe1\u5c4f\u5e55\u524d\u7684\u4f60\u8bfb\u5b8c\u80af\u5b9a\u662f\u6709\u6536\u83b7\u7684\uff0c\u5f53\u7136\uff0c\u6700\u5927\u7684\u6536\u83b7\u76ee\u524d\u662f\u6211\u81ea\u5df1\u54c8\u54c8\u54c8\u3002<\/p>\n<p><strong>\u5168\u65871\u4e072000\u591a\u5b57\uff0c\u6b22\u8fce\u6162\u6162\u98df\u7528\uff01\u7531\u4e8e\u672c\u4eba\u6c34\u5e73\u6709\u9650\uff0c\u6587\u4e2d\u80af\u5b9a\u8fd8\u6709\u8bb8\u591a\u4e0d\u8db3\u4e4b\u5904\uff0c\u6b22\u8fce\u5927\u5bb6\u6307\u51fa\uff01<\/strong><\/p>\n<h2>\u5b66\u4e60 HashMap \u4e4b\u524d\uff0c\u6211\u4eec\u9700\u8981\u77e5\u9053\u4ec0\u4e48\uff1f<\/h2>\n<p>\u6211\u4eec\u77e5\u9053 HashMap \u5c31\u662f Java \u4e2d\u5bf9\u54c8\u5e0c\u8868\u8fd9\u79cd\u6570\u636e\u7ed3\u6784\u7684\u5b9e\u73b0\uff0c\u5018\u82e5\u4f60\u4e0d\u77e5\u9053\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\uff0c\u90a3\u4e48\u81ea\u7136\u5b66\u4e60 HashMap \u5c31\u4f1a\u6709\u5927\u5927\u7684\u56f0\u96be\uff0c\u5018\u82e5\u4f60\u77e5\u9053\u54c8\u5e0c\u8868\uff0c\u4f46\u4ec5\u4ec5\u662f\u61f5\u61f5\u61c2\u61c2\uff0c\u6709\u4e2a\u7b80\u5355\u4e86\u89e3\uff0c\u90a3\u81ea\u7136\u56f0\u96be\u4f1a\u964d\u4f4e\u8bb8\u591a\u3002<\/p>\n<p>\u6240\u4ee5\uff0c\u5728\u5b66\u4e60 HashMap \u4e4b\u524d\uff0c\u6211\u4eec\u81ea\u7136\u9700\u8981\u5148\u77e5\u9053\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\uff0c\u5f53\u7136\u8fd8\u9700\u8981\u77e5\u9053\u94fe\u8868\uff0c\u4e0d\u8fc7\u672c\u7bc7\u6587\u7ae0\u4ec5\u5bf9\u54c8\u5e0c\u8868\u4f5c\u51fa\u8bf4\u660e\u3002\u4e0b\u9762\u5c06\u5f00\u59cb\u8bb2\u8bb2\u54c8\u5e0c\u8868\u8fd9\u79cd\u62bd\u8c61\u7684\u6570\u636e\u7ed3\u6784\uff0c\u4e4b\u6240\u4ee5\u8bf4\u62bd\u8c61\uff0c\u662f\u56e0\u4e3a\u4e0b\u9762\u53ea\u8bf4\u54c8\u5e0c\u8868\u5e94\u8be5\u5177\u5907\u7684\u529f\u80fd\uff0c\u4f46\u662f\u4e0d\u4f1a\u7ed9\u51fa\u5177\u4f53\u5b9e\u73b0\uff0c\u6bd4\u5982\u8bf4\u6211\u4eec\u53ef\u4ee5\u7b80\u5355\u5730\u4f7f\u7528\u6570\u7ec4\u6765\u5b9e\u73b0\u54c8\u5e0c\u8868\uff0c\u662f\u5427\uff0c\u4f46\u662f Java \u4e2d\u7684\u54c8\u5e0c\u8868\u7684\u5b9e\u73b0\u5c31\u4e0d\u662f\u5355\u5355\u4e00\u4e2a\u6570\u7ec4\u5c31\u5b9e\u73b0\u4e86\u7684\u3002<\/p>\n<p>\u597d\u4e86\uff0c\u5e9f\u8bdd\u5c11\u8bf4\uff0c\u5f00\u641e\uff01<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000042929806\" alt=\"\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\uff1f\" title=\"\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\uff1f\" loading=\"lazy\"><\/p>\n<h2>\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\uff1f<\/h2>\n<p>\u54c8\u5e0c\u8868\uff08Hash Table\uff0c\u4e5f\u6709\u53e6\u4e00\u4e2a\u79f0\u547c\uff1a\u6563\u5217\u8868\uff09\u3002<\/p>\n<p>\u54c8\u5e0c\u8868\u662f\u4e00\u79cd\u53ef\u4ee5\u901a\u8fc7\u952e\uff08Key\uff09\u76f4\u63a5\u8bbf\u95ee\u5b58\u50a8\u5728\u67d0\u4e2a\u4f4d\u7f6e\u4e0a\u7684\u503c\uff08Value\uff09\u7684\u6570\u636e\u7ed3\u6784\u3002<\/p>\n<p>Hash \u88ab\u7ffb\u8bd1\u6210\u300c\u54c8\u5e0c\u300d\u3001\u300c\u6563\u5217\u300d\u3002Key \u88ab\u7ffb\u8bd1\u6210\u300c\u952e\u300d\u3001\u300c\u5173\u952e\u5b57\u300d<\/p>\n<h3>\u54c8\u5e0c\u8868\u53ef\u4ee5\u7528\u6765\u5e72\u561b\uff1f<\/h3>\n<p>\u5f88\u7b80\u5355\uff0c\u548c\u6211\u4eec\u4ee5\u524d\u5b66\u4e60\u7684\u6570\u636e\u7ed3\u6784\u4e00\u6837\uff0c\u53ef\u4ee5\u7528\u6765\u5b58\u50a8\u6570\u636e\u3002<\/p>\n<p>\u8fd9\u4e0d\u662f\u5e9f\u8bdd\u561b\uff1f\u786e\u5b9e\u662f\u5e9f\u8bdd\u3002<\/p>\n<p>\u597d\u5427\uff0c\u90a3\u4e48\u90fd\u53ef\u4ee5\u5b58\u50a8\u6570\u636e\uff0c\u4e3a\u4ec0\u4e48\u8fd8\u4f1a\u51fa\u73b0\u54c8\u5e0c\u8868\uff1f\u76f4\u63a5\u7528\u4ee5\u524d\u7684\u987a\u5e8f\u8868\u3001\u94fe\u8868\u3001\u6808\u3001\u961f\u5217\uff0c\u8fd9\u4e9b\u6570\u636e\u7ed3\u6784\u6765\u5b58\u50a8\u4e0d\u884c\u5417\uff1f\u8fd9\u4e2a\u95ee\u9898\u95ee\u5f97\u597d\uff0c\u786e\u5b9e\uff0c\u53cd\u6b63\u90fd\u662f\u5b58\u50a8\uff0c\u4e3a\u4ec0\u4e48\u8fd8\u8981\u54c8\u5e0c\u8868\uff1f<\/p>\n<p>\u8981\u56de\u7b54\u8fd9\u4e2a\u95ee\u9898\uff0c\u5c31\u5f97\u8bf4\u8bf4\u4e3a\u4ec0\u4e48\u8981\u6709\u6570\u636e\u7ed3\u6784\u4e86\uff0c\u4e4b\u6240\u4ee5\u9700\u8981\u6570\u636e\u7ed3\u6784\uff0c\u6709\u4e00\u4e2a\u76ee\u7684\u5c31\u662f\uff1a\u66f4\u6709\u6548\u5730\u8fdb\u884c\u6570\u636e\u7684\u5b58\u50a8\uff0c\u4e0d\u540c\u7684\u6570\u636e\u7ed3\u6784\u6709\u4e0d\u540c\u7684\u7279\u6027\uff0c\u987a\u5e8f\u8868\u53ef\u4ee5\u901a\u8fc7\u4e0b\u6807\u5feb\u901f\u7684\u67e5\u627e\u51fa\u6570\u636e\u3001\u94fe\u8868\u53ef\u4ee5\u4e0d\u9700\u8981\u5360\u7528\u4e00\u6574\u7247\u8fde\u7eed\u7684\u5b58\u50a8\u7a7a\u95f4\u8fdb\u884c\u5b58\u50a8\u7b49\u7b49\u3002\u54c8\u5e0c\u8868\u4e5f\u662f\u4e00\u6837\u3002<\/p>\n<h3>\u54c8\u5e0c\u8868\u5982\u4f55\u5b58\u50a8\u6570\u636e\uff1f<\/h3>\n<p>\u54c8\u5e0c\u8868\u5b58\u50a8\u6570\u636e\uff0c\u7ed9\u5b9a\u4e00\u4e2a Key\uff0c\u5b58\u50a8\u4e00\u4e2a Value\u3002\u8fd9\u91cc\u5c31\u9700\u8981\u7528\u5230\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570\uff08\u6563\u5217\u51fd\u6570\uff09\u3002<\/p>\n<p>\u4ee5\u6570\u5b66\u4e2d\u7684\u300c\u51fd\u6570\u300d\u6765\u7406\u89e3\uff0c\u5c31\u662f\u6709\u4e00\u4e2a\u51fd\u6570\u662f\u8fd9\u6837\u7684 $f(x) = y$\uff0c\u4e00\u4e2a $x$ \u901a\u8fc7\u51fd\u6570 $f$ \u6620\u5c04\u6210\u503c $y$ \u3002<\/p>\n<p>\u90a3\u4e48\u54c8\u5e0c\u51fd\u6570\u4e5f\u53ef\u4ee5\u8fd9\u6837\u7406\u89e3\uff1a$hash(key) = address$<\/p>\n<p>\u5373\u952e\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u6620\u5c04\u6210\u4e86\u4e00\u4e2a\u5730\u5740\uff0c\u8fd9\u4e2a\u5730\u5740\u53ef\u4ee5\u662f\u6570\u7ec4\u4e0b\u6807\u3001\u5185\u5b58\u5730\u5740\u7b49\u3002<\/p>\n<p>\u6240\u4ee5\u5462\uff0c\u5b58\u50a8\u5c31\u662f\uff0c\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\uff0c\u628a Key \u6620\u5c04\u5230\u67d0\u4e2a\u5730\u5740\uff0c\u7136\u540e\u5c06 Value \u5b58\u50a8\u5230\u8fd9\u4e2a\u5730\u5740\u4e0a\u3002<\/p>\n<p>\u90a3\u4e48\u5b58\u50a8\u540e\u5982\u4f55\u83b7\u53d6\uff0c\u5982\u4f55\u67e5\u627e\u5230\u8fd9\u4e2a Value \u5462\uff1f\u8fd8\u662f\u4e00\u6837\uff0c\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u83b7\u5f97 Key \u6620\u5c04\u7684\u5730\u5740\uff0c\u7136\u540e\u4ece\u8fd9\u4e2a\u5730\u5740\u53d6\u51fa Value \u3002\u7406\u60f3\u7684\u60c5\u51b5\u4e0b\uff0c\u5728\u54c8\u5e0c\u8868\u4e2d\u67e5\u627e\u6570\u636e\uff0c\u67e5\u627e\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f $O(1)$ \u3002<\/p>\n<p>\u6240\u8c13\u7684\u300c\u54c8\u5e0c\u300d\uff0c\u5c31\u662f Key \u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u5f97\u5230\u4e00\u4e2a\u51fd\u6570\u503c\uff08\u54c8\u5e0c\u503c\u3001\u54c8\u5e0c\u5730\u5740\uff09\u7684\u8fc7\u7a0b\u3002<\/p>\n<h3>\u4ec0\u4e48\u662f\u54c8\u5e0c\u51b2\u7a81\uff1f<\/h3>\n<p>\u5728\u6570\u5b66\u4e0a\uff0c\u51fd\u6570\u7684\u6620\u5c04\u53ef\u4ee5\u662f\u4e00\u5bf9\u4e00\uff0c\u4e5f\u53ef\u4ee5\u662f\u591a\u5bf9\u4e00\u7684\uff0c\u4e5f\u5c31\u662f\u8bf4\u4e00\u4e2a $x$ \u53ef\u4ee5\u6620\u5c04\u4e00\u4e2a $y$ \uff0c\u4e5f\u53ef\u4ee5\u591a\u4e2a $x$ \u6620\u5c04\u5230\u540c\u4e00\u4e2a $y$ \u4e0a\u3002<\/p>\n<p>\u54c8\u5e0c\u51fd\u6570\u4e5f\u4e00\u6837\uff0c\u5b83\u6709\u53ef\u80fd\u51fa\u73b0\u591a\u5bf9\u4e00\u7684\u60c5\u51b5\uff0c\u5373\u591a\u4e2a\u4e0d\u540c\u7684 Key\uff0c\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u5f97\u5230\u540c\u4e00\u4e2a\u5730\u5740\uff08\u54c8\u5e0c\u503c\uff09\u3002<\/p>\n<p>\u8fd9\u5c31\u51fa\u73b0\u95ee\u9898\u4e86\uff0c\u8fd9\u79cd\u60c5\u51b5\uff0c\u5c31\u79f0\u4e3a\u300c\u54c8\u5e0c\u51b2\u7a81\u300d\u3002<\/p>\n<blockquote><p>\u54c8\u5e0c\u51b2\u7a81\u5b8c\u6574\u5b9a\u4e49\uff1a\u54c8\u5e0c\u51fd\u6570\u53ef\u80fd\u628a\u4e24\u4e2a\u6216\u4e24\u4e2a\u4ee5\u4e0a\u7684\u4e0d\u540c\u5173\u952e\u5b57\u6620\u5c04\u5230\u540c\u4e00\u4e2a\u5730\u5740\uff0c\u8fd9\u79cd\u60c5\u51b5\u79f0\u4e3a\u51b2\u7a81\u3002\u53d1\u751f\u51b2\u7a81\u7684\u4e0d\u540c\u5173\u952e\u5b57\u79f0\u4e3a\u540c\u4e49\u8bcd\u3002<\/p><\/blockquote>\n<p>\u4f60\u60f3\u4e00\u4e0b\uff0c\u5982\u679c\u4e24\u4e2a\u4e0d\u540c\u7684 Key\uff0c\u6bd4\u65b9\u8bf4 Key1 \u548c Key2\uff0c\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u5f97\u5230\u540c\u4e00\u4e2a\u5730\u5740\uff0c\u90a3\u4e48\u4f60\u4e0d\u89e3\u51b3\u8fd9\u4e2a\u51b2\u7a81\uff0c\u76f4\u63a5\u8fdb\u884c\u5b58\u50a8\uff0c\u90a3\u4e48\u5c31\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<ul>\n<li>Key1 \u5148\u5b58\u50a8\uff0cKey2 \u540e\u5b58\u50a8\uff0c\u81ea\u7136\u53ea\u4fdd\u5b58\u4e86 Key2<\/li>\n<li>Key2 \u5148\u5b58\u50a8\uff0cKey1 \u540e\u5b58\u50a8\uff0c\u81ea\u7136\u53ea\u4fdd\u5b58\u4e86 Key1<\/li>\n<\/ul>\n<p>\u8fd9\u79cd\u60c5\u51b5\u662f\u6211\u4eec\u4e0d\u60f3\u770b\u5230\u7684\uff0c\u6240\u4ee5\u6211\u4eec\u5fc5\u987b\u89e3\u51b3\u51b2\u7a81\u3002<\/p>\n<h3>\u5982\u4f55\u89e3\u51b3\u51b2\u7a81\uff1f<\/h3>\n<p>\u5728\u89e3\u51b3\u51b2\u7a81\u4e4b\u524d\uff0c\u6211\u4eec\u5e94\u8be5\u5c3d\u91cf\u51cf\u5c11\u51b2\u7a81\u7684\u53d1\u751f\uff0c\u8fd9\u5c31\u9700\u8981\u8bbe\u8ba1\u5f97OK\u7684\u54c8\u5e0c\u51fd\u6570\u3002\u5f53\u7136\u51b2\u7a81\u662f\u5fc5\u7136\u7684\uff0c\u662f\u9003\u4e0d\u6389\u7684\uff0c\u5f53\u6570\u636e\u91cf\u591f\u591a\u7684\u65f6\u5019\uff0c\u5fc5\u7136\u4f1a\u53d1\u751f\u51b2\u7a81\uff0c\u6240\u4ee5\u5c31\u9700\u8981\u8bbe\u8ba1\u597d\u89e3\u51b3\u51b2\u7a81\u7684\u65b9\u6cd5\u3002<\/p>\n<p>\u54c8\u5e0c\u51fd\u6570\u7684\u8bbe\u8ba1\u6ce8\u610f\u70b9\uff1a<\/p>\n<ul>\n<li>\u51fd\u6570\u7684\u5b9a\u4e49\u57df\u5fc5\u987b\u5305\u542b\u6240\u6709\u7684 Key\uff0c\u51fd\u6570\u7684\u503c\u57df\u5fc5\u987b\u5305\u542b\u6240\u6709\u7684 Value\u3002\u5176\u4e2d\u503c\u57df\u662f\u8ddf\u54c8\u5e0c\u8868\u7684\u5927\u5c0f\u6709\u5173\u7684\u3002<\/li>\n<li>\u51fd\u6570\u8ba1\u7b97\u51fa\u6765\u7684\u5730\u5740\uff08\u54c8\u5e0c\u503c\uff09\u5e94\u8be5\u80fd\u591f\u5747\u5300\u5206\u5e03\u5728\u54c8\u5e0c\u8868\u7684\u5185\u5b58\u5730\u5740\u7a7a\u95f4\u4e0a\uff0c\u4ece\u800c\u51cf\u5c11\u51b2\u7a81\u7684\u53d1\u751f\u3002<\/li>\n<li>\u51fd\u6570\u80fd\u591f\u7b80\u5355\u5c31\u7b80\u5355\u5b9e\u73b0\uff0c\u8fd9\u6837\u8ba1\u7b97\u4f1a\u5f88\u5feb\u3002<\/li>\n<\/ul>\n<p>\u89e3\u51b3\u51b2\u7a81\u7684\u65b9\u6cd5\uff1a<\/p>\n<p>\u89e3\u51b3\u51b2\u7a81\u7684\u601d\u60f3\u5c31\u662f\u4e3a\u51b2\u7a81\u7684 Key \u627e\u4e0b\u4e00\u4e2a\u6ca1\u6709\u88ab\u5360\u7528\u7684\u5730\u5740\u3002<\/p>\n<ul>\n<li>\u5f00\u653e\u5b9a\u5740\u6cd5<\/li>\n<li>\u62c9\u94fe\u6cd5<\/li>\n<\/ul>\n<p>\u8fd9\u91cc\u5c31\u53ea\u8bf4\u8fd9\u4e2a\u62c9\u94fe\u6cd5\u3002<\/p>\n<h3>\u62c9\u94fe\u6cd5<\/h3>\n<p>\u628a\u6240\u6709\u53d1\u751f\u51b2\u7a81\u7684 Key \u5b58\u50a8\u5728\u4e00\u4e2a\u7ebf\u6027\u94fe\u8868\u4e2d\uff0c\u8fd9\u4e2a\u94fe\u8868\u7531 Key \u54c8\u5e0c\u8fc7\u540e\u5f97\u5230\u7684\u5730\u5740\uff08\u54c8\u5e0c\u5730\u5740\uff09\u552f\u4e00\u6807\u8bc6\uff0c\u8fd9\u5c31\u662f\u62c9\u94fe\u6cd5\uff0c\u9002\u7528\u4e8e\u7ecf\u5e38\u63d2\u5165\u548c\u5220\u9664\u7684\u60c5\u51b5\u3002<\/p>\n<h3>\u54c8\u5e0c\u8868\u67e5\u627e\u6548\u7387<\/h3>\n<p>\u5e73\u5747\u67e5\u627e\u957f\u5ea6\uff08ASL-Average Search Length\uff09\uff0c\u53ef\u8861\u91cf\u54c8\u5e0c\u8868\u7684\u67e5\u627e\u6548\u7387\u3002<\/p>\n<p>ASL\u4f9d\u8d56\u4e8e\u54c8\u5e0c\u8868\u7684\u300c\u88c5\u586b\u56e0\u5b50\uff08\u8d1f\u8f7d\u56e0\u5b50\uff09\u300d<\/p>\n<p>$$<br \/>\n\u88c5\u586b\u56e0\u5b50\u7684\u5b9a\u4e49\uff1a\u03b1 = \/frac{\u54c8\u5e0c\u8868\u4e2d\u7684\u5143\u7d20\u4e2a\u6570}{\u54c8\u5e0c\u8868\u7684\u957f\u5ea6}\u200b<br \/>\n$$<\/p>\n<p>\u88c5\u586b\u56e0\u5b50\u8d8a\u5927\uff0c\u90a3\u4e48\u51b2\u7a81\u7684\u53ef\u80fd\u5c31\u8d8a\u5927\uff0c\u53cd\u4e4b\u4ea6\u7136\u3002<\/p>\n<h2>1.7 \u7248 HashMap<\/h2>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000042929807\" alt=\"1.7 \u7684HashMap\" title=\"1.7 \u7684HashMap\" loading=\"lazy\"><\/p>\n<p>\u73b0\u5728\u77e5\u9053\u4ec0\u4e48\u662f\u54c8\u5e0c\u8868\u4e86\uff0c\u90a3\u4e48\u63a5\u4e0b\u6765\u5c31\u770b\u770b Java \u4e2d\u5bf9\u54c8\u5e0c\u8868\u7684\u5b9e\u73b0\u2014\u2014HashMap<\/p>\n<h3>\u518d\u6b21\u521d\u8bc6 1.7 \u7684 HashMap<\/h3>\n<p>\u6211\u4eec\u5148\u770b\u770b\u6587\u6863\u662f\u600e\u6837\u8bf4\u7684\uff0c\u540c\u65f6\u6211\u8fdb\u884c\u4e86\u5927\u4f53\u7684\u7ffb\u8bd1\u3002\uff08\u8fd9\u4e9b\u8bf4\u660e\u53ef\u4ee5\u4ece\u6e90\u7801\u7684\u5f00\u5934\u627e\u5230\uff09<\/p>\n<blockquote><p>Hash table based implementation of the <code>Map<\/code> interface. This implementation provides all of the optional map operations, and permits <code>null<\/code> values and the <code>null<\/code> key. (The <code>HashMap<\/code> class is roughly equivalent to <code>Hashtable<\/code>, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.<\/p><\/blockquote>\n<p>\u54c8\u5e0c\u8868\u662f\u901a\u8fc7\u5b9e\u73b0 Map \u63a5\u53e3\u5b9e\u73b0\u7684\uff0c\u56e0\u4e3a Map \u63a5\u53e3\u63d0\u4f9b\u4e86\u6240\u6709\u7684\u6620\u5c04\u64cd\u4f5c\uff0c<strong>\u5e76\u4e14\u5141\u8bb8\u7a7a\u503c\u548c\u7a7a\u952e<\/strong>\uff08HashMap\u8fd9\u4e2a\u7c7b\u53ef\u4ee5\u7b80\u5355\u7684\u770b\u4f5c\u662f HashTable \u7c7b\uff0c\u4e0e\u4e4b\u4e0d\u540c\u662f\uff0cHashMap \u662f<strong>\u975e\u540c\u6b65\u4e14\u5141\u8bb8\u5b58\u50a8\u7a7a\u6570\u636e\u7684<\/strong>\uff09\u3002HashMap \u8fd9\u4e2a\u7c7b<strong>\u4e0d\u4fdd\u8bc1\u6620\u5c04\u7684\u987a\u5e8f<\/strong>\uff0c\u7279\u522b\u662f\u4e0d\u4fdd\u8bc1\u8fd9\u4e2a\u987a\u5e8f\u4f1a\u968f\u7740\u65f6\u95f4\u7684\u6539\u53d8\u800c\u4fdd\u6301\u4e0d\u53d8\u3002<\/p>\n<blockquote><p>This implementation provides constant-time performance for the basic operations (<code>get<\/code> and <code>put<\/code>), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the &#8220;capacity&#8221; of the <code>HashMap<\/code> instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it&#8217;s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.<\/p><\/blockquote>\n<p>\u5f53\u54c8\u5e0c\u51fd\u6570\u6070\u5f53\u5730\u5c06\u5143\u7d20\u6620\u5c04\u5230\u54c8\u5e0c\u6876\uff08the buckets\uff09\u4e2d\uff0c\u90a3\u4e48\u5c31\u5177\u6709\u5e38\u91cf\u65f6\u95f4\u91cc\u7684\u57fa\u672c\u64cd\u4f5c\uff08get \u548c put\uff09\u6027\u80fd\u3002\u904d\u5386 HashMap \u8fd9\u4e2a\u96c6\u5408\u7684\u65f6\u5019\uff0c<strong>\u904d\u5386\u7684\u65f6\u95f4\u4e0e HashMap \u5b9e\u4f8b\u7684\u5bb9\u91cf\uff08\u54c8\u5e0c\u6876\u7684\u6570\u91cf\uff09\u52a0\u4e0a\u5b83\u7684\u5927\u5c0f\uff08Key\u548cValue\u7684\u6620\u5c04\u6570\u91cf\uff0c\u5373\u952e\u503c\u5bf9\u7684\u6570\u91cf\uff09\u6210\u6b63\u6bd4<\/strong>\uff0c\u56e0\u6b64\uff0c\u4e0d\u8981\u8bbe\u7f6e\u521d\u59cb\u7684\u5bb9\u91cf\u592a\u9ad8\uff0c\u6216\u8005\u8d1f\u8f7d\u56e0\u5b50\u592a\u4f4e\uff0c\u8fd9\u662f\u975e\u5e38\u91cd\u8981\u7684\u3002<\/p>\n<blockquote><p>An instance of <code>HashMap<\/code> has two parameters that affect its performance: <em>initial capacity<\/em> and <em>load factor<\/em>. The <em>capacity<\/em> is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The <em>load factor<\/em> is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is <em>rehashed<\/em> (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.<\/p><\/blockquote>\n<p>HashMap \u7684\u5b9e\u4f8b\uff0c\u6709\u4e24\u4e2a\u53c2\u6570\u4f1a\u5f71\u54cd\u5b83\u7684\u6027\u80fd\uff1a<strong>\u521d\u59cb\u5bb9\u91cf<\/strong>\u548c<strong>\u8d1f\u8f7d\u56e0\u5b50<\/strong>\u3002<\/p>\n<p>\u521d\u59cb\u5bb9\u91cf\u5c31\u662f\u54c8\u5e0c\u8868\u4e2d\u7684\u54c8\u5e0c\u6876\u7684\u6570\u91cf\uff0c\u6240\u8c13\u54c8\u5e0c\u6876\uff0c\u5c31\u662f\u4e00\u4e2a\u4e2a\u7684\u6570\u7ec4\u5143\u7d20\u6240\u5360\u7684\u5751\u4f4d\uff0c\u6211\u4eec\u53ef\u4ee5\u79f0\u6574\u4e2a\u6570\u7ec4\u4e3a table \u6570\u7ec4\uff0c\u7136\u540e\u91cc\u9762\u7684\u4e00\u4e2a\u4e2a\u5143\u7d20\u4f4d\u7f6e\uff08table[i]\uff09\u5c31\u662f\u54c8\u5e0c\u6876\u3002\u4f60\u7ed9\u5b9a\u4e00\u4e2a\u521d\u59cb\u5bb9\u91cf\uff0c\u90a3\u4e48\u8fd9\u4e2a\u5bb9\u91cf\u5c31\u4f1a\u5728 table \u6570\u7ec4\u521b\u5efa\u7684\u65f6\u5019\uff0c\u4f5c\u4e3a\u8fd9\u4e2a table \u6570\u7ec4\u7684\u5bb9\u91cf\uff0c\u5373\u5176\u957f\u5ea6\u3001\u5927\u5c0f\u3002<\/p>\n<p>\u8d1f\u8f7d\u56e0\u5b50\u662f\u8861\u91cf\u5728\u5f53\u524d HashMap \u81ea\u52a8\u6269\u5bb9\u524d\uff0c\u6709\u591a\u5c11\u4e2a\u54c8\u5e0c\u6876\u662f\u53ef\u4ee5\u88ab\u83b7\u53d6\u5230\u7684\u3002<strong>\u5f53\u54c8\u5e0c\u8868\u4e2d\u7684 Entry \u5bf9\u8c61\uff08\u952e\u503c\u5bf9\uff09\u7684\u6570\u91cf\u8d85\u8fc7\u4e86\u8d1f\u8f7d\u56e0\u5b50\u548c\u5f53\u524d\u5bb9\u91cf\u7684\u4e58\u79ef\u65f6\uff08load factor \u00d7 capacity\uff09\uff0c\u90a3\u4e48\u54c8\u5e0c\u8868\u5c31\u4f1a\u8fdb\u884c\u91cd\u65b0\u54c8\u5e0c\uff08rehashed\uff0c\u91cd\u6784\u6574\u4e2a\u54c8\u5e0c\u8868\uff09\uff0ctable \u6570\u7ec4\u5c31\u53d8\u4e3a\u539f\u6765\u7684\u4e24\u500d\u5927\uff0c\u5373\u6269\u5bb9\u4e24\u500d<\/strong>\u3002<\/p>\n<blockquote><p>As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the <code>HashMap<\/code> class, including <code>get<\/code> and <code>put<\/code>). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.<\/p><\/blockquote>\n<p>\u901a\u5e38\u6765\u8bf4\uff0c<strong>\u9ed8\u8ba4\u7684\u8d1f\u8f7d\u56e0\u5b50\u662f 0.75<\/strong>\uff0c\u5b83\u662f\u4e00\u4e2a\u5f88\u597d\u7684\u5e73\u8861\uff0c\u5e73\u8861\u4e86\u65f6\u95f4\u4ee5\u53ca\u7a7a\u95f4\uff0c\u8fd9\u4e2a\u503c\u8fc7\u9ad8\uff0c\u867d\u7136\u4f1a\u964d\u4f4e\u7a7a\u95f4\u7684\u5f00\u9500\uff0c\u4f46\u662f\u4f1a\u589e\u52a0\u66f4\u591a\u7684\u65f6\u95f4\u6765\u67e5\u627e\u3002\u5f53\u8bbe\u7f6e HashMap \u7684\u521d\u59cb\u5bb9\u91cf\u65f6\uff0c\u5e94\u8be5\u3002\u8003\u8651\u597d\u9884\u671f\u7684 Entry \u6570\u91cf\u4ee5\u53ca\u8d1f\u8f7d\u56e0\u5b50\uff0c\u4ee5\u6b64\u51cf\u5c11 rehash \u7684\u6b21\u6570\u3002\u5982\u679c\u54c8\u5e0c\u8868\u7684\u521d\u59cb\u5bb9\u91cf\uff08table \u6570\u7ec4\u7684\u957f\u5ea6\uff09\u5927\u4e8e Entry \u6570\u91cf\u9664\u4ee5\u8d1f\u8f7d\u56e0\u5b50\uff0c\u5219\u4e0d\u4f1a\u53d1\u751f rehash \u64cd\u4f5c\u3002<\/p>\n<blockquote><p>If many mappings are to be stored in a <code>HashMap<\/code> instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. Note that using many keys with the same <code>hashCode()<\/code> is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are <a href=\"https:\/\/link.segmentfault.com\/?enc=U7zvno02S6FgEk2v1DVTvg%3D%3D.YBdqo7FmRj7avEKbP2C5mWo31IfwdjXe7AbLMOG%2BRqLCgV3WwQ80YOjTDehX%2BlaipGV0HsSBGFUhmoHQsQrnKnh7IiWSlSmrc7%2F5hu2iltk%3D\" rel=\"nofollow\"><code>Comparable<\/code><\/a>, this class may use comparison order among keys to help break ties.<\/p><\/blockquote>\n<p>\u5982\u679c\u9700\u8981\u4f7f\u7528 HashMap \u5b9e\u4f8b\u6765\u5b58\u50a8\u8bb8\u591a\u7684\u6620\u5c04\uff0c\u90a3\u4e48\u5c31\u9700\u8981\u521b\u5efa\u4e00\u4e2a\u591f\u5927\u5bb9\u91cf\u7684 HashMap \u5b9e\u4f8b\uff0c\u8fd9\u6837\u6548\u7387\u662f\u6700\u5927\u7684\uff0c\u6bd4\u8d77\u4f60\u641e\u4e00\u4e2a\u5c0f\u5bb9\u91cf\u7684 HashMap\uff0c\u7136\u540e\u8ba9\u5b83\u81ea\u5df1 rehash\u3001table \u6570\u7ec4\u7ffb\u500d\u3002\u6ce8\u610f\uff0c\u4f7f\u7528\u8bb8\u591a\u6709\u7740\u76f8\u540c hashCode() \u7684 Key \u7684\u8bdd\uff0c\u90a3\u80af\u5b9a\u662f\u4f1a\u964d\u4f4e\u54c8\u5e0c\u8868\u7684\u6027\u80fd\u7684\uff0c\u56e0\u4e3a\u51b2\u7a81\u591a\u4e86\uff0c\u4e3a\u4e86\u964d\u4f4e\u8fd9\u79cd\u5f71\u54cd\uff0c\u5f53\u8fd9\u4e9b Key \u662f\u53ef\u6bd4\u8f83\u7684\u60c5\u51b5\u4e0b\uff0c\u90a3\u4e48\u54c8\u5e0c\u8868\u65e7\u53ef\u4ee5\u4f7f\u7528\u6bd4\u8f83\u7684\u65b9\u5f0f\u53bb\u89e3\u51b3\u3002<\/p>\n<blockquote>\n<p><strong>Note that this implementation is not synchronized.<\/strong> If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it <em>must<\/em> be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be &#8220;wrapped&#8221; using the <a href=\"https:\/\/link.segmentfault.com\/?enc=FUXRz%2Fomd%2FsA9y6yoOo7hg%3D%3D.xgtKc0a%2B3c6oBHBYgWeM9wsWYRhabKdDEQACEc2mr%2BEK9YYMRKKriF0QgYHpb0K3MldOi33tUmgAB8Jy9Xp%2FChez9F21XefpVZSfLrkFWGvDrU914roqDOOx2Pxr2vfv3sVD4WyuHEXyJF0%2BOYjwBw%3D%3D\" rel=\"nofollow\"><code>Collections.synchronizedMap<\/code><\/a>) method. This is best done at creation time, to prevent accidental unsynchronized access to the map:<\/p>\n<pre><code class=\"java\">Map m = Collections.synchronizedMap(new HashMap(...));<\/code><\/pre>\n<\/blockquote>\n<p>\u4e0a\u9762\u7684\u610f\u601d\u5c31\u662f\u8bf4\uff0c\u9700\u8981<strong>\u6ce8\u610f HashMap \u662f\u4e0d\u540c\u6b65\u7684\uff0c\u4e5f\u5c31\u662f\u975e\u7ebf\u7a0b\u5b89\u5168\u7684<\/strong>\uff0c\u5728\u591a\u7ebf\u7a0b\u5e76\u53d1\u7684\u60c5\u51b5\u4e0b\u5bf9 HashMap \u8fdb\u884c\u64cd\u4f5c\uff08\u6dfb\u52a0\u3001\u5220\u9664\u3001\u6620\u5c04\uff09\uff0c\u5c31\u4f1a\u53d1\u751f\u7ebf\u7a0b\u5b89\u5168\u95ee\u9898\uff0c\u5bfc\u81f4\u6570\u636e\u4e0d\u4e00\u81f4\uff0c\u5982\u679c\u60f3\u5728\u591a\u7ebf\u7a0b\u7684\u60c5\u51b5\u4e0b\u4f7f\u7528 HashMap\uff0c\u90a3\u4e48\u53ef\u4ee5\u4f7f\u7528 <code>Collections.synchronizedMap<\/code> \u65b9\u6cd5\u5c06\u666e\u901a\u7684 HashMap \u5305\u88c5\u6210\u540c\u6b65\u7684 HashMap\u3002\u4e0d\u8fc7\u4e0d\u63a8\u8350\u8fd9\u6837\u4f7f\u7528\uff0c\u6211\u4eec<strong>\u63a8\u8350\u4f7f\u7528 ConcurrentHashMap<\/strong>\u3002<\/p>\n<blockquote><p>The iterators returned by all of this class&#8217;s &#8220;collection view methods&#8221; are <em>fail-fast<\/em>: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator&#8217;s own <code>remove<\/code> method, the iterator will throw a <a href=\"https:\/\/link.segmentfault.com\/?enc=mkdp2OCPcnma43glRsAQOg%3D%3D.yFH4JEypPYFuCQfiPiPMZt%2FA5qiSnGRvb3NVSSCOJeNONMuvWaETfG3Cy%2FHinILisY3GzWFr%2FGzzP92fTiUdYsakUHazy93zl0toVgXdDyKnruuwGhVHRLB75zDNsz4c\" rel=\"nofollow\"><code>ConcurrentModificationException<\/code><\/a>. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.<\/p><\/blockquote>\n<p><strong>\u8fed\u4ee3\u5668\u5feb\u901f\u5931\u8d25\uff08fail-fast\uff09<\/strong>\uff1a\u5982\u679c Map \u5728\u8fed\u4ee3\u5668\u8fdb\u884c\u8fed\u4ee3\u7684\u65f6\u5019\uff0cMap \u4e2d\u7684\u6570\u636e\u88ab\u4fee\u6539\u4e86\uff0c\u90a3\u4e48\u8fed\u4ee3\u5668\u5c31\u4f1a\u629b\u51fa\u4e00\u4e2a\u5f02\u5e38\uff1a<code>ConcurrentModificationException<\/code>\u3002\u56e0\u4e3a\u6015\u6709\u4e0d\u786e\u5b9a\u7684\u884c\u4e3a\u98ce\u9669\uff0c\u4e3b\u8981\u6765\u8bf4\u5c31\u662f\u6015\u6570\u636e\u4e0d\u4e00\u81f4\uff0c\u6015\u7ebf\u7a0b\u4e0d\u5b89\u5168\u3002<\/p>\n<hr>\n<p>\u770b\u5b8c\u4e86\u6587\u6863\u7684\u8bf4\u660e\uff0c\u73b0\u5728\u53ef\u4ee5\u77e5\u9053\uff0cHashMap \u5927\u6982\u6709\u8fd9\u6837\u7684\u4e1c\u897f<\/p>\n<ul>\n<li>\u54c8\u5e0c\u8868\u7684\u952e\u503c\u5bf9\uff08Entry\uff09\u662f\u5b58\u50a8\u5728\u4e00\u4e2a\u540d\u4e3a table \u7684\u6570\u7ec4\u4e2d\u7684\u3002Entry \u7684\u8bdd\uff0c\u662f\u628a Key\u3001Value\u3001hash \u503c\uff0c\u5c01\u88c5\u4e3a Entry \u5bf9\u8c61\u3002<\/li>\n<li>table \u6570\u7ec4\u91cc\u9762\u7684\u4e00\u4e2a\u4e2a\u5143\u7d20\u4f4d\u7f6e\uff08table[i]\uff09\u5c31\u662f\u54c8\u5e0c\u6876\u3002<\/li>\n<li>\u54c8\u5e0c\u6876\u5b58\u50a8\u7684\u5c31\u662f Entry\uff0c\u4e5f\u5c31\u662f\u8bf4\u4e00\u4e2a\u4e2a\u7684\u54c8\u5e0c\u6876\uff0c\u5b58\u50a8\u7740\u4e00\u4e2a\u4e2a\u7684 Entry \u5bf9\u8c61\u3002<\/li>\n<li>\u54c8\u5e0c\u8868\u7684\u521d\u59cb\u5bb9\u91cf\u6307\u7684\u5c31\u662f table \u6570\u7ec4\u7684\u957f\u5ea6\u3002<\/li>\n<li><strong>\u54c8\u5e0c\u8868\u7684\u5bb9\u91cf<\/strong>\u6307\u7684\u662f table \u6570\u7ec4\u7684\u957f\u5ea6\uff1b<strong>\u54c8\u5e0c\u8868\u7684\u5927\u5c0f<\/strong>\u6307\u7684\u662f Key \u548c Value \u6620\u5c04\u7684\u6570\u91cf\uff0c\u5373\u952e\u503c\u5bf9\u7684\u6570\u91cf\u3002\u8fd9\u4e2a\u5f88\u91cd\u8981\uff0c\u9700\u8981\u641e\u6e05\u695a\u54c8\u5e0c\u8868\u7684\u300c\u5bb9\u91cf\u300d\u548c\u300c\u5bb9\u91cf\u300d\uff0c\u522b\u641e\u6df7\u4e86\u3002<\/li>\n<li>\u5f53 <code>Entry \u5bf9\u8c61\u7684\u6570\u91cf &gt; load factor \u00d7 capacity<\/code> \u65f6\uff0c\u5c31\u4f1a\u81ea\u52a8\u6269\u5bb9\uff0ctable \u6570\u7ec4\u6269\u5bb9\u4e3a\u539f\u6765\u7684\u4e24\u500d\u3002<\/li>\n<li>\u54c8\u5e0c\u8868\u662f\u7ebf\u7a0b\u4e0d\u5b89\u5168\u7684\u3002<\/li>\n<\/ul>\n<p>\u770b\u5230\u8fd9\u91cc\uff0c\u53ef\u80fd\u8fd8\u662f\u6709\u4e9b\u62bd\u8c61\uff0c\u6ca1\u4e8b\uff0c\u63a5\u4e0b\u6765\u6211\u4eec\u770b\u4e0b\u6e90\u7801\u3002<\/p>\n<h3>HashMap \u4e2d\u7684\u6210\u5458\u53d8\u91cf<\/h3>\n<p>\u9996\u5148\u5148\u770b\u770b HashMap \u5b9a\u4e49\u7684\u6210\u5458\u53d8\u91cf\uff1a<\/p>\n<pre><code class=\"java\">public class HashMap&lt;K,V&gt;\n    extends AbstractMap&lt;K,V&gt;\n    implements Map&lt;K,V&gt;, Cloneable, Serializable\n{\n    \/**\n     * The default initial capacity - MUST be a power of two.\n     * \u9ed8\u8ba4\u7684\u521d\u59cb\u5316\u5bb9\u91cf\u5927\u5c0f\u4e3a16\uff0c\u8fd9\u4e2a\u5927\u5c0f\u5fc5\u987b\u4e3a2\u6b21\u5e42\n     *\/\n    static final int DEFAULT_INITIAL_CAPACITY = 16;\n    \n    \/**\n     * The maximum capacity, used if a higher value is implicitly specified\n     * by either of the constructors with arguments.\n     * MUST be a power of two &lt;= 1&lt;&lt;30.\n     * \u6700\u5927\u7684\u5bb9\u91cf\uff0c\u5982\u679c\u4efb\u610f\u5e26\u53c2\u6784\u9020\u51fd\u6570\u4f20\u5165\u7684\u503c\u5927\u4e8e\u8fd9\u4e2a\u6700\u5927\u5bb9\u91cf\uff0c\u5c31\u4f7f\u7528\u8fd9\u4e2a\u6700\u5927\u5bb9\u91cf\n     * 1 \u5de6\u79fb 30\u4f4d\uff0c\u5373 2\u768430\u6b21\u65b9\n     *\/\n    static final int MAXIMUM_CAPACITY = 1 &lt;&lt; 30;\n    \n    \/**\n     * The load factor used when none specified in constructor.\n     * \u9ed8\u8ba4\u8d1f\u8f7d\u56e0\u5b50 0.75\n     *\/\n    static final float DEFAULT_LOAD_FACTOR = 0.75f;\n    \n    \/**\n     * The table, resized as necessary. Length MUST Always be a power of two.\n     * table \u6570\u7ec4\uff0c\u5fc5\u8981\u65f6\u5c31\u53ef\u4ee5\u91cd\u7f6e\u5927\u5c0f\uff0c\u957f\u5ea6\u5fc5\u987b\u603b\u662f2\u6b21\u5e42\uff0c\u6ce8\u610f\u8fd9\u91cc\u7684\u6570\u7ec4\u7c7b\u578b\u7684 Entry\n     * Entry \u662f\u4e00\u4e2a\u5185\u90e8\u7c7b\uff0c\u4e0b\u9762\u5c31\u53ef\u4ee5\u770b\u5230\u4e86\n     *\/\n    transient Entry[] table;\n    ... \n    \/**\n     * Entry \u7c7b\uff0c\u4e3b\u8981\u4f5c\u4e3a\u4e00\u4e2a\u5b58\u50a8 Key \u548c Value \u7684\u8282\u70b9\uff0c\u540c\u65f6\u4fdd\u5b58\u5f53\u524d\u7684\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u8ba1\u7b97\u51fa\u6765\u7684 hash\n     * next \u6307\u9488\uff0c\u4e3b\u8981\u7528\u4e8e\u53d1\u751f\u51b2\u7a81\u65f6\uff0c\u4f7f\u7528\u62c9\u94fe\u6cd5\u89e3\u51b3\u51b2\u7a81\uff0c\u6307\u5411\u94fe\u8868\u4e0b\u4e00\u4e2a Entry \u8282\u70b9\u7684\n     *\/\n    static class Entry&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; {\n        final K key;     \/\/ \u952e\n        V value;         \/\/ \u503c\n        Entry&lt;K,V&gt; next; \/\/ \u6307\u5411\u4e0b\u4e00\u4e2a\u8282\u70b9 \uff0c\u4ece\u800c\u5f62\u6210\u89e3\u51b3\u51b2\u7a81\u7684\u94fe\u8868\n        final int hash;  \/\/ \u54c8\u5e0c\u503c\n        ...\n    }\n    \n    \/**\n     * The number of key-value mappings contained in this map.\n     * size \u4ee3\u8868\u7684\u5c31\u662f\u5f53\u524d\u5b58\u50a8\u5728 map \u4e2d\u7684 Key-Value \u6620\u5c04\u7684\u6570\u91cf\uff0c\u5373 Entry \u7684\u6570\u91cf\n     *\/\n    transient int size;\n    \n    \/**\n     * The next size value at which to resize (capacity * load factor).\n     * @serial\n     * table \u91cd\u7f6e\u5927\u5c0f\u7684\u9608\u503c\uff0c\u8fd9\u4e2a\u9608\u503c\u5c31\u662f\u4e4b\u524d\u8bf4\u7684 load factor * capacity\n     *\/\n    int threshold;\n    \n    \/**\n     * The load factor for the hash table.\n     *\n     * @serial\n     * \u8d1f\u8f7d\u56e0\u5b50\n     *\/\n    final float loadFactor;\n    \n     \/**\n     * The number of times this HashMap has been structurally modified\n     * Structural modifications are those that change the number of mappings in\n     * the HashMap or otherwise modify its internal structure (e.g.,\n     * rehash).  This field is used to make iterators on Collection-views of\n     * the HashMap fail-fast.  (See ConcurrentModificationException).\n     * \u8fd9\u4e2a\u53d8\u91cf\u4e3b\u8981\u4e0e fail-fast \u5feb\u901f\u5931\u8d25 \u6709\u5173\uff0c\u540e\u9762\u518d\u8bf4\uff0c\u5148\u7559\u4e2a\u5370\u8c61\u3002\n     *\/\n    transient int modCount;\n    ...\n}<\/code><\/pre>\n<p>\u6240\u4ee5\u8bf4\uff0c\u5728 JDK 1.7 \u53ca\u4ee5\u524d\uff0cHashMap \u7684\u5e95\u5c42\u6570\u636e\u7ed3\u6784\u662f\u300c\u6570\u7ec4+\u94fe\u8868\u300d\uff0c\u8fd9\u91cc\u7684\u6570\u7ec4\u6307\u7684\u5c31\u662f Entry \u7c7b\u578b\u7684 table \u6570\u7ec4\uff0c\u540c\u65f6\u4f7f\u7528 Entry \u4f5c\u4e3a\u94fe\u8868\u7684\u8282\u70b9\u3002<\/p>\n<p>\u4e0a\u56fe\u8bf4\u8bdd\uff01<\/p>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000042929808\" alt=\"hashmap 1.7 \u793a\u610f\u56fe\" title=\"hashmap 1.7 \u793a\u610f\u56fe\" loading=\"lazy\"><\/p>\n<h3>4 \u4e2a\u6784\u9020\u65b9\u6cd5<\/h3>\n<p>\u63a5\u4e0b\u6765\u770b\u770b\u6784\u9020\u65b9\u6cd5\uff0cHashMap \u4e2d\u6709 4 \u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u6309\u6e90\u7801\u4e2d\u7684\u51fa\u73b0\u987a\u5e8f\u5982\u4e0b\uff1a<\/p>\n<ul>\n<li><code>public HashMap(int initialCapacity, float loadFactor) <\/code><\/li>\n<li><code>public HashMap(int initialCapacity)<\/code><\/li>\n<li><code>public HashMap()<\/code><\/li>\n<li><code>public HashMap(Map&lt;? extends K, ? extends V&gt; m)<\/code><\/li>\n<\/ul>\n<p>\u7b2c\u4e00\u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u4e24\u4e2a\u53c2\u6570\uff0c\u4e00\u4e2a\u521d\u59cb\u5bb9\u91cf\uff0c\u53e6\u4e00\u4e2a\u8d1f\u8f7d\u56e0\u5b50\uff0c\u5f88\u660e\u663e\uff0c\u5c31\u662f\u6784\u9020\u4e00\u4e2a\u6709\u7740\u786e\u5207\u521d\u59cb\u5bb9\u91cf\u548c\u786e\u5207\u8d1f\u8f7d\u56e0\u5b50\u7684 HashMap \u5b9e\u4f8b\uff0c\u6e90\u7801\u662f\u8fd9\u6837\u7684\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Constructs an empty &lt;tt&gt;HashMap&lt;\/tt&gt; with the specified initial\n     * capacity and load factor.\n     * \n     * @param  initialCapacity the initial capacity\n     * @param  loadFactor      the load factor\n     * @throws IllegalArgumentException if the initial capacity is negative\n     *         or the load factor is nonpositive\n     *\/\n    public HashMap(int initialCapacity, float loadFactor) {\n        \/\/ \u4e0b\u97623\u4e2aif\uff0c\u662f\u4fdd\u8bc1\u4ee3\u7801\u7684\u5065\u58ee\u6027\uff0c\u4e0d\u662f\u4e3b\u8981\u5185\u5bb9\n        \/\/ \u521d\u59cb\u5bb9\u91cf\u5c0f\u4e8e0\uff0c\u90a3\u4e48\u629b\u51fa\u975e\u6cd5\u53c2\u6570\u5f02\u5e38\n        if (initialCapacity &lt; 0)\n            throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; +\n                                               initialCapacity);\n        \/\/ \u521d\u59cb\u5bb9\u91cf\u5927\u4e8e\u6700\u5927\u5bb9\u91cf\uff082^30\uff09\uff0c\u76f4\u63a5\u5c062^30\u4f5c\u4e3a\u521d\u59cb\u5bb9\u91cf\n        if (initialCapacity &gt; MAXIMUM_CAPACITY)\n            initialCapacity = MAXIMUM_CAPACITY;\n        \/\/ \u5982\u679c\u8d1f\u8f7d\u56e0\u5b50\u5c0f\u4e8e\u7b49\u4e8e0\uff0c\u6216\u8005\u8d1f\u8f7d\u56e0\u5b50\u6709\u95ee\u9898\uff0c\u629b\u51fa\u5f02\u5e38\n        if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))\n            throw new IllegalArgumentException(&quot;Illegal load factor: &quot; +\n                                               loadFactor);\n        \/\/ \u4e3b\u8981\u5185\u5bb9\u5728\u8fd9\u91cc\n        \/\/ Find a power of 2 &gt;= initialCapacity\n        \/\/ \u627e\u5230\u4e00\u4e2a\u4e8c\u6b21\u5e42\u7684\u6570\uff0c\u5982\u679c\u5f53\u524d\u8f93\u5165\u7684\u521d\u59cb\u5bb9\u91cf\u521a\u597d\u7684\u4e8c\u6b21\u5e42\uff0c\u5c31\u4e0d\u7528\u627e\u4e86\n        int capacity = 1;\n        while (capacity &lt; initialCapacity)\n            capacity &lt;&lt;= 1;\n        \n        this.loadFactor = loadFactor;                \/\/ \u521d\u59cb\u5316\uff0c\u8d4b\u503c\n        threshold = (int)(capacity * loadFactor);    \/\/ \u81ea\u52a8\u6269\u5bb9\u7684\u9608\u503c\n        table = new Entry[capacity];                \/\/ \u521b\u5efa\u5927\u5c0f\u4e3acapacity\u7684Entry\u6570\u7ec4\n        init();    \/\/ \u4e00\u4e2a\u7a7a\u65b9\u6cd5\uff0c\u6709\u4ec0\u4e48\u7528\uff1f\u8fd9\u4e2a\u5148\u4e0d\u7ba1\uff0c\u4e4b\u540e\u518d\u8bf4\uff0c\u76ee\u524d\u77e5\u9053\u4e0a\u9762\u7684\u5c31\u8db3\u591f\u4e86\u3002\n    }<\/code><\/pre>\n<p>\u5b9e\u9645\u4e0a\uff0c\u641e\u5b9a\u4e0a\u9762\u7b2c\u4e00\u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u540e\u9762\u7684\u6784\u9020\u65b9\u6cd5\u5c31\u8f7b\u800c\u6613\u4e3e\u4e86\u3002\u7b2c\u4e8c\u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u53ea\u662f\u8f93\u5165\u4e86\u4e00\u4e2a\u521d\u59cb\u5316\u5bb9\u91cf\uff0c\u76f4\u63a5\u8c03\u7528\u7b2c\u4e00\u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u800c\u8d1f\u8f7d\u56e0\u5b50\u5c31\u662f\u9ed8\u8ba4\u7684 0.75\u3002<\/p>\n<pre><code class=\"java\">    public HashMap(int initialCapacity) {\n        this(initialCapacity, DEFAULT_LOAD_FACTOR);\n    }<\/code><\/pre>\n<p>\u7b2c\u4e09\u4e2a\u65e0\u53c2\u7684\u6784\u9020\u65b9\u6cd5\uff0c\u76f4\u63a5\u4f7f\u7528\u9ed8\u8ba4 0.75 \u7684\u8d1f\u8f7d\u56e0\u5b50\u4ee5\u53ca\u9ed8\u8ba4\u7684\u521d\u59cb\u5316\u5bb9\u91cf\u4e3a 16 \u7684 Entry \u7c7b\u578b\u7684 table \u6570\u7ec4\u3002\u7136\u540e\u9ed8\u8ba4\u7684\u9608\u503c\u5c31\u662f 0.75 \u00d7 16 = 12\uff0c\u5373\u5f53 Entry \u4e2a\u6570\u8d85\u8fc7 12\uff0c\u5b58\u50a8\u7b2c 13 \u4e2a Entry \u7684\u65f6\u5019\uff0c\u5c31\u4f1a\u8fdb\u884c resize\u3001rehash\u3002<\/p>\n<pre><code class=\"java\">    public HashMap() {\n        this.loadFactor = DEFAULT_LOAD_FACTOR;\n        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);\n        table = new Entry[DEFAULT_INITIAL_CAPACITY];\n        init();\n    }<\/code><\/pre>\n<p>\u7b2c\u56db\u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u63a5\u6536\u4e00\u4e2a\u786e\u5207\u7684 Map\uff0c\u7528 HashMap \u5305\u88c5\u8fd9\u4e2a\u786e\u5207\u7684 Map<\/p>\n<pre><code class=\"java\">    \/**\n     * Constructs a new &lt;tt&gt;HashMap&lt;\/tt&gt; with the same mappings as the\n     * specified &lt;tt&gt;Map&lt;\/tt&gt;.  The &lt;tt&gt;HashMap&lt;\/tt&gt; is created with\n     * default load factor (0.75) and an initial capacity sufficient to\n     * hold the mappings in the specified &lt;tt&gt;Map&lt;\/tt&gt;.\n     *\n     * @param   m the map whose mappings are to be placed in this map\n     * @throws  NullPointerException if the specified map is null\n     *\/\n    public HashMap(Map&lt;? extends K, ? extends V&gt; m) {\n        this(Math.max((int) (m.size() \/ DEFAULT_LOAD_FACTOR) + 1,\n                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);\n        putAllForCreate(m);\n    }<\/code><\/pre>\n<p>\u4ee5\u4e0a\uff0c\u5c31\u662f HashMap \u7684 4 \u4e2a\u6784\u9020\u65b9\u6cd5\uff0c\u770b\u6765\u8fd8\u662f\u53ef\u4ee5\u641e\u5b9a\u7684\u561b\uff01<\/p>\n<h3>\u6270\u52a8\/\u54c8\u5e0c\u51fd\u6570<\/h3>\n<p>\u63a5\u7740\u770b\u6e90\u7801\uff0c\u53d1\u73b0\u5c31\u662f hash() \u4e86\u3002<strong>\u6211\u4eec\u77e5\u9053\uff0c\u5728 Object \u4e2d\uff0c\u5df2\u7ecf\u6709\u4e00\u4e2a hashCode() \u65b9\u6cd5\u4e86\uff0c\u8fd9\u4e2a hashCode() \u53ef\u4ee5\u8bf4\u662f\u4e00\u4e2a\u54c8\u5e0c\u51fd\u6570\uff0c\u90a3\u4e3a\u4ec0\u4e48\u5728 HashMap \u4e2d\uff0c\u53c8\u8fd8\u9700\u8981\u53e6\u4e00\u4e2a hash() \u65b9\u6cd5\u5462\uff1f<\/strong><\/p>\n<p>\u5728\u6e90\u7801\u6ce8\u91ca\u91cc\u5df2\u7ecf\u8bf4\u660e\u4e86\uff0c\u5c31\u662f\u62b5\u5fa1\u4f4e\u8d28\u91cf\u7684\u54c8\u5e0c\u51fd\u6570\uff0c\u8ba9 hashCode() \u8ba1\u7b97\u51fa\u6765\u7684\u54c8\u5e0c\u7801\u518d\u6b21\u6270\u52a8\uff08\u518d\u6b21\u54c8\u5e0c\uff09\uff0c\u8fd9\u662f\u975e\u5e38\u91cd\u8981\u7684\uff0c\u56e0\u4e3a HashMap \u4f7f\u7528\u4e8c\u6b21\u5e42\u957f\u5ea6\u7684 table \u6570\u7ec4\uff0c\u4e0d\u8fdb\u884c\u518d\u6b21\u54c8\u5e0c\u7684\u8bdd\uff0c\u5c31\u4f1a\u9047\u5230 hashCode \u5728\u8f83\u4f4e\u4f4d\u6ca1\u6709\u5dee\u5f02\u7684\u51b2\u7a81\uff0c\u6240\u4ee5\u9700\u8981\u4f7f\u7528\u8fd9\u4e2a hash() \u65b9\u6cd5\u3002\u603b\u800c\u8a00\u4e4b\uff0c\u5c31\u662f\u518d\u6b21\u6270\u52a8\uff0c\u964d\u4f4e\u51b2\u7a81\u53d1\u751f\u7684\u6982\u7387\u3002<\/p>\n<p><strong>\u6709\u5c0f\u4f19\u4f34\u53ef\u80fd\u6709\u7591\u60d1\uff0c\u300c\u4f4e\u8d28\u91cf\u7684\u54c8\u5e0c\u51fd\u6570\u300d\uff1fhashCode() \u4e0d\u662f Java \u56fa\u5b9a\u5b9e\u73b0\u597d\u7684\u5417\uff1f\u4e3a\u4ec0\u4e48\u6015\u6709\u4f4e\u8d28\u91cf\u7684 hashCode() ?<\/strong><\/p>\n<p>\u8fd9\u4e2a\u95ee\u9898\u95ee\u5f97\u597d\uff0c\u5b9e\u9645\u4e0a\uff0c\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0 hashCode() \u662f\u4e00\u4e2a\u672c\u5730\u65b9\u6cd5\uff08Native Method\uff09<\/p>\n<pre><code class=\"java\">public native int hashCode();<\/code><\/pre>\n<p>\u8fd9\u5c31\u610f\u5473\u7740\uff0chashCode() \u5e76\u4e0d\u662f\u7531 Java \u8bed\u8a00\u5b9e\u73b0\u7684\uff0c\u800c\u662f\u7531 C \u6216 C++ \u8fd9\u4e9b\u975e Java \u8bed\u8a00\u662f\u5b9e\u73b0\u7684\u3002<strong>\u540c\u4e00\u4e2a native \u65b9\u6cd5\uff0c\u5982\u679c\u7528\u4e0d\u540c\u7684 JVM \u53bb\u8c03\u7528\uff0c\u90a3\u4e48\u8fd0\u884c\u6548\u7387\u53ef\u80fd\u662f\u4e0d\u4e00\u6837\u7684\uff0c\u56e0\u4e3a\u4e0d\u540c\u7684 JVM \u5bf9\u4e8e\u67d0\u4e2a native \u65b9\u6cd5\u90fd\u6709\u81ea\u5df1\u7684\u5b9e\u73b0\uff0c\u6240\u4ee5\u624d\u9700\u8981\u6270\u52a8\u51fd\u6570\u8fdb\u884c\u518d\u6b21\u54c8\u5e0c<\/strong>\u3002<\/p>\n<p>hash() \u65b9\u6cd5\uff08\u6270\u52a8\u51fd\u6570\uff09\u4f20\u5165\u7684\u53c2\u6570\u662f Key \u7684 hashCode() \u8ba1\u7b97\u51fa\u6765\u7684\u54c8\u5e0c\u7801\uff08\u503c\uff09\uff0c\u5c06\u8fd9\u4e2a\u54c8\u5e0c\u7801\u7ecf\u8fc7 hash() \u65b9\u6cd5\u5f97\u5230\u6700\u7ec8\u7684 hash \u503c\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Applies a supplemental hash function to a given hashCode, which\n     * defends against poor quality hash functions.  This is critical\n     * because HashMap uses power-of-two length hash tables, that\n     * otherwise encounter collisions for hashCodes that do not differ\n     * in lower bits. Note: Null keys always map to hash 0, thus index 0.\n     *\/\n    static int hash(int h) {\n        \/\/ This function ensures that hashCodes that differ only by\n        \/\/ constant multiples at each bit position have a bounded\n        \/\/ number of collisions (approximately 8 at default load factor).\n        h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);\n        return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);\n    }<\/code><\/pre>\n<h3>\u7559\u4e2a\u5370\u8c61-indexFor<\/h3>\n<p><code>indexFor()<\/code> \u65b9\u6cd5\uff0c<code>\u54c8\u5e0c\u503c<\/code>\u548c<code>\u6570\u7ec4\u957f\u5ea6\u51cf\u4e00<\/code>\u8fdb\u884c<code>\u4e0e\u8fd0\u7b97<\/code>\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Returns index for hash code h.\n     *\/\n    static int indexFor(int h, int length) {\n        return h &amp; (length-1);\n    }<\/code><\/pre>\n<p>\u83b7\u53d6\u54c8\u5e0c\u8868\u7684\u5927\u5c0f\u3001\u5224\u65ad\u54c8\u5e0c\u8868\u662f\u5426\u4e3a\u7a7a<\/p>\n<pre><code class=\"java\">    \/**\n     * Returns the number of key-value mappings in this map.\n     *\n     * @return the number of key-value mappings in this map\n     *\/\n    public int size() {\n        return size;\n    }\n\n    \/**\n     * Returns &lt;tt&gt;true&lt;\/tt&gt; if this map contains no key-value mappings.\n     *\n     * @return &lt;tt&gt;true&lt;\/tt&gt; if this map contains no key-value mappings\n     *\/\n    public boolean isEmpty() {\n        return size == 0;\n    }<\/code><\/pre>\n<h3>put \u7684\u8fc7\u7a0b<\/h3>\n<p>HashMap \u7684 put() \u65b9\u6cd5\uff1a<\/p>\n<ul>\n<li><code>public V put(K key, V value)<\/code><\/li>\n<\/ul>\n<p>\u8fd9\u4e2a\u65b9\u6cd5\u5c31\u662f\u5c06\u67d0\u4e2a\u786e\u5207\u7684 Key \u4e0e \u67d0\u4e2a\u786e\u5207\u7684 Value \u8054\u7cfb\u8d77\u6765\uff0c\u5b58\u50a8\u5230\u54c8\u5e0c\u8868\u4e2d\uff0c\u8fd9\u6837\u5b83\u4eec\u4e4b\u95f4\u5c31\u5efa\u7acb\u8d77\u6620\u5c04\u7684\u5173\u7cfb\u4e86\u3002<\/p>\n<p>\u5982\u679c\u5f53\u524d\u54c8\u5e0c\u8868\u4e2d\u6709\u4e86\u8fd9\u4e2a Key\uff0c\u90a3\u4e48\u5c31\u7528\u65b0\u7684 Value \u8986\u76d6\u6389\u65e7\u7684 Value\u3002<\/p>\n<p>Key \u548c Value \u53ef\u4ee5\u662f null\uff0c\u53ea\u80fd\u6709\u4e00\u4e2a Key \u4e3a null\uff0c\u53ef\u4ee5\u6709\u591a\u4e2a Value \u4e3a null\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Associates the specified value with the specified key in this map.\n     * If the map previously contained a mapping for the key, the old\n     * value is replaced.\n     *\n     * @param key key with which the specified value is to be associated\n     * @param value value to be associated with the specified key\n     * @return the previous value associated with &lt;tt&gt;key&lt;\/tt&gt;, or\n     *         &lt;tt&gt;null&lt;\/tt&gt; if there was no mapping for &lt;tt&gt;key&lt;\/tt&gt;.\n     *         (A &lt;tt&gt;null&lt;\/tt&gt; return can also indicate that the map\n     *         previously associated &lt;tt&gt;null&lt;\/tt&gt; with &lt;tt&gt;key&lt;\/tt&gt;.)\n     *\/\n    public V put(K key, V value) {\n        if (key == null)\n            return putForNullKey(value);\n        \/\/ \u5c06 Key \u7684 hashCode \u518d\u6b21\u54c8\u5e0c\u5f97\u5230\u6700\u7ec8\u7684 hash \u503c\n        int hash = hash(key.hashCode());\n        \/\/ \u5c06 hash \u503c\u4e0e\u6570\u7ec4\u957f\u5ea6\u51cf\u4e00\u8fdb\u884c\u4e0e\u8fd0\u7b97\uff0c\u8ba1\u7b97\u6700\u7ec8\u7684\u54c8\u5e0c\u5730\u5740\uff08\u5373\u6570\u7ec4\u4e0b\u6807\uff09\n        int i = indexFor(hash, table.length);\n        \/\/ for \u5faa\u73af\u662f\u904d\u5386\u8fd9\u4e2a\u54c8\u5e0c\u6876\u4e0a\u7684\u94fe\u8868\uff0c\u5982\u679c\u6709\u94fe\u8868\u7684\u8bdd\uff0c\u5373 e.next != null \u8bf4\u660e\u6709\u94fe\u8868\u4e86\n        for (Entry&lt;K,V&gt; e = table[i]; e != null; e = e.next) {\n            Object k;\n            \/\/ \u5982\u679c\u8be5\u4f4d\u7f6e\u7684 hash \u503c\u548c\u5f53\u524d\u8981\u5b58\u50a8\u7684 Key \u7684 hash \u503c\u4e00\u6837\uff0c\u8bf4\u660e\u53ef\u80fd\u662f\u540c\u4e00 Key \u6216\u4e0d\u540c\u7684 Key\n            \/\/ \u540c\u4e00 Key \u7684\u8bdd\u5c31\u53ef\u4ee5\u8986\u76d6\uff0c\u4e0d\u540c Key \u7684\u8bdd\u5c31\u9700\u8981\u89e3\u51b3\u8fd9\u4e2a\u51b2\u7a81\n            \/\/ \u5148\u662f\u6bd4\u8f83\u5185\u5b58\u5730\u5740\u662f\u5426\u76f8\u7b49\uff0c\u5982\u679c\u5185\u5b58\u5730\u5740\u4e0d\u76f8\u7b49\uff0c\u518d\u53bb\u4f7f\u7528 equals \u65b9\u6cd5\u5224\u65ad\u4e24\u4e2a Key \u662f\u4e0d\u662f\u540c\u4e00\u4e2a\u3002\n            \/\/ \u5982\u679c\u5185\u5b58\u5730\u5740\u76f8\u7b49\uff0c\u8bf4\u660e\u662f\u540c\u4e00\u4e2a Key \u4e86\uff0c\u4e0d\u5fc5\u4f7f\u7528 equals \u4e86\n            \/\/ equals \u5224\u65ad\u662f\u76f8\u7b49\u7684\u8bdd\uff0c\u90a3\u4e48\u80af\u5b9a\u662f\u540c\u4e00\u4e2a Key \u4e86\uff0c\u56e0\u4e3a hashCode \u76f8\u7b49\u4e0d\u80fd\u8bf4\u660e\u4e24\u4e2a\u5bf9\u8c61\u76f8\u7b49\n            \/\/ \u4f46\u4e24\u4e2a\u5bf9\u8c61\u76f8\u7b49\u7684\u8bdd\uff0c\u90a3\u4e48 equals \u4e00\u5b9a\u76f8\u7b49\u3002\n            if (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) {\n                \/\/ \u8fdb\u5165\u8fd9\u91cc\uff0c\u8bf4\u660e\u662f\u540c\u4e00\u4e2a Key\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u7528\u65b0 Value \u8986\u76d6\u6389\u65e7 Value \u4e86\n                V oldValue = e.value;\n                e.value = value;\n                e.recordAccess(this);    \/\/ \u8fd9\u4e2a\u5148\u4e0d\u7ba1\n                return oldValue;\n            }\n        }\n        \/\/ \u8d70\u5230\u8fd9\u91cc\uff0c\u8bf4\u660e Map \u4e2d\u6ca1\u6709\u8fd9\u4e2a Key\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u6dfb\u52a0\u8fd9\u4e2a Key-Value \u7684\u6620\u5c04\u4e86\n        modCount++;    \/\/ \u8bf4\u660e\u6570\u636e\u53d1\u751f\u4e86\u6539\u53d8\uff0cfail-fast \u4f1a\u7528\u5230\n        addEntry(hash, key, value, i);    \/\/ \u6dfb\u52a0\u8fd9\u4e2aEntry\n        return null;\n    }\n\n    \/**\n     * Offloaded version of put for null keys\n     *\/\n    private V putForNullKey(V value) {\n        \/\/ \u5224\u65ad\u6709\u6ca1\u6709\u8fd9\u4e2a null Key\uff0c\u6709\u5c31\u65b0\u7684 Value \u8986\u76d6\u65e7\u7684 Value\n        for (Entry&lt;K,V&gt; e = table[0]; e != null; e = e.next) {\n            if (e.key == null) {\n                V oldValue = e.value;\n                e.value = value;\n                e.recordAccess(this);\n                return oldValue;\n            }\n        }\n        \/\/ \u6ca1\u6709\uff0c\u90a3\u4e48\u5c31\u6dfb\u52a0\u4e0a\u8fd9\u4e2a Key \u4e3a null \u7684\u6620\u5c04\n        modCount++;\n        addEntry(0, null, value, 0);\n        return null;\n    }\n\n    static class Entry&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; {\n        ...\n         \/**\n         * This method is invoked whenever the value in an entry is\n         * overwritten by an invocation of put(k,v) for a key k that's already\n         * in the HashMap.\n         *\/\n        void recordAccess(HashMap&lt;K,V&gt; m) {\n        }       \n        \n    }\n<\/code><\/pre>\n<p>\u6240\u4ee5\uff0c\u6574\u4e2a\u8fc7\u7a0b\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<p>\u5c06 Key \u7684 hashCode <strong>\u518d\u6b21\u54c8\u5e0c<\/strong>\u5f97\u5230\u6700\u7ec8\u7684 hash \u503c\uff0c\u7136\u540e\u901a\u8fc7\u8fd9\u4e2a hash \u503c\u4e0e\u6570\u7ec4\u957f\u5ea6\u51cf\u4e00\u8fdb\u884c<strong>\u4e0e\u8fd0\u7b97<\/strong>\uff0c\u8ba1\u7b97\u6700\u7ec8\u7684\u54c8\u5e0c\u5730\u5740\uff0c\u63a5\u7740\u5c31\u904d\u5386\u8fd9\u4e2a\u54c8\u5e0c\u6876\uff08\u5982\u679c\u8fd9\u4e2a\u6876\u4e0a\u6709\u94fe\u8868\u7684\u8bdd\uff0c\u5982\u679c\u8fd9\u4e2a\u54c8\u5e0c\u6876\u6ca1\u6709\u5b58\u50a8\u5143\u7d20\uff0c\u90a3\u4e48\u76f4\u63a5\u5b58\u50a8\u5230\u5f53\u524d\u54c8\u5e0c\u6876\uff09\uff0c\u5224\u65ad\u8be5\u4f4d\u7f6e\u7684 hash \u503c\u548c\u5f53\u524d\u8981\u5b58\u50a8\u7684 Key \u7684 hash \u503c\u662f\u5426\u4e00\u6837\uff1a<\/p>\n<ul>\n<li>\u4e00\u6837\u8bf4\u660e\u662f\u540c\u4e00\u4e2a Key\uff0c\u5219\u53ef\u4ee5\u8986\u76d6<\/li>\n<li>\n<p>\u4e0d\u4e00\u6837\u8bf4\u660e\u4e0d\u540c Key\uff0c\u53d1\u751f\u54c8\u5e0c\u51b2\u7a81\uff0c\u9700\u8981\u89e3\u51b3\u54c8\u5e0c\u51b2\u7a81\uff0c\u90a3\u4e48\u5148\u662f\u6bd4\u8f83\u8fd9\u4e24\u4e2a Key \u7684\u5185\u5b58\u5730\u5740\u662f\u5426\u76f8\u7b49\uff1a<\/p>\n<ul>\n<li>\n<p>\u5982\u679c\u5185\u5b58\u5730\u5740\u4e0d\u76f8\u7b49\uff0c\u518d\u53bb\u4f7f\u7528 equals \u65b9\u6cd5\u5224\u65ad\u4e24\u4e2a Key \u662f\u4e0d\u662f\u540c\u4e00\u4e2a\u3002<\/p>\n<ul>\n<li>equals \u5224\u65ad\u4e24\u4e2a Key \u4e3a true\uff0c\u76f4\u63a5\u65b0 Value \u8986\u76d6\u65e7 Value\u3002<\/li>\n<li>equals \u5224\u65ad\u4e24\u4e2a Key \u4e3a false\uff0c\u5982\u679c\u5f53\u524d\u54c8\u5e0c\u6876\u6709\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u90a3\u4e48\u4e0b\u4e00\u4e2a\u8282\u70b9\u8fdb\u884c\u5faa\u73af\u5224\u65ad\u3002\u5982\u679c\u5728\u5f53\u524d\u94fe\u8868\u8282\u70b9\u4e00\u76f4\u5224\u65ad\u51fa false\uff0c\u5219\u5c06\u8fd9\u4e2a Key \u5c01\u88c5\u6210 Entry\uff0c\u5934\u63d2\u6cd5\u63d2\u5165\u8be5\u94fe\u8868\u3002<\/li>\n<\/ul>\n<\/li>\n<li>\u5982\u679c\u5185\u5b58\u5730\u5740\u76f8\u7b49\uff0c\u8bf4\u660e\u662f\u540c\u4e00\u4e2a Key \u4e86\uff0c\u4e0d\u5fc5\u4f7f\u7528 equals \u4e86\uff0c\u6b64\u65f6\u76f4\u63a5\u65b0 Value \u8986\u76d6\u65e7 Value\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>\u90a3\u4e48\u5230\u8fd9\u91cc\uff0c\u6211\u76f8\u4fe1\u4f60\u5df2\u7ecf\u770b\u61c2\u4e86 put \u7684\u8fc7\u7a0b\u4e86\uff01<\/p>\n<h3>get \u7684\u8fc7\u7a0b<\/h3>\n<p>HashMap \u7684 get() \u65b9\u6cd5\uff1a<\/p>\n<ul>\n<li><code>public V get(Object key)<\/code><\/li>\n<\/ul>\n<p>\u5982\u679c HashMap \u4e2d\u6709\u8fd9\u4e2a Key\uff0c\u90a3\u4e48\u5c31\u8fd4\u56de\u8fd9\u4e2a Key \u6620\u5c04\u7684 Value\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Returns the value to which the specified key is mapped,\n     * or {@code null} if this map contains no mapping for the key.\n     *\n     * &lt;p&gt;More formally, if this map contains a mapping from a key\n     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :\n     * key.equals(k))}, then this method returns {@code v}; otherwise\n     * it returns {@code null}.  (There can be at most one such mapping.)\n     *\n     * &lt;p&gt;A return value of {@code null} does not &lt;i&gt;necessarily&lt;\/i&gt;\n     * indicate that the map contains no mapping for the key; it's also\n     * possible that the map explicitly maps the key to {@code null}.\n     * The {@link #containsKey containsKey} operation may be used to\n     * distinguish these two cases.\n     *\n     * @see #put(Object, Object)\n     *\/\n    public V get(Object key) {\n        if (key == null)\n            return getForNullKey();\n        \/\/ \u5c06 Key \u7684 hashCode \u518d\u6b21\u54c8\u5e0c\u5f97\u5230\u6700\u7ec8\u7684 hash \u503c\n        int hash = hash(key.hashCode());\n        \/\/ indexFor(hash, table.length) \u83b7\u53d6 Key \u6240\u5728 table \u6570\u7ec4\u4e2d\u7684\u4e0b\u6807\n        for (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)];\n             e != null;\n             e = e.next) {\n            \/\/ for \u5faa\u73af\u662f\u904d\u5386\u8fd9\u4e2a\u54c8\u5e0c\u6876\u4e0a\u7684\u94fe\u8868\uff0c\u5982\u679c\u6709\u94fe\u8868\u7684\u8bdd\n            Object k;\n            \/\/ \u5224\u65ad\u8be5\u4f4d\u7f6e\u4e0a\u7684 Key \u662f\u5426\u4e3a\u6211\u4eec\u9700\u8981\u7684 Key\n            if (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k)))\n                return e.value;\n        }\n        return null;\n    }<\/code><\/pre>\n<p>\u76f8\u4fe1\u4f60\u641e\u61c2\u4e86 put \u7684\u8fc7\u7a0b\uff0c\u90a3\u4e48 get \u7684\u8fc7\u7a0b\u4e5f\u4e0d\u96be\u7406\u89e3\uff0c\u8fc7\u7a0b\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<p>\u5c06 Key \u7684 hashCode <strong>\u518d\u6b21\u54c8\u5e0c<\/strong>\u5f97\u5230\u6700\u7ec8\u7684 hash \u503c\uff0c\u7136\u540e\u901a\u8fc7\u8fd9\u4e2a hash \u503c\u4e0e\u6570\u7ec4\u957f\u5ea6\u51cf\u4e00\u8fdb\u884c<strong>\u4e0e\u8fd0\u7b97<\/strong>\uff0c\u8ba1\u7b97\u6700\u7ec8\u7684\u54c8\u5e0c\u5730\u5740\uff08\u88ab\u5c01\u88c5\u6210 <code>indexFor<\/code> \u65b9\u6cd5\u4e86\uff09\uff0c\u63a5\u7740\u8fd8\u662f\u4e00\u6837\uff0c\u904d\u5386\u54c8\u5e0c\u6876\uff0c\u5224\u65ad\u8be5\u4f4d\u7f6e\u4e0a\u7684 Key \u662f\u5426\u4e3a\u6211\u4eec\u9700\u8981\u7684 Key\u3002<\/p>\n<h3>\u81ea\u52a8\u6269\u5bb9-resize+transfer<\/h3>\n<p>\u4e0a\u9762\u6211\u4eec\u4e5f\u8bf4\u4e86\uff0c\u6709\u4e00\u4e2a\u9608\u503c\uff0c\u5373 <code>load factor \u00d7 capacity<\/code> \u8fd9\u4e2a\u9608\u503c\uff0c\u5982\u679c\u5f53\u524d\u54c8\u5e0c\u8868\u7684\u5927\u5c0f\u8d85\u8fc7\u4e86\u8fd9\u4e2a\u9608\u503c\uff0c\u90a3\u4e48\u54c8\u5e0c\u8868\u662f\u9700\u8981\u6269\u5bb9\u7684\uff0c\u5728 HashMap \u4e2d\uff0c\u5b83\u662f\u4e0d\u8981\u624b\u52a8\u5e72\u9884\uff0c\u662f\u4f1a\u81ea\u52a8\u8fdb\u884c\u6269\u5bb9\u7684\u3002\u90a3\u4e48\u5b83\u662f\u600e\u6837\u81ea\u52a8\u6269\u5bb9\u7684\uff1f<\/p>\n<p>\u56de\u987e\uff1a<\/p>\n<ul>\n<li>\u54c8\u5e0c\u8868\u7684\u5bb9\u91cf\uff1a\u662f\u6307 table \u6570\u7ec4\u7684\u957f\u5ea6\u3002<\/li>\n<li>\u54c8\u5e0c\u8868\u7684\u5927\u5c0f\uff1a\u662f\u6307\u5b58\u50a8\u5728\u54c8\u5e0c\u8868\u4e2d\u7684\u5143\u7d20\uff08Entry \u7c7b\u578b\u7684\u5143\u7d20\uff09\u7684\u4e2a\u6570\u3002<\/li>\n<li>capacity\uff08\u5bb9\u91cf\uff09\uff1a\u9ed8\u8ba416<\/li>\n<li>load factor\uff08\u8d1f\u8f7d\u56e0\u5b50\uff09\uff1a\u9ed8\u8ba40.75<\/li>\n<li>threshold\uff08\u9608\u503c\uff09\uff1a\u9ed8\u8ba4 0.75 \u00d7 16 = 12\uff0c\u5373\u54c8\u5e0c\u8868\u5927\u5c0f\u8d85\u8fc712\u5c31\u4f1a\u81ea\u52a8\u6269\u5bb9<\/li>\n<\/ul>\n<p>\u6211\u4eec\u56de\u53bb\u770b\u4e0b put \u64cd\u4f5c\uff0c\u53ef\u4ee5\u770b\u5230\u5012\u6570\u7b2c\u4e8c\u884c\u4ee3\u7801\u6709\u4e2a <code>addEntry()<\/code> \u65b9\u6cd5<\/p>\n<pre><code class=\"java\">    public V put(K key, V value) {\n        if (key == null)\n            return putForNullKey(value);\n        int hash = hash(key.hashCode());\n        int i = indexFor(hash, table.length);\n        for (Entry&lt;K,V&gt; e = table[i]; e != null; e = e.next) {\n            Object k;\n            if (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) {\n                V oldValue = e.value;\n                e.value = value;\n                e.recordAccess(this);\n                return oldValue;\n            }\n        }\n\n        modCount++;\n        addEntry(hash, key, value, i);    \/\/ \u5c31\u662f\u8fd9\u91cc\uff0c\u6dfb\u52a0 Entry \u5bf9\u8c61\n        return null;\n    }<\/code><\/pre>\n<p>\u770b <code>addEntry()<\/code> \u7684\u6e90\u7801\uff0c\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<ul>\n<li>\u5b58\u50a8 Key\u3001Value\u3001hash \u503c\u5230\u6307\u5b9a\u7684\u54c8\u5e0c\u6876\u4e2d\u3002<\/li>\n<li>\u5224\u65ad\u5f53\u524d\u54c8\u5e0c\u8868\u5927\u5c0f\u52a0\u4e00\u540e\uff0c\u6709\u6ca1\u6709\u8d85\u51fa\u9608\u503c\u3002\u8d85\u8fc7\u9608\u503c\u5219\u8fdb\u884c\u54c8\u5e0c\u8868\u5bb9\u91cf\u7684 <code>resize()<\/code> \u64cd\u4f5c\u3002<\/li>\n<\/ul>\n<p>\u6240\u4ee5\u8fd9\u4e2a\u6269\u5bb9\u5c31\u662f\u901a\u8fc7 <code>addEntry()<\/code> \u65b9\u6cd5\u91cc\u7684 <code>size++ &gt;= threshold<\/code> \u8fdb\u884c\u5224\u65ad\u662f\u5426\u9700\u8981\u6269\u5bb9\uff0c\u8fdb\u800c\u8c03\u7528\u6269\u5bb9\u65b9\u6cd5 <code>resize()<\/code> \u5b9e\u73b0\u6240\u8c13\u7684\u81ea\u52a8\u6269\u5bb9\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Adds a new entry with the specified key, value and hash code to\n     * the specified bucket.  It is the responsibility of this\n     * method to resize the table if appropriate.\n     *\n     * Subclass overrides this to alter the behavior of put method.\n     *\/\n    void addEntry(int hash, K key, V value, int bucketIndex) {\n        Entry&lt;K,V&gt; e = table[bucketIndex];\n        table[bucketIndex] = new Entry&lt;&gt;(hash, key, value, e);\n        if (size++ &gt;= threshold)\n            resize(2 * table.length);\n    }<\/code><\/pre>\n<p>\u6211\u4eec\u53ef\u4ee5\u770b\u5230 <code>resize()<\/code> \u7684\u65f6\u5019\uff0c\u53c2\u6570\u662f<strong>\u4e24\u500d\u7684\u6570\u7ec4\u957f\u5ea6<\/strong>\uff0c\u4e5f\u5c31\u662f\u8bf4\u5c06\u54c8\u5e0c\u8868\u7684\u5bb9\u91cf\u6269\u5927\u6210\u539f\u6765\u7684\u4e24\u500d\u3002<\/p>\n<pre><code class=\"java\">resize(2 * table.length);<\/code><\/pre>\n<p>\u90a3\u4e0b\u9762\u6211\u4eec\u770b\u770b\u6269\u5bb9\u662f\u600e\u6837\u5b50\u7684\uff0c\u770b\u770b <code>resize()<\/code> \u6e90\u7801\uff1a<\/p>\n<p>\u6e90\u7801\u6ce8\u91ca\u4e5f\u8bf4\u4e86\uff0c\u5c06\u4f1a\u5bf9 HashMap \u5b9e\u4f8b\u5b58\u50a8\u7684 Entry \u8fdb\u884c rehash\uff08\u518d\u6b21\u54c8\u5e0c\uff09\u5230\u4e00\u4e2a\u6269\u5bb9\u540e\u7684\u65b0\u6570\u7ec4\u3002\u5982\u679c\u5f53\u524d\u5bb9\u91cf\u662f\u6700\u5927\u5bb9\u91cf\uff08MAXIMUM_CAPACITY\uff0c1 &lt;&lt;&lt; 30\uff0c\u5373$2^{30}$\uff09\u4e86\uff0c\u90a3\u4e48\u5c31\u4e0d\u4f1a\u8fdb\u884c\u6269\u5bb9\uff0c\u540c\u65f6\u8bbe\u7f6e\u9608\u503c\u4e3a <code>Integer.MAX_VALUE<\/code>\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Rehashes the contents of this map into a new array with a\n     * larger capacity.  This method is called automatically when the\n     * number of keys in this map reaches its threshold.\n     *\n     * If current capacity is MAXIMUM_CAPACITY, this method does not\n     * resize the map, but sets threshold to Integer.MAX_VALUE.\n     * This has the effect of preventing future calls.\n     *\n     * @param newCapacity the new capacity, MUST be a power of two;\n     *        must be greater than current capacity unless current\n     *        capacity is MAXIMUM_CAPACITY (in which case value\n     *        is irrelevant).\n     *\/\n    void resize(int newCapacity) {\n        Entry[] oldTable = table;            \/\/ \u539f\u6570\u7ec4\n        int oldCapacity = oldTable.length;    \/\/ \u539f\u6570\u7ec4\u957f\u5ea6 = \u539f\u5bb9\u91cf\n        if (oldCapacity == MAXIMUM_CAPACITY) {\n            threshold = Integer.MAX_VALUE;\n            return;\n        }\n\n        \/\/ \u521b\u5efa\u4e00\u4e2a\u6bd4\u539f\u6570\u7ec4\u957f\u5ea6\u5927\u4e24\u500d\u7684\u65b0\u6570\u7ec4\n        Entry[] newTable = new Entry[newCapacity];\n        \/\/ \u8f6c\u79fb\u539f\u6570\u7ec4\u4e2d\u7684\u5143\u7d20\uff08Entry \u5bf9\u8c61\uff09\u5230\u65b0\u6570\u7ec4\u4e2d\n        transfer(newTable);\n        \/\/ \u539f\u6570\u7ec4\u5f15\u7528\u6307\u5411\u65b0\u6570\u7ec4\n        table = newTable;\n        \/\/ \u91cd\u65b0\u8ba1\u7b97\u9608\u503c\n        threshold = (int)(newCapacity * loadFactor);\n    }\n\n    \/**\n     * Transfers all entries from current table to newTable.\n     *\/\n    void transfer(Entry[] newTable) {\n        Entry[] src = table;    \/\/ \u539f\u6570\u7ec4\n        int newCapacity = newTable.length;\n        \/\/ \u904d\u5386\u539f\u6570\u7ec4\n        for (int j = 0; j &lt; src.length; j++) {\n            \/\/ e \u53ef\u4ee5\u770b\u6210\u4e00\u4e2a\u6307\u9488\uff0c\u6307\u5411\u7b2cj\u4e2a\u54c8\u5e0c\u6876\u4e0a\u7684Entry\u8282\u70b9\n            Entry&lt;K,V&gt; e = src[j];\n            if (e != null) {\n                src[j] = null;\n                do {\n                    \/\/ \u770b\u5f53\u524d\u4f4d\u7f6e\u4e0a\u7684 Entry \u6709\u6ca1\u6709 next\uff0c\u6709\u5219\u8bf4\u660e\u662f\u94fe\u8868\n                    \/\/ next \u662f null\uff0c\u8bf4\u660e\u6ca1\u6709\u94fe\u8868\uff0c\u90a3\u4e48\u5c31\u4e0d\u4f1a\u6267\u884c\u4e0b\u9762\u7684 while\n                    Entry&lt;K,V&gt; next = e.next;\n                    \/\/ \u8ba1\u7b97\u5f53\u524d Entry \u5728\u65b0\u6570\u7ec4\u4e2d\u7684\u4f4d\u7f6e\n                    int i = indexFor(e.hash, newCapacity);\n                    \/\/ e \u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\u6307\u5411\u65b0\u7684\u54c8\u5e0c\u6876\uff0c\u53ef\u4ee5\u628a\u54c8\u5e0c\u6876\u5f53\u4f5c\u8868\u5934\uff0c\u8fd9\u6837\u65b9\u4fbf\u5934\u63d2\u6cd5\u63d2\u5165\u5143\u7d20\n                    e.next = newTable[i];\n                    \/\/ \u65b0\u7684\u54c8\u5e0c\u6876\u5b58\u50a8\u8fd9\u4e2a\u8282\u70b9\n                    newTable[i] = e;\n                    \/\/ \u79fb\u52a8\u6307\u9488 e \u6307\u5411\u4e0b\u4e00\u8282\u70b9\n                    e = next;\n                } while (e != null);\n            }\n        }\n    }<\/code><\/pre>\n<p>\u6240\u4ee5\uff0c\u603b\u7684\u6765\u8bf4\uff0c<strong>\u6269\u5bb9\u7684\u8fc7\u7a0b\u662f\u8fd9\u6837\u7684<\/strong>\uff1a<\/p>\n<p>\u6211\u4eec put \u4e00\u4e2a\u5143\u7d20\u5230\u54c8\u5e0c\u8868\uff0c\u8fd9\u4e2a\u8fc7\u7a0b\u4f1a\u8c03\u7528 <code>addEntry()<\/code> \u65b9\u6cd5\uff0c\u5728\u5b9e\u9645\u63d2\u5165\u4e00\u4e2a\u5143\u7d20\u540e\uff0c\u5224\u65ad\u5f53\u524d size \u662f\u5426\u5927\u4e8e\u9608\u503c\uff0c\u5927\u4e8e\u7684\u8bdd\u5c31\u4f1a\u6269\u5bb9\uff0c\u6269\u5bb9\u7684\u8bdd\uff0c\u4f1a\u4f20\u5165\u4e00\u4e2a\u4e24\u500d\u539f\u6570\u7ec4\u5927\u5c0f\u7684\u53c2\u6570\uff0c\u7136\u540e\u521b\u5efa\u4e00\u4e2a\u65b0\u7684\u6570\u7ec4\uff0c\u8fd9\u4e2a\u6570\u7ec4\u7684\u957f\u5ea6\u662f\u539f\u6570\u7ec4\u7684\u4e24\u500d\uff0c\u518d\u901a\u8fc7\u4e00\u4e2a <code>transfer()<\/code> \u65b9\u6cd5\uff0c\u5c06\u539f\u6570\u7ec4\u4e2d\u7684 Entry \u91cd\u65b0\u54c8\u5e0c\uff08rehash\uff09\u5230\u65b0\u6570\u7ec4\u4e2d\uff0c\u6700\u540e\u5c06\u539f\u6570\u7ec4\u5f15\u7528\u6307\u5411\u65b0\u6570\u7ec4\uff0c\u540c\u65f6\u8ba1\u7b97\u4e0b\u65b0\u7684\u9608\u503c\u3002<\/p>\n<h3>1.7 \u603b\u7ed3<\/h3>\n<p>1.7 \u7684 HashMap\uff0c<strong>\u5e95\u5c42\u662f Entry \u7c7b\u578b\u7684\u6570\u7ec4 + Entry \u7c7b\u578b\u7684\u94fe\u8868<\/strong>\u3002<\/p>\n<p>\u8fd9\u4e2a\u6570\u7ec4\u79f0\u4e3a <strong>table \u6570\u7ec4<\/strong>\uff08\u4e5f\u6709\u7684\u4eba\u79f0\u4e3a\u6876\u6570\u7ec4\uff09\uff0c\u6570\u7ec4\u4e0a\u7684\u6bcf\u4e2a\u4f4d\u7f6e\uff0c\u53ef\u4ee5\u79f0\u4e3a<strong>\u54c8\u5e0c\u6876<\/strong>\uff0c\u6bcf\u4e00\u4e2a\u54c8\u5e0c\u6876\u90fd\u662f\u5b58\u50a8 Entry \u7c7b\u578b\u7684\u5143\u7d20\u7684\uff0c\u540c\u65f6\u53ef\u4ee5\u77e5\u9053<strong>\u6bcf\u4e2a\u54c8\u5e0c\u6876\u4f4d\u7f6e\u4e0a\u90fd\u53ef\u4ee5\u5bf9\u5e94\u7740\u4e00\u4e2a\u89e3\u51b3\u51b2\u7a81\u7684\u94fe\u8868\u7684\u4f4d\u7f6e<\/strong>\u3002<\/p>\n<p>\u5982\u679c\u5f53\u8981\u5b58\u50a8\u7684 Key-Value \u7684 Key \u4e0e\u5f53\u524d\u4f4d\u7f6e\u4e0a\u7684 Key \u53d1\u751f\u51b2\u7a81\uff0c\u90a3\u4e48\u5c31\u9700\u8981\u8fdb\u884c<strong>\u5934\u63d2\u6cd5<\/strong>\uff0c\u5c06\u8be5 Key \u63d2\u5165\u5f53\u524d\u54c8\u5e0c\u6876\u5bf9\u5e94\u7684\u94fe\u8868\u3002<\/p>\n<p>\u5982\u679c\u5f53\u524d\u5b58\u50a8\u7684\u5143\u7d20\u7684\u4e2a\u6570\u8d85\u8fc7\u4e86<strong>\u9608\u503c<\/strong>\uff08threshold = load factor \u00d7 capacity\uff09\uff0c\u90a3\u4e48\u5c31\u4f1a\u8fdb\u884c<strong>\u6269\u5bb9<\/strong>\uff0c\u521b\u5efa\u4e00\u4e2a<strong>\u4e24\u500d\u539f\u6570\u7ec4\u5927\u5c0f\u7684\u65b0\u6570\u7ec4<\/strong>\uff0c\u7136\u540e\u5c06\u539f\u6570\u7ec4\u4e2d\u7684\u5143\u7d20<strong>\u91cd\u65b0\u54c8\u5e0c<\/strong>\u5230\u65b0\u6570\u7ec4\u4e2d\uff0c\u6700\u540e\u539f\u6570\u7ec4\u5f15\u7528\u6307\u5411\u65b0\u6570\u7ec4\uff0c\u8fdb\u800c\u5b8c\u6210\u6269\u5bb9\u3002<\/p>\n<h2>1.8 \u7248 HashMap<\/h2>\n<p><img decoding=\"async\" referrerpolicy=\"no-referrer\" src=\"https:\/\/segmentfault.com\/img\/remote\/1460000042929809\" alt=\"1.8 \u7684HashMap\" title=\"1.8 \u7684HashMap\" loading=\"lazy\"><\/p>\n<p>\u5728 JDK 1.8 \u5f00\u59cb\uff0c\u5c31\u53d8\u6210\u4e86\u300c\u6570\u7ec4+\u94fe\u8868\/\u7ea2\u9ed1\u6811\u300d<\/p>\n<p>\u770b\u770b\u6e90\u7801\u4e0e1.7\u6709\u4ec0\u4e48\u533a\u522b<\/p>\n<h3>\u770b\u770b\u533a\u522b<\/h3>\n<ul>\n<li>DEFAULT_INITIAL_CAPACITY \u5199\u6cd5\u53d8\u9ad8\u7ea7\u4e86\uff0c\u4ece <code>16<\/code> \u76f4\u63a5\u6539\u6210 <code>1 &lt;&lt; 4<\/code><\/li>\n<\/ul>\n<pre><code class=\"java\">static final int DEFAULT_INITIAL_CAPACITY = 1 &lt;&lt; 4; \/\/ aka 16<\/code><\/pre>\n<ul>\n<li>\u51fa\u73b0\u4e00\u4e2a<code>TREEIFY_THRESHOLD<\/code>\uff0c\u6811\u5316\u9608\u503c\uff0c\u5373\u94fe\u8868\u8f6c\u6210\u7ea2\u9ed1\u6811\u7684\u9608\u503c\uff0c\u9ed8\u8ba4\u4e3a 8\u3002<\/li>\n<\/ul>\n<pre><code class=\"java\">static final int TREEIFY_THRESHOLD = 8;<\/code><\/pre>\n<ul>\n<li>\u51fa\u73b0\u4e00\u4e2a<code>UNTREEIFY_THRESHOLD<\/code>\uff0c\u89e3\u9664\u6811\u5316\u7684\u9608\u503c\uff0c\u5373\u7ea2\u9ed1\u6811\u4e2d\u7684 Entry \u6570\u91cf\u5c0f\u4e8e 6\uff0c\u90a3\u4e48\u5c31\u4ece\u7ea2\u9ed1\u6811\u9000\u5316\u6210\u94fe\u8868\u3002<\/li>\n<\/ul>\n<pre><code class=\"java\">static final int UNTREEIFY_THRESHOLD = 6;<\/code><\/pre>\n<ul>\n<li>\u51fa\u73b0\u4e00\u4e2a<code>MIN_TREEIFY_CAPACITY<\/code>\uff0c\u6700\u5c0f\u6811\u5316\u5bb9\u91cf\uff0c\u5373 table \u6570\u7ec4\u7684\u957f\u5ea6\u6700\u5c0f\u9700\u8981 64\uff0c\u624d\u6709\u673a\u4f1a\u6811\u5316\u3002<\/li>\n<\/ul>\n<pre><code class=\"java\">static final int MIN_TREEIFY_CAPACITY = 64;<\/code><\/pre>\n<h3>Node<\/h3>\n<p>\u63a5\u7740\uff0c\u6211\u4eec\u770b\u5230\u8fd9\u91cc\u5b9a\u4e49\u4e86\u4e00\u4e2a Node \u8282\u70b9\uff0c\u901a\u8fc7\u5bf9\u6bd4 1.7 \u7248\u7684\uff0c\u53ef\u4ee5\u53d1\u73b0\u8fd9\u4e2a\u628a 1.7 \u4e2d\u7684 Entry \u6362\u4e86\u4e2a\u540d\uff0c\u5b9a\u4e49\u6210 Node \u8282\u70b9\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u5728 1.8 \u4e2d\u7684 table \u6570\u7ec4\uff0c\u5176\u7c7b\u578b\u4e0d\u518d\u662f Entry \u7c7b\u578b\uff0c\u800c\u662f Node \u7c7b\u578b\uff0c\u5373 Node \u7c7b\u578b\u7684 table \u6570\u7ec4\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Basic hash bin node, used for most entries.  (See below for\n     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)\n     *\/\n    static class Node&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; {\n        final int hash;\n        final K key;\n        V value;\n        Node&lt;K,V&gt; next;\n\n        Node(int hash, K key, V value, Node&lt;K,V&gt; next) {\n            this.hash = hash;\n            this.key = key;\n            this.value = value;\n            this.next = next;\n        }\n\n        public final K getKey()        { return key; }\n        public final V getValue()      { return value; }\n        public final String toString() { return key + &quot;=&quot; + value; }\n\n        public final int hashCode() {\n            return Objects.hashCode(key) ^ Objects.hashCode(value);\n        }\n\n        public final V setValue(V newValue) {\n            V oldValue = value;\n            value = newValue;\n            return oldValue;\n        }\n\n        public final boolean equals(Object o) {\n            if (o == this)\n                return true;\n            if (o instanceof Map.Entry) {\n                Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;\n                if (Objects.equals(key, e.getKey()) &amp;&amp;\n                    Objects.equals(value, e.getValue()))\n                    return true;\n            }\n            return false;\n        }\n    }<\/code><\/pre>\n<p>Node \u6570\u7ec4<\/p>\n<pre><code class=\"java\">transient Node&lt;K,V&gt;[] table;<\/code><\/pre>\n<h3>\u6270\u52a8\u51fd\u6570<\/h3>\n<p>hash()\uff0c\u6270\u52a8\u51fd\u6570\u53d1\u751f\u4e86\u53d8\u5316\uff0c1.8 \u6e90\u7801\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<p>\u8ba9 Key \u7684 hashCode \u4e0e\u4e0a hashCode \u65e0\u7b26\u53f7\u53f3\u79fb 16 \u4f4d\uff0c\u6700\u7ec8\u4e0e\u8fd0\u7b97\u7684\u7ed3\u679c\u5c31\u662f\u6700\u7ec8\u7684 hash \u503c\u3002<\/p>\n<pre><code class=\"java\">    static final int hash(Object key) {\n        int h;\n        return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);\n    }<\/code><\/pre>\n<p>\u800c 1.7 \u7684\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<pre><code class=\"java\">    static int hash(int h) {\n        h ^= (h &gt;&gt;&gt; 20) ^ (h &gt;&gt;&gt; 12);\n        return h ^ (h &gt;&gt;&gt; 7) ^ (h &gt;&gt;&gt; 4);\n    }<\/code><\/pre>\n<h3>\u6784\u9020\u65b9\u6cd5<\/h3>\n<p>\u6784\u9020\u65b9\u6cd5\u4e5f\u6709\u53d8\u5316\uff0c\u4f46\u662f\u4e3b\u8981\u7684\u8fc7\u7a0b\u8fd8\u662f\u4e00\u6837\u7684\uff0c\u4e3b\u8981\u7684\u533a\u522b\u5c31\u662f\uff0c\u6b64\u65f6\u7684 table \u6570\u7ec4\u8fd8\u6ca1\u6709\u88ab\u521b\u5efa\u51fa\u6765\u3002<\/p>\n<pre><code class=\"java\">    \/**\n     * Returns a power of two size for the given target capacity.\n     *\/\n    static final int tableSizeFor(int cap) {\n        int n = cap - 1;\n        n |= n &gt;&gt;&gt; 1;\n        n |= n &gt;&gt;&gt; 2;\n        n |= n &gt;&gt;&gt; 4;\n        n |= n &gt;&gt;&gt; 8;\n        n |= n &gt;&gt;&gt; 16;\n        return (n &lt; 0) ? 1 : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;\n    }\n\n    public HashMap(int initialCapacity, float loadFactor) {\n        if (initialCapacity &lt; 0)\n            throw new IllegalArgumentException(&quot;Illegal initial capacity: &quot; +\n                                               initialCapacity);\n        if (initialCapacity &gt; MAXIMUM_CAPACITY)\n            initialCapacity = MAXIMUM_CAPACITY;\n        if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))\n            throw new IllegalArgumentException(&quot;Illegal load factor: &quot; +\n                                               loadFactor);\n        this.loadFactor = loadFactor;\n        this.threshold = tableSizeFor(initialCapacity);\n    }\n\n    public HashMap() {\n        this.loadFactor = DEFAULT_LOAD_FACTOR; \/\/ all other fields defaulted\n    }<\/code><\/pre>\n<p>\u53ef\u4ee5\u8bf4\u5728 1.8 \u8fd9\u91cc\uff0cHashMap \u5c5e\u4e8e<strong>\u61d2\u52a0\u8f7d<\/strong>\u7684\u4e86\uff0c\u90a3\u4e48 table \u6570\u7ec4\u4f55\u65f6\u52a0\u8f7d\uff08\u521b\u5efa\uff09\u5462\uff1f\u6ca1\u9519\uff0c\u5c31\u662f\u5728 put \u7684\u65f6\u5019\u624d\u521b\u5efa\u7684\u3002\u4e0b\u9762\u6211\u4eec\u6765\u770b\u770b\u3002<\/p>\n<h3>put \u7684\u53d8\u5316<\/h3>\n<p>put \u591a\u4e86\u4e00\u5c42\u5c01\u88c5\uff0c\u9700\u8981\u5728 <code>putVal()<\/code> \u65b9\u6cd5\u4e2d\u7406\u89e3<\/p>\n<ul>\n<li><code>final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)<\/code><\/li>\n<li><code>hash<\/code>\uff1aKey \u901a\u8fc7\u6270\u52a8\u51fd\u6570\u5f97\u5230\u6700\u7ec8 hash \u503c\u3002<\/li>\n<li><code>key<\/code>\u3001<code>value<\/code>\uff1a\u952e \u548c \u503c\u3002<\/li>\n<li><code>onlyIfAbsent<\/code>\uff1a\u5982\u679c\u4e3a true\uff0c\u90a3\u4e48\u4e0d\u4f1a\u6539\u53d8\u5df2\u5b58\u5728\u7684\u503c\u3002<\/li>\n<li><code>evict<\/code>\uff1a\u5982\u679c\u4e3a false\uff0c\u8bf4\u660e table \u6570\u7ec4\u6b63\u5728\u521b\u5efa\u4e2d\u3002<\/li>\n<\/ul>\n<p>put \u7684\u601d\u8def\u8fd8\u662f\u4e00\u6837\u7684\uff1a\u6839\u636e Key \u8ba1\u7b97\u51fa\u54c8\u5e0c\u5730\u5740\uff0c\u5224\u65ad\u8fd9\u4e2a\u5730\u5740\u4e0a\u6709\u6ca1\u6709\u51b2\u7a81\uff0c\u6ca1\u6709\u5219\u76f4\u63a5\u63d2\u5165\u8fd9\u4e2a Node\uff0c\u6709\u5219\u9700\u8981\u89e3\u51b3\u51b2\u7a81\u3002\u53d8\u5316\u5927\u7684\u5c31\u662f\u4ee3\u7801\u7684\u5b9e\u73b0\uff08\u7ea2\u9ed1\u6811\u3001\u5c3e\u63d2\u6cd5\uff09\u3002<\/p>\n<pre><code class=\"java\">    public V put(K key, V value) {\n        return putVal(hash(key), key, value, false, true);\n    }\n\n    \/**\n     * Implements Map.put and related methods.\n     *\n     * @param hash hash for key\n     * @param key the key\n     * @param value the value to put\n     * @param onlyIfAbsent if true, don't change existing value\n     * @param evict if false, the table is in creation mode.\n     * @return previous value, or null if none\n     *\/\n    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,\n                   boolean evict) {\n        \/\/ tab-&gt; table \u6570\u7ec4\n        \/\/ p-&gt; node \u6307\u9488\uff0c\u6307\u5411\u54c8\u5e0c\u6876\u4e2d\u7b2c\u4e00\u4e2a\u8282\u70b9\uff0c\u53ef\u4ee5\u8bf4\u662f\u94fe\u8868\u8868\u5934\u8282\u70b9\n        \/\/ n-&gt; \u4ee3\u8868 table \u6570\u7ec4\u7684\u957f\u5ea6\n        \/\/ i-&gt; \u4ee3\u8868 table \u6570\u7ec4\u7684\u4e0b\u6807\n        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;\n        \/\/ \u7b2c\u4e00\u6b21 put \u5c31\u4f1a\u8fdb\u5165\u8fd9\u4e2a\u5224\u65ad\uff0c\u8fdb\u884c\u6570\u7ec4\u7684\u521b\u5efa\n        if ((tab = table) == null || (n = tab.length) == 0)\n            n = (tab = resize()).length;\n        \/\/ \u5982\u679c put \u7684\u8fd9\u4e2a Key\uff0c\u627e\u5230\u7684\u4f4d\u7f6e\u4e0d\u4f1a\u51b2\u7a81\uff0c\u90a3\u4e48\u76f4\u63a5\u521b\u5efa\u4e00\u4e2a Node \u8282\u70b9\u5b58\u50a8\u8fd9\u4e2a\u952e\u503c\u5bf9\n        if ((p = tab[i = (n - 1) &amp; hash]) == null)\n            tab[i] = newNode(hash, key, value, null);\n        else {\n            \/\/ \u53d1\u751f\u51b2\u7a81\u8fdb\u5165\u8fd9\u91cc\n            Node&lt;K,V&gt; e; K k;\n            \/\/ \u5224\u65ad\u662f\u5426\u662f\u540c\u4e00\u4e2aKey\uff0c\u662f\u5c31\u628a\u6307\u9488 e \u6307\u5411\u8fd9\u4e2a\u8282\u70b9 p\uff0c\u7136\u540e\u76f4\u63a5\u8d70\u4e0b\u9762\u7684 e \u662f\u5426\u4e3a\u7a7a\u7684\u5224\u65ad\u4e86\n            if (p.hash == hash &amp;&amp;\n                ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))\n                e = p;\n            else if (p instanceof TreeNode)    \/\/ Key \u4e0d\u540c\uff0c\u8d70\u8fd9\u91cc\uff0c\u5982\u679c\u8fd9\u4e2a\u8282\u70b9 p \u662f\u4e00\u4e2a\u6811\u8282\u70b9\n                e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);\n            else {    \/\/ Key \u4e0d\u540c\uff0c\u6ca1\u6709\u6811\u5316\uff0c\u9700\u8981\u904d\u5386\u94fe\u8868\n                for (int binCount = 0; ; ++binCount) {\n                    \/\/ e \u6307\u5411\u7684 p \u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u5982\u679c\u4e3a\u7a7a\uff0c\u8bf4\u660e\u662f\u94fe\u8868\u5c3e\u90e8\u4e86\n                    if ((e = p.next) == null) {\n                        p.next = newNode(hash, key, value, null);\n                        if (binCount &gt;= TREEIFY_THRESHOLD - 1) \/\/ -1 for 1st\n                            treeifyBin(tab, hash);\n                        break;\n                    }\n                    \/\/ \u8d70\u5230\u8fd9\u91cc\uff0c\u4e0d\u662f\u94fe\u8868\u5c3e\u90e8\uff0c\u7ee7\u7eed\u5224\u65ad Key \u76f8\u540c\u4e0e\u5426\uff0c\u76f8\u540c\u5c31\u8df3\u51fa\u5faa\u73af\uff0c\u8d70\u4e0b\u9762\u7684\u5224\u65ad\n                    if (e.hash == hash &amp;&amp;\n                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))\n                        break;\n                    \/\/ \u79fb\u52a8\u6307\u9488\n                    p = e;\n                }\n            }\n            \/\/ \u8fd9\u91cc\u5c31\u662f\uff0c\u5982\u679c\u662f\u540c\u4e00\u4e2a Key \uff0c\u5c31\u4f1a\u8d70\u8fd9\u91cc\u7684\u8986\u76d6\n            if (e != null) { \/\/ existing mapping for key\n                V oldValue = e.value;\n                if (!onlyIfAbsent || oldValue == null)\n                    e.value = value;\n                afterNodeAccess(e);\n                return oldValue;\n            }\n        }\n        ++modCount;\n        if (++size &gt; threshold)    \/\/ \u5224\u65ad\u662f\u5426\u9700\u8981\u6269\u5bb9\n            resize();\n        afterNodeInsertion(evict);\n        return null;\n    }<\/code><\/pre>\n<h3>get \u7684\u53d8\u5316<\/h3>\n<p>get \u4e5f\u662f\uff0c\u591a\u4e86\u4e00\u5c42\u5c01\u88c5\uff0c\u601d\u8def\u8fd8\u662f\u4e00\u6837\uff0c\u83b7\u53d6\u54c8\u5e0c\u5730\u5740\uff0c\u5224\u65ad\u8be5\u4f4d\u7f6e\u4e0a\u7684\u5143\u7d20\u662f\u5426\u662f\u6211\u4eec\u60f3\u8981\u7684\u3002<\/p>\n<pre><code class=\"java\">    public V get(Object key) {\n        Node&lt;K,V&gt; e;\n        return (e = getNode(hash(key), key)) == null ? null : e.value;\n    }\n\n    final Node&lt;K,V&gt; getNode(int hash, Object key) {\n        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; int n; K k;\n        \/\/ \u5224\u65ad\u5f53\u524d\u54c8\u5e0c\u8868\u662f\u5426\u5b58\u5728\u3001\u662f\u5426\u6709\u5143\u7d20\u3001\u5f97\u5230\u7684\u54c8\u5e0c\u5730\u5740\u4e0a\u662f\u5426\u6709\u5143\u7d20\uff08\u7b97\u6cd5\u7684\u5065\u58ee\u6027\uff09\n        \/\/ \u5224\u65ad\u4e3a false \u7684\u8bdd\uff0c\u81ea\u7136\u8bf4\u660e\u6ca1\u6709\u4efb\u4f55\u5143\u7d20\uff0c\u8fd8 get \u4e2a p\uff1f\n        if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;\n            (first = tab[(n - 1) &amp; hash]) != null) {\n            \/\/ \u54c8\u5e0c\u6876\u7b2c\u4e00\u4e2a\u5143\u7d20\u662f\u6211\u4eec\u60f3\u8981\u7684\uff1f\u662f\u5c31\u76f4\u63a5\u8fd4\u56de\u4e86\n            if (first.hash == hash &amp;&amp; \/\/ always check first node\n                ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))\n                return first;\n            \/\/ \u4e0d\u662f\uff0c\u90a3\u4e48\u770b\u54c8\u5e0c\u6876\u4e0a\u7684\u94fe\u8868\/\u7ea2\u9ed1\u6811\n            if ((e = first.next) != null) {\n                if (first instanceof TreeNode)\n                    return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);\n                do {\n                    if (e.hash == hash &amp;&amp;\n                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))\n                        return e;\n                } while ((e = e.next) != null);\n            }\n        }\n        return null;\n    }<\/code><\/pre>\n<h3>\u6269\u5bb9\u673a\u5236<\/h3>\n<p>1.8 \u7684\u6269\u5bb9\u673a\u5236\uff0c\u53d8\u5316\u5c31\u5927\u4e86\uff01\u5728 1.7 \u7684\u65f6\u5019\uff0c\u4e3b\u8981\u662f\u901a\u8fc7 <code>resize()<\/code> \u548c <code>transfer()<\/code> \u76f8\u4e92\u914d\u5408\u5b8c\u6210\u6269\u5bb9\u53ca\u5143\u7d20\u8f6c\u79fb\u7684\uff0c\u5728 1.8 \u7684\u65f6\u5019\uff0c\u76f4\u63a5\u628a <code>transfer()<\/code> \u4e5f\u641e\u5230 <code>resize()<\/code> \u4e2d\u4e86\uff0c\u800c\u4e14 transfer \u7684 rehash \u7684\u7b97\u6cd5\u5f88\u7f8e\u5999\u3002\u4e0d\u8fc7\u6269\u5bb9\u65f6\u673a\u8fd8\u662f\u4e00\u6837\uff0c\u8d85\u8fc7\u9608\u503c\u5c31\u4f1a\u6269\u5bb9\u3002<\/p>\n<p>\u6211\u4eec\u770b\u770b\u6e90\u7801\u662f\u8fd9\u6837\u7684\uff1a<\/p>\n<pre><code class=\"java\">    final Node&lt;K,V&gt;[] resize() {\n        Node&lt;K,V&gt;[] oldTab = table;    \/\/ \u4e00\u5f00\u59cb table \u8fd8\u6ca1\u521b\u5efa\uff0c\u6240\u4ee5\u7b2c\u4e00\u6b21\u8fd9\u91cc\u7684 oldTab \u4e3a\u7a7a\n        int oldCap = (oldTab == null) ? 0 : oldTab.length;\n        int oldThr = threshold;\n        int newCap, newThr = 0;\n        if (oldCap &gt; 0) {\n            if (oldCap &gt;= MAXIMUM_CAPACITY) {\n                threshold = Integer.MAX_VALUE;\n                return oldTab;\n            }\n            else if ((newCap = oldCap &lt;&lt; 1) &lt; MAXIMUM_CAPACITY &amp;&amp;\n                     oldCap &gt;= DEFAULT_INITIAL_CAPACITY)\n                newThr = oldThr &lt;&lt; 1; \/\/ double threshold \u9608\u503c\u66f4\u65b0\u4e3a\u539f\u6765\u7684\u4e24\u500d\n        }\n        else if (oldThr &gt; 0) \/\/ initial capacity was placed in threshold\n            newCap = oldThr;\n        else {               \/\/ zero initial threshold signifies using defaults\n            \/\/ \u9ed8\u8ba4\u521d\u59cb\u5316\n            newCap = DEFAULT_INITIAL_CAPACITY;\n            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);\n        }\n        if (newThr == 0) {\n            float ft = (float)newCap * loadFactor;\n            newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (float)MAXIMUM_CAPACITY ?\n                      (int)ft : Integer.MAX_VALUE);\n        }\n        threshold = newThr;\n        @SuppressWarnings({&quot;rawtypes&quot;,&quot;unchecked&quot;})\n        \/\/ \u6269\u5bb9\uff0c\u521b\u5efa\u65b0\u7684 Node \u6570\u7ec4\uff08\u5f53\u7136\uff0c\u7b2c\u4e00\u6b21\u521b\u5efa\u6570\u7ec4\u4e5f\u662f\u5728\u8fd9\u91cc\u521b\u5efa\uff09\n        Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])new Node[newCap];\n        table = newTab;\n        \/\/ \u539f\u6570\u7ec4\u4e0d\u4e3a\u7a7a\n        if (oldTab != null) {\n            \/\/ \u904d\u5386\u539f\u6570\u7ec4\n            for (int j = 0; j &lt; oldCap; ++j) {\n                Node&lt;K,V&gt; e;    \/\/ \u53ef\u4ee5\u770b\u6210\u4e00\u4e2a\u6307\u9488\n                if ((e = oldTab[j]) != null) {    \/\/ \u5224\u65ad\u7b2cj\u4e2a\u54c8\u5e0c\u6876\u662f\u5426\u4e3a\u7a7a\n                    oldTab[j] = null;\n                    if (e.next == null)        \/\/ \u5982\u679c\u8fd9\u4e2a\u54c8\u5e0c\u6876\u6ca1\u6709\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u8bf4\u660e\u6ca1\u6709\u94fe\u8868\n                        newTab[e.hash &amp; (newCap - 1)] = e;\n                    else if (e instanceof TreeNode)    \/\/ \u5982\u679c\u8fd9\u4e2a\u8282\u70b9\u662f\u6811\u8282\u70b9\n                        ((TreeNode&lt;K,V&gt;)e).split(this, newTab, j, oldCap);\n                    else { \/\/ preserve order\n                        \/\/ \u4e0d\u662f\u6811\u8282\u70b9\u5e76\u4e14\u6709\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u8bf4\u660e\u6709\u94fe\u8868\n                        Node&lt;K,V&gt; loHead = null, loTail = null;\n                        Node&lt;K,V&gt; hiHead = null, hiTail = null;\n                        Node&lt;K,V&gt; next;\n                        \/\/ \u5c3e\u63d2\u6cd5\u8f6c\u79fb\u94fe\u8868\u6570\u636e\uff0c\u76f4\u5230\u94fe\u8868\u6ca1\u6709\u5143\u7d20\u4e3a\u6b62\n                        do {\n                            next = e.next;\n                            \/\/ \u5982\u679c\u8fd9\u4e2a\u4e0e\u64cd\u4f5c\u7ed3\u679c\u4e3a0\uff0c\u90a3\u4e48\u653e\u5165\u65b0\u6570\u7ec4\u7684\u4f4d\u7f6e\u548c\u539f\u6570\u7ec4\u7684\u4f4d\u7f6e\u662f\u4e00\u6837\u7684\n                            if ((e.hash &amp; oldCap) == 0) {\n                                if (loTail == null)    \/\/ \u76f4\u63a5\u653e\u5165\n                                    loHead = e;\n                                else                \/\/ \u5c3e\u63d2\u6cd5\n                                    loTail.next = e;\n                                loTail = e;\n                            }\n                            \/\/ \u4e0e\u64cd\u4f5c\u7ed3\u679c\u4e0d\u4e3a0\uff0c\u9700\u8981\u91cd\u65b0\u8ba1\u7b97\u5b58\u653e\u7684\u4f4d\u7f6e\n                            else {\n                                if (hiTail == null)    \/\/ \u76f4\u63a5\u653e\u5165\n                                    hiHead = e;\n                                else                \/\/ \u5c3e\u63d2\u6cd5\n                                    hiTail.next = e;\n                                hiTail = e;\n                            }\n                        } while ((e = next) != null);\n                        if (loTail != null) {\n                            loTail.next = null;\n                            newTab[j] = loHead;\n                        }\n                        if (hiTail != null) { \n                            \/\/ \u65b0\u4f4d\u7f6e\uff1a\u6240\u5728\u7684\u539f\u6570\u7ec4\u4f4d\u7f6e\u4e0b\u6807\u52a0\u4e0a\u539f\u6570\u7ec4\u5bb9\u91cf\uff08\u957f\u5ea6\uff09\n                            hiTail.next = null;\n                            newTab[j + oldCap] = hiHead;\n                        }\n                    }\n                }\n            }\n        }\n        \/\/ \u7b2c\u4e00\u6b21\u4e0d\u4f1a\u8d70\u4e0a\u9762\u7684 if\uff0c\u76f4\u63a5\u8fd4\u56de\u65b0\u521b\u5efa\u9ed8\u8ba4\u5bb9\u91cf\u548c\u9608\u503c\u7684\u6570\u7ec4\n        return newTab;\n    }<\/code><\/pre>\n<p>\u8fd9\u91cc\u9762<strong>\u6700\u96be\u7406\u89e3<\/strong>\u7684\u5c31\u662f <code>(e.hash &amp; oldCap) == 0<\/code><\/p>\n<ul>\n<li>\u8fd0\u7b97\u7ed3\u679c\u4e3a 0 \u7684\u8bdd\uff0c\u90a3\u4e48\u653e\u5165\u65b0\u6570\u7ec4\u7684\u4f4d\u7f6e\u548c\u539f\u6570\u7ec4\u7684\u4f4d\u7f6e\u662f\u4e00\u6837\u7684<\/li>\n<li>\u8fd0\u7b97\u7ed3\u679c\u4e0d\u4e3a 0 \u7684\u8bdd\uff0c\u90a3\u4e48\u5c31\u9700\u8981\u91cd\u65b0\u8ba1\u7b97\u4f4d\u7f6e\uff08\u65b0\u4f4d\u7f6e\uff1a\u6240\u5728\u7684\u539f\u6570\u7ec4\u4f4d\u7f6e\u4e0b\u6807\u52a0\u4e0a\u539f\u6570\u7ec4\u5bb9\u91cf\uff08\u957f\u5ea6\uff09\uff09<\/li>\n<\/ul>\n<h3>\u7406\u89e3 (e.hash &#038; oldCap) == 0<\/h3>\n<p><strong>\u9700\u8981\u77e5\u9053\u7684\u662f\uff1a<\/strong><\/p>\n<ul>\n<li>e.hash\uff1a e \u53ef\u4ee5\u770b\u6210\u4e00\u4e2a\u6307\u9488\uff0c\u662f\u4e00\u4e2a\u6307\u5411\u5f53\u524d\u904d\u5386\u5230\u7684 Node \u8282\u70b9\u7684\u6307\u9488\uff0chash \u6307\u7684\u662f\u8be5 Node \u8282\u70b9\u5b58\u50a8\u7684 Key \u7684 hash \u503c\uff0c\u5373 hash \u503c\u662f\u901a\u8fc7 <code>hash(key.hashCode())<\/code> \u5f97\u5230\u7684\u6700\u7ec8\u5b58\u50a8\u7684 hash \u503c\u3002<\/li>\n<li>oldCap\uff1a\u8868\u793a\u539f\u6570\u7ec4\u7684\u5bb9\u91cf\uff0c\u5373\u539f\u6570\u7ec4\u957f\u5ea6\uff0c\u540c\u65f6\u8fd9\u4e2a\u957f\u5ea6\u662f 2 \u6b21\u65b9\u5e42\uff0c\u6bd4\u5982 $2^4 = 16$<\/li>\n<\/ul>\n<p><strong>\u4f55\u65f6\u8fd9\u4e2a\u64cd\u4f5c\u7b49\u4e8e 0 \uff1f<\/strong><\/p>\n<p>\u6211\u4eec\u53ef\u4ee5\u4ece oldCap \u5165\u624b\uff0c\u5047\u8bbe oldCap \u662f 16\uff0c\u90a3\u4e48\u5176\u4e8c\u8fdb\u5236\u4e3a <code>10000<\/code><\/p>\n<p>\u5982\u679c\u6211\u4eec\u60f3 <code>e.hash &amp; oldCap<\/code> \u7b49\u4e8e 0\uff0c\u90a3\u4e48<strong>\u8be5 Key \u7684 hash \u503c\u7684\u4e8c\u8fdb\u5236\u6700\u9ad8\u4f4d\u5fc5\u987b\u4e3a 0<\/strong>\uff0c\u5269\u4e0b\u7684\u4e8c\u8fdb\u5236\u4f4d\u53ef\u4ee5\u4e0d\u7ba1\uff0c\u8fd9\u6837\u8fdb\u884c\u4e0e\u8fd0\u7b97\u540e\u7684\u7ed3\u679c\u80af\u5b9a\u662f<strong>\u7b49\u4e8e<\/strong> 0 \u7684\u3002<\/p>\n<p>\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5047\u8bbe\u6b64\u65f6 hash \u503c\u5bf9\u5e94\u7684\u4e8c\u8fdb\u5236\u4e3a <code>01111<\/code>\uff0c\u90a3\u4e48\u548c oldCap \u8fdb\u884c\u4e0e\u8fd0\u7b97\uff1a<\/p>\n<p><code>`e.hash &amp; oldCap<\/code> = <code>10000 &amp; 01111<\/code> = 00000 = 0<\/p>\n<p>\u663e\u800c\u6613\u89c1\uff0c\u5f53 hash \u503c\u4e8c\u8fdb\u5236\u7684\u6700\u9ad8\u4f4d\u4e3a 0 \u7684\u65f6\u5019\uff0c\u548c oldCap \u8fdb\u884c\u4e0e\u8fd0\u7b97\u540e\uff0c\u7ed3\u679c\u5fc5\u5b9a\u4e3a0<\/p>\n<p><strong>\u4f46\u662f\u8fd9\u4e2a\u548c\u6269\u5bb9\u540e\u4f4d\u7f6e\u6709\u4ec0\u4e48\u5173\u7cfb\u5462\uff1f<\/strong>\u6211\u4eec\u77e5\u9053\uff0c\u6269\u5bb9\u662f\u6269\u4e3a\u539f\u6765\u7684\u4e24\u500d\u7684\uff0c\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u770b\u4e0b\uff0c\u8ba1\u7b97\u6269\u5bb9\u540e\u8be5Node \u8282\u70b9\u5e94\u8be5\u5728\u54ea\u4e2a\u65b0\u4f4d\u7f6e\u3002<\/p>\n<p>\u8ba1\u7b97\u6269\u5bb9\u540e\u7684\u4f4d\u7f6e\uff0c\u6211\u4eec\u77e5\u9053\u662f\u8fd9\u6837\u7684\uff0c\u300chash \u503c &#038; \u6570\u7ec4\u957f\u5ea6\u51cf\u4e00\u300d\u7684\u8fd0\u7b97\u7ed3\u679c\uff0c\u5c31\u662f\u6211\u4eec\u9700\u8981\u7684\u6570\u7ec4\u4e0b\u6807\u3002<\/p>\n<p>\u6269\u5bb9\u540e\u7684\u5e94\u8be5\u5728\u7684\u4f4d\u7f6e\uff08oldCap \u662f 16\uff0c2 \u500d\u5c31\u662f32\uff0c32 \u5bf9\u5e94\u4e8c\u8fdb\u5236 100000\uff0c\u51cf\u4e00\u64cd\u4f5c\u540e\u4e3a 011111\uff09\uff1a<\/p>\n<p><code>hash &amp; 2 \u00d7 oldCap - 1<\/code> = <code>01111 &amp; 011111<\/code> = <code>01111<\/code><\/p>\n<p>\u90a3\u6ca1\u6269\u5bb9\u4e4b\u524d\u7684\u4f4d\u7f6e\u5728\u90a3\u91cc\uff1f\u6211\u4eec\u8ba1\u7b97\u4e0b\uff1a<\/p>\n<p><code>hash &amp; oldCap - 1<\/code> = <code>01111 &amp; 01111<\/code> = <code>01111<\/code><\/p>\n<p>\u6240\u4ee5\uff0c\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u6b64\u65f6\u6269\u5bb9\u540e\u548c\u6269\u5bb9\u524d\uff0c\u8be5\u5143\u7d20\u7684\u4f4d\u7f6e\u6ca1\u6709\u53d1\u751f\u53d8\u5316\u3002 \u56e0\u6b64\uff0c\u624d\u6709\u8fd9\u4e2a\u7ed3\u8bba\uff1a<strong>\u8fd0\u7b97\u7ed3\u679c\u4e3a 0 \u7684\u8bdd\uff0c\u90a3\u4e48\u653e\u5165\u65b0\u6570\u7ec4\u7684\u4f4d\u7f6e\u548c\u539f\u6570\u7ec4\u7684\u4f4d\u7f6e\u662f\u4e00\u6837\u7684<\/strong>\u3002<\/p>\n<p><strong>\u4f55\u65f6\u8fd9\u4e2a\u64cd\u4f5c\u4e0d\u7b49\u4e8e 0 \uff1f<\/strong><\/p>\n<p>\u540c\u6837\uff0c\u4ece oldCap \u5165\u624b\uff0c\u5047\u8bbe\u6b64\u65f6 oldCap \u662f16\uff0c\u5bf9\u5e94\u4e8c\u8fdb\u5236\u4e3a <code>10000<\/code><\/p>\n<p>\u5982\u679c\u6211\u4eec\u60f3 <code>e.hash &amp; oldCap<\/code> \u4e0d\u7b49\u4e8e 0\uff0c\u90a3\u4e48<strong>\u8be5 Key \u7684 hash \u503c\u7684\u4e8c\u8fdb\u5236\u6700\u9ad8\u4f4d\u5fc5\u987b\u4e3a 1<\/strong>\uff0c\u5269\u4e0b\u7684\u4e8c\u8fdb\u5236\u4f4d\u53ef\u4ee5\u4e0d\u7ba1\uff0c\u8fd9\u6837\u8fdb\u884c\u4e0e\u8fd0\u7b97\u540e\u7684\u7ed3\u679c\u80af\u5b9a\u662f<strong>\u4e0d\u7b49\u4e8e<\/strong> 0 \u7684\u3002<\/p>\n<p>\u8fd8\u662f\u4e00\u6837\uff0c\u4e3e\u4f8b\u5b50\uff0c\u5047\u8bbe hash \u503c\u5bf9\u5e94\u7684\u4e8c\u8fdb\u5236\u4e3a <code>10001<\/code>\uff0c\u90a3\u4e48\u548c oldCap \u8fdb\u884c\u4e0e\u8fd0\u7b97\uff1a<\/p>\n<p><code>e.hash &amp; oldCap<\/code> = <code>10001 &amp; 10000<\/code> = 10000 = 16 \u2260 0<\/p>\n<p>\u663e\u800c\u6613\u89c1\uff0chash \u503c\u4e8c\u8fdb\u5236\u7684\u6700\u9ad8\u4f4d\u4e3a 1\uff0c\u90a3\u4e48\u8be5\u7ed3\u679c\u5fc5\u5b9a\u4e0d\u4e3a 0<\/p>\n<p><strong>\u540c\u7406\uff0c\u6765\u770b\u4e0b\u6269\u5bb9\u524d\u540e\u7684\u4f4d\u7f6e\u5173\u7cfb\u3002<\/strong><\/p>\n<p>\u6269\u5bb9\u524d\u7684\u4f4d\u7f6e\uff1a<\/p>\n<p><code>hash &amp; oldCap - 1<\/code> = <code>10001 &amp; 01111<\/code> = <code>00001<\/code> = 1 <\/p>\n<p>\u6269\u5bb9\u540e\u7684\u4f4d\u7f6e\uff1a<\/p>\n<p><code>hash &amp; 2 \u00d7 oldCap - 1<\/code> = <code>10001 &amp; 011111<\/code> = <code>10001<\/code> = 17<\/p>\n<p>\u5b83\u4eec\u4e4b\u95f4\u6709\u4e00\u79cd\u5de7\u5999\u7684\u5173\u7cfb\uff0c\u5c31\u662f\uff1a\u300c\u6269\u5bb9\u540e\u7684\u4f4d\u7f6e\u300d\u4f1a\u7b49\u4e8e\u300c\u6269\u5bb9\u524d\u7684\u4f4d\u7f6e\u300d\u52a0\u4e0a\u300c\u6269\u5bb9\u524d\u7684\u6570\u7ec4\u5bb9\u91cf\u300d\uff0c\u4e5f\u5c31\u662f\u8bf4 <code>10001(\u6269\u5bb9\u540e\u7684\u4f4d\u7f6e) = 1(\u6269\u5bb9\u524d\u7684\u4f4d\u7f6e) + 10000(\u6269\u5bb9\u524d\u7684\u6570\u7ec4\u5bb9\u91cf\uff0c16)<\/code><\/p>\n<p>\u6240\u4ee5\uff0c\u624d\u6709\u8fd9\u4e2a\u7ed3\u8bba\uff1a<strong>\u8fd0\u7b97\u7ed3\u679c\u4e0d\u4e3a 0 \u7684\u8bdd\uff0c\u90a3\u4e48\u5c31\u9700\u8981\u91cd\u65b0\u8ba1\u7b97\u4f4d\u7f6e\uff08\u65b0\u4f4d\u7f6e\uff1a\u6240\u5728\u7684\u539f\u6570\u7ec4\u4f4d\u7f6e\u4e0b\u6807\u52a0\u4e0a\u539f\u6570\u7ec4\u5bb9\u91cf\uff08\u957f\u5ea6\uff09\uff09<\/strong>\u3002<\/p>\n<h3>\u5173\u4e8e\u7ea2\u9ed1\u6811<\/h3>\n<p>\u5f85\u5b8c\u5584\uff0c\u7b49\u7740\u586b\u5751\u3002<\/p>\n<h3>1.8 \u603b\u7ed3<\/h3>\n<p>\u5728 1.8 \u7684 HashMap\u4e2d\uff0c\u5e95\u5c42\u662f Node \u7c7b\u578b\u7684\u6570\u7ec4 + Node \u7c7b\u578b\u7684\u94fe\u8868 \u6216\u8005 + Node \u7c7b\u578b\u7684\u7ea2\u9ed1\u6811\u3002<\/p>\n<p>\u6bd4\u8d77 1.7 \u6765\u8bf4\uff0c\u53d8\u5316\u8fd8\u662f\u633a\u591a\u7684\uff0c\u6e90\u7801\u7684\u5199\u6cd5\u4e5f\u53d8\u5f97\u66f4\u52a0\u9ad8\u7ea7\uff0c\u5f53\u7136\u6548\u7387\u4e5f\u53d8\u5f97\u66f4\u9ad8\u4e86\uff0c\u5f15\u5165\u4e86\u7ea2\u9ed1\u6811\u63d0\u9ad8\u67e5\u627e\u6548\u7387\u3002\u56e0\u4e3a\u5f15\u5165\u4e86\u7ea2\u9ed1\u6811\uff0c\u6240\u4ee5\u89e3\u51b3\u51b2\u7a81\u7684\u65f6\u5019\uff0c\u5c31\u6709\u4e9b\u533a\u522b\u4e86\u3002<\/p>\n<p>\u5982\u679c\u5f53\u8981\u5b58\u50a8\u7684 Key-Value \u7684 Key \u4e0e\u5f53\u524d\u4f4d\u7f6e\u4e0a\u7684 Key \u53d1\u751f\u51b2\u7a81\uff0c\u90a3\u4e48\u5c31\u9700\u8981\u8fdb\u884c\u5c3e\u63d2\u6cd5\uff081.7 \u5c31\u662f\u5934\u63d2\u6cd5\uff09\uff0c\u5c06\u8be5 Key \u63d2\u5165\u5f53\u524d\u54c8\u5e0c\u6876\u5bf9\u5e94\u7684\u94fe\u8868\uff0c\u5f53\u8fd9\u4e2a\u94fe\u8868\u7684\u957f\u5ea6\u5927\u4e8e 8 \u4e14\u6570\u7ec4\u957f\u5ea6\u5927\u4e8e\u7b49\u4e8e 64 \u65f6\uff0c\u5f53\u524d\u94fe\u8868\u5c31\u4f1a\u6811\u5316\uff0c\u8f6c\u6210\u7ea2\u9ed1\u6811\uff0c\u5f53\u7ea2\u9ed1\u6811\u4e2d\u7684\u5143\u7d20\u5c0f\u4e8e 6 \u65f6\uff0c\u90a3\u4e48\u5c31\u4f1a\u9000\u5316\u56de\u6765\u6210\u4e3a\u94fe\u8868\u3002\u5982\u679c\u4ec5\u4ec5\u94fe\u8868\u957f\u5ea6\u5927\u4e8e 8\uff0c\u4f46\u662f\u6570\u7ec4\u957f\u5ea6\u5c0f\u4e8e 64\uff0c\u90a3\u4e48\u5c31\u53ea\u4f1a\u8fdb\u884c\u6269\u5bb9\uff0c\u4e0d\u4f1a\u628a\u94fe\u8868\u6811\u5316\uff08\u8fd9\u90e8\u5206\u7684\u6e90\u7801\u5728 <code>treeifyBin()<\/code> \u65b9\u6cd5\u4e2d\uff09\u3002<\/p>\n<h2>\u7ed3\u8bed<\/h2>\n<p>\u4ee5\u4e0a\uff0c\u5c31\u662f\u6d45\u5165\u6d45\u51fa 1.7 \u548c 1.8 \u7684 HashMap\uff01<\/p>\n<h2>\u6700\u540e\u7684\u6700\u540e<\/h2>\n<p><strong>\u7531\u672c\u4eba\u6c34\u5e73\u6240\u9650\uff0c\u96be\u514d\u6709\u9519\u8bef\u4ee5\u53ca\u4e0d\u8db3\u4e4b\u5904\uff0c <code>\u5c4f\u5e55\u524d\u7684\u9753\u4ed4\u9753\u5973\u4eec<\/code> \u5982\u6709\u53d1\u73b0\uff0c\u6073\u8bf7\u6307\u51fa\uff01<\/strong><\/p>\n<p><strong>\u6700\u540e\uff0c\u8c22\u8c22\u4f60\u770b\u5230\u8fd9\u91cc\uff0c\u8c22\u8c22\u4f60\u8ba4\u771f\u5bf9\u5f85\u6211\u7684\u52aa\u529b\uff0c\u5e0c\u671b\u8fd9\u7bc7\u535a\u5ba2\u5bf9\u4f60\u6709\u6240\u5e2e\u52a9\uff01<\/strong><\/p>\n<p><strong>\u4f60\u8f7b\u8f7b\u5730\u70b9\u4e86\u4e2a\u8d5e\uff0c\u90a3\u5c06\u5728\u6211\u7684\u5fc3\u91cc\u4e16\u754c\u589e\u6dfb\u4e00\u9897\u660e\u4eae\u800c\u8000\u773c\u7684\u661f\uff01<\/strong><\/p>\n<p><a href=\"https:\/\/segmentfault.com\/a\/1190000042929803\">https:\/\/segmentfault.com\/a\/1190000042929803<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u524d\u8a00 HashMap \u662f\u6211\u4eec\u6700\u6700\u6700\u5e38\u7528\u7684\u4e1c\u897f\u4e86\uff0c\u5b83\u5c31\u662f\u6211\u4eec\u5728\u5927\u5b66\u4e2d\u5b66\u4e60\u6570\u636e\u7ed3\u6784\u7684\u65f6\u5019\uff0c\u5b66\u5230\u7684\u54c8\u5e0c\u8868\u8fd9\u79cd\u6570\u636e\u7ed3\u6784 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-10006940","post","type-post","status-publish","format-standard","hentry","category-share"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10006940","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=10006940"}],"version-history":[{"count":0,"href":"https:\/\/itmax.cn\/index.php?rest_route=\/wp\/v2\/posts\/10006940\/revisions"}],"wp:attachment":[{"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=10006940"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=10006940"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itmax.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=10006940"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}