{"id":223093,"date":"2011-01-19T04:16:29","date_gmt":"2011-01-18T20:16:29","guid":{"rendered":"http:\/\/blog.yangzhe1991.org\/?p=223093"},"modified":"2014-03-14T19:08:20","modified_gmt":"2014-03-14T11:08:20","slug":"java-util-hashmaphashtable","status":"publish","type":"post","link":"https:\/\/yangzhe1991.org\/blog\/2011\/01\/java-util-hashmaphashtable\/","title":{"rendered":"java.util.HashMap\/Hashtable"},"content":{"rendered":"

\u524d\u6587<\/a>\u5df2\u7ecf\u63d0\u5230\u4e86\u5b9e\u73b0\u5b57\u5178\u7684\u4e00\u79cd\u5f62\u5f0f\uff0c\u4e8c\u53c9\u6811\u3002\u4e0b\u9762\u6765\u8bf4\u53e6\u4e00\u79cd\u5f62\u5f0f\uff0c\u54c8\u5e0c\u3002<\/p>\n

\u5176\u5b9e\u65e0\u8bba\u662fTreap,SBT\u6216\u8005AVL\uff0cRBT\uff0c\u6211\u89c9\u5f97\u6211\u4eec\u90fd\u5e94\u8be5\u5927\u81f4\u4e86\u89e3\u4e00\u4e0b\u3002\u5c24\u5176\u662ftreap\u5728\u5b9e\u73b0\u4e0a\u6bd4\u8f83\u65b9\u4fbf\uff0cOI\u7684\u6bd4\u8d5b\u53ef\u80fd\u5728\u9ad8\u7ea7\u70b9\u7684\u6bd4\u8d5b\u4e2d\u4f1a\u7528\u5230\u3002ACM\u56e0\u4e3a\u53ef\u4ee5\u4f7f\u7528STL\uff08\u4f3c\u4e4eOI\u4e5f\u5feb\u4e86\uff09\uff0c\u52a0\u4e0a\u53ef\u4ee5\u6284\u6a21\u7248\uff0c\u5bf9\u8fd9\u79cd\u5e95\u5c42\u7684\u5b9e\u73b0\u770b\u4f3c\u8981\u6c42\u4e0d\u5927\uff0c\u4f46\u6211\u89c9\u5f97\u53ea\u6709\u4e86\u89e3\u5e95\u5c42\u5b9e\u73b0\u4e4b\u540e\u624d\u4f1a\u66f4\u5bb9\u6613\u5b66\u4e60\u5176\u4ed6\u7684\u4e1c\u897f\u3002\u66f4\u4f55\u51b5ACM\/OI\u66f4\u5e94\u8be5\u662f\u7d20\u8d28\u6559\u80b2\uff0c\u4e0d\u5e94\u8be5\u4e0d\u9700\u8981\u81ea\u5df1\u5199\u7684\u5c31\u53ef\u4ee5\u5199\u4e0d\u51fa\u6765\u3002<\/p>\n

\u90a3\u7bc7RBT\u7684\u6587\u7ae0\u6ca1\u6709\u4efb\u4f55\u56fe\u548c\u4ee3\u7801\u54ea\u6015\u662f\u4f2a\u4ee3\u7801\uff0c\u6211\u89c9\u5f97\u62ff\u5b83\u5f53\u6559\u6750\u800c\u4e14\u771f\u5b66\u4f1a\u7684\u4eba\u6211\u5e94\u8be5\u989d\u5916\u7684\u611f\u8c22\u4e00\u4e0b\u2026\u2026\u8fd9\u7bc7\u8bb2\u54c8\u5e0c\u5b57\u5178\u7684\u6211\u4f1a\u4ee5java\u91cc\u7684\u6e90\u7801\u4e3a\u4e3b\u3002\u611f\u89c9java\u7684\u4ee3\u7801\u53ef\u8bfb\u6027\u6bd4cpp\u548cc\u5f3a\u592a\u591a\u4e86\u3002\u5c24\u5176\u662fjava\u8bed\u8a00\u672c\u8eab\u7684\u90a3\u4e9b\u5305\u6bd4\u5982uitl\u4ec0\u4e48\u7684\u5f88\u5bb9\u6613\u901a\u8fc7\u8bfb\u6e90\u7801\u6765\u638c\u63e1\u539f\u7406\uff0c\u800cSTL\u7684\u4ee3\u7801\u5728\u6211\u770b\u6765\u5c31\u662f\u4e2a\u60b2\u5267\u2026\u2026\u54ea\u6015\u4f3c\u4e4e\u53f7\u79f0\u53ef\u8bfb\u6027\u6700\u5f3a\u7684CGI\u5b9e\u73b0\u6211\u8fd8\u662f\u5f88\u96be\u50cfjava\u8fd9\u6837\u8f7b\u677e\u8bfb\u61c2\u3002\u5f53\u7136\uff0cjava\u91cc\u4e5f\u6709\u7528\u4e8c\u53c9\u6811\u5f62\u6210\u7684\u5b57\u5178\uff0c\u53ebTreeMap\/TreeSet\uff0c\u5e95\u5c42\u4e5f\u662f\u7ea2\u9ed1\u6811\u5b9e\u73b0\uff0c\u56e0\u6b64\u8fed\u4ee3\u5668\u4e5f\u662f\u6709\u5e8f\u7684\u3002<\/p>\n

\u5148\u5927\u81f4\u5c06\u4e00\u4e0b\u4ec0\u4e48\u662fhash\u3002\u7b80\u5355\u8bf4\u5c31\u662f\u8ba9\u6bcf\u4e2a\u5143\u7d20\u90fd\u6709\u4e00\u4e2a\u7a0d\u5fae\u77ed\u5c0f\u4e00\u4e9b\u7684\u4ee3\u7801\uff0c\u8fd9\u6837\u5f88\u591a\u5143\u7d20\u5c31\u53ef\u4ee5\u901a\u8fc7\u4e00\u4e2a\u5f88\u5c0f\u8303\u56f4\u7684\u6570\u5b57\u8fdb\u884c\u7d22\u5f15\uff0c\u6700\u666e\u901a\u7684hash\u5c31\u662f\u8ba1\u6570\u6392\u5e8f\uff0c\u5373\u5f00\u4e00\u4e2a\u4ecemin\u5230max\u7684\u6570\u7ec4hash[]\uff0c\u770b\u89c1\u4e00\u4e2ax\u5c31hash[x]++,\u7136\u540e\u5c31\u77e5\u9053\u6bcf\u4e2a\u6811\u6709\u51e0\u4e2a\uff0c\u6392\u5e8f\u4ec0\u4e48\u7684\u4e5f\u662f\u7ebf\u6027\u65f6\u95f4\u7684\u3002\u5f53\u6570\u7ec4\u4e0b\u6807\u8981\u5f88\u5927\u8fdb\u800c\u5f88\u8d39\u5185\u5b58\u7684\u65f6\u5019\uff0c\u5c31\u8981\u901a\u8fc7\u4e00\u4e2ahash\u51fd\u6570\u6765\u83b7\u5f97\u4e00\u4e2a\u5c0f\u5f97\u591a\u7684\u6570\u5b57\uff0c\u5f88\u663e\u7136\u4f1a\u6709\u91cd\u590d\uff0c\u6211\u4eec\u79f0\u4e4b\u4e3a\u201c\u78b0\u649e\u201d\u3002\u5982\u4f55\u9ad8\u6548\u7684\u5904\u7406\u78b0\u649e\uff0c\u4ee5\u53ca\u63d0\u51fa\u4e00\u4e2a\u5f88\u597d\u5f88\u5747\u5300\u7684hash\u51fd\u6570\u5c31\u662f\u54c8\u5e0c\u8868\u7684\u6548\u7387\u4e4b\u6240\u5728\u3002<\/p>\n

\u5728java\u4e2d\uff0c\u4e0e\u54c8\u5e0c\u4ece\u540d\u5b57\u4e0a\u76f4\u63a5\u76f8\u5173\u7684\u6709\u4e09\u4e2a\uff0cHashMap\uff0cHashtable\uff0cHashSet\u3002\u7b2c\u4e09\u4e2a\u663e\u7136\u662f\u96c6\u5408\u800c\u524d\u4e24\u4e2a\u624d\u662f\u5b57\u5178\u3002\u800cHashSet\u5e95\u5c42\u5c31\u662f\u7528\u4e00\u4e2a\u7ea6\u7b49\u4e8e value\u4e3a\u7a7a\u7684HashMap\uff08\u51c6\u786e\u7684\u8bf4\u662f\u641e\u4e86\u4e00\u4e2aprivate static final Object PRESENT = new Object();\u6240\u6709\u7684value\u90fd\u7b49\u4e8e\u8fd9\u4e2aPRESENT\uff09\u3002\u56e0\u6b64\u660e\u767d\u524d\u4e24\u4e2a\u600e\u4e48\u56de\u4e8b\u5c31\u77e5\u9053set\u600e\u4e48\u56de\u4e8b\u4e86\uff0c\u8fd9\u70b9\u8ddfSTL\u7c7b\u4f3c\u3002\u4e24\u8005\u5747\u5b9e\u73b0\u4e86Map<K,V>\u63a5\u53e3\uff0c\u800cMap\u63a5\u53e3\u5b9a\u4e49\u4e86\u8033\u719f\u80fd\u8be6\u7684put,get,size\u4ec0\u4e48\u7684\uff0c\u56e0\u6b64\u4e24\u8005\u4f7f\u7528\u4e0a\u533a\u522b\u4e0d\u5927\u3002\u552f\u4e8c\u7684\u533a\u522b\u5728\u4e8e\uff1aHashMap\u652f\u6301null\u4e3akey\uff0c\u6709\u4e2aprivate V getForNullKey()\u65b9\u6cd5\uff0chashtable\u6ca1\u6709\uff1b\u8fd8\u6709\u4e00\u4e2a\u662fhashmap\u662f\u201c\u4e0d\u540c\u6b65\u201d\u7684\uff0c\u7528\u5b98\u65b9\u6587\u6863\u7684\u539f\u8bdd\u5c31\u662f\u201c\u5982\u679c\u591a\u4e2a\u7ebf\u7a0b\u540c\u65f6\u8bbf\u95ee\u6b64\u6620\u5c04\uff0c\u800c\u5176\u4e2d\u81f3\u5c11\u4e00\u4e2a\u7ebf\u7a0b\u4ece\u7ed3\u6784\u4e0a\u4fee\u6539\u4e86\u8be5\u6620\u5c04\uff0c\u5219\u5b83\u5fc5\u987b<\/em>\u4fdd\u6301\u5916\u90e8\u540c\u6b65\u201d\u3002\u5f53\u7136\uff0c\u8ddf\u54c8\u5e0c\u6709\u5173\u7684\u8fd8\u6709\u4e00\u4e2ahashcode\uff0c\u8fd9\u662f\u5728Object\u7c7b\u91cc\u7684\u4e00\u4e2a\u65b9\u6cd5\uff08\u8ddf\u4ec0\u4e48toString\u4e4b\u6d41\u4e00\u6837\uff09\uff0c\u7531\u4e8e\u9700\u8981\u5e95\u5c42JVM\u7684\u652f\u6301\u624d\u80fd\u5f62\u6210int\u5e76\u8fd4\u56de\uff0c\u56e0\u6b64\u770bjava\u6e90\u7801\u662f\u770b\u4e0d\u5230object\u7c7b\u91cc\u7684\u65b9\u6cd5\u90fd\u662f\u5982\u4f55\u5b9e\u73b0\u7684\uff0c\u5f97\u770bjvm\u7684\u6e90\u7801\u624d\u53ef\u4ee5\u3002<\/p>\n

\u9664\u4e86\u5171\u7528map\u63a5\u53e3\u4e4b\u5916\uff0c\u8fd8\u6709\u4fe9\u63a5\u53e3\u4e5f\u5171\u7528\uff0c\u8c8c\u4f3c\u4e0e\u672c\u6587\u5173\u7cfb\u4e0d\u5927\uff0c\u800c\u4e14\u6211\u8fd8\u53d1\u73b0\u4e24\u5904\u7684\u4ee3\u7801\u867d\u7136implement\u4e00\u4e2a\u63a5\u53e3\u4f46\u4e00\u4e2ajava.io\u4e00\u4e2a\u6ca1\u5199\uff0c\u5728\u4e24\u8005\u90fdimport java.io.*\u7684\u60c5\u51b5\u4e0b\uff0c\u4e0d\u77e5\u9053\u4e3a\u4f55\u4f1a\u6709\u8fd9\u4e2a\u5c0fbug\u2026\u2026<\/p>\n

\u4e24\u8005\u5747\u7ee7\u627f\u81ea\u5404\u81ea\u4e13\u5c5e\u7684\u4e00\u4e2a\u62bd\u8c61\u7c7b\uff0c\u4e00\u4e2aAbstractMap\uff0c\u4e00\u4e2aDictionary\u3002\u524d\u8005\u5b9e\u73b0\u4e86\u4e0d\u5c11\u4e1c\u897f\uff08\u4e0d\u8fc7\u7ee7\u627f\u800c\u6765\u7684hashmap\u597d\u591a\u90fd\u7ed9\u91cd\u5199\u4e86\uff09\uff0c\u800c\u540e\u8005\u5f7b\u5e95\u5c31\u662f\u62bd\u8c61\u7684\uff0c\u65e0\u4efb\u4f55\u5b9e\u73b0\u2026\u2026\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u7ee7\u627f\u524d\u8005\u6765\u5b9e\u73b0\u6211\u4eec\u81ea\u5df1\u7684\u54c8\u5e0cmap\u65b9\u6848\uff0c\u540e\u8005\u5c31\u5f88\u96be\u3002\u800c\u4e14\u5176\u5b9e\u90a3\u4e2a\u5b57\u5178\u62bd\u8c61\u7c7b\u672c\u8eab\u5c31\u662f\u4e00\u4e2a\u63a5\u53e3\u7f62\u4e86\uff0c\u6240\u4ee5\u73b0\u5728\u7684\u6587\u6863\u4f1a\u6ce8\u660e\uff0c\u8be5\u7c7b\u5df2\u7ecf\u8fc7\u65f6\uff0c\u8bf7\u4f7f\u7528map\u63a5\u53e3\u800c\u975e\u7ee7\u627f\u6b64\u7c7b\u3002\u770b\u4e86\u770b\u53d1\u73b0hashtable\u662fjava1.0\u5c31\u6709\u7684\uff0c\u800chashmap\u662f1.2\u7684\uff0cmap\u63a5\u53e3\u4e5f\u662f1.2\u7684\uff0c\u56e0\u6b64\u8fd9\u5e94\u8be5\u662f\u4e2a\u5386\u53f2\u9057\u7559\u95ee\u9898\u5427\u3002\u603b\u4e4b\u53ef\u4ee5\u8ba4\u4e3ahashtable.java\u5b9e\u73b0\u4e86\u5168\u90e8\u529f\u80fd\u800chashmap.java\u9760\u5f88\u591a\u7236\u7c7b\u7684\u4e1c\u897f\u3002\u751a\u81f3\u6211\u901a\u8fc7\u8fd9\u4e2a\u624d\u53d1\u73b0iterator\u662f1.2\u624d\u6709\u7684\u63a5\u53e3\uff0c\u5f00\u59cb\u7528\u4e00\u4e2a\u5f88\u4e0d\u6210\u719f\u65b9\u6cd5\u540d\u8fd8\u5f88\u957f\u7684Enumeration<\/em>\u63a5\u53e3\uff0c\u8fd9\u4e2a\u5728hashtalbe\u4e5f\u662f\u80fd\u770b\u89c1\u7684\uff0c\u521a\u770b\u89c1\u8fd8\u5947\u602a\u8fd9\u662f\u795e\u9a6c\u2026\u2026<\/p>\n

\u6211\u4eec\u77e5\u9053hash\u7684\u7cbe\u9ad3\u662f\u641e\u51fa\u6765\u4e00\u4e2a\u6700\u597d\u72ec\u4e00\u65e0\u4e8c\u7684\u6570\u5b57\u7136\u540e\u5206\u5217\uff0c\u4e00\u65e6\u53d1\u73b0\u6709\u78b0\u649e\u5c31\u901a\u8fc7\u4e00\u4e9b\u65b9\u6cd5\u89e3\u51b3\u3002\u6700\u5e38\u89c1\u7684\u65b9\u6cd5\u662f\u7528\u94fe\u8868\uff0c\u5373\u540c\u6837\u4e00\u4e2ahash\u7684\u90fd\u62c9\u51fa\u6765\u5728\u4e00\u4e2a\u94fe\u8868\u91cc\u3002java\u4e5f\u662f\u8fd9\u6837\u5b9e\u73b0\u7684\u3002\u65e0\u8bbahashtable\u8fd8\u662fhashmap\u90fd\u6709\u4e00\u4e2a\u5185\u90e8\u9759\u6001\u7c7bEntry<K,V>\uff0c\u4f46hashmap\u7684\u4e0d\u662f\u79c1\u6709\u7684\u800c\u662f\u65e0\u524d\u7f00\u7684\u5305\u8bbf\u95ee\u6743\u9650\uff0c\u4e0d\u77e5\u9053\u4e3a\u5565\u3002\u4e24\u8005\u7684\u6210\u5458\u5747\u4e3a\u8fd9\u56db\u4e2a\uff1a<\/p>\n

int hash;<\/div>\n
K key;<\/div>\n
V value;<\/div>\n
Entry<K,V> next;<\/div>\n

\u6784\u9020\u65b9\u6cd5\u4e5f\u7c7b\u4f3c\uff0c\u53ea\u662f\u4ee3\u7801\u98ce\u683c\u4e0d\u4e00\u6837\uff08\u8981\u662f\u8ba9HLP\u6216\u8005\u4e00\u4e9b\u8001\u5e08\u770b\uff0c\u5199hashtable\u7684\u5b66\u751f\u5206\u4f1a\u9ad8\uff0c\u56e0\u4e3ahashmap\u6709\u5f88\u591a\u5355\u5b57\u6bcd\u53d8\u91cf\uff0c\u4e0d\u7b26\u5408\u7f16\u7801\u89c4\u8303\uff09\u3002\u8fd9\u91cc\u62ff\u7b26\u5408\u89c4\u8303\u7684\uff0cmap\u7684\u53ea\u662f\u6ca1\u6709protected\u5173\u952e\u5b57\u800c\u5df2\uff1a<\/p>\n

protected Entry(int hash, K key, V value, Entry<K,V> next) {<\/p>\n

<\/span> this.hash = hash;<\/p>\n

<\/span> this.key = key;<\/p>\n

<\/span> this.value = value;<\/p>\n

<\/span> this.next = next;<\/p>\n

<\/span>}<\/p>\n

\u4e24\u4e2ahash\u7684\u201c\u539f\u5b50\u5bf9\u8c61\u201d\u5747\u4e3a\u4e00\u4e2a\u4e2a\u7684Entry\uff0c\u4efb\u4f55\u4e00\u4e2a\u65b0\u5bf9\u8c61\u90fd\u662f\u901a\u8fc7\u5c01\u88c5\u6210Entry\u540e\u5b9e\u73b0\u7684\u3002\u8fd9\u91cc\u63d2\u64ad\u4e00\u53e5\uff0c\u53d1\u73b0\u6709\u4e2atransient\u5173\u952e\u5b57\uff0c\u8bb2\u5f00\u6765\u592a\u590d\u6742\uff0c\u800c\u4e14\u6211\u4e5f\u6ca1\u592a\u61c2\uff0c\u53ef\u4ee5\u81ea\u5df1google\u3002<\/p>\n

\u7136\u540e\u4e24\u8005\u5c31\u6709\u5f88\u5927\u7684\u4e0d\u540c\u4e86\u3002\u5148\u4ece\u53e4\u8001\u7684hshtable\u8bf4\u8d77\u3002<\/p>\n

public synchronized V put(K key, V value) {<\/p>\n

<\/span>\/\/ Make sure the value is not null<\/p>\n

<\/span>if (value == null) {<\/p>\n

<\/span> throw new NullPointerException();<\/p>\n

<\/span>}<\/p>\n

<\/span>\/\/ Makes sure the key is not already in the hashtable.<\/p>\n

<\/span>Entry tab[] = table;<\/p>\n

<\/span>int hash = key.hashCode();<\/p>\n

<\/span>int index = (hash & 0x7FFFFFFF) % tab.length;<\/p>\n

<\/span>for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {<\/p>\n

<\/span> if ((e.hash == hash) && e.key.equals(key)) {<\/p>\n

<\/span>V old = e.value;<\/p>\n

<\/span>e.value = value;<\/p>\n

<\/span>return old;<\/p>\n

<\/span> }<\/p>\n

<\/span>}<\/p>\n

<\/span>modCount++;<\/p>\n

<\/span>if (count >= threshold) {<\/p>\n

<\/span> \/\/ Rehash the table if the threshold is exceeded<\/p>\n

<\/span> rehash();<\/p>\n

tab = table;<\/p>\n

index = (hash & 0x7FFFFFFF) % tab.length;<\/p>\n

<\/span>}<\/p>\n

<\/span>\/\/ Creates the new entry.<\/p>\n

<\/span>Entry<K,V> e = tab[index];<\/p>\n

<\/span>tab[index] = new Entry<K,V>(hash, key, value, e);<\/p>\n

<\/span>count++;<\/p>\n

<\/span>return null;<\/p>\n

}<\/p>\n

\u53ef\u4ee5\u770b\u51fa\uff0chash\u7684\u83b7\u5f97\u662f\u9760\u83b7\u5f97\u8be5\u5bf9\u8c61\u7684hashcode\u7136\u540e\u53d6\u4e0e\u518d\u53d6\u6a21\uff0c\u81f3\u4e8e\u4e3a\u4f55\u662f0x7FFFFFFF\uff0c\u5e94\u8be5\u8ddfhashcode\u6709\u5173\u3002\u7136\u540e\u5199\u4e2a\u7a0b\u5e8f\u770b\u4e86\u770b\u4e00\u822c\u5bf9\u8c61\u7684hashcode\u503c\uff0c\u53d1\u73b0int\uff08\u5176\u5b9e\u5e94\u8be5\u662f\u4e00\u4e2aInteger\u5bf9\u8c61\uff0c\u56e0\u4e3aint\u53d8\u91cf\u4e0d\u662f\u5bf9\u8c61\uff0c\u56e0\u6b64java\u5176\u5b9e\u5e76\u975e\u662f100%\u9762\u5411\u5bf9\u8c61\u7684\uff09\u7684hashcode\u5c31\u662f\u90a3\u4e2a\u6570\uff0c\u800clong\u7684hashcode\u662f\u6b63\u6570\u4e00\u6837\uff0c\u8d1f\u6570\u7684\u8bdd\u5c31\u53d8\u6b63\u518d\u51cf1.\u5b57\u7b26\u4e32\u7684\u5c31\u7ea6\u7b49\u4e8e\u4e0d\u4e00\u5b9a\u4e86\u3002\u603b\u4e4b\uff0c\u5c31\u662f\u4e00\u4e2a\u5f88\u660e\u663e\u7684\u4e1c\u897f\u5f97\u5230index\uff0c\u7136\u540e\u653e\u8fdbtab\u90a3\u4e2a\u6570\u7ec4\u3002\u800c\u4e14\u53ef\u4ee5\u770b\u51fa\u6765\uff0c\u540e\u8fdb\u7684\u79bb\u6839\u66f4\u8fd1\u3002<\/p>\n

public synchronized V get(Object key) {<\/p>\n

<\/span>Entry tab[] = table;<\/p>\n

<\/span>int hash = key.hashCode();<\/p>\n

<\/span>int index = (hash & 0x7FFFFFFF) % tab.length;<\/p>\n

<\/span>for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {<\/p>\n

<\/span> if ((e.hash == hash) && e.key.equals(key)) {<\/p>\n

<\/span>return e.value;<\/p>\n

<\/span> }<\/p>\n

<\/span>}<\/p>\n

<\/span>return null;<\/p>\n

}<\/p>\n

get\u5c31\u5dee\u4e0d\u591a\u4e86\uff0c\u53ef\u4ee5\u770b\u5230\u53ea\u8981\u662f\u8ba1\u7b97hash\u5c31\u90fd\u5f97\u6709\u90a3\u884c\u7b97\u5f0f\uff0c\u800c\u4e00\u4f1a\u770bhashmap\u5c31\u77e5\u9053\u4eba\u5bb6\u641e\u4e86\u4e2a\u4e13\u95e8\u7684\u51fd\u6570\uff0c\u9700\u8981\u7b97\u5c31\u8c03\u7528\u4e00\u4e0b\u3002\u56e0\u6b64hashtable\u7684\u4ee3\u7801\u5176\u5b9e\u5199\u7684\u5e76\u6ca1\u6709hashmap\u597d\u3002<\/p>\n

\u6211\u4eec\u77e5\u9053\uff0c\u4e24\u79cdhash\u90fd\u6709\u4e24\u4e2a\u53ef\u9009\u6784\u9020\u53c2\u6570\uff0c\u5bb9\u91cf\u548c\u52a0\u8f7d\u56e0\u5b50\uff0c\u9ed8\u8ba4\u5206\u522b\u4e3a11\u548c0.75\uff0c\u524d\u8005\u5c31\u662f\u521d\u59cb\u6570\u7ec4\u5927\u5c0f\uff0c\u4e24\u8005\u76f8\u4e58\u518d\u53d6\u6574\u662f\u6700\u5927\u5bb9\u79ef\u3002\u4e00\u65e6\u6574\u4e2ahash\u8868\u5185\u7684\u5143\u7d20\u4e2a\u6570\u8fbe\u5230\u8fd9\u4e2a\u5236\uff0c\u5c31\u8981\u8fdb\u884crehash\u64cd\u4f5c\uff08put\u51fd\u6570\u91cc\u6709\u4f53\u73b0\uff09\uff0crehash\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n

protected void rehash() {<\/p>\n

<\/span>int oldCapacity = table.length;<\/p>\n

<\/span>Entry[] oldMap = table;<\/p>\n

<\/span>int newCapacity = oldCapacity * 2 + 1;<\/p>\n

<\/span>Entry[] newMap = new Entry[newCapacity];<\/p>\n

<\/span>modCount++;<\/p>\n

<\/span>threshold = (int)(newCapacity * loadFactor);<\/p>\n

<\/span>table = newMap;<\/p>\n

<\/span>for (int i = oldCapacity ; i– > 0 \ud83d\ude09 {<\/p>\n

<\/span> for (Entry<K,V> old = oldMap[i] ; old != null ; ) {<\/p>\n

<\/span>Entry<K,V> e = old;<\/p>\n

<\/span>old = old.next;<\/p>\n

<\/span>int index = (e.hash & 0x7FFFFFFF) % newCapacity;<\/p>\n

<\/span>e.next = newMap[index];<\/p>\n

<\/span>newMap[index] = e;<\/p>\n

<\/span> }<\/p>\n

<\/span>}<\/p>\n

}<\/p>\n

\u9053\u7406\u5f88\u7b80\u5355\uff0c\u5c31\u662f\u5c06\u5bb9\u91cf*2+1(\u4e4b\u6240\u4ee5\u8981\u52a01\u662f\u56e0\u4e3a\u4e00\u822chash\u7684\u5bb9\u91cf\u4e3a\u5c3d\u91cf\u8d28\u6570\u8d77\u7801\u5f97\u662f\u5947\u6570\uff0c\u53ef\u4ee5\u51cf\u5c11\u78b0\u649e\u7684\u53ef\u80fd\uff0c\u800c\u521d\u59cb\u768411\u4f3c\u4e4e\u4e5f\u662f\u6bd4\u8f83\u4e0d\u9519\u7684\uff0c\u56e0\u4e3a11\uff0c23\uff0c47\u90fd\u662f\u8d28\u6570)\uff0c\u7136\u540e\u91cd\u65b0\u5165\u65b0\u7684\u6570\u7ec4\u3002\u987a\u4fbf\u63d0\u4e00\u53e5\uff0carraylist\u7684\u521d\u59cb\u5bb9\u91cf\u662f10\uff0c\u6bcf\u6b21\u4e0d\u591f\u4e86\u5c31\u5bb9\u91cf*2\uff0cvector\u7c7b\u4f3c\u3002\u53ef\u4ee5\u770b\u51fa0.75\u7684\u9ed8\u8ba4\u56e0\u5b50\u4f1a\u7ecf\u5e38\u5bfc\u81f4rehash\uff0c\u4f46\u8fd9\u610f\u5473\u7740\u5c3d\u91cf\u907f\u514d\u78b0\u649e\u7684\u53d1\u751f\uff08\u56e0\u4e3a\u7edf\u8ba1\u5b66\u4e0a\u5e73\u57474\u4e2a\u5751\u7ed93\u4e2a\u841d\u535c\uff0c\u4fe9\u841d\u535c\u649e\u4e0a\u7684\u6982\u7387\u4e0d\u592a\u5927\uff0c\u4ee8\u841d\u535c\u5c31\u66f4\u5c0f\u4e86\uff09\u3002\u603b\u4e4b0.75\u662f\u4e00\u4e2a\u7ecf\u9a8c\u4e0a\u6700\u597d\u7684\u5e73\u8861\uff0c\u5f53\u7136\u53ef\u4ee5\u624b\u52a8\u4fee\u6539\uff0c\u81f3\u4e8e\u5927\u4e86\u6216\u8005\u5c0f\u4e86\u4f1a\u600e\u6837\uff0c\u5982\u679c\u4f60\u7406\u89e3\u6211\u8bf4\u7684\u4e86\u4e5f\u5c31\u660e\u767d\u4e86\u3002<\/p>\n

hashtable\u5c31\u662f\u5982\u6b64\u7684\u7b80\u5355\uff0c\u6211\u89c9\u5f97\u8fd9\u4e2a\u8ba9\u6211\u4eec\u5199\u4e5f\u4e0d\u96be\u5199\u51fa\u6765\u5dee\u4e0d\u591a\u7684\u3002\u6ca1\u51c6\u6bd4\u4eba\u5bb6\u5199\u7684\u597d\uff0c\u5c24\u5176\u662f\u4e0d\u4f1a\u5199for (int i = oldCapacity ; i– > 0 \ud83d\ude09 \u8fd9\u7c7b\u88c513\u4ee3\u7801\u2026\u2026<\/p>\n

\u4e0b\u9762\u8bb2hashmap\uff0c\u4e4b\u524d\u8bf4\u8fc7\u83b7\u53d6hash\u7684\u503chashtable\u6ca1\u6709\u5c06\u7b97\u5f0f\u4ee3\u7801\u590d\u7528\uff0c\u800chashmap\u7684hash\u51fd\u6570\u5c31\u662f\u5e72\u8fd9\u4e2a\u7684\uff1a<\/p>\n

static int hash(int h) {<\/p>\n

\/\/ This function ensures that hashCodes that differ only by<\/p>\n

\/\/ constant multiples at each bit position have a bounded<\/p>\n

\/\/ number of collisions (approximately 8 at default load factor).<\/p>\n

h ^= (h >>> 20) ^ (h >>> 12);<\/p>\n

return h ^ (h >>> 7) ^ (h >>> 4);<\/p>\n

}<\/p>\n

\u8fd9\u4e2ahash\u5c31\u662f\u5404\u79cd\u5f02\u6216\uff0c\u6211\u4e5f\u4e0d\u77e5\u9053\u4e3a\u5565\u8fd9\u6837\u5c31\u597d\u3002\u77e5\u9053\u7684\u53ef\u4ee5\u7ed9\u6211\u8bb2\u8bb2\u3002<\/p>\n

hashmap\u7684get\u3001put\u548chashtable\u57fa\u672c\u6ca1\u533a\u522b\uff0c\u53ea\u4e0d\u8fc7\u56e0\u4e3amap\u652f\u6301key==null\uff0c\u56e0\u6b64\u6709\u4e00\u4e2a\u4e13\u95e8\u7684\u5904\u7406\u3002null\u7684hash\u6c38\u8fdc\u662f0.\u6b64\u5916hashmap\u7684\u5404\u79cd\u64cd\u4f5c\u90fd\u5c01\u88c5\u4e86\uff0c\u6bd4\u5982void addEntry(int hash, K key, V value, int bucketIndex)\u3002\u4e0d\u8fc7\u6709\u4e2a\u4e0d\u540c\u662fhashmap\u5728rehash\u7684\u65f6\u5019\u7528\u8fd9\u4e2a\uff1a<\/p>\n

void resize(int newCapacity) {<\/p>\n

Entry[] oldTable = table;<\/p>\n

int oldCapacity = oldTable.length;<\/p>\n

if (oldCapacity == MAXIMUM_CAPACITY) {<\/p>\n

threshold = Integer.MAX_VALUE;<\/p>\n

return;<\/p>\n

}<\/p>\n

Entry[] newTable = new Entry[newCapacity];<\/p>\n

transfer(newTable);<\/p>\n

table = newTable;<\/p>\n

threshold = (int)(newCapacity * loadFactor);<\/p>\n

}<\/p>\n

\u91cc\u9762\u7684transfer\u5c31\u662f\u8ddfhashtable\u4e00\u6837\u7684\u94fe\u8868\u5f0f\u7684\u63d2\u5165\u3002\u56e0\u4e3a\u65b0\u7684\u5bb9\u91cf\u662f\u53c2\u6570\uff0c\u6240\u4ee5\u9700\u8981\u544a\u8bc9\u5927\u5bb6\u8c03\u7528\u6b64\u51fd\u6570\u7684\u65f6\u5019\u662fresize(2 * table.length)\uff0c\u5c31\u662f\u8bf4\u5927\u5c0f\u53ea\u662f\u5355\u7eaf\u7684\u6269\u5927\u4e862\u500d\u800c\u975e\u518d+1\uff0c\u800c\u4e14hashmap\u6709\u4e2a\u6700\u5927\u7684\u5bb9\u91cfMAXIMUM_CAPACITY=\u00a01 << 30\uff0c\u8d85\u8fc7\u8fd9\u4e2a\u5c31\u4e0d\u6269\u5bb9\u4e86\uff0c\u800chashtable\u4f3c\u4e4e\u6ca1\u8fd9\u4e2a\u9650\u5236\u3002\u4e0d\u8fc7\u5b9e\u9645\u4e0a\u5982\u679c\u771f\u7684\u4e0d\u9650\u5236\u5230\u6700\u540e\u4e00\u5b9a\u4f1a\u60b2\u5267\u7684\u3002\u81f3\u4e8e\u4e3a\u4f55\u4e0d\u5fc5+1\uff0c\u53ea\u80fd\u8bf4\u662f\u56e0\u4e3ahash\u51fd\u6570\u592a\u597d\u4e86\u56e0\u800c\u4e0d\u7528\u90a3\u4e48\u9ebb\u70e6\u4e86\u2026\u2026<\/p>\n

\u5230\u8fd9\u91cc\u672c\u6587\u5c31\u5927\u529f\u544a\u6210\u4e86\u3002\u6700\u540e\u603b\u7ed3\u4e00\u4e0b\uff1a<\/p>\n

hash\u5f88\u7b80\u5355\uff0c\u96be\u7684\u662fhash\u51fd\u6570\u3002\u800c\u6211\u4eec\u4e0d\u53ef\u80fd\u6240\u6709\u7684\u90fd\u7528hashcode\u6765\u83b7\u53d6\u8fd9\u4e2a\u51e0\u4e4e\u5f88\u968f\u673a\u7684\u7801\uff0c\u5927\u591a\u6570\u6211\u4eec\u8981hash\u7684\u4e1c\u897f\u5f97\u7531\u6211\u4eec\u81ea\u5df1\u5199hash\uff0c\u65e0\u8bba\u53c2\u6570\u8fd8\u662f\u7b97\u6cd5\u3002<\/p>\n

java\u63d0\u4f9b\u7684\u4e1c\u897f\u5f88\u591a\uff0c\u56e0\u4e3a\u6bd4c++\u66f4\u5e74\u8f7b\u800c\u4e14\u968f\u65f6\u66f4\u65b0\u6240\u4ee5\u6bd4c++\u5728\u5e93\u4e0a\u8981\u597d\u4e00\u4e9b\uff0c\u4f46\u4f9d\u7136\u6709\u65b0\u65e7\u597d\u574f\u3002\u90a3\u8fd9\u4e2a\u6765\u8bf4\uff0chashmap\u5e94\u8be5\u597d\u4e8ehashtable\u3002\u4e0d\u8fc7\u6587\u6863\u8bf4hashmap\u662f\u4e0d\u540c\u6b65\u7684\uff0c\u4f46\u6211\u6ca1\u770b\u51fa\u6765\u4e24\u8005\u6709\u4f55\u533a\u522b\uff0c\u4e5f\u8bb8\u53ea\u662f\u56e0\u4e3a\u52a0\u4e86\u90a3\u51e0\u4e2a\u5173\u952e\u5b57\u9020\u6210\u7684\uff1f<\/p>\n","protected":false},"excerpt":{"rendered":"

\u524d\u6587\u5df2\u7ecf\u63d0\u5230\u4e86\u5b9e\u73b0\u5b57\u5178\u7684\u4e00\u79cd\u5f62\u5f0f\uff0c\u4e8c\u53c9\u6811\u3002\u4e0b\u9762\u6765\u8bf4\u53e6\u4e00\u79cd\u5f62\u5f0f\uff0c\u54c8\u5e0c\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[9,14],"_links":{"self":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223093"}],"collection":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/comments?post=223093"}],"version-history":[{"count":1,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223093\/revisions"}],"predecessor-version":[{"id":224559,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223093\/revisions\/224559"}],"wp:attachment":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/media?parent=223093"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/categories?post=223093"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/tags?post=223093"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}