\u8fd9\u7bc7\u6587\u7ae0\u4e3b\u8981\u662f\u5bf9JDK6\u548cJava8\u91ccjava.util.HashMap\u7684\u4e00\u4e9b\u6e90\u7801\u7684\u89e3\u8bfb\u3002Java8\u91cc\u7684\u6539\u8fdb\u4e3b\u8981\u662f\u4e3a\u4e86\u89e3\u51b3\u54c8\u5e0c\u78b0\u649e\u653b\u51fb\u3002<\/p>\n
\u8fd9\u4e2a\u6e90\u7801\u89e3\u8bfb\u4e3b\u8981\u5173\u6ce8\u57fa\u7840\u6570\u636e\u7ed3\u6784\u3001put(key,value)\u903b\u8f91 \u548c\u904d\u5386\u6240\u6709\u952e\u503c\u5bf9\u7684\u903b\u8f91\u3002
\n<\/p>\n
JDK1.6<\/h2>\n\u57fa\u7840\u6570\u636e\u7ed3\u6784<\/h3>\n
\u5148\u770b\u4e0bJDK1.6\u91cc\u9762HashMap\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5148\u662f\u94fe\u8868\u7684\u7ed3\u6784\uff1a<\/p>\n
static class Entry<K,V> implements Map.Entry<K,V> {\n final K key ;\n V value;\n Entry<K,V> next; \/\/ \u6307\u5411\u94fe\u8868\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\u3002\n int hash ; \/\/ \u6839\u636ekey\u7684hashCode\u8ba1\u7b97\u5f97\u5230\uff0c\u5373\u4f7f\u8fdb\u884cresize\u4e5f\u4e0d\u4f1a\u6539\u53d8\u3002\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n<\/code><\/pre>\n\u5355\u5411\u94fe\u8868\u3002<\/p>\n
\u4f4d\u6876\u7684\u7ed3\u6784\uff1a<\/p>\n
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,\n Cloneable, Serializable {\n\n \/\/ \u4f4d\u6876\uff0c\u6bcf\u4e2a\u952e\u503c\u5bf9\u90fd\u5c01\u88c5\u4e3aEntry\u7ed3\u6784\u3002\n \/\/ \u4f4d\u6876\u4f1a\u521d\u59cb\u5316\u4e3a\u4e00\u4e2a\u5927\u4e8e\u7528\u6237\u6307\u5b9a\u7684\u521d\u59cb\u5bb9\u91cf\u7684initialCapacity\u7684\n transient Entry<K,V>[] table;\n\n \/\/ HashMap\u53d1\u751f\u7ed3\u6784\u6027\u4fee\u6539\u7684\u6b21\u6570\uff0c\u4e5f\u7528\u4e8e\u5224\u65ad\u662f\u5426\u5b58\u5728\u5e76\u53d1\u4fee\u6539\u6216\u8fed\u4ee3\u89c6\u56fe\u7684\u5feb\u901f\u5931\u8d25\uff0c\n \/\/ \u5982\u679c\u5b58\u5728\u8fd9\u4e24\u79cd\u60c5\u51b5\uff0c\u629b\u51faConcurrentModificationException\u5f02\u5e38\u3002\n \/\/ \u7528volatile\u4fdd\u8bc1\u4e86\u5185\u5b58\u53ef\u89c1\u6027\n transient volatile int modCount;\n\n \/\/ \u5b9e\u9645\u5b58\u50a8\u7684\u5bf9\u952e\u503c\u5bf9\u7684\u6570\u91cf\n transient int size;\n\n \/\/ \u8d1f\u8f7d\u56e0\u5b50\n final float loadFactor;\n\n \/\/ \u5f53\u952e\u503c\u5bf9\u7684\u6570\u91cf\u8fbe\u5230\u6216\u8d85\u8fc7\u8fd9\u4e2a\u9600\u503c\u65f6\uff0c\u5c06\u5bf9\u4f4d\u6876\u8fdb\u884c\u6269\u5c55\uff0c\u518d\u628a\u6240\u6709\u5143\u7d20\u91cd\u65b0\u6563\u5217\u5230\u65b0\u4f4d\u6876\u3002\n int threshold;\n\n \/\/ \u4e0b\u9762\u4ece\u6784\u9020\u51fd\u6570\u770b\u770b\u4e0a\u9762\u51e0\u4e2a\u5c5e\u6027\u7684\u5173\u7cfb\u3002\n public HashMap(int initialCapacity, float loadFactor) {\n if (initialCapacity < 0)\n throw new IllegalArgumentException(\"Illegal initial capacity: \"\n + initialCapacity);\n\n if (initialCapacity > MAXIMUM_CAPACITY)\n initialCapacity = MAXIMUM_CAPACITY;\n\n if (loadFactor <= 0 || Float.isNaN(loadFactor))\n throw new IllegalArgumentException(\"Illegal load factor: \"\n + loadFactor);\n\n \/\/ \u4f4d\u6876\u7684\u957f\u5ea6\u5fc5\u987b\u662f2\u7684\u5e42\uff0c\u5927\u4e8einitialCapacity\u7684\u6700\u5c0f\u7684\u4e14\u662f2\u7684\u5e42\u7684\u6570\u3002\n \/\/ Find a power of 2 >= initialCapacity\n int capacity = 1;\n while (capacity < initialCapacity)\n capacity <<= 1;\n\n this.loadFactor = loadFactor; \n threshold = ( int) (capacity * loadFactor); \/\/ \u6bcf\u6b21resize\u90fd\u4f1a\u6539\u53d8\n table = new Entry[capacity];\n init(); \/\/ \u7a7a\u65b9\u6cd5\uff0c\u7559\u7ed9\u5b50\u7c7b\u5b9e\u73b0\n }\n\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u548c\u5e38\u91cf\u7701\u7565\n}\n<\/code><\/pre>\n\u57fa\u7840\u65b9\u6cd5<\/h3>\n\/\/ \u8ba1\u7b97hash\u503ch\u5728\u957f\u5ea6\u4e3alength\u7684\u4f4d\u6876\u7684\u4f4d\u7f6e\u3002\nstatic int indexFor(int h, int length) {\n \/\/ \u7528\u4f4d\u8fd0\u7b97\u66ff\u4ee3\u6c42\u6a21\uff0c\u8fd9\u5c31\u662f\u4e3a\u4ec0\u4e48\u4f4d\u6876\u7684\u957f\u5ea6\u5fc5\u987b\u662f2\u7684\u5e42\u3002\n return h & (length - 1);\n}\n\n\/\/ \u6839\u636ekey\u7684hashCode h\u6765\u8ba1\u7b97\u4e00\u4e2a\u65b0\u7684hash\u503c\u3002\n\/\/ \u6309\u6e90\u7801\u91cc\u7684\u8bf4\u660e\uff0c\u53ea\u7528key\u7684hashCode\u7684\u4f4e\u4f4d\u5b57\u8282\u5bb9\u6613\u78b0\u649e\u51b2\u7a81\u3002\nstatic int hash(int h) {\n \/\/ This function ensures that hashCodes that differ only by\n \/\/ constant multiples at each bit position have a bounded\n \/\/ number of collisions (approximately 8 at default load factor).\n h ^= (h >>> 20) ^ (h >>> 12);\n return h ^ (h >>> 7) ^ (h >>> 4);\n}\n<\/code><\/pre>\nput\u65b9\u6cd5<\/h3>\npublic V put(K key, V value) {\n \/\/ \u7531\u4e8eHashMap\u8fd0\u884ckey\u4e3a\u7a7a\uff0c\u6240\u4ee5\u9700\u8981\u5bf9key\u4e3anull\u7684\u8fdb\u884c\u7279\u6b8a\u5904\u7406\u3002\n if (key == null)\n return putForNullKey(value);\n\n \/\/ \u6839\u636ekey\u7684hashCode h\u6765\u8ba1\u7b97\u4e00\u4e2a\u65b0\u7684hash\u503c\u3002\n int hash = hash(key.hashCode());\n\n \/\/ \u786e\u5b9akey\u6240\u5728\u4f4d\u6876\u7684\u4f4d\u7f6e\u3002\n int i = indexFor(hash, table.length);\n\n \/\/ \u904d\u5386\u94fe\u8868\uff0chashCode\u76f8\u7b49\u7684\u4e0d\u4e00\u5b9a\u5c31\u662f\u540c\u4e00\u4e2a\u5bf9\u8c61\u3002\n for (Entry<K, V> e = table[i]; e != null; e = e.next) {\n Object k;\n \/\/ hashCode\u76f8\u7b49\u7684\u4e0d\u4e00\u5b9a\u5c31\u662f\u540c\u4e00\u4e2a\u5bf9\u8c61\u3002\n \/\/ \u5148\u5224\u65ad\u5bf9\u8c61\u5f15\u7528\u76f8\u7b49\uff0c\u4e00\u822c\u60c5\u51b5\u4e0b\u66f4\u65b0\u4e00\u4e2akey-value\u7684key\n \/\/ \u90fd\u662f\u540c\u4e00\u4e2a\u5bf9\u8c61\u7684\uff0c\u6240\u4ee5\u53ef\u4ee5\u51cf\u5c11\u4e00\u6b21\u65b9\u6cd5\u8c03\u7528\u3002\n if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {\n \/\/ \u5982\u679ckey\u5df2\u5b58\u5728\uff0c\u5219\u66f4\u65b0\u5bf9\u5e94\u7684\u503c\n V oldValue = e.value;\n e.value = value;\n e.recordAccess( this); \/\/ \u7a7a\u65b9\u6cd5\n return oldValue;\n }\n }\n\n \/\/ \u66f4\u65b0\u8ba1\u6570\u5668\uff0c\u5982\u679c\u6b63\u5728\u8fed\u4ee3\uff0c\u5219\u53ef\u4ee5\u5feb\u901f\u5931\u8d25\uff0c\n \/\/ \u629b\u51faConcurrentModificationException\u5f02\u5e38\u3002\n modCount++; \n addEntry(hash, key, value, i); \/\/ \u6dfb\u52a0\u65b0\u8282\u70b9\n return null ;\n}\n\nprivate V putForNullKey(V value) {\n \/\/ key\u4e3anull\u7684Entry\u603b\u662f\u653e\u5728\u4f4d\u68760\u3002\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}\n\/\/ \u611f\u89c9\u5bf9key\u4e3anull\u7684Entry\u6bd4\u8f83\u86cb\u75bc\uff0c\u5982\u679c\u8fd9\u4e2aEntry\u4f5c\u4e3a\u4e00\u4e2a\u72ec\u7acb\u7684\u5c5e\u6027\uff0c\n\/\/ \u5219\u5728\u904d\u5386\u7684\u65f6\u5019\u9700\u8981\u7279\u6b8a\u5904\u7406\u4e0b\u3002\n\n\nvoid addEntry(int hash, K key, V value, int bucketIndex) {\n \/\/ \u53d6\u51fa\u6240\u5728\u4f4d\u6876\u7684\u94fe\u8868\u7684\u9996\u8282\u70b9\u3002\n Entry<K, V> e = table[bucketIndex];\n\n \/\/ \u628a\u539f\u5934\u8282\u70b9\u4f5c\u4e3a\u65b0\u8282\u70b9\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u628a\u65b0\u8282\u70b9\u67e5\u5230\u94fe\u8868\u7684\u9996\u90e8\u3002\n table[bucketIndex] = new Entry<K, V>(hash, key, value, e);\n\n \/\/ \u5982\u679c\u8fbe\u5230\u6216\u8d85\u8fc7\u9600\u503c\uff0c\u5219\u8fdb\u884c\u6269\u5bb9\u548c\u91cd\u65b0\u6563\u5217\u3002\n if (size++ >= threshold)\n resize(2 * table.length);\n}\n<\/code><\/pre>\nget\u65b9\u6cd5<\/h3>\n
\u4e0eput\u65b9\u6cd5\u7684\u903b\u8f91\u5f88\u76f8\u4f3c\u3002<\/p>\n
resize\u65b9\u6cd5<\/h3>\n
resize\u65f6\u539f\u6709\u7684Entry\u4e0d\u4f1a\u53d8\uff0c\u76f4\u63a5\u6563\u5217\u5230\u65b0\u7684\u4f4d\u6876\u3002<\/p>\n
void resize(int newCapacity) {\n Entry[] oldTable = table;\n int oldCapacity = oldTable.length;\n if (oldCapacity == MAXIMUM_CAPACITY) {\n threshold = Integer.MAX_VALUE;\n return;\n }\n\n Entry[] newTable = new Entry[newCapacity]; \/\/ \u521b\u5efa\u6307\u5b9a\u5bb9\u91cf\u7684\u65b0\u7684\u4f4d\u6876\n transfer(newTable); \/\/ \u628aEntry\u6563\u5217\u5230\u65b0\u7684\u4f4d\u6876\n table = newTable;\n threshold = ( int) (newCapacity * loadFactor);\/\/ \u8ba1\u7b97\u65b0\u7684\u9600\u503c\n}\n\nvoid transfer(Entry[] newTable) {\n \/\/ \u8fd9\u91cc\u628a\u5bf9\u8c61\u7684\u5c5e\u6027\u8d4b\u503c\u7ed9\u672c\u5730\u53d8\u91cf\u662f\u4e3a\u4e86\u63d0\u5347\u6027\u80fd\uff0c\u65b9\u6cd5\u7684\u672c\u5730\u53d8\u91cf\u662f\u5b58\u653e\u5728\u65b9\u6cd5\u6808\u4e0a\u7684\uff0c\n \/\/ \u5bf9\u8c61\u7684\u5c5e\u6027\u662f\u5b58\u653e\u5728\u5806\u4e0a\u7684\uff0c\u8bbf\u95ee\u6808\u6bd4\u8bbf\u95ee\u5806\u8981\u9ad8\u6548\u3002\u8fd9\u79cd\u505a\u6cd5\u5728\u5f88\u591a\u5730\u65b9\u90fd\u53ef\u4ee5\u770b\u5230\u3002\n Entry[] src = table;\n int newCapacity = newTable.length;\n for (int j = 0; j < src.length; j++) { \/\/ \u904d\u5386\u4f4d\u6876\n Entry<K, V> e = src[j];\n if (e != null) {\n src[j] = null;\n \/\/ \u904d\u5386\u94fe\u8868\n do {\n Entry<K, V> next = e.next;\n \/\/ \u8ba1\u7b97Entry\u5728\u65b0\u4f4d\u6876\u7684\u4f4d\u7f6e\n int i = indexFor(e.hash, newCapacity);\n \/\/ \u4e0b\u9762\u4e24\u884c\u628aEntry\u63d2\u5230\u94fe\u8868\u7684\u9996\u90e8\n e.next = newTable[i];\n newTable[i] = e;\n e = next;\n } while (e != null);\n }\n }\n}\n<\/code><\/pre>\n\u903b\u8f91\u4e0d\u7b97\u590d\u6742\u3002<\/p>\n
\u904d\u5386<\/h3>\n
\u8fd9\u91cc\u53ea\u8bf4\u904d\u5386entrySet\uff0c\u5b83\u662f\u901a\u8fc7\u4e00\u4e2aHashIterator\u7684\u5185\u90e8\u7c7b\u6765\u5b9e\u73b0\u7684\u3002<\/p>\n
private abstract class HashIterator<E> implements Iterator<E> {\n Entry<K, V> next; \/\/ \u5f85\u8fd4\u56de\u7684\u4e0b\u4e00\u4e2aentry\n int expectedModCount; \/\/ \u7528\u4e8e\u5feb\u901f\u5931\u8d25\n int index; \/\/ \u904d\u5386\u7684\u5f53\u524d\u69fd\u4f4d\uff0c\u9ed8\u8ba4\u4ece0\u53f7\u69fd\u4f4d\u5f00\u59cb\n Entry<K, V> current; \/\/ \u5f53\u524d\u5df2\u8fd4\u56de\u7684\u6700\u540e\u7684entry\n\n HashIterator() {\n expectedModCount = modCount;\n if (size > 0) { \/\/ advance to first entry\n Entry[] t = table;\n \/\/ \u5b9a\u4f4d\u5230\u7b2c\u4e00\u4e2a\u4e0d\u4e3anull\u7684Entry\n while (index < t.length && (next = t[index++]) == null)\n ;\n }\n }\n\n public final boolean hasNext() {\n return next != null;\n }\n\n final Entry<K, V> nextEntry() {\n \/\/ \u68c0\u6d4b\u662f\u5426\u5b58\u5728\u5e76\u53d1\u4fee\u6539\u3002\n if (modCount != expectedModCount)\n throw new ConcurrentModificationException();\n\n Entry<K, V> e = next;\n\n \/\/ \u9632\u6b62\u4e0d\u8c03\u7528hasNext()\u65b9\u6cd5\u5224\u65ad\u662f\u5426\u8fd8\u6709\u66f4\u591a\u5143\u7d20\u800c\u76f4\u63a5\u8c03\u7528next()\u65b9\u6cd5\u7684\u60c5\u51b5\u3002\n if (e == null) \n throw new NoSuchElementException();\n\n if ((next = e.next) == null) {\n \/\/ \u5f53\u524d\u6240\u5728\u94fe\u8868\u904d\u5386\u5b8c\u6210\uff0c\u5b9a\u4f4d\u5230\u4e0b\u4e00\u4e2a\u4e0d\u4e3anull\u7684entry\n Entry[] t = table;\n while (index < t.length && (next = t[index++]) == null)\n ;\n }\n current = e;\n return e;\n }\n\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n<\/code><\/pre>\n\u5728Java8\u7684\u8fdb\u5316<\/h2>\n
\u8bf4\u660e\u4e0b\uff1a\u8fd9\u4e2a\u662f\u57fa\u4e8eJava 8 EA \u7248\u91cc\u7684\u6e90\u7801\u3002<\/strong><\/p>\nJava 8 \u91ccHashMap\u7684\u4e00\u4e2a\u91cd\u5927\u6539\u8fdb\u662f\u4e3a\u4e86\u89e3\u51b3\u54c8\u5e0c\u78b0\u649e\u653b\u51fb\uff0c\u8fd9\u4e2a\u54c8\u5e0c\u78b0\u649e\u653b\u51fb\u7b80\u5355\u8bf4\u5c31\u662f\u901a\u8fc7\u7cbe\u5fc3\u6784\u5efa\u4e00\u7ec4key\uff0c\u4f7f\u8fd9\u4e9bkey\u90fd\u6620\u5c04\u5230\u540c\u4e00\u4e2a\u69fd\u4f4d\uff0c\u4f7f\u6574\u4e2aHashMap\u9000\u5316\u4e3a\u4e00\u4e2a\u5355\u94fe\u8868\uff0c\u8fd9\u4f1a\u5927\u5927\u52a3\u5316HashMap\u7684\u64cd\u4f5c\u6027\u80fd\uff0c\u66f4\u591a\u4fe1\u606f\u53ef\u4ee5google\u4e4b\u3002<\/p>\n
\u6539\u8fdb\u4e3b\u8981\u6709\u4e0b\u9762\u8fd9\u4e9b\uff1a<\/p>\n
\n- \u5bf9\u4e8ekey\u4e3anull\u7684entry\uff0c\u653e\u5728\u72ec\u7acb\u7684\u5c5e\u6027\u91cc\u3002<\/li>\n
- \u5f53\u67d0\u4e2a\u69fd\u4f4d\u7684\u94fe\u8868\u7684\u957f\u5ea6\u8fbe\u5230\u67d0\u4e2a\u9600\u503c\u65f6\uff0c\u8fd9\u4e2a\u94fe\u8868\u5c06\u88ab\u8f6c\u6362\u4e3a\u7ea2\u9ed1\u6811\u3002<\/li>\n
- modCount\u53bb\u9664\u4e86volatile\u4fee\u9970\u7b26\uff0c\u6bd5\u7adf\u8fd9\u4e2a\u7c7b\u662f\u58f0\u660e\u4e3a\u975e\u7ebf\u7a0b\u5b89\u5168\u7684\u3002volatile\u53d8\u91cf\u7684\u8bfb\u5199\u9700\u8981\u4e00\u4e9b\u5185\u5b58\u5173\u5361\uff0c\u5f00\u9500\u5927\u70b9\u3002<\/li>\n
- \u589e\u52a0\u4e86\u4e00\u4e2ahashSeed\u5c5e\u6027\uff0c\u7528\u4e8e\u63d0\u5347key\u6563\u5217\u5230\u69fd\u7684\u968f\u673a\u6027\u3002<\/li>\n<\/ul>\n
\u5728\u4e0b\u9762\u7684\u4ee3\u7801\u903b\u8f91\u91cc\uff0c\u7ea2\u9ed1\u6811\u5185\u90e8\u5982\u4f55\u5904\u7406\uff0c\u8fd9\u91cc\u4e0d\u6d89\u53ca\u3002<\/p>\n
\u57fa\u7840\u6570\u636e\u7ed3\u6784<\/h3>\n\/\/ \u94fe\u8868\u8282\u70b9\nstatic class Entry<K, V> implements Map.Entry<K, V> {\n final K key;\n V value;\n Object next; \/\/ \u53ef\u4ee5\u662f Entry \u6216 TreeNode\uff0c\u7c7b\u578b\u4e0d\u518d\u662fEntry\n final int hash;\n\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n\n\/\/ \u7ea2\u9ed1\u6811\u7684\u8282\u70b9\nfinal static class TreeNode<K, V> {\n TreeNode parent; \/\/ red-black tree links\n TreeNode left;\n TreeNode right;\n TreeNode prev; \/\/ needed to unlink next upon deletion\n boolean red;\n final HashMap.Entry<K, V> entry; \/\/ \n\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n\n\n\/\/ \u7ea2\u9ed1\u6811\nfinal class TreeBin {\n static final int TREE_THRESHOLD = 16; \/\/ \u94fe\u8868\u957f\u5ea6\u8fbe\u5230\u8fd9\u4e2a\u9600\u503c\u65f6\u5c06\u8f6c\u6362\u4e3a\u7ea2\u9ed1\u6811\n TreeNode<K, V> root; \/\/ \u7ea2\u9ed1\u6811\u7684\u6839\u8282\u70b9\n TreeNode<K, V> first; \/\/ \u6709\u5e8f\u904d\u5386\u7ea2\u9ed1\u6811\u65f6\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n\n\/\/ HashMap\u7684\u4e3b\u8981\u5c5e\u6027\npublic class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,\n Cloneable, Serializable {\n \/\/ \u7701\u7565\u4e00\u4e9b\u5e38\u91cf\u5b9a\u4e49\n \/\/ \u69fd\u6570\u7ec4\u7684\u7c7b\u578b\u53d8\u4e3aObject\uff0c\u4e0d\u518d\u662fEntry\uff0c\u56e0\u4e3a\u69fd\u8fd8\u53ef\u4ee5\u653eTreeBin\u4e86\u3002\n transient Object[] table = EMPTY_TABLE;\n transient int size;\n int threshold;\n final float loadFactor;\n\n \/\/ \u53bb\u9664\u4e86volatile\u4fee\u9970\u7b26\uff0c\u6bd5\u7adf\u8fd9\u4e2a\u7c7b\u662f\u58f0\u660e\u4e3a\u975e\u7ebf\u7a0b\u5b89\u5168\u7684\u3002\n \/\/ volatile\u53d8\u91cf\u7684\u8bfb\u5199\u9700\u8981\u4e00\u4e9b\u5185\u5b58\u5173\u5361\uff0c\u5f00\u9500\u5927\u70b9\n transient int modCount;\n\n \/\/ \u968f\u673a\u79cd\u5b50\uff0c\u589e\u52a0key\u6563\u5217\u5230\u69fd\u7684\u968f\u673a\u6027\u3002\n transient final int hashSeed;\n\n \/\/ \u5b58\u50a8key\u4e3anull\u7684entry\u3002\n transient Entry<K, V> nullKeyEntry = null;\n\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n<\/code><\/pre>\n\u57fa\u7840\u65b9\u6cd5<\/h3>\nfinal int hash(Object k) {\n \/\/ hashSeed \u662f\u6bcf\u4e2a\u5b9e\u4f8b\u4e00\u4e2a\u7684\uff0c\u7528\u4e8e\u589e\u52a0\u968f\u673a\u6027\u3002\n int h = hashSeed ^ k.hashCode(); \n\n \/\/ This function ensures that hashCodes that differ only by\n \/\/ constant multiples at each bit position have a bounded\n \/\/ number of collisions (approximately 8 at default load factor).\n h ^= (h >>> 20) ^ (h >>> 12);\n return h ^ (h >>> 7) ^ (h >>> 4);\n}\n\n\/\/ indexFor \u65b9\u6cd5\u6ca1\u6709\u6539\u53d8\nstatic int indexFor(int h, int length) {\n \/\/ assert Integer.bitCount(length) == 1 :\n \/\/ \"length must be a non-zero power of 2\";\n return h & (length - 1);\n}\n<\/code><\/pre>\nput\u65b9\u6cd5<\/h3>\npublic V put(K key, V value) {\n \/\/ \u5982\u679c\u8349\u6570\u7ec4\u4e3a\u7a7a\u5219\u521d\u59cb\u5316\n if (table == EMPTY_TABLE) {\n inflateTable(threshold);\n }\n \/\/ \u7279\u6b8a\u5904\u7406key\u4e3anull\u7684\u952e\u503c\u5bf9\n if (key == null)\n return putForNullKey(value);\n\n \/\/ \u6839\u636ekey\u8ba1\u7b97\u54c8\u5e0c\u503c\n int hash = hash(key);\n\n \/\/ \u5b9a\u4f4d\u69fd\u4f4d\n int i = indexFor(hash, table.length);\n\n boolean checkIfNeedTree = false; \/\/ \u662f\u5426\u9700\u8981\u628a\u94fe\u8868\u8f6c\u6362\u4e3a TreeBin?\n\n if (table[i] instanceof Entry) {\/\/ \u662f\u4e2a\u94fe\u8868\n \/\/ Bin contains ordinary Entries. Search for key in the linked list\n \/\/ of entries, counting the number of entries. Only check for\n \/\/ TreeBin conversion if the list size is >= TREE_THRESHOLD.\n \/\/ (The conversion still may not happen if the table gets resized.)\n int listSize = 0; \/\/ \u8ba1\u7b97\u94fe\u8868\u957f\u5ea6\n Entry<K, V> e = (Entry<K, V>) table[i];\n for (; e != null; e = (Entry<K, V>) e.next) {\n Object k;\n \/\/ \u67e5\u627ekey\uff0c\u5982\u679c\u627e\u5230\u5219\u66f4\u65b0\u5bf9\u5e94\u7684\u503c\n if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {\n V oldValue = e.value;\n e.value = value;\n e.recordAccess( this);\n return oldValue;\n }\n listSize++;\n }\n \/\/ \u6ca1\u6709\u627e\u5230\uff0c\u9700\u8981\u6dfb\u52a0Entry\n \/\/ \u5224\u65ad\u662f\u5426\u9700\u8981\u628a\u94fe\u8868\u8f6c\u6362\u4e3a\u7ea2\u9ed1\u6811\n checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;\n\n } else if (table[i] != null) {\n \/\/ \u8fd9\u4e2a\u69fd\u4e3a\u5b58\u653e\u7684\u4e0d\u662f\u94fe\u8868\uff0c\u4e14\u4e0d\u4e3a\u7a7a\uff0c\u5219\u5fc5\u7136\u662f\u7ea2\u9ed1\u6811\n TreeBin e = (TreeBin) table[i];\n TreeNode p = e.putTreeNode(hash, key, value, null);\n if (p == null) { \/\/ putTreeNode() \u6dfb\u52a0\u4e86\u4e00\u4e2a\u65b0\u8282\u70b9\n modCount++;\n size++;\n \/\/ \u5982\u679c\u952e\u503c\u5bf9\u7684\u6570\u91cf\u5df2\u8fbe\u5230\u9600\u503c\uff0c\u91cd\u6563\u5217\n if (size >= threshold) {\n resize(2 * table.length);\n }\n return null ;\n } else { \/\/ putTreeNode() \u53d1\u73b0\u8fd9\u4e2akey\u5df2\u5b58\u5728\n Entry<K, V> pEntry = (Entry<K, V>) p.entry;\n V oldVal = pEntry.value;\n pEntry.value = value;\n pEntry.recordAccess( this);\n return oldVal;\n }\n }\n modCount++;\n \/\/ \u69fd\u4f4d\u4e3a\u7a7a\u6216\u5728\u94fe\u8868\u91cc\u6ca1\u6709\u627e\u5230\u5bf9\u5e94\u7684key\uff0c\u65b0\u589e\u8282\u70b9\u3002\n addEntry(hash, key, value, i, checkIfNeedTree);\n return null ;\n}\n\nvoid addEntry(int hash, K key, V value, int bucketIndex,\n boolean checkIfNeedTree) {\n \/\/ assert key != null;\n if ((size >= threshold) && (null != table[bucketIndex])) {\n resize(2 * table.length);\n hash = hash(key); \/\/ \u5e94\u8be5\u4e0d\u9700\u8981\u91cd\u65b0\u8ba1\u7b97\u54c8\u5e0c\u503c\u554a\uff1f\uff1f\n bucketIndex = indexFor(hash, table.length);\n }\n createEntry(hash, key, value, bucketIndex, checkIfNeedTree);\n}\n\nvoid createEntry(int hash, K key, V value, int bucketIndex,\n boolean checkIfNeedTree) {\n \/\/ assert key != null;\n @SuppressWarnings( \"unchecked\")\n Entry<K, V> e = (Entry<K, V>) table[bucketIndex];\n \/\/ \u628a\u65b0\u7684Entry\u67e5\u5230\u94fe\u8868\u9996\u90e8\u5148\n table[bucketIndex] = newEntry(hash, key, value, e);\n size++;\n\n if (checkIfNeedTree) {\/\/ \u9700\u8981\u628a\u94fe\u8868\u8f6c\u6362\u4e3a\u7ea2\u9ed1\u6811\n int listSize = 0;\n for (e = (Entry<K, V>) table[bucketIndex]; e != null; e = (Entry<K, V>) e.next) {\n listSize++;\n if (listSize >= TreeBin.TREE_THRESHOLD) { \/\/ Convert to TreeBin\n \/\/ \u5982\u679ckey\u662fString\u7c7b\u578b\u6216\u5b9e\u73b0\u4e86java.lang.Comparable\u63a5\u53e3\u624d\u8f6c\u6362\u3002\n if (comparableClassFor(key) != null) {\n TreeBin t = new TreeBin();\/\/ \u521b\u5efa\u4e00\u4e2a\u7ea2\u9ed1\u6811\n t.populate((Entry) table[bucketIndex]);\/\/ \u628a\u94fe\u8868\u91cc\u7684Entry\u586b\u5145\u5230\u7ea2\u9ed1\u6811\n table[bucketIndex] = t;\/\/ \u628a\u7ea2\u9ed1\u6811\u653e\u5230\u69fd\u4f4d\u4e0a\u3002\n }\n break;\n }\n }\n }\n}\n\n\/\/ \u7528\u72ec\u7acb\u7684Entry\u6765\u5b58\u50a8key\u4e3anull\u7684\u60c5\u51b5\uff0c\u7b80\u5355\u591a\u4e86\u3002\nprivate V putForNullKey(V value) {\n if (nullKeyEntry != null) {\n V oldValue = nullKeyEntry.value;\n nullKeyEntry.value = value;\n nullKeyEntry.recordAccess( this);\n return oldValue;\n }\n modCount++;\n size++; \/\/ newEntry() skips size++\n nullKeyEntry = newEntry(0, null, value, null);\n return null ;\n}\n<\/code><\/pre>\nget\u903b\u8f91<\/h3>\nfinal Entry<K, V> getEntry(Object key) {\n \/\/ \u6ca1\u6709\u952e\u503c\u5bf9\n if (size == 0) {\n return null ;\n }\n \/\/ key\u4e3anull\uff0c\u76f4\u63a5\u8fd4\u56de\u5bf9\u5e94\u7684Entry\n if (key == null) {\n return nullKeyEntry;\n }\n\n \/\/ \u8ba1\u7b97\u54c8\u5e0c\u503c\uff0c\u5b9a\u4f4d\u69fd\u4f4d\n int hash = hash(key);\n int bin = indexFor(hash, table.length);\n\n if (table[bin] instanceof Entry) {\n \/\/ \u69fd\u4f4d\u5b58\u653e\u7684\u94fe\u8868\uff0c\u903b\u8f91\u4e0e\u65e7\u7684\u76f8\u540c\n Entry<K, V> e = (Entry<K, V>) table[bin];\n for (; e != null; e = (Entry<K, V>) e.next) {\n Object k;\n if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {\n return e;\n }\n }\n } else if (table[bin] != null) {\n \/\/ \u5b58\u653e\u7684\u662f\u7ea2\u9ed1\u6811\uff0c\u59d4\u6258\u7ed9\u7ea2\u9ed1\u6811\u53bb\u67e5\u627e\n TreeBin e = (TreeBin) table[bin];\n TreeNode p = e.getTreeNode(hash, (K) key);\n if (p != null) {\n \/\/ assert p.entry.hash == hash && p.entry.key.equals(key);\n return (Entry<K, V>) p.entry;\n } else {\n return null ;\n }\n }\n return null ;\n}\n<\/code><\/pre>\n\u904d\u5386\u6240\u6709Entry\u7684\u903b\u8f91<\/h3>\n
\u904d\u5386\u6240\u6709Entry\u4ecd\u7136\u501f\u52a9\u7c7bHashIterator\u3002<\/p>\n
private abstract class HashIterator<E> implements Iterator<E> {\n Object next; \/\/ \u4e0b\u4e00\u4e2a\u5f85\u8fd4\u56de\u7684\u952e\u503c\u5bf9\uff0c\u53ef\u4ee5\u662fEntry \u6216 TreeNode\n int expectedModCount; \/\/ \u7528\u4e8e\u5feb\u901f\u5931\u8d25\n int index; \/\/ \u5f53\u524d\u904d\u5386\u7684\u69fd\u4f4d\uff0c\u9ed8\u8ba4\u4ece\u69fd\u4f4d0\u5f00\u59cb\n Object current; \/\/ \u5f53\u524d\u8fd4\u56de\u7684\u6700\u540e\u4e00\u4e2a\u952e\u503c\u5bf9\uff0c\u53ef\u4ee5\u662f Entry \u6216 TreeNode\n\n HashIterator() {\n expectedModCount = modCount;\n if (size > 0) { \/\/ advance to first entry\n if (nullKeyEntry != null) {\n \/\/ nullKeyEntry\u4f5c\u4e3a\u4e00\u4e2a\u72ec\u7acb\u5c5e\u6027\uff0c\u4e0d\u4f1a\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u9700\u8981\u7279\u6b8a\u5904\u7406\uff0c\u4f18\u5148\u8fd4\u56de\u3002\n next = nullKeyEntry;\n } else {\n findNextBin();\n }\n }\n }\n\n public final boolean hasNext() {\n return next != null;\n }\n\n @SuppressWarnings( \"unchecked\")\n final Entry<K, V> nextEntry() {\n if (modCount != expectedModCount) {\n throw new ConcurrentModificationException();\n }\n Object e = next;\n Entry<K, V> retVal;\n\n if (e == null)\n throw new NoSuchElementException();\n\n if (e instanceof TreeNode) { \/\/ \u6b63\u5728\u904d\u5386\u7ea2\u9ed1\u6811\n retVal = (Entry<K, V>) ((TreeNode) e).entry;\n next = retVal.next;\n } else { \/\/ \u6b63\u5728\u904d\u5386\u94fe\u8868\n retVal = (Entry<K, V>) e;\n next = ((Entry<K, V>) e).next;\n }\n\n \/\/ \u5982\u679c\u5f53\u524d\u94fe\u8868\u6216\u7ea2\u9ed1\u6811\u5df2\u904d\u5386\u5b8c\uff0c\u5b9a\u4f4d\u5230\u4e0b\u4e00\u4e2a\u69fd\u3002\n if (next == null) {\n findNextBin();\n }\n current = e;\n return retVal;\n }\n\n private void findNextBin() {\n \/\/ assert next == null;\n Object[] t = table;\n\n \/\/ \u5b9a\u4f4d\u5230\u4e0b\u4e00\u4e2a\u4e0d\u4e3a\u7a7a\u7684\u69fd\u4f4d\n while (index < t.length && (next = t[index++]) == null)\n ;\n if (next instanceof HashMap.TreeBin) {\n \/\/ \u5982\u679c\u69fd\u4f4d\u4e0a\u5b58\u653e\u7684\u662f\u7ea2\u9ed1\u6811\uff0c\u5219\u7528next\u6307\u5411\u7ea2\u9ed1\u6811\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u3002\n next = ((TreeBin) next).first;\n \/\/ assert next != null; \/\/ There should be no empty TreeBins\n }\n }\n\n \/\/ \u5176\u4ed6\u65b9\u6cd5\u7701\u7565\n}\n<\/code><\/pre>\n\u6b22\u8fce\u5173\u6ce8\u6211\u7684\u5fae\u4fe1\u516c\u4f17\u53f7: coderbee\u7b14\u8bb0<\/strong>\uff0c\u53ef\u4ee5\u66f4\u53ca\u65f6\u56de\u590d\u4f60\u7684\u8ba8\u8bba\u3002<\/p>\n![](\"https:\/\/coderbee.net\/wp-content\/uploads\/2019\/01\/coderbee-note.jpg\")
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6982\u8ff0 java.util.HashMap \u662fJDK\u91cc\u6563\u5217\u7684\u4e00\u4e2a\u5b9e\u73b0\uff0cJDK6\u91cc\u91c7 … \u7ee7\u7eed\u9605\u8bfb