{"id":11518,"date":"2023-06-29T16:28:15","date_gmt":"2023-06-29T08:28:15","guid":{"rendered":"http:\/\/123.57.164.21\/?p=11518"},"modified":"2023-06-29T16:28:15","modified_gmt":"2023-06-29T08:28:15","slug":"hashmap%e4%b8%ba%e4%bb%80%e4%b9%88%e6%98%af%e7%ba%bf%e7%a8%8b%e4%b8%8d%e5%ae%89%e5%85%a8%e7%9a%84","status":"publish","type":"post","link":"https:\/\/92it.top\/?p=11518","title":{"rendered":"HashMap\u4e3a\u4ec0\u4e48\u662f\u7ebf\u7a0b\u4e0d\u5b89\u5168\u7684"},"content":{"rendered":"\n

\u5927\u5bb6\u90fd\u77e5\u9053HasnMap\u5728\u591a\u7ebf\u7a0b\u7684\u573a\u666f\u4e2d\u662f\u4e0d\u5b89\u5168\u7684\uff0c\u4e3a\u4ec0\u4e48\u5462\uff1f\u9996\u5148\u8981\u4ece\u5b83\u7684\u5e95\u5c42\u6570\u636e\u7ed3\u6784\u8bf4\u8d77\u2026\u2026<\/p>\n\n\n\n

JDK7\u4e2d\u7684HashMap<\/strong><\/p>\n\n\n\n

\n\n\n\n

HashMap\u5e95\u5c42\u7ef4\u62a4\u4e00\u4e2a\u6570\u7ec4\uff0c\u6570\u7ec4\u4e2d\u7684\u6bcf\u4e00\u9879\u90fd\u662f\u4e00\u4e2aEntry<\/p>\n\n\n\n

transient Entry<K,V>[] table;<\/pre>\n\n\n\n
\u6211\u4eec\u5411 HashMap \u4e2d\u6240\u653e\u7f6e\u7684\u5bf9\u8c61\u5b9e\u9645\u4e0a\u662f\u5b58\u50a8\u5728\u8be5\u6570\u7ec4\u5f53\u4e2d\uff1b \u800cMap\u4e2d\u7684key\uff0cvalue\u5219\u4ee5Entry\u7684\u5f62\u5f0f\u5b58\u653e\u5728\u6570\u7ec4\u4e2d<\/p>\n\n\n\n
static class Entry<K,V> implements Map.Entry<K,V> {\n        final K key;\n        V value;\n        Entry<K,V> next;\n        int hash;<\/pre>\n\n\n\n
\u800c\u8fd9\u4e2aEntry\u5e94\u8be5\u653e\u5728\u6570\u7ec4\u7684\u54ea\u4e00\u4e2a\u4f4d\u7f6e\u4e0a\uff08\u8fd9\u4e2a\u4f4d\u7f6e\u901a\u5e38\u79f0\u4e3a\u4f4d\u6876\u6216\u8005hash\u6876\uff0c\u5373hash\u503c\u76f8\u540c\u7684Entry\u4f1a\u653e\u5728\u540c\u4e00\u4f4d\u7f6e\uff0c\u7528\u94fe\u8868\u76f8\u8fde\uff09\uff0c\u662f\u901a\u8fc7key\u7684hashCode\u6765\u8ba1\u7b97\u7684\u3002<\/p>\n\n\n\n
final int hash(Object k) {\n        int h = 0;\n        h ^= k.hashCode();\n\n        h ^= (h >>> 20) ^ (h >>> 12);\n        return h ^ (h >>> 7) ^ (h >>> 4);\n    }\n<\/pre>\n\n\n\n
\u901a\u8fc7hash\u8ba1\u7b97\u51fa\u6765\u7684\u503c\u5c06\u4f1a\u4f7f\u7528indexFor\u65b9\u6cd5\u627e\u5230\u5b83\u5e94\u8be5\u6240\u5728\u7684table\u4e0b\u6807\uff1a<\/p>\n\n\n\n
static int indexFor(int h, int length) {\n        return h & (length-1);\n    }<\/pre>\n\n\n\n
\u8fd9\u4e2a\u65b9\u6cd5\u5176\u5b9e\u76f8\u5f53\u4e8e\u5bf9table.length\u53d6\u6a21\u3002<\/p>\n\n\n\n
\u5f53\u4e24\u4e2akey\u901a\u8fc7hashCode\u8ba1\u7b97\u76f8\u540c\u65f6\uff0c\u5219\u53d1\u751f\u4e86hash\u51b2\u7a81(\u78b0\u649e)\uff0cHashMap\u89e3\u51b3hash\u51b2\u7a81\u7684\u65b9\u5f0f\u662f\u7528\u94fe\u8868\u3002<\/p>\n\n\n\n
\u5f53\u53d1\u751fhash\u51b2\u7a81\u65f6\uff0c\u5219\u5c06\u5b58\u653e\u5728\u6570\u7ec4\u4e2d\u7684Entry\u8bbe\u7f6e\u4e3a\u65b0\u503c\u7684next\uff08\u8fd9\u91cc\u8981\u6ce8\u610f\u7684\u662f\uff0c\u6bd4\u5982A\u548cB\u90fdhash\u540e\u90fd\u6620\u5c04\u5230\u4e0b\u6807i\u4e2d\uff0c\u4e4b\u524d\u5df2\u7ecf\u6709A\u4e86\uff0c\u5f53map.put(B)\u65f6\uff0c\u5c06B\u653e\u5230\u4e0b\u6807i\u4e2d\uff0cA\u5219\u4e3aB\u7684next\uff0c\u6240\u4ee5\u65b0\u503c\u5b58\u653e\u5728\u6570\u7ec4\u4e2d\uff0c\u65e7\u503c\u5728\u65b0\u503c\u7684\u94fe\u8868\u4e0a\uff09<\/p>\n\n\n\n
\u793a\u610f\u56fe\uff1a<\/p>\n\n\n\n
\"\"<\/figure><\/div>\n\n\n\n
\u6240\u4ee5\u5f53hash\u51b2\u7a81\u5f88\u591a\u65f6\uff0cHashMap\u9000\u5316\u6210\u94fe\u8868\u3002<\/p>\n\n\n\n
\u603b\u7ed3\u4e00\u4e0bmap.put\u540e\u7684\u8fc7\u7a0b\uff1a<\/strong><\/p>\n\n\n\n
\n\n\n\n
\u5f53\u5411 HashMap \u4e2d put \u4e00\u5bf9\u952e\u503c\u65f6\uff0c\u5b83\u4f1a\u6839\u636e key\u7684 hashCode \u503c\u8ba1\u7b97\u51fa\u4e00\u4e2a\u4f4d\u7f6e\uff0c \u8be5\u4f4d\u7f6e\u5c31\u662f\u6b64\u5bf9\u8c61\u51c6\u5907\u5f80\u6570\u7ec4\u4e2d\u5b58\u653e\u7684\u4f4d\u7f6e\u3002<\/p>\n\n\n\n
\u5982\u679c\u8be5\u4f4d\u7f6e\u6ca1\u6709\u5bf9\u8c61\u5b58\u5728\uff0c\u5c31\u5c06\u6b64\u5bf9\u8c61\u76f4\u63a5\u653e\u8fdb\u6570\u7ec4\u5f53\u4e2d\uff1b\u5982\u679c\u8be5\u4f4d\u7f6e\u5df2\u7ecf\u6709\u5bf9\u8c61\u5b58\u5728\u4e86\uff0c\u5219\u987a\u7740\u6b64\u5b58\u5728\u7684\u5bf9\u8c61\u7684\u94fe\u5f00\u59cb\u5bfb\u627e(\u4e3a\u4e86\u5224\u65ad\u662f\u5426\u503c\u76f8\u540c\uff0cmap\u4e0d\u5141\u8bb8<key,value>\u952e\u503c\u5bf9\u91cd\u590d)\uff0c \u5982\u679c\u6b64\u94fe\u4e0a\u6709\u5bf9\u8c61\u7684\u8bdd\uff0c\u518d\u53bb\u4f7f\u7528 equals\u65b9\u6cd5\u8fdb\u884c\u6bd4\u8f83\uff0c\u5982\u679c\u5bf9\u6b64\u94fe\u4e0a\u7684\u6bcf\u4e2a\u5bf9\u8c61\u7684 equals \u65b9\u6cd5\u6bd4\u8f83\u90fd\u4e3a false\uff0c\u5219\u5c06\u8be5\u5bf9\u8c61\u653e\u5230\u6570\u7ec4\u5f53\u4e2d\uff0c\u7136\u540e\u5c06\u6570\u7ec4\u4e2d\u8be5\u4f4d\u7f6e\u4ee5\u524d\u5b58\u5728\u7684\u90a3\u4e2a\u5bf9\u8c61\u94fe\u63a5\u5230\u6b64\u5bf9\u8c61\u7684\u540e\u9762\u3002<\/p>\n\n\n\n
\u503c\u5f97\u6ce8\u610f\u7684\u662f\uff0c\u5f53key\u4e3anull\u65f6\uff0c\u90fd\u653e\u5230table[0]\u4e2d<\/p>\n\n\n\n
private V putForNullKey(V value) {\n        for (Entry<K,V> e = table[0]; e != null; e = e.next) {\n            if (e.key == null) {\n                V oldValue = e.value;\n                e.value = value;\n                e.recordAccess(this);\n                return oldValue;\n            }\n        }\n        modCount++;\n        addEntry(0, null, value, 0);\n        return null;\n    }<\/pre>\n\n\n\n
\u5f53size\u5927\u4e8ethreshold\u65f6\uff0c\u4f1a\u53d1\u751f\u6269\u5bb9\u3002<\/p>\n\n\n\n
threshold=capacity*loadFactor<\/strong><\/p>\n\n\n\n