• 源碼閱讀
• 多線程下形成死循環(huán)的原因
• key為什么一般用字符串比較多，能用其他對象，或者自定義的對象嗎？為什么

源碼閱讀

基礎

1.擴容基礎系數(shù)： loadFactor=0.75f
2.存儲的基本數(shù)據(jù)結構：transient Entry<K,V>[] table
3.默認初始化table大?。篿nitialCapacity =1 << 4
4.當前table元素個數(shù)：size
5.threshold=loadFactor*table大小

構造函數(shù)

public HashMap(int initialCapacity, float loadFactor) {
     //各種判斷，省略...
    //這里只是做了容量和擴容系數(shù)的初始化
    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}

put操作

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);//如果table為空就初始化table
    }
    if (key == null)
        return putForNullKey(value);//對key==null的情況做個特殊處理,允許key=null
    int hash = hash(key);
    int i = indexFor(hash, table.length);//根據(jù)key的hash值和當前table的長度計算該Entry位于數(shù)組中的位置
   //循環(huán)判斷該Entry是否已經(jīng)存在于數(shù)組第i個位置上的鏈表里
    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++;
    addEntry(hash, key, value, i);//插入操作
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果當前容量>=table.length*0.75f &&table的第i個位置!=null就擴容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//擴容和元素重排
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

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];//創(chuàng)建一個新的Entry數(shù)組
    transfer(newTable, initHashSeedAsNeeded(newCapacity));//重排
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //遍歷old table中的所有元素
    for (Entry<K,V> e : table) {
        //每個元素遍歷自身的鏈表
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //計算在新table中的位置，并插入
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

get操作

get操作很簡單，就是根據(jù)key的hash值定位到該key對應table中的位置，如果該key對應的hash有重復（即在table[i]上有鏈表結構），就挨個比較該鏈表上的每個節(jié)點（Entry）中key的值

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) {
    if (size == 0) {
        return null;
    }
    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;
}

圖解

內(nèi)部結構圖

• 初始化和put操作

    HashMap map = new HashMap(2)
    map.put("k1","v1");
    map.put("k2","v2");
  

初始化

put操作(1)

put操作(2)

• 正常resize操作

    map.put("k3","v3");
  

初始狀態(tài)

resize(1)

resize(2)

resize(3)

• 多線程線resize造成死循環(huán)

    HashMap map = new HashMap(2);
    map.put("k1","v1");
    map.put("k2","v2");
    
    
    map.put("k3","v3");//A線程操作
    map.put("k4","v4");//B線程操作
  

假設A線程和B線程同時進入resize方法的transfer方法的
Entry<K,V> next = e.next; 這一行
這時B線程被掛起，A線程執(zhí)行完之后，B線程再執(zhí)行，我們看看這時會發(fā)生什么？

初始狀態(tài)

B線程被刮起前狀態(tài)

A線程執(zhí)行完畢

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
}

B-resize(1)

B-resize(2)

多線程下形成死循環(huán)的原因

多線程情況下，當多個線程同時對同一個hashmap進行resize操作時，就有可能造成鏈表的循環(huán)調用，具體原因如圖解所示。

key一般用字符串比較多，能用其他對象，或者自定義的對象嗎？為什么

 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

• HashMap支持傳入泛型，所以肯定支持對象，也肯定支持自定義對象（不支持基本數(shù)據(jù)類型哦），但是在用自定義對象的時候一定要注意要重寫hashCode和equals方法，因為Object的equals默認是比較兩個對象的地址是否相等，所以即使兩個對象的屬相一摸一樣，在HashMap中依舊被當作是兩個不同的key。