HashMap解惑

HashMap中有一些我們容易忽視的點，

Java代碼  

1. public V put(K key, V value) {  

2.         if (table == EMPTY_TABLE) {  

3.             inflateTable(threshold);  

4.         }  

5.         if (key == null)  

6.             return putForNullKey(value);  

7.         int hash = hash(key);  

8.         int i = indexFor(hash, table.length);  

9.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {  

10.             Object k;  

11.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

12.                 V oldValue = e.value;  

13.                 e.value = value;  

14.                 e.recordAccess(this);  

15.                 return oldValue;  

16.             }  

17.         }  

18.   

19.         modCount++;  

20.         addEntry(hash, key, value, i);  

21.         return null;  

22.     }  

 由上述代碼知道，hash值是用來確定bucketIndex，equals是用來和鏈表上的值比較，因此對于key是自定義的類，強烈建議重寫hashCode和equals方法。

 再看如下代碼下載

Java代碼  

1. void addEntry(int hash, K key, V value, int bucketIndex) {  

2.         if ((size >= threshold) && (null != table[bucketIndex])) {  

3.             resize(2 * table.length);  

4.             hash = (null != key) ? hash(key) : 0;  

5.             bucketIndex = indexFor(hash, table.length);  

6.         }  

7.   

8.         createEntry(hash, key, value, bucketIndex);  

9.     }  

 if條件告訴我們rehash的條件要同時滿足兩個：map中元素個數不小于閥值即容量*負載因子，對應的bucketIndex處有元素。

 另外，如下代碼作備忘，

Java代碼  

1. static int indexFor(int h, int length) {  

2.         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";  

3.         return h & (length-1);  

4.     }