{"id":1137,"date":"2017-12-05T17:32:35","date_gmt":"2017-12-05T09:32:35","guid":{"rendered":"http:\/\/blog.xiunian.wang\/?p=1137"},"modified":"2021-09-23T00:28:25","modified_gmt":"2021-09-22T16:28:25","slug":"hashmap%e7%9a%84%e5%ae%9e%e7%8e%b0%e5%8e%9f%e7%90%86","status":"publish","type":"post","link":"https:\/\/blog.xiunian.wang\/?p=1137","title":{"rendered":"HashMap\u7684\u5b9e\u73b0\u539f\u7406"},"content":{"rendered":"

\u63a5\u7740\u6628\u5929\u7684\u95ee\u9898<\/h3>\n

-HashMap \u7528\u7684\u591a\u5417\uff1f
\n– \u55ef\u633a\u591a\u7684
\n– \u80fd\u8bf4\u8bf4\u5176\u539f\u7406\u5417\uff1f
\n– HashMap \u662f\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7Key \u6765\u5b58\u50a8\u4e00\u4e9bvalue\u3002 \u5229\u7528Key\u7684HashCode \u505a\u4e3a\u5185\u5b58\u5730\u5740\uff0c\u4ee5\u4fbf\u4e8e\u5f88\u5feb\u7684\u67e5\u627e\u5230\u5bf9\u5e94\u7684Value\u3002
\n– \u4ec0\u4e48\u5185\u5b58\u5730\u5740\uff1f
\n– \u5c31\u662fjava\u865a\u62df\u673a\u4e2d\u7684\u5185\u5b58\u554a\uff0c\u4e0d\u77e5\u9053\u662f\u5806\u8fd8\u662f\u6808
\n– \u554a\uff1f\uff1f\uff1f\uff08\u5fc3\u91cc\u6d3b\u52a8\uff1a\u5988\u52d2\u4e2a\u86cb\uff0c\u4e00\u672c\u6b63\u7ecf\u7684\u80e1\u8bf4\u516b\u9053\uff09\u597d\u6211\u4eec\u4e0d\u8bf4\u8fd9\u4e2a\uff0c\u90a3\u4f60\u8bf4\u5230HashCode \uff0c\u8bf7\u95eeHashCode \u6709\u53ef\u80fd\u53d1\u751f\u78b0\u649e\u5417\uff1f
\n– \u5f53\u7136\u4f1a\uff08hashCode \u8fd4\u56de\u7684\u4e5f\u5c31\u662fint \u884c\uff0c\u6700\u591a\u4e5f\u5c31\u662f2\u768432\u6b21\u65b9\u4e2a\u3002\u603b\u662f\u6709\u9650\u7684\u561b\uff0c\u800c\u6211\u4eec\u7684\u5bf9\u8c61\u53ef\u4ee5\u65e0\u9650\u5236\u521b\u5efa\uff0c\u867d\u7136\u6211\u8fd8\u6ca1\u6709\u5bf9\u8c61\uff09
\n– \u90a3HashMap\u662f\u5982\u4f55\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u7684\u5462\u3002
\n– \u989d\uff0c\u8fd9\u4e2a\u51e0\u7387\u4f1a\u5f88\u5c0f\u5427\uff0c\u53ef\u80fd\u9700\u8981\u6211\u4eec\u91cd\u5199\u4e00\u4e0bkey\u7684hashCode\uff0c\u56e0\u4e3aKey \u4e5f\u662fObject\u7c7b\u7684\u5b50\u7c7b\u5427\u3002\u6240\u4ee5\u53ef\u4ee5\u91cd\u5199\uff0c\u989d\u3002\u3002\u3002
\n– \u3002\u3002\u3002\u3002<\/p>\n

\u627f\u8ba4\uff0c\u6ca1\u770b\u8fc7HashMap \u6e90\u7801\uff0c\u6211\u7684\u9519\u3002\u6211\u5e94\u8be5\u76f4\u63a5\u8bf4\u6ca1\u770b\u8fc7\u7684\u3002\u5c34\u5c2c\u3002
\n\u90a3\u4eca\u5929\u6765\u5177\u4f53\u770b\u4e00\u4e0b \u3002
\n\u8bf4\u70b9\u7b80\u5355\u7684\uff0cHashMap \u600e\u4e48\u5b58\u50a8\u6211\u4eec\u7684 Key Value\uff0c\u4eceput \u65b9\u6cd5\u5f00\u59cb\u8ddf\u8e2a\u3002<\/p>\n

public V put(K key, V value) {\nreturn putVal(hash(key), key, value, false, true);\n}<\/pre>\n
\u4e00\u4e2ahash \u51fd\u6570\u3002\uff08\u8fd9\u4e2a\u6709\u5174\u8da3\u53ef\u4ee5\u518d\u770b\u770b\u662f\u600e\u4e48\u7b97\u7684,\u6211\u5199\u5b8c\u8fd9\u4e2a\u518d\u53bb\u770b\u770b) \u7b97\u51fa\u4e86Hash.
\n<\/p>\n
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,\n                   boolean evict) {\n        Node<K,V>[] tab; Node<K,V> p; int n, i;\n        if ((tab = table) == null || (n = tab.length) == 0)\n            n = (tab = resize()).length;\n        if ((p = tab[i = (n - 1) & hash]) == null)\n            tab[i] = newNode(hash, key, value, null);\n        else {\n            Node<K,V> e; K k;\n            if (p.hash == hash &&\n                ((k = p.key) == key || (key != null && key.equals(k))))\n                e = p;\n            else if (p instanceof TreeNode)\n                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);\n            else {\n                for (int binCount = 0; ; ++binCount) {\n                    if ((e = p.next) == null) {\n                        p.next = newNode(hash, key, value, null);\n                        if (binCount >= TREEIFY_THRESHOLD - 1) \/\/ -1 for 1st\n                            treeifyBin(tab, hash);\n                        break;\n                    }\n                    if (e.hash == hash &&\n                        ((k = e.key) == key || (key != null && key.equals(k))))\n                        break;\n                    p = e;\n                }\n            }\n-----<\/pre>\n
\u786e\u5b9e\uff0cKey Value \u7b49\u4fe1\u606f\u4f5c\u4e3a\u4e00\u4e2aNode \u653e\u5230\u4e86\u4e00\u4e2a Node\u7684\u6570\u7ec4\u91cc\u9762\u3002\u5982\u679c\u51fa\u73b0\u6211\u4eec\u4e0a\u9762\u8bf4\u7684\u90a3\u79cd\u60c5\u51b5\uff0ckey \u4e0d\u4e00\u6837\uff0c\u4f46\u662f\u5176hash \u4e00\u81f4\u7684\u60c5\u51b5\u4e0b\uff0c\uff08\u5047\u8bbe\u4e4b\u524d\u5b58\u5728\u4e86\u4e00\u5065\u503c\u5bf9\uff09 \u8fd9\u65f6\u5019\u6211\u4eec\u53bb\u770b \u4e0a\u8ff0\u4ee3\u7801\u4e2d\u7684 p\uff0c\u901a\u8fc7\u4e00\u4e2afor\u5faa\u73af\u627e\u5230Node\u7684\u94fe\u8868<\/b>\u7684\u7ed3\u5c3e\u3002\u7136\u540e\u628a\u6211\u4eec\u7684\u65b0\u7684Node\u6302\u5230\u4e0a\u9762\u8fd9\u65f6\u5019\u770b\u8d77\u6765\u60f3\u8fd9\u4e2a\u6837\u5b50\"\"<\/p>\n
\u6211\u4eec\u53ef\u4ee5\u770b\u5230\u6a2a\u6392\u5c31\u662f\u6570\u7ec4\uff08\u5ffd\u7565\u524d\u9762Node1\uff09\uff0c\u7ad6\u6392\u5c31\u662f\u540c\u4e00\u4e2ahashCode \u5bf9\u5e94\u7684\u4e0d\u540cNode\u3002<\/p>\n
Node \u662f\u4ec0\u4e48 \uff0c\u6211\u4eec\u53ef\u4ee5\u770b\u5230\u5176\u5b9e\u5c31\u662f\u5bf9Key Value\u7684\u4e00\u4e2a\u5c01\u88c5\uff0c\u5b9e\u73b0\u4e86Entry\u63a5\u53e3\uff0c\u540c\u65f6Node \u4e5f\u662f\u4e00\u4e2a\u94fe\u8868\u7684\u8282\u70b9\u3002\u56e0\u6b64\uff0c\u53ef\u4ee5\u65e0\u9650\u62d3\u5c55\u4e0b\u53bb\u3002
\n\u597d\u4e86\uff0c\u5f88\u76f4\u89c2\u7684\u77e5\u9053\u4e86HashMap\u4e2d\u7684\u6570\u636e\u7ed3\u6784\u3002<\/p>\n
\u90a3\u4e48 \u95ee\u9898\u6765\u4e86 HashMap \u5982\u4f55\u67e5\u627e\u5230\u6211\u4eec\u7684Value \u7684\u5462\uff1f\u6211\u5148\u731c\u60f3\u4e00\u4e0b<\/p>\n
\u7b2c\u4e00\u6b65\uff0c\u8fd8\u662f\u8ba1\u7b97key\u7684hash<\/p>\n
\u7b2c\u4e8c\u6b65\uff0c\u7136\u540e\u7528hash \u53bb\u904d\u5386Node \u6570\u7ec4<\/del>\uff0c\u5bf9\u6bd4\u5176Node \u4e2d\u5b58\u50a8\u7684hash\u662f\u5426\u4e00\u81f4
\n\u4fee\u6b63\u4e00\u4e0b\uff0c\u8fd9\u91cc\u5e76\u4e0d\u662f\u904d\u5386\u4e86\u6570\u7ec4\uff0c\u800c\u662f\u76f4\u63a5\u7528hashcode \u548c\u6570\u7ec4\u7684\u957f\u5ea6-1 \u8fdb\u884c\u4e86 &\u8fd0\u7b97\uff0c \u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(1) ,\u904d\u5386\u7684\u8bdd\u65f6\u95f4\u590d\u6742\u5ea6\u4e45\u8fddO(n)\u4e86<\/p>\n
if ((tab = table) != null && (n = tab.length) > 0 &&\n            (first = tab[(n - 1) & hash]) != null) {\n            if (first.hash == hash && \/\/ always check first node\n                ((k = first.key) == key || (key != null && key.equals(k))))\n                return first;<\/pre>\n
\u7b2c\u4e09\u6b65\uff0c \u53d1\u73b0\u6570\u7ec4\u4e2d\u5b58\u5728\uff0c\u7136\u540e\u628aNode \u4e2d\u7684Key Value return \u51fa\u6765<\/p>\n
\u4f46\u662f\u95ee\u9898\u6765\u4e86 hashCode\u76f8\u540c\u3002\u4e5f\u5c31\u662f\u4f1a\u6709\u4e00\u4e9b\u60c5\u51b5\u662f\u4e0a\u56fe\u4e2d\u7ad6\u4e0b\u6765\u7684\u8282\u70b9\u94fe\u8868\uff0c\u5979\u4eec\u7684hash\u90fd\u662f\u4e00\u81f4\u7684\u554a\uff0c\u600e\u4e48\u529e\uff1f\u770b\u6e90\u7801\u3002\u70b9\u5f00get\u65b9\u6cd5<\/p>\n
final Node<K,V> getNode(int hash, Object key) {\n    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;\n    if ((tab = table) != null && (n = tab.length) > 0 &&\n        (first = tab[(n - 1) & hash]) != null) {\n        if (first.hash == hash && \/\/ always check first node\n            ((k = first.key) == key || (key != null && key.equals(k))))\n            return first;\n        if ((e = first.next) != null) {\n            if (first instanceof TreeNode)\n                return ((TreeNode<K,V>)first).getTreeNode(hash, key);\n            do {\n                if (e.hash == hash &&\n                    ((k = e.key) == key || (key != null && key.equals(k))))\n                    return e;\n            } while ((e = e.next) != null);\n        }\n    }\n    return null;\n}<\/pre>\n
\u4ee3\u7801\u5f88\u77ed\uff0c \u5173\u952e\u4ee3\u7801<\/p>\n
            if (first.hash == hash && \/\/ always check first node\n                ((k = first.key) == key || (key != null && key.equals(k))))\n                return first;\n\/\/\/\/\/\n                do {\n                    if (e.hash == hash &&\n                        ((k = e.key) == key || (key != null && key.equals(k))))\n                        return e;\n                } while ((e = e.next) != null);\n\/\/\/\/<\/pre>\n
\u770b\u5230\u4e86\u6ca1\uff0c\u56e0\u4e3akey\u7684hash\u76f8\u540c\uff0c\u56e0\u6b64\u5728\u7ad6\u76f4\u65b9\u5411\u53d8\u91cf\u94fe\u8868\u76f4\u63a5\u7528\u4e86key \u672c\u8eab\u6765\u5224\u65ad \u4e0d\u53ef\u80fd\u51fa\u73b0key\u76f8\u540c hashCode \u4e0d\u540c\u7684\u60c5\u51b5\uff0c\u6240\u4ee5\u4e00\u4e2akey \u53ea\u80fd\u5bf9\u5e94\u4e00\u4e2avalue\u3002 \u8fd9\u91cc\u6ce8\u610f\uff0c\u9664\u4e86== \u5224\u65ad\uff0c\u800c\u4e14\u7528\u4e86 equal \u53bb\u5224\u65ad\uff0c \u4e5f\u5c31\u662f\u8bf4\u5047\u5982\u6211\u4eec\u53ef\u4ee5\u4fee\u6539\u4e86equal\u65b9\u6cd5\uff0c\u5c06\u4f1a\u5bfc\u81f4 \u4e0d\u540c\u7684key\uff08\u6709\u53ef\u80fdhash\u76f8\u540c\uff09\uff0c\u5bf9\u5e94\u540c\u4e00\u4e2aValue\uff0c\u8fd9\u6837\u5c31\u4e0d\u5b89\u5168\u4e86\uff0c\u56e0\u6b64\uff0c\u6211\u4eec\u4e00\u822c\u7528String \u4f5c\u4e3akey \u56e0\u4e3aString \u662ffinal\u7684\u3002\u6211\u4eec\u6ca1\u6cd5\u91cd\u5199\u5176equal \u65b9\u6cd5\uff0c\u5c31\u662f\u8fd9\u4e2a\u539f\u56e0\u3002
\n\u8fd9\u5176\u4e2d\u8fd8\u6709\u51e0\u4e2a\u95ee\u9898\u3002\u6211\u61d2\u5f97\u5199\u4e86\uff0c\u5927\u5bb6\u81ea\u5df1\u60f3\u60f3\uff0c\u9f13\u52b1\u5728\u4e0b\u9762\u7559\u8a00\u53bb\u8ba8\u8bba
\n1 \u6570\u7ec4\u5b58\u50a8Node \uff0c\u800c\u6570\u7ec4\u5bb9\u91cf\u4e00\u5f00\u59cb\u5c31\u662f\u786e\u5b9a\u7684\uff0c\u90a3\u5982\u4f55\u52a8\u6001\u6dfb\u52a0\u5230\u6570\u7ec4\u7684\u5462\uff1f \u5173\u952e\u8bcd load factor
\n2 \u4e3a\u4ec0\u4e48\u8981\u7528\u6570\u7ec4\u53bb\u5b58\u50a8\uff0c\u76f4\u63a5\u7528\u94fe\u8868\u6216\u8005\u6811\u4e0d\u884c\u5417\uff1f
\n3 \u4ee3\u7801\u4e2dTreeNode \u51fa\u73b0\u4e86\u597d\u591a\u6b21\uff0c\u90a3\u662f\u4ec0\u4e48\uff1f<\/p>\n
\u4e0b\u9762\u5206\u6790View\u7684\u7ed8\u5236\u6d41\u7a0b\u3002\u3002\u3002\u3002 \u4e0d\u8981\u4ee5\u4e3a\u6211\u770b\u4e0d\u61c2\u6e90\u7801\u3002MMP<\/p>\n","protected":false},"excerpt":{"rendered":"
\u63a5\u7740\u6628\u5929\u7684\u95ee\u9898 -HashMap \u7528\u7684\u591a\u5417\uff1f – \u55ef\u633a\u591a\u7684 – \u80fd\u8bf4\u8bf4\u5176\u539f\u7406\u5417\uff1f – HashMap \u662f\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff0c\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7Key \u6765\u5b58\u50a8\u4e00\u4e9bvalue\u3002 \u5229\u7528Key\u7684HashCode \u505a\u4e3a\u5185\u5b58\u5730\u5740\uff0c\u4ee5\u4fbf\u4e8e\u5f88\u5feb\u7684\u67e5\u627e\u5230\u5bf9\u5e94\u7684Value\u3002 – \u4ec0\u4e48\u5185\u5b58\u5730\u5740\uff1f – \u5c31\u662fjava\u865a\u62df\u673a\u4e2d\u7684\u5185\u5b58\u554a\uff0c\u4e0d\u77e5\u9053\u662f\u5806\u8fd8\u662f\u6808 – \u554a\uff1f\uff1f\uff1f\uff08\u5fc3\u91cc\u6d3b\u52a8\uff1a\u5988\u52d2\u4e2a\u86cb\uff0c\u4e00\u672c\u6b63\u7ecf\u7684\u80e1\u8bf4\u516b\u9053\uff09\u597d\u6211\u4eec\u4e0d\u8bf4\u8fd9\u4e2a\uff0c\u90a3\u4f60\u8bf4\u5230HashCode \uff0c\u8bf7\u95eeHashCode \u6709\u53ef\u80fd\u53d1\u751f\u78b0\u649e\u5417\uff1f – \u5f53\u7136\u4f1a\uff08hashCode \u8fd4\u56de\u7684\u4e5f\u5c31\u662fint \u884c\uff0c\u6700\u591a\u4e5f\u5c31\u662f2\u768432\u6b21\u65b9\u4e2a\u3002\u603b\u662f\u6709\u9650\u7684\u561b\uff0c\u800c\u6211\u4eec\u7684\u5bf9\u8c61\u53ef\u4ee5\u65e0\u9650\u5236\u521b\u5efa\uff0c\u867d\u7136\u6211\u8fd8\u6ca1\u6709\u5bf9\u8c61\uff09 – \u90a3HashMap\u662f\u5982\u4f55\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u7684\u5462\u3002 – \u989d\uff0c\u8fd9\u4e2a\u51e0\u7387\u4f1a\u5f88\u5c0f\u5427\uff0c\u53ef\u80fd\u9700\u8981\u6211\u4eec\u91cd\u5199\u4e00\u4e0bkey\u7684hashCode\uff0c\u56e0\u4e3aKey \u4e5f\u662fObject\u7c7b\u7684\u5b50\u7c7b\u5427\u3002\u6240\u4ee5\u53ef\u4ee5\u91cd\u5199\uff0c\u989d\u3002\u3002\u3002 – \u3002\u3002\u3002\u3002 \u627f\u8ba4\uff0c\u6ca1\u770b\u8fc7HashMap \u6e90\u7801\uff0c\u6211\u7684\u9519\u3002\u6211\u5e94\u8be5\u76f4\u63a5\u8bf4\u6ca1\u770b\u8fc7\u7684\u3002\u5c34\u5c2c\u3002 \u90a3\u4eca\u5929\u6765\u5177\u4f53\u770b\u4e00\u4e0b \u3002 \u8bf4\u70b9\u7b80\u5355\u7684\uff0cHashMap \u600e\u4e48\u5b58\u50a8\u6211\u4eec\u7684 Key Value\uff0c\u4eceput \u65b9\u6cd5\u5f00\u59cb\u8ddf\u8e2a\u3002 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } … <\/p>\n
Continue reading “HashMap\u7684\u5b9e\u73b0\u539f\u7406”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,9],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=\/wp\/v2\/posts\/1137"}],"collection":[{"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1137"}],"version-history":[{"count":14,"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=\/wp\/v2\/posts\/1137\/revisions"}],"predecessor-version":[{"id":1662,"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=\/wp\/v2\/posts\/1137\/revisions\/1662"}],"wp:attachment":[{"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1137"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1137"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.xiunian.wang\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1137"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}