{"id":2155,"date":"2021-05-25T21:19:26","date_gmt":"2021-05-25T13:19:26","guid":{"rendered":"https:\/\/coderbee.net\/?p=2155"},"modified":"2021-05-25T22:48:53","modified_gmt":"2021-05-25T14:48:53","slug":"hashtable","status":"publish","type":"post","link":"https:\/\/coderbee.net\/index.php\/java\/20210525\/2155","title":{"rendered":"HashTable \u6709\u4ec0\u4e48\u5947\u602a\u7684\u77e5\u8bc6\uff1f"},"content":{"rendered":"

\u672c\u6587\u6d89\u53ca\u7684\u6e90\u7801\u57fa\u4e8e JDK 1.8.0_101 \u3002<\/p>\n

1. HashTable<\/h1>\n
    \n
  1. \u91c7\u7528\u6570\u7ec4 + \u94fe\u8868\uff08\u8868\u5934\u63d2\u5165\uff09\u65b9\u5f0f\u89e3\u51b3\u54c8\u5e0c\u51b2\u7a81\u3002<\/li>\n
  2. \u6240\u6709\u7684 public \u65b9\u6cd5\u90fd\u7528 synchronized<\/code> \u4fee\u9970\u4ee5\u4fdd\u8bc1\u7ebf\u7a0b\u5b89\u5168\u3002<\/li>\n
  3. \u5728\u6784\u9020\u65f6\u5c31\u521d\u59cb\u5316\u69fd\u6570\u7ec4\uff08\u9ed8\u8ba4\u5927\u5c0f\u4e3a 11<\/code>\uff09\u3002<\/li>\n
  4. \u952e\u3001\u503c \u90fd\u4e0d\u80fd\u4e3a null<\/code>\u3002<\/li>\n
  5. \u6307\u5b9a key \u7684\u76ee\u6807\u69fd\u7684\u5b9a\u4f4d\u903b\u8f91\uff1a(key.hashCode() & 0x7FFFFFFF) % table.length<\/code>\uff0c\u63a9\u7801+\u6c42\u6a21\u3002<\/li>\n
  6. \u69fd\u6570\u7ec4\u7684\u6700\u5927\u5c3a\u5bf8\u4e3a MAX_ARRAY_SIZE: Integer.MAX_VALUE - 8<\/code>(\u51cf 8 \u662f\u56e0\u4e3a\u4e00\u4e9b JVM \u4f1a\u5728\u6570\u7ec4\u91cc\u4fdd\u7559\u4e00\u4e9b header words)\u3002<\/li>\n
  7. \u6269\u5bb9\u903b\u8f91\u4e3a \u4e24\u500d + 1\u3002<\/li>\n
  8. \u9608\u503c\u4e3a\uff1a (int)(capacity * loadFactor)<\/code>\uff0c\u4f46\u4e0d\u80fd\u8d85\u8fc7 MAX_ARRAY_SIZE + 1<\/code>\u3002<\/li>\n<\/ol>\n

    <\/p>\n

    1.1 put \u65b9\u6cd5\u903b\u8f91<\/h3>\n
      \n
    1. \u901a\u8fc7 key \u8ba1\u7b97\u51fa\u76ee\u6807\u69fd\u4f4d index \uff1b<\/li>\n
    2. \u904d\u5386 table[index]<\/code> \u94fe\u8868\uff0c\u5982\u679c key \u5b58\u5728\uff0c\u5219\u66ff\u6362 value\uff0c\u8fd4\u56de\u524d\u503c\u3002<\/li>\n
    3. \u5982\u679c key \u4e0d\u5b58\u5728\uff0c\u7ee7\u7eed\u3002<\/li>\n
    4. \u5224\u65ad\u5143\u7d20\u6570\u91cf\u662f\u5426\u8fbe\u5230\u9608\u503c\uff0c\u8fbe\u5230\u7684\u8bdd\u8fdb\u884c\u6269\u5bb9 rehash\uff0c\u7136\u540e\u91cd\u65b0\u8ba1\u7b97\u76ee\u6807\u69fd\u4f4d index\u3002<\/li>\n
    5. \u521b\u5efa\u65b0\u7684 Entry\uff0c\u628a Entry \u63d2\u5165\u5230\u94fe\u8868\u7684\u5934\u90e8\u3002<\/li>\n<\/ol>\n

      1.2 rehash \u903b\u8f91<\/h3>\n
        \n
      1. \u6570\u7ec4\u6269\u5bb9\u81f3 oldCapacity * 2 + 1<\/code>\uff0c\u4f46\u4e0d\u80fd\u8d85\u8fc7 MAX_ARRAY_SIZE \u3002<\/li>\n
      2. \u628a\u65e7 map \u4e0a\u7684\u5143\u7d20\u8f6c\u79fb\u5230\u65b0\u7684 map\uff1a\u9010\u4e2a\u69fd\u4f4d\u3001\u9010\u4e2a\u94fe\u8868\u904d\u5386 \u3002<\/li>\n<\/ol>\n
        protected void rehash() {\n    int oldCapacity = table.length;\n    Entry<?,?>[] oldMap = table;\n\n    \/\/ overflow-conscious code\n    int newCapacity = (oldCapacity << 1) + 1;\n    if (newCapacity - MAX_ARRAY_SIZE > 0) {\n        if (oldCapacity == MAX_ARRAY_SIZE)\n            \/\/ Keep running with MAX_ARRAY_SIZE buckets\n            return;\n        newCapacity = MAX_ARRAY_SIZE;\n    }\n    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];\n\n    modCount++;\n    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);\n    table = newMap;\n\n    for (int i = oldCapacity ; i-- > 0 ;) {\n        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {\n            Entry<K,V> e = old;\n            old = old.next;\n\n            int index = (e.hash & 0x7FFFFFFF) % newCapacity;\n            e.next = (Entry<K,V>)newMap[index];\n            newMap[index] = e;\n        }\n    }\n}\n<\/code><\/pre>\n
        1.3 get \u65b9\u6cd5<\/h3>\n
          \n
        1. \u8ba1\u7b97 key \u7684\u76ee\u6807\u69fd\u4f4d index\uff1b<\/li>\n
        2. \u904d\u5386 table[index]<\/code> \u4e0a\u7684\u94fe\u8868\u4ee5\u67e5\u627e key\uff0c\u627e\u5230\u8fd4\u56de value\u3001\u627e\u4e0d\u5230\u8fd4\u56de null \u3002<\/li>\n<\/ol>\n
          1.4 remove \u65b9\u6cd5<\/h3>\n
            \n
          1. \u8ba1\u7b97 key \u7684\u76ee\u6807\u69fd\u4f4d index\uff1b<\/li>\n
          2. \u904d\u5386 table[index]<\/code> \u4e0a\u7684\u94fe\u8868\u67e5\u627e key\uff0c\u521d\u59cb\u5316\u524d\u9a71 prev \u4e3a null\uff0c\u627e\u5230 key \u7684 entry e \u540e\uff0c\u5982\u679c prev \u4e0d\u4e3a null \u5219\u8bbe\u7f6e prev.next = e.next<\/code>\uff0c\u5426\u5219\u8bf4\u660e e \u5c31\u5728\u94fe\u8868\u7684\u5934\u90e8\uff0c\u8bbe\u7f6e table[index] = e.next<\/code>\u3002<\/li>\n<\/ol>\n
            \n
            \u6b22\u8fce\u5173\u6ce8\u6211\u7684\u5fae\u4fe1\u516c\u4f17\u53f7: coderbee\u7b14\u8bb0<\/strong> \u3002
            \n<\/p>\n","protected":false},"excerpt":{"rendered":"
            \u672c\u6587\u6d89\u53ca\u7684\u6e90\u7801\u57fa\u4e8e JDK 1.8.0_101 \u3002 1. HashTable \u91c7 … \u7ee7\u7eed\u9605\u8bfb →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[355],"_links":{"self":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/2155"}],"collection":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/comments?post=2155"}],"version-history":[{"count":2,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/2155\/revisions"}],"predecessor-version":[{"id":2157,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/2155\/revisions\/2157"}],"wp:attachment":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/media?parent=2155"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/categories?post=2155"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/tags?post=2155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}