關於hashmap的理解

首先分析第一個比較重要的方法 put 方法，源碼如下

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);  //這裡判斷key是否為空,若為空則調用putForNullKey處理null值
int hash = hash(key); //根據key的hashCode計算hash值
int i = indexFor(hash, table.length);//搜索該key的hash值在table中的索引,其中table是當HashMap用於存放entry的一個數組

//這裡迴圈遍歷table中對應該索引的entry，若發現存在key與put進來的key相同則覆蓋其value值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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++;

//將key value 添加到 索引i處
addEntry(hash, key, value, i);
return null;
}

分析上面的源碼，我們可以得到下麵的結論:

當我們試圖將一個key-value 調用put方法放入HashMap的時候，首先會調用key的hashCode方法算出該Entry存放的位置，若兩個key的hashCode相同則在table中的存儲位置相同，則先調用equals方法判斷兩個key是否相同，相同則覆蓋，不相同則產生一個Entry鏈表(因為table數組中一個索引位置只能放入一個Entry，所以當有多個key的hashCode相同時，這些key就會以鏈表的形式存在，並且最後put進來的key在鏈表的最前面)

然後則是HashMap的構造方法，這裡以 HashMap(int initialCapacity, float loadFactor)這個構造器為例，源碼如下

public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;

this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}

從上面的源碼可以看出 ，初始容量不能為負數，若初始容量大於最大容量，則讓它等於最大容量，負載因數必須大於0，並且傳入的initialCapacity不是HashMap的容量大小，

實際容量大小的計算規則是大於傳入的initialCapacity的最小的2的n次方，比如傳入的initialCapacity是5 那麼實際容量則是8 因為2的3次方大於5。

下麵再分析一下HashMap的存儲性能，下麵的 get方法的源碼

public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

再次強調一下table的概念，table就是當我們初始化一個HashMap時，會自動創建一個長度為capacity的Entry數組，我們把這個數組存放元素的位置叫“桶”，並且每個桶只存儲一個Entry元素(也就是我們的鍵值對)，並且當我們put一個鍵值對時，先計算key的hashCode來判斷這個鍵值對會放入哪一個桶，所以若多個key的hashCode相同時，他們都要被放入一個桶裡面，但是一個桶裡面只能放入一個Entry(鍵值對)，要解決這個問題先看下麵的代碼

Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

這時Entry的構造方法，我們可以看出Entry對象包含一個Entry的引用，用來指向下一個Entry，這樣就解決了hashCode相同，存放衝突的問題，所以當有多個key的hashCode相同時，就會形成一個Entry鏈，我們從get方法可以看出當系統通過key的hashCode找到了對應的桶的時候，會遍歷這個Entry鏈，來找到我們要取的value的key，這個時候，若剛好這個Entry在鏈表的末端(也就是我們最開始put進去的Entry)那麼當這個鏈表太長了，勢必會影響我們的查詢性能，這個時候就引出了loadFactor(負載因數的說法)，HashMap的預設附在因數是0.75，我對負載因數的理解就是，表示HashMap在什麼時候擴容，也就是說若我們初始的HashMap容量是16 負載因數是0.75，那麼當有12個“桶”有了Entry時，HashMap

就會擴容，並且擴大的容量是原來容量的2倍，為什麼是12呢？因為0.75x16=12。並且負載因數是可以更改的，修改它的前提是如果記憶體比較緊張就可以適當的增加負載因數，

若空間，記憶體比較充足，更關註查詢效率則減少負載因數。為什麼會這樣呢？因為若負載因數減少了，比如說減少到了0.5，預設HashMap容量大小還是16，那麼當我有8個"桶"中存放了Entry數組時我就會擴容了，該桶里的Entry鏈相比於之前就不會那麼長，從而提升了查詢性能。

今天先到這裡，下次再寫。