{"id":201323,"date":"2020-11-24T21:36:27","date_gmt":"2020-11-24T13:36:27","guid":{"rendered":"http:\/\/4563.org\/?p=201323"},"modified":"2020-11-24T21:36:27","modified_gmt":"2020-11-24T13:36:27","slug":"%e5%a4%a7%e4%bd%ac%e4%bb%ac%ef%bc%8c-hashmap-%e7%9a%84%e6%ba%90%e7%a0%81%e6%9c%89%e4%b8%aa%e4%b8%8d%e6%98%8e%e7%99%bd%e7%9a%84%e5%9c%b0%e6%96%b9%e6%b1%82%e5%8a%a9","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=201323","title":{"rendered":"\u5927\u4f6c\u4eec\uff0c hashmap \u7684\u6e90\u7801\u6709\u4e2a\u4e0d\u660e\u767d\u7684\u5730\u65b9\u6c42\u52a9"},"content":{"rendered":"
\n
\n
\n

\u5927\u4f6c\u4eec\uff0c hashmap \u7684\u6e90\u7801\u6709\u4e2a\u4e0d\u660e\u767d\u7684\u5730\u65b9\u6c42\u52a9 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : levizheng <\/span> <\/i> 4<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u8bf7\u95ee\u4e00\u4e0b\u3002hashmap \u5728 putVal \u7684\u65f6\u5019\uff0c\u4e3a\u4ec0\u4e48\u5728\u5f53\u524d\u7684\u8282\u70b9\u662f\u7ea2\u9ed1\u6811\u7684\u60c5\u51b5\u4e0b\uff0c\u76f4\u63a5\u63d2\u5165\u6570\u636e\u5c31\u53ef\u4ee5\uff0c\u800c\u4e0d\u662f\u50cf\u94fe\u8868\u4e00\u6837\u5148\u5faa\u73af\u904d\u5386\u5224\u65ad key \u662f\u5426\u76f8\u540c\u5462\uff1f\u6e23\u6e23\u975e\u79d1\u73ed\u5c0f\u767d\u4e0d\u61c2\u6570\u636e\u7ed3\u6784\uff0c\u6c42\u5404\u4f4d\u5927\u4f6c\u8d50\u6559<\/p>\n

if (p.hash == hash &&                 ((k = p.key) == key || (key != null && key.equals(k))))                 e = p;             else if (p instanceof TreeNode)                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);             else {                 for (int binCount = 0; ; ++binCount) {                     if ((e = p.next) == null) {                         p.next = newNode(hash, key, value, null);                         if (binCount >= TREEIFY_THRESHOLD - 1) \/\/ -1 for 1st                             treeifyBin(tab, hash);                         break;                     }                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         break;                     p = e;                 }             }   <\/code><\/pre>\n<\/p><\/div>\n
 \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (8<\/span>)        <\/div>\n
 <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : xuanbg <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u5faa\u73af\u904d\u5386\u5224\u65ad key \u662f\u5426\u76f8\u540c\u7684\u8bdd\uff0c\u8fd8\u7528\u4ec0\u4e48 hash\u2026\u2026                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : GM <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u5faa\u73af\u904d\u5386\u5224\u65ad key \u662f\u5426\u76f8\u540c\u7684\u8bdd\uff0c\u8fd8\u7528\u4ec0\u4e48 hash\u2026\u2026 +1                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : Joker123456789 <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u4f60\u518d\u770b\u4e00\u4e0b putTreeVal \u8fd9\u4e2a\u65b9\u6cd5\u7684\u6e90\u7801\u5462\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : aneureka <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u4e00\u4e0d\u5728 context \u91cc 2333\uff0c\u4f60\u53ef\u4ee5\u770b\u770b TreeNode.putTreeVal \u7684\u65b9\u6cd5\u5b9e\u73b0\uff0c\u76f2\u731c\u8fd8\u662f\u6309\u7ea2\u9ed1\u6811\u641c\u7d22\u8282\u70b9\u6765\u505a\u7684\uff08\u5f53\u7136\u4e0d\u540c\u4e8e\u7b80\u5355\u5faa\u73af\u904d\u5386\uff09\uff0c\u6709\u5219\u66ff\u6362\uff0c\u65e0\u5219\u63d2\u5165                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : Joker123456789 <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @GM 
    \u9996\u5148\u4e0d\u540c\u7684\u5bf9\u8c61\uff0chashcode \u53ef\u80fd\u4f1a\u4e00\u6837\uff0c\u8fd9\u5c31\u5bfc\u81f4\u4e86 \u4f60 put \u4e24\u4e2a\u4e0d\u540c\u7684 key \u53ef\u80fd hashcode \u4e00\u6837\uff0c\u9020\u6210\u5b58\u5230\u540c\u4e00\u4e2a\u4e0b\u6807\u91cc\u3002 \u4f46\u662f\u4f60\u660e\u660e put \u7684\u662f\u4e24\u4e2a\u4e0d\u540c\u7684 key\uff0c\u603b\u4e0d\u80fd\u76f4\u63a5\u8986\u76d6\u5427\uff0c\u6240\u4ee5 \u624d\u6709\u4e86\u6570\u7ec4+\u94fe\u8868\u7684 \u6570\u636e\u7ed3\u6784\uff0c\u5c31\u662f\u5f53 hash \u78b0\u649e\u65f6\uff0c\u5728\u540c\u4e00\u4e2a\u4e0b\u6807\u91cc \u628a\u4e24\u4e2a\u503c\u5b58\u8fdb\u53bb\u3002 \u4f46\u662f\u4e5f\u4e0d\u80fd\u76f4\u63a5\u8ffd\u52a0\u5427\uff0c\u6240\u4ee5\u9700\u8981\u5faa\u73af\u8fd9\u4e2a\u94fe\u8868\uff0c\u5224\u65ad hasncode \u548c\u503c\u662f\u5426\u90fd\u8ddf\u4f60 put \u8fdb\u6765\u7684\u8fd9\u4e2a key \u76f8\u7b49\uff0c\u5982\u679c\u76f8\u7b49\u5c31\u8986\u76d6 value\uff0c\u4e0d\u76f8\u7b49\u624d\u8ffd\u52a0\u3002<\/p>\n
    \u73b0\u5728 hashmap \u505a\u4e86\u4f18\u5316\uff0c\u5f53\u4e00\u4e2a\u4e0b\u6807\u91cc\u7684\u94fe\u8868\u8fc7\u957f\u65f6\uff0c\u4f1a\u81ea\u52a8\u8f6c\u6210\u7ea2\u9ed1\u6811\u3002                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : dasinigetudou <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 “`
     final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,<\/p>\n
    \u200b int h, K k, V v) {<\/p>\n
    \u200b Class<?> kc = null;<\/p>\n
    \u200b boolean searched = false;<\/p>\n
    \u200b TreeNode<K,V> root = (parent != null) ? root() : this;<\/p>\n
    \u200b for (TreeNode<K,V> p = root;;) {<\/p>\n
    \u200b \/\/\u6811\u7684\u6839\u8282\u70b9\u5f00\u59cb\u904d\u5386<\/p>\n
    \u200b int dir, ph; K pk;<\/p>\n
    \u200b \/\/\u6bd4\u8f83\u6839\u8282\u70b9\u7684 hash \u503c\uff0cdir \u731c\u6d4b\u662f\u51b3\u5b9a\u8282\u70b9\u63d2\u5165\u65f6\u5e94\u8be5\u63d2\u5230\u5de6\u5b50\u8282\u70b9\u8fd8\u662f\u53f3\u5b50\u8282\u70b9<\/p>\n
    \u200b if ((ph = p.hash) > h)<\/p>\n
    \u200b dir = -1;<\/p>\n
    \u200b else if (ph < h)<\/p>\n
    \u200b dir = 1;<\/p>\n
    \u200b else if ((pk = p.key) == k || (k != null && k.equals(pk)))<\/p>\n
    \u200b \/\/\u5982\u679c\u6839\u8282\u70b9\u7684 key \u548c\u8981\u63d2\u5165\u8282\u70b9\u7684 key \u76f8\u540c\uff0c\u76f4\u63a5\u8fd4\u56de\u6839\u8282\u70b9<\/p>\n
    \u200b return p;<\/p>\n
    \u200b else if ((kc == null &&<\/p>\n
    \u200b (kc = comparableClassFor(k)) == null) ||<\/p>\n
    \u200b (dir = compareComparables(kc, k, pk)) == 0) {<\/p>\n
    \u200b \/\/\u6839\u8282\u70b9\u7684 key \u548c\u8981\u63d2\u5165\u7684 key \u4e0d\u540c\uff0c\u5f00\u59cb\u6bd4\u8f83\u6839\u8282\u70b9\u7684\u5de6\u53f3\u5b50\u8282\u70b9<\/p>\n
    \u200b if (!searched) {<\/p>\n
    \u200b TreeNode<K,V> q, ch;<\/p>\n
    \u200b searched = true;<\/p>\n
    \u200b if (((ch = p.left) != null &&<\/p>\n
    \u200b (q = ch.find(h, k, kc)) != null) ||<\/p>\n
    \u200b ((ch = p.right) != null &&<\/p>\n
    \u200b (q = ch.find(h, k, kc)) != null))<\/p>\n
    \u200b \/\/\u627e\u5230\u76f8\u540c\u7684 key\uff0c\u5c06\u8282\u70b9\u8fd4\u56de<\/p>\n
    \u200b return q;<\/p>\n
    \u200b }<\/p>\n
    \u200b \/\/\u8fd9\u91cc\u8bb0\u5f55\u4e0b dir\uff0c\u53ef\u80fd\u662f\u51b3\u5b9a\u4e3a\u4e86\u5982\u679c\u4ece\u5b50\u8282\u70b9\u4e5f\u627e\u4e0d\u5230\u63a5\u4e0b\u6765\u521b\u5efa\u65b0\u7684\u8282\u70b9\u63d2\u5165\u5230\u5de6\u8fb9\u8fd8\u662f\u53f3\u8fb9<\/p>\n
    \u200b dir = tieBreakOrder(k, pk);<\/p>\n
    \u200b }<\/p>\n
    \u200b \/\/\u5230\u8fd9\u91cc\u5c31\u662f\u4ece\u7ea2\u9ed1\u6811\u627e\u4e0d\u5230\u7b26\u5408\u8981\u6c42\u7684\u8282\u70b9\u4e86\uff0c\u521b\u5efa\u65b0\u7684\u8282\u70b9\uff0c\u63d2\u5165\u5230\u7ea2\u9ed1\u6811<\/p>\n
    \u200b TreeNode<K,V> xp = p;<\/p>\n
    \u200b if ((p = (dir <= 0) ? p.left : p.right) == null) {<\/p>\n
    \u200b Node<K,V> xpn = xp.next;<\/p>\n
    \u200b TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);<\/p>\n
    \u200b if (dir <= 0)<\/p>\n
    \u200b xp.left = x;<\/p>\n
    \u200b else<\/p>\n
    \u200b xp.right = x;<\/p>\n
    \u200b xp.next = x;<\/p>\n
    \u200b x.parent = x.prev = xp;<\/p>\n
    \u200b if (xpn != null)<\/p>\n
    \u200b ((TreeNode<K,V>)xpn).prev = x;<\/p>\n
    \u200b moveRootToFront(tab, balanceInsertion(root, x));<\/p>\n
    \u200b return null;<\/p>\n
    \u200b }<\/p>\n
    \u200b }<\/p>\n
    \u200b }
    “`
    \u4e0d\u77e5\u9053\u5206\u6790\u7684\u5bf9\u4e0d\u5bf9~\u5e0c\u671b\u5927\u4f6c\u4e00\u8d77\u4ea4\u6d41                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : dasinigetudou <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 “`
     final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
     int h, K k, V v) {
     Class<?> kc = null;
     boolean searched = false;
     TreeNode<K,V> root = (parent != null) ? root() : this;
     for (TreeNode<K,V> p = root;;) {
     \/\/\u6811\u7684\u6839\u8282\u70b9\u5f00\u59cb\u904d\u5386
     int dir, ph; K pk;
     \/\/\u6bd4\u8f83\u6839\u8282\u70b9\u7684 hash \u503c\uff0cdir \u731c\u6d4b\u662f\u51b3\u5b9a\u8282\u70b9\u63d2\u5165\u65f6\u5e94\u8be5\u63d2\u5230\u5de6\u5b50\u8282\u70b9\u8fd8\u662f\u53f3\u5b50\u8282\u70b9
     if ((ph = p.hash) > h)
     dir = -1;
     else if (ph < h)
     dir = 1;
     else if ((pk = p.key) == k || (k != null && k.equals(pk)))
     \/\/\u5982\u679c\u6839\u8282\u70b9\u7684 key \u548c\u8981\u63d2\u5165\u8282\u70b9\u7684 key \u76f8\u540c\uff0c\u76f4\u63a5\u8fd4\u56de\u6839\u8282\u70b9
     return p;
     else if ((kc == null &&
     (kc = comparableClassFor(k)) == null) ||
     (dir = compareComparables(kc, k, pk)) == 0) {
     \/\/\u6839\u8282\u70b9\u7684 key \u548c\u8981\u63d2\u5165\u7684 key \u4e0d\u540c\uff0c\u5f00\u59cb\u6bd4\u8f83\u6839\u8282\u70b9\u7684\u5de6\u53f3\u5b50\u8282\u70b9
     if (!searched) {
     TreeNode<K,V> q, ch;
     searched = true;
     if (((ch = p.left) != null &&
     (q = ch.find(h, k, kc)) != null) ||
     ((ch = p.right) != null &&
     (q = ch.find(h, k, kc)) != null))
     \/\/\u627e\u5230\u76f8\u540c\u7684 key\uff0c\u5c06\u8282\u70b9\u8fd4\u56de
     return q;
     }
     \/\/\u8fd9\u91cc\u8bb0\u5f55\u4e0b dir\uff0c\u53ef\u80fd\u662f\u51b3\u5b9a\u4e3a\u4e86\u5982\u679c\u4ece\u5b50\u8282\u70b9\u4e5f\u627e\u4e0d\u5230\u63a5\u4e0b\u6765\u521b\u5efa\u65b0\u7684\u8282\u70b9\u63d2\u5165\u5230\u5de6\u8fb9\u8fd8\u662f\u53f3\u8fb9
     dir = tieBreakOrder(k, pk);
     }<\/p>\n
     \/\/\u5230\u8fd9\u91cc\u5c31\u662f\u4ece\u7ea2\u9ed1\u6811\u627e\u4e0d\u5230\u7b26\u5408\u8981\u6c42\u7684\u8282\u70b9\u4e86\uff0c\u521b\u5efa\u65b0\u7684\u8282\u70b9\uff0c\u63d2\u5165\u5230\u7ea2\u9ed1\u6811
     TreeNode<K,V> xp = p;
     if ((p = (dir <= 0) ? p.left : p.right) == null) {
     Node<K,V> xpn = xp.next;
     TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
     if (dir <= 0)
     xp.left = x;
     else
     xp.right = x;
     xp.next = x;
     x.parent = x.prev = xp;
     if (xpn != null)
     ((TreeNode<K,V>)xpn).prev = x;
     moveRootToFront(tab, balanceInsertion(root, x));
     return null;
     }
     }
     }
    “`                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n
    \n
    \n
     \u4e3b<\/span> \u8cc7\u6df1\u5927\u4f6c : levizheng <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 @Joker123456789 
    @aneureka 
    @dasinigetudou 
    \u611f\u8c22\u5927\u4f6c\u4eec\uff0c\u679c\u7136\u662f putTreeVal \u65b9\u6cd5\u91cc\u8fdb\u884c\u4e86\u5224\u65ad\uff0c\u4e4b\u524d\u770b\u7684\u4e0d\u4ed4\u7ec6\u4e86                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n","protected":false},"excerpt":{"rendered":"
    \u5927\u4f6c\u4eec\uff0c hashmap \u7684\u6e90\u7801\u6709…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201323"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=201323"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/201323\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=201323"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=201323"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=201323"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}