—HashMap—
優點：超級快速的查詢速度，時間復雜度可以達到O（1）的數據結構非HashMap莫屬。動態的可變長存儲數據（相對于數組而言）。
缺點：需要額外計算一次hash值，如果處理不當會占用額外的空間。
—HashMap如何使用—
平時我們使用hashmap如下
|
1
2
3
|
Map<Integer,String> maps=new HashMap<Integer,String>(); maps.put(1, "a"); maps.put(2, "b"); |
上面代碼新建了一個HashMap并且插入了兩個數據，這里不接受基本數據類型來做K,V
如果這么寫的話，就會出問題了：
|
1
|
Map<int,double> maps=new HashMap<int,double>(); |
我們為什么要這樣使用呢？請看源碼：
|
1
2
3
|
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable |
這是HashMap實現類的定義。
—HashMap是一個動態變長的數據結構—
在使用HashMap的時候，為了提高執行效率，我們往往會設置HashMap初始化容量：
|
1
|
Map<String,String> rm=new HashMap<String,String>(2) |
或者使用guava的工具類Maps，可以很方便的創建一個集合，并且，帶上合適的大小初始化值。
|
1
|
Map<String, Object> map = Maps.newHashMapWithExpectedSize(7); |
那么為什么要這樣使用呢？我們來看他們的源碼構造函數。
未帶參的構造函數：
|
1
2
3
4
5
6
|
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } |
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
|
1
2
3
4
5
6
7
8
9
10
|
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } |
名詞解釋：
|
1
2
3
|
DEFAULT_LOAD_FACTOR //默認加載因子，如果不制定的話是0.75 DEFAULT_INITIAL_CAPACITY //默認初始化容量，默認是16 threshold //閾（yu）值 根據加載因子和初始化容量計算得出 ，<span style="color: rgb(54, 46, 43); font-family: "microsoft yahei";">threshold表示當HashMap的size大于threshold時會執行resize操作。 |
因此我們知道了，如果我們調用無參數的構造方法的話，我們將得到一個16容量的數組。
所以問題就來了：如果初始容量不夠怎么辦？
數組是定長的，如何用一個定長的數據來表示一個不定長的數據呢，答案就是找一個更長的，但是在resize的時候是很降低效率的。所以我們建議HashMap的初始化的時候要給一個靠譜的容量大小。
—HashMap的Put方法—
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public V put(K key, V value) { if (key == null) //鍵為空的情況，HashMap和HashTable的一個區別 return putForNullKey(value); int hash = hash(key.hashCode()); //根據鍵的hashCode算出hash值 int i = indexFor(hash, table.length); //根據hash值算出究竟該放入哪個數組下標中 for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整個for循環實現了如果存在K那么就替換V Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++;//計數器 addEntry(hash, key, value, i); //添加到數組中 return null; } |
如果插入的數據超過現有容量就會執行
|
1
|
addEntry(hash, key, value, i); |
|
1
2
3
4
5
6
|
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) <span style="color:#ff0000;"><strong> resize(2 * table.length);} |
這里顯示了如果當前 size++ >threshold 的話那么就會擴展當前的size的兩倍，執行resize（2*table.length）,那么他們是如何擴展的呢？
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; <span style="color: rgb(51, 51, 51); font-family: Arial;">new 一個新的數組，</span> <strong> <span style="color:#ff0000;">transfer(newTable);</span> </strong> //將就數組轉移到新的數組中 table = newTable; threshold = (int)(newCapacity * loadFactor); //重新計算容量 } |
對于轉移數組transfer是如何轉移的呢？
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = <strong><span style="color:#ff0000;">indexFor(e.hash, newCapacity); //根據hash值個容量重新計算下標</span></strong> e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } |
—hashmap擴容額外執行次數—
因此如果我們要添加一個1000個元素的hashMap，如果我們用默認值那么我么需要額外的計算多少次呢
當大于16*0.75=12的時候，需要從新計算12次
當大于16*2*0.75=24的時候，需要額外計算24次
……
當大于16*n*0.75=768的時候，需要額外計算768次
所以我們總共在擴充過程中額外計算12+24+48+……+768次
因此強力建議我們在項目中如果知道范圍的情況下，我們應該手動指定初始大小像這樣：
|
1
|
Map<Integer,String> maps=new HashMap<Integer,String>(1000); |
總結：這就是為什么當hashmap使用過程中如果超出 初始容量后他的執行效率嚴重下降的原因。
以上就是本文關于Java源碼角度分析HashMap用法的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/lee_sire/article/details/53424735
