{"id":4788,"date":"2020-02-16T14:40:38","date_gmt":"2020-02-16T06:40:38","guid":{"rendered":"https:\/\/www.xttblog.com\/?p=4788"},"modified":"2020-02-16T14:40:38","modified_gmt":"2020-02-16T06:40:38","slug":"java-map-%e6%89%a9%e5%ae%b9%e6%97%b6%ef%bc%8c%e4%b8%ba%e4%bb%80%e4%b9%88%e6%8e%a8%e8%8d%90%e6%98%af2%e7%9a%84%e5%b9%82","status":"publish","type":"post","link":"https:\/\/www.xttblog.com\/?p=4788","title":{"rendered":"Java Map \u6269\u5bb9\u65f6\uff0c\u4e3a\u4ec0\u4e48\u63a8\u8350\u662f2\u7684\u5e42"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">\u5173\u4e8e Java \u96c6\u5408\u7684\u9762\u8bd5\u9898\u7f51\u4e0a\u4e5f\u6709\u5f88\u591a\uff0c\u5f88\u591a\u90fd\u662f\u57fa\u4e8e\u6e90\u7801\u7684\u89e3\u6bd2\u3002\u4f46\u6709\u65f6\u5019\u9762\u8bd5\u5b98\u4f1a\u51fa\u5176\u4e0d\u610f\uff0c\u95ee\u4e00\u4e9b\u8bbe\u8ba1\u65b9\u9762\u7684\u95ee\u9898\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6bd4\u5982\uff0c\u6211\u4eec\u4eca\u5929\u6807\u9898\u8981\u8ba8\u8bba\u7684\uff0cJava \u4e2d\u5e38\u89c1\u7684 HashMap \u7b49 Map \u7c7b\u96c6\u5408\uff0c\u5728\u6269\u5bb9\u65f6\uff0c\u4e3a\u4ec0\u4e48\u662f 2 \u500d\uff0c\u800c\u4e0d\u662f 1.5 \u500d\uff0c3 \u500d\uff0c10 \u500d\u7b49\u3002\u8fd9\u4e48\u8bbe\u8ba1\u6709\u4ec0\u4e48\u610f\u4e49\u5417\uff1f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5f53 map \u4e2d\u5305\u542b\u7684 Entry \u7684\u6570\u91cf\u5927\u4e8e\u7b49\u4e8e threshold = loadFactor * capacity \u7684\u65f6\u5019\uff0c\u4e14\u65b0\u5efa\u7684 Entry \u521a\u597d\u843d\u5728\u4e00\u4e2a\u975e\u7a7a\u7684\u6876\u4e0a\uff0c\u6b64\u523b\u89e6\u53d1\u6269\u5bb9\u673a\u5236\uff0c\u5c06\u5176\u5bb9\u91cf\u6269\u5927\u4e3a 2 \u500d\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u4e2a 2 \u662f\u6709\u4e00\u4e9b\u7279\u6b8a\u7684\u610f\u4e49\u7684\u3002\u6211\u4eec\u5148\u4ece\u4e00\u4e9b\u6e90\u7801\u4e2d\u770b\u51fa\u8fd9\u4e9b\u8bbe\u8ba1\u7684\u5de7\u5999\u4e4b\u5904\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/**\n * The default initial capacity - MUST be a power of two.\n *\/\nstatic final int DEFAULT_INITIAL_CAPACITY = 16;<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>public HashMap(int initialCapacity, float loadFactor) {\n    if (initialCapacity &lt; 0)\n        throw new IllegalArgumentException(\"Illegal initial capacity: \" +\n                                           initialCapacity);\n    if (initialCapacity &gt; MAXIMUM_CAPACITY)\n        initialCapacity = MAXIMUM_CAPACITY;\n    if (loadFactor &lt;= 0 || Float.isNaN(loadFactor))\n        throw new IllegalArgumentException(\"Illegal load factor: \" +\n                                           loadFactor);\n\n    \/\/ Find a power of 2 &gt;= initialCapacity \u627e\u5230\u4e00\u4e2a\u5927\u4e8e\u7b49\u4e8e\u521d\u59cb\u5bb9\u91cf\u7684\u4e14\u662f2\u7684\u5e42\u7684\u6570\u4f5c\u4e3a\u5b9e\u9645\u5bb9\u91cf\n    int capacity = 1;\n    while (capacity &lt; initialCapacity)\n        capacity &lt;&lt;= 1;\n\n    this.loadFactor = loadFactor;\n    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);\n    table = new Entry[capacity];\n    useAltHashing = sun.misc.VM.isBooted() &amp;&amp;\n            (capacity &gt;= Holder.ALTERNATIVE_HASHING_THRESHOLD);\n    init();\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u901a\u8fc7\u4ee5\u4e0a\u6211\u4eec\u77e5\u9053 HashMap \u7684\u5bb9\u91cf\u5fc5\u987b\u662f 2 \u7684\u5e42\uff0c\u90a3\u4e48\u4e3a\u4ec0\u4e48\u8981\u8fd9\u4e48\u8bbe\u8ba1\u5462\uff1f\u7b54\u6848\u5f53\u7136\u662f\u4e3a\u4e86\u6027\u80fd\u3002\u5728 HashMap \u901a\u8fc7\u952e\u7684\u54c8\u5e0c\u503c\u8fdb\u884c\u5b9a\u4f4d\u6876\u4f4d\u7f6e\u7684\u65f6\u5019\uff0c\u8c03\u7528\u4e86\u4e00\u4e2a indexFor(hash, table.length); \u65b9\u6cd5\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/**\n * Returns index for hash code h.\n *\/\nstatic int indexFor(int h, int length) {\n    return h &amp; (length-1);\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u53ef\u4ee5\u770b\u5230\u8fd9\u91cc\u662f\u5c06\u54c8\u5e0c\u503c h \u4e0e\u6876\u6570\u7ec4\u7684 length-1\uff08\u5b9e\u9645\u4e0a\u4e5f\u662f map \u7684\u5bb9\u91cf-1\uff09\u8fdb\u884c\u4e86\u4e00\u4e2a\u4e0e\u64cd\u4f5c\u5f97\u51fa\u4e86\u5bf9\u5e94\u7684\u6876\u7684\u4f4d\u7f6e\uff0ch &amp; (length-1)\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4f46\u662f\u4e3a\u4ec0\u4e48\u4e0d\u91c7\u7528 h % length \u8fd9\u79cd\u8ba1\u7b97\u65b9\u5f0f\u5462\uff1f<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u90a3\u662f\u56e0\u4e3a Java \u4e2d\u7684 %\u3001\/ \u64cd\u4f5c\u6bd4 &amp; \u6162 10 \u500d\u5de6\u53f3\uff0c\u56e0\u6b64\u91c7\u7528 &amp; \u8fd0\u7b97\u4f1a\u63d0\u9ad8\u6027\u80fd\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u901a\u8fc7\u9650\u5236 length \u662f\u4e00\u4e2a 2 \u7684\u5e42\u6570\uff0ch &amp; (length-1) \u548c h % length \u7ed3\u679c\u662f\u4e00\u81f4\u7684\u3002\u8fd9\u5c31\u662f\u4e3a\u4ec0\u4e48\u8981\u9650\u5236\u5bb9\u91cf\u5fc5\u987b\u662f\u4e00\u4e2a 2 \u7684\u5e42\u7684\u539f\u56e0\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e3e\u4e2a\u7b80\u5355\u7684\u4f8b\u5b50\u8bf4\u660e\u8fd9\u4e24\u4e2a\u64cd\u4f5c\u7684\u7ed3\u679c\u4e00\u81f4\u6027\uff1a<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5047\u8bbe\u6709\u4e2a hashcode \u662f 311\uff0c\u5bf9\u5e94\u7684\u4e8c\u8fdb\u5236\u662f(1 0011 0111)\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">length \u4e3a 16\uff0c\u5bf9\u5e94\u7684\u4e8c\u8fdb\u5236\u4f4d (1 0000)\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>%\u64cd\u4f5c\uff1a311 = 16*19 + 7\uff1b\u6240\u4ee5\u7ed3\u679c\u4e3a7\uff0c\u4e8c\u8fdb\u5236\u4f4d(0111)\uff1b<\/li><li>&amp;\u64cd\u4f5c\uff1a(1 0011 0111) &amp; (0111) = 0111 = 7, \u4e8c\u8fdb\u5236\u4f4d(0111)<\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">1 0011 0111 = (1 0011 0000) + (0111) = (1<em>2^4 + 1<\/em> 2^5 + 0<em>2^6 + 0<\/em>2^7 + 1<em>2^8 ) + 7 = 2^4<\/em>(1 + 2 + 0 + 0 + 16) + 7 = 16 * 19 + 7; \u548c % \u64cd\u4f5c\u4e00\u81f4\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5982\u679c length \u662f\u4e00\u4e2a 2 \u7684\u5e42\u7684\u6570\uff0c\u90a3\u4e48 length-1 \u5c31\u4f1a\u53d8\u6210\u4e00\u4e2a mask, \u5b83\u4f1a\u5c06 hashcode \u4f4e\u4f4d\u53d6\u51fa\u6765\uff0chashcode \u7684\u4f4e\u4f4d\u5b9e\u9645\u5c31\u662f\u4f59\u6570\uff0c\u548c\u53d6\u4f59\u64cd\u4f5c\u76f8\u6bd4\uff0c\u4e0e\u64cd\u4f5c\u4f1a\u5c06\u6027\u80fd\u63d0\u5347\u5f88\u591a\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u53c2\u8003\u8d44\u6599<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/bugs.java.com\/bugdatabase\/view_bug.do?bug_id=4631373\" target=\"_blank\" rel=\"noreferrer noopener\" aria-label=\"JDK-4631373 : Integer division and modulo operations are very slow\uff08\u5728\u65b0\u7a97\u53e3\u6253\u5f00\uff09\">JDK-4631373 : Integer division and modulo operations are very slow<\/a><\/li><\/ul>\n<!-- <audio autoplay=\"autoplay\" height=\"100\" width=\"100\" hidden=\"true\"><source src=\"https:\/\/c.coka.la\/orAvPR.mp3\" type=\"audio\/mp3\"\/><\/audio><img decoding=\"async\" src=\"https:\/\/images.weserv.nl\/?url=https:\/\/ws3.sinaimg.cn\/large\/8fa5dcfcgy1g4em3rzar5j20ib089ae0.jpg\" alt=\"\u4e1a\u4f59\u8349\u516c\u4f17\u53f7\"\/> --><p><!-- <img decoding=\"async\" src=\"https:\/\/raw.githubusercontent.com\/xmt1139057136\/xttblog\/master\/8fa5dcfcgy1g4em3rzar5j20ib089ae0.jpg\" alt=\"\u4e1a\u4f59\u8349\u516c\u4f17\u53f7\"\/>--><img decoding=\"async\" src=\"https:\/\/saas.51autoparts.cn\/api\/admin\/sys-file\/oss\/file?fileName=84db51f8561e448f9a4fda2eff0811f9.jpg\" alt=\"\u4e1a\u4f59\u8349\u516c\u4f17\u53f7\"\/><\/p><p>\u6700\u540e\uff0c\u6b22\u8fce\u5173\u6ce8\u6211\u7684\u4e2a\u4eba\u5fae\u4fe1\u516c\u4f17\u53f7\uff1a\u4e1a\u4f59\u8349\uff08yyucao\uff09\uff01<b>\u53ef\u52a0\u4f5c\u8005\u5fae\u4fe1\u53f7\uff1a<font color=\"red\">xttblog2<\/font>\u3002\u5907\u6ce8\uff1a\u201c1\u201d\uff0c\u6dfb\u52a0\u535a\u4e3b\u5fae\u4fe1\u62c9\u4f60\u8fdb\u5fae\u4fe1\u7fa4\u3002\u5907\u6ce8\u9519\u8bef\u4e0d\u4f1a\u540c\u610f\u597d\u53cb\u7533\u8bf7\u3002<\/b>\u518d\u6b21\u611f\u8c22\u60a8\u7684\u5173\u6ce8\uff01\u540e\u7eed\u6709\u7cbe\u5f69\u5185\u5bb9\u4f1a\u7b2c\u4e00\u65f6\u95f4\u53d1\u7ed9\u60a8\uff01\u539f\u521b\u6587\u7ae0\u6295\u7a3f\u8bf7\u53d1\u9001\u81f3532009913@qq.com\u90ae\u7bb1\u3002\u5546\u52a1\u5408\u4f5c\u4e5f\u53ef\u6dfb\u52a0\u4f5c\u8005\u5fae\u4fe1\u8fdb\u884c\u8054\u7cfb\uff01<\/p><p>\u672c\u6587\u539f\u6587\u51fa\u5904\uff1a<a href=\"https:\/\/www.xttblog.com\">\u4e1a\u4f59\u8349<\/a>\uff1a &raquo; <a href=\"https:\/\/www.xttblog.com\/?p=4788\">Java Map \u6269\u5bb9\u65f6\uff0c\u4e3a\u4ec0\u4e48\u63a8\u8350\u662f2\u7684\u5e42<\/a><\/p><!-- <div class=\"bd-reward-stl\"><button id=\"bdRewardBtn\"><span><\/span><\/button><\/div> -->","protected":false},"excerpt":{"rendered":"<p>\u5173\u4e8e Java \u96c6\u5408\u7684\u9762\u8bd5\u9898\u7f51\u4e0a\u4e5f\u6709\u5f88\u591a\uff0c\u5f88\u591a\u90fd\u662f\u57fa\u4e8e\u6e90\u7801\u7684\u89e3\u6bd2\u3002\u4f46\u6709\u65f6\u5019\u9762\u8bd5\u5b98\u4f1a\u51fa\u5176\u4e0d\u610f\uff0c\u95ee\u4e00\u4e9b\u8bbe\u8ba1\u65b9\u9762\u7684\u95ee [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[1741,1164,1161,1163,1743],"class_list":["post-4788","post","type-post","status-publish","format-standard","hentry","category-java","tag-arraylist","tag-concurrenthashmap","tag-hashmap","tag-linkedhashmap","tag-linkedlist"],"_links":{"self":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/4788","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4788"}],"version-history":[{"count":1,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/4788\/revisions"}],"predecessor-version":[{"id":4789,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=\/wp\/v2\/posts\/4788\/revisions\/4789"}],"wp:attachment":[{"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4788"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4788"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xttblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4788"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}