HashMap就是一個(gè)散列表向拆，它是通過“拉鏈法”解決哈希沖突的。

1. 哈希表-拉鏈法

2. HashMap的存取實(shí)現(xiàn)

既然是線性數(shù)組汛骂，為什么能隨機(jī)存群蹦！？這里HashMap用了一個(gè)小算法帘瞭，大致是這樣實(shí)現(xiàn)：

// 存儲(chǔ)時(shí):
int hash = key.hashCode(); // 這個(gè)hashCode方法這里不詳述,只要理解每個(gè)key的hash是一個(gè)固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

// 取值時(shí):
int hash = key.hashCode();
int index = hash % Entry[].length;
//int index = hash & (tab.length - 1);
return Entry[index];

1）put
疑問：如果兩個(gè)key通過hash%Entry[].length得到的index相同淑掌，會(huì)不會(huì)有覆蓋的危險(xiǎn)？
　　這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個(gè)概念蝶念。上面我們提到過Entry類里面有一個(gè)next屬性抛腕，作用是指向下一個(gè)Entry芋绸。打個(gè)比方， 第一個(gè)鍵值對A進(jìn)來担敌，通過計(jì)算其key的hash得到的index=0摔敛，記做:Entry[0] = A。一會(huì)后又進(jìn)來一個(gè)鍵值對B全封，通過計(jì)算其index也等于0马昙，現(xiàn)在怎么辦？
HashMap會(huì)這樣做:B.next = A,Entry[0] = B,如果又進(jìn)來C,index也等于0,那么C.next = B,Entry[0] = C刹悴；這樣我們發(fā)現(xiàn)index=0的地方其實(shí)存取了A,B,C三個(gè)鍵值對,他們通過next這個(gè)屬性鏈接在一起行楞。所以疑問不用擔(dān)心。

也就是說數(shù)組中存儲(chǔ)的是最后插入的元素土匀。插入時(shí)子房，先找到數(shù)組索引，取出數(shù)組在索引代表的entry值(鏈表頭)就轧，遍歷鏈表的每一個(gè)entry節(jié)點(diǎn)池颈，當(dāng)entry的hashcode值與put進(jìn)來的key的hashcode值相等并且(entry的key與put進(jìn)來的key是同一對象或者entry.key.equals(put進(jìn)來的key))，就會(huì)執(zhí)行替換操作钓丰，并且返回之前oldValue躯砰。到這里為止，HashMap的大致實(shí)現(xiàn)携丁，我們應(yīng)該已經(jīng)清楚了琢歇。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value); //null總是放在數(shù)組的第一個(gè)鏈表中
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //遍歷鏈表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果key在鏈表中已存在，則替換為新value
        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) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //參數(shù)e, 是Entry.next
    //如果size超過threshold梦鉴，則擴(kuò)充table大小李茫。再散列
    if (size++ >= threshold)
            resize(2 * table.length);
}

//確定數(shù)組index：hashcode % table.length取模
/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

當(dāng)然HashMap里面也包含一些優(yōu)化方面的實(shí)現(xiàn)，這里也說一下肥橙。比如：Entry[]的長度一定后魄宏，隨著map里面數(shù)據(jù)的越來越長，這樣同一個(gè)index的鏈就會(huì)很長存筏，會(huì)不會(huì)影響性能宠互？HashMap里面設(shè)置一個(gè)因子，隨著map的size越來越大椭坚，Entry[]會(huì)以一定的規(guī)則加長長度予跌。
2）get

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    //先定位到數(shù)組元素，再遍歷該元素處的鏈表
    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.equals(k)))
            return e.value;
    }
    return null;
}

3）null key的存取
null key總是存放在Entry[]數(shù)組的第一個(gè)元素善茎。

 private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

4）確定數(shù)組index：hashcode % table.length取模
HashMap存取時(shí)券册，都需要計(jì)算當(dāng)前key應(yīng)該對應(yīng)Entry[]數(shù)組哪個(gè)元素，即計(jì)算數(shù)組下標(biāo)；算法如下：

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

按位取并烁焙，作用上相當(dāng)于取模mod或者取余%航邢。
這意味著數(shù)組下標(biāo)相同，并不表示hashCode相同骄蝇。

5）table初始大小

public HashMap(int initialCapacity, float loadFactor) {
    .....
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

注意table初始大小并不是構(gòu)造函數(shù)中的initialCapacityＩ乓蟆！
而是 >= initialCapacity的2的n次冪Ｆ蛘ァ；嘀５庇椤吃既！

3. 解決hash沖突的辦法

HashMap實(shí)現(xiàn)原理分析

4.再散列rehash過程

HashMap實(shí)現(xiàn)原理分析

參考：

1. HashMap實(shí)現(xiàn)原理分析

推薦閱讀

• HashMap，ArrayMap跨细，SparseArray源碼分析及性能對比