LruCache是Android的一個(gè)內(nèi)部類粪躬，提供了基于內(nèi)存實(shí)現(xiàn)的緩存，打算分析一下其實(shí)現(xiàn)的原理拐辽，不過發(fā)現(xiàn)其內(nèi)部是基于LinkedHashMap育韩，而這個(gè)又是基于HashMap，所以蛇更，從頭開始學(xué)習(xí)咯瞻赶。

在討論HashMap前赛糟，有必要先談?wù)剶?shù)組和鏈表這兩種常用數(shù)據(jù)結(jié)構(gòu)。

數(shù)組在內(nèi)存中開辟的空間是連續(xù)的砸逊，如果要插入或者刪除一個(gè)node虑灰，那么這個(gè)node之后的所有數(shù)據(jù)都要整體move，但數(shù)組的查詢快（二分查找）痹兜。其特點(diǎn)是：尋址容易，增刪困難

鏈表在內(nèi)存中離散存儲颤诀，插入和刪除十分輕松字旭，但查詢較慢，每次都要從頭到尾遍歷一遍崖叫。其特點(diǎn)是：尋址困難遗淳，增刪容易

哈希表的存在就是取其精華，去其糟粕心傀。

哈希表有多種不同的實(shí)現(xiàn)方案屈暗，本文接下來介紹的是最常用的一種（也是JDK中HashMap的實(shí)現(xiàn)方案）—— 拉鏈法，我們可以理解為“數(shù)組+鏈表” 脂男。如圖：

（以下是以 Android SDK 里面的方法养叛，和 Java JDK 里面的些許不同，谷歌程序猿：烏拉）

HashMap內(nèi)部其實(shí)就是一個(gè)Entry數(shù)組(table)

/**
 * The hash table. If this hash map contains a mapping for null, it is
 * not represented this hash table.
 */
transient HashMapEntry<K, V>[] table;

數(shù)組中每個(gè)元素都可以看成一個(gè)桶宰翅，每一個(gè)桶又構(gòu)成了一條鏈表弃甥。

源碼

構(gòu)造方法

/**
 * Constructs a new empty {@code HashMap} instance.
 */
@SuppressWarnings("unchecked")
public HashMap() {
    table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
    threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}

看構(gòu)造方法，會涉及到HashMapEntry這個(gè)數(shù)據(jù)結(jié)構(gòu)

static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;// 鍵
    V value;// 值
    final int hash;// 哈希值
    HashMapEntry<K, V> next;// 指向下一個(gè)節(jié)點(diǎn)

    HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
        this.key = key;
        this.value = value;
        this.hash = hash;
        this.next = next;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    // 判斷兩個(gè)Entry是否相等
    
    @Override public final boolean equals(Object o) {
        if (!(o instanceof Entry)) {// 如果Object o不是Entry類型汁讼，直接返回false
            return false;
        }
        Entry<?, ?> e = (Entry<?, ?>) o;
        return Objects.equal(e.getKey(), key)
                && Objects.equal(e.getValue(), value);// 若兩個(gè)Entry的“key”和“value”都相等淆攻，則返回true。
    }

    @Override public final int hashCode() {// 實(shí)現(xiàn)hashCode()嘿架，判斷存儲在哪個(gè)數(shù)組里面
        return (key == null ? 0 : key.hashCode()) ^
                (value == null ? 0 : value.hashCode());
    }

    @Override public final String toString() {
        return key + "=" + value;
    }
}

這是一個(gè)靜態(tài)內(nèi)部類 HashMapEntry瓶珊，實(shí)現(xiàn)的是Entry接口，是HashMap鏈?zhǔn)酱鎯?yīng)的鏈表（數(shù)組加鏈表形式）

繼續(xù)看耸彪，涉及到了 EMPTY_TABLE 定義如下

/**
 * An empty table shared by all zero-capacity maps (typically from default
 * constructor). It is never written to, and replaced on first put. Its size
 * is set to half the minimum, so that the first resize will create a
 * minimum-sized table.
 */
private static final Entry[] EMPTY_TABLE
        = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

 /**
 * Min capacity (other than zero) for a HashMap. Must be a power of two
 * greater than 1 (and less than 1 << 30).
 */
private static final int MINIMUM_CAPACITY = 4;

MINIMUM_CAPACITY往右移動(dòng)一位伞芹，大小變?yōu)?了

所以上面的構(gòu)造函數(shù)就是在HashMap中有一個(gè)table，保存的是一個(gè)HashMapEntry類型的數(shù)組搜囱，數(shù)組的大小為2（區(qū)別與OracleJDK丑瞧，其默認(rèn)大小是16）

/**
 * Constructs a new {@code HashMap} instance with the specified capacity.
 *
 * @param capacity
 *            the initial capacity of this hash map.
 * @throws IllegalArgumentException
 *                when the capacity is less than zero.
 */
public HashMap(int capacity) {
    if (capacity < 0) {//容量小于領(lǐng)，拋異常
        throw new IllegalArgumentException("Capacity: " + capacity);
    }

    if (capacity == 0) {//容量為零蜀肘，替換成默認(rèn)的EMPTY_TABLE
        @SuppressWarnings("unchecked")
        HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
        table = tab;
        threshold = -1; // Forces first put() to replace EMPTY_TABLE
        return;
    }

    if (capacity < MINIMUM_CAPACITY) {//不能小于規(guī)定的最小值绊汹，也就是4
        capacity = MINIMUM_CAPACITY;
    } else if (capacity > MAXIMUM_CAPACITY) {不能大于規(guī)定的最大值，也就是 1 << 30
        capacity = MAXIMUM_CAPACITY;
    } else {//尋找最合適的
        capacity = Collections.roundUpToPowerOfTwo(capacity);
    }
    makeTable(capacity);
}

Collections.roundUpToPowerOfTwo()

/**
 * Returns the smallest power of two >= its argument, with several caveats:
 * If the argument is negative but not Integer.MIN_VALUE, the method returns
 * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
 * returns Integer.MIN_VALUE. If the argument is zero, the method returns
 * zero.
 * @hide
 */
public static int roundUpToPowerOfTwo(int i) {
    i--; // If input is a power of two, shift its high-order bit right.

    // "Smear" the high-order bit all the way to the right.
    i |= i >>>  1;
    i |= i >>>  2;
    i |= i >>>  4;
    i |= i >>>  8;
    i |= i >>> 16;

    return i + 1;
}

看注釋應(yīng)該知道這個(gè)方法的功能就是返回一個(gè)比指定值i扮宠，也就是上面的 capacity 大的2的n次方的最小值

例如輸入i = 17西乖，二進(jìn)制表示為00010001

• i -- 后狐榔，　　　　 二進(jìn)制表示為 00010000，十進(jìn)制i = 16
• i >>> 1 后获雕，　　 二進(jìn)制表示為 00001000薄腻，十進(jìn)制i = 8
• i |= 后，　　　　 二進(jìn)制表示為 00011000届案，十進(jìn)制i = 24
• i >>> 2 后庵楷，　　 二進(jìn)制表示為 00000110，十進(jìn)制i = 6
• i |= 后楣颠，　　　　 二進(jìn)制表示為 00011110尽纽，十進(jìn)制i = 30
• i >>> 4 后，　　 二進(jìn)制表示為 00000001童漩，十進(jìn)制i = 1
• i |= 后弄贿，　　　　 二進(jìn)制表示為 00011111，十進(jìn)制i = 31
• i >>> 8 后矫膨，　 　二進(jìn)制表示為 00011111差凹，十進(jìn)制i = 31
• i |= 后，　　　　 二進(jìn)制表示為 00011111侧馅，十進(jìn)制i = 31
• i >>> 16 后危尿，　　二進(jìn)制表示為 00011111，十進(jìn)制i = 31
• i |= 后施禾，　　　　 二進(jìn)制表示為 00011111脚线，十進(jìn)制i = 31
• i + 1 后，　　　 二進(jìn)制表示為 00100000弥搞，十進(jìn)制i = 32

所以邮绿，比i = 17大的最小的2的次方應(yīng)該是2的5次方

例如輸入i = 16，二進(jìn)制表示為0001000

• i -- 后攀例，　　　　 二進(jìn)制表示為 00001111船逮，十進(jìn)制i = 15
• i >>> 1 后，　　 二進(jìn)制表示為 00000111粤铭，十進(jìn)制i = 7
• i |= 后挖胃，　　　　 二進(jìn)制表示為 00001111，十進(jìn)制i = 15
• i >>> 2 后梆惯， 　　 二進(jìn)制表示為 00000011酱鸭，十進(jìn)制i = 3
• i |= 后，　　　　 二進(jìn)制表示為 00001111垛吗，十進(jìn)制i = 15
• i >>> 4 后凹髓， 　　 二進(jìn)制表示為 00000000，十進(jìn)制i = 0
• i |= 后怯屉，　　　　 二進(jìn)制表示為 00001111蔚舀，十進(jìn)制i = 15
• i >>> 8 后饵沧，　　 二進(jìn)制表示為 00001111，十進(jìn)制i = 15
• i |= 后赌躺，　　　　 二進(jìn)制表示為 00001111狼牺，十進(jìn)制i = 15
• i >>> 16 后，　　二進(jìn)制表示為 00001111礼患，十進(jìn)制i = 15
• i |= 后是钥，　　　　 二進(jìn)制表示為 00001111，十進(jìn)制i = 15
• i + 1 后缅叠， 　　　 二進(jìn)制表示為 00010000咏瑟，十進(jìn)制i = 16

所以，比i = 16大的最小的2的次方應(yīng)該是2的4次方痪署，就是其本身

言歸正傳，繼續(xù)看 makeTable 方法

makeTable()

/**
 * Allocate a table of the given capacity and set the threshold accordingly.
 * @param newCapacity must be a power of two
 */
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
    @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
            = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
    table = newTable;
    threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity 
    return newTable;
}

根據(jù)代碼可知兄旬，其初始化了一個(gè)HashMapEntry類型的數(shù)組table狼犯，用來存放HashMapEntry，而threshold如它的翻譯般领铐，就是一個(gè)闕值悯森，這個(gè)值是將來擴(kuò)容的參考，是容量的3/4(新閾值 = 新容量/2 + 新容量/4绪撵，相當(dāng)于乘以容量的 3/4瓢姻，not care 加載因子)

/**
 * Constructs a new {@code HashMap} instance with the specified capacity and
 * load factor.
 *
 * @param capacity
 *            the initial capacity of this hash map.
 * @param loadFactor
 *            the initial load factor.
 * @throws IllegalArgumentException
 *                when the capacity is less than zero or the load factor is
 *                less or equal to zero or NaN.
 */
public HashMap(int capacity, float loadFactor) {
    this(capacity);

    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new IllegalArgumentException("Load factor: " + loadFactor);
    }

    /*
     * Note that this implementation ignores loadFactor; it always uses
     * a load factor of 3/4. This simplifies the code and generally
     * improves performance.
     */
}

上面這個(gè)個(gè)構(gòu)造方法最終會調(diào)用這個(gè)構(gòu)造方法 HashMap(int capacity)，看注釋音诈，里面說明了裝載因子為0.75幻碱。

注意：OracleJDK 中的閾值計(jì)算公式是：當(dāng)前 Entry 數(shù)組長度*加載因子，其默認(rèn)的加載因子是0.75细溅，加載因子也可以通過構(gòu)造器來設(shè)置褥傍。AndroidJDK 的加載因子也是0.75，不同的是喇聊，AndroidJDK 不支持其他數(shù)值的加載因子

/**
 * Constructs a new {@code HashMap} instance containing the mappings from
 * the specified map.
 *
 * @param map
 *            the mappings to add.
 */
public HashMap(Map<? extends K, ? extends V> map) {
    this(capacityForInitSize(map.size()));
    constructorPutAll(map);
}

這個(gè)構(gòu)造方法傳入的參數(shù)是個(gè) map恍风，根據(jù) map 的大小初始化。

HashMap 的構(gòu)造方法講完后誓篱，一般我們使用時(shí)朋贬，都是先往里面放數(shù)據(jù)，下面就看看 put() 方法

put()

/**
 * Maps the specified key to the specified value.
 *
 * @param key
 *            the key.
 * @param value
 *            the value.
 * @return the value of any previous mapping with the specified key or
 *         {@code null} if there was no such mapping.
 */
@Override 
public V put(K key, V value) {
    if (key == null) {// 若key為null窜骄，則將該鍵值對添加到table[0]中锦募。
        return putValueForNullKey(value);
    }
    // 若key不為null，則計(jì)算該key的哈希值啊研，然后將其添加到該哈希值對應(yīng)的鏈表中御滩。
    int hash = Collections.secondaryHash(key);// Collections.secondaryHash能夠使得hash過后的值的分布更加均勻鸥拧，盡可能地避免沖突
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);// 根據(jù)hash值計(jì)算存儲位置 index的值永遠(yuǎn)都是0到2的n次方減1之間，可以保證結(jié)果不大于tab.length
    
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {// 循環(huán)遍歷Entry數(shù)組,若key對應(yīng)的鍵值對已經(jīng)存在削解，則用新的value取代舊的value富弦。然后返回原來的 oldValue
        if (e.hash == hash && key.equals(e.key)) {//根據(jù)hash值是否相等以及 key值是否一樣進(jìn)行判斷
            preModify(e);
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }

    // No entry for (non-null) key is present; create one
    modCount++;// 修改次數(shù)+1
    if (size++ > threshold) {// 如何hashmap的大小超過了闕值，進(jìn)行擴(kuò)容
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);// 添加新的Entry
    return null;
}

里面涉及到了氛驮，Collections.secondaryHash(key)腕柜，該函數(shù)的原理在這里

從源碼可以看出，put 方法是有返回值的（可以理解為put也是包含了get方法的精髓）矫废，根據(jù)返回值不同盏缤，可以有其他作用。

另外蓖扑，我們構(gòu)造 HashMap 的構(gòu)造方法時(shí)唉铜， 闕值 threshold = -1 ，是滿足二倍擴(kuò)容的律杠，也就是說潭流，在 AndroidJDK 的 HashMap 中使用無參構(gòu)造方法后，第一次 put 數(shù)據(jù)就會觸發(fā)哈希表的二倍擴(kuò)容柜去，因?yàn)閿U(kuò)容后數(shù)組的長度發(fā)生了變化灰嫉，所以數(shù)據(jù)入桶的位置也會發(fā)生變化，這個(gè)時(shí)候需要新構(gòu)建 Hash 表嗓奢。而另外讼撒，HashMap 是允許 Key 為null，看看 putValueForNullKey 方法

putValueForNullKey()

private V putValueForNullKey(V value) {
    HashMapEntry<K, V> entry = entryForNullKey;
    if (entry == null) {
        addNewEntryForNullKey(value);
        size++;// hashmap大小 + 1
        modCount++;// 修改次數(shù) + 1
        return null;
    } else {
        preModify(entry);
        V oldValue = entry.value;
        entry.value = value;
        return oldValue;
    }
}

entryForNullKey的定義如下

 /**
 * The entry representing the null key, or null if there's no such mapping.
 */
transient HashMapEntry<K, V> entryForNullKey;

還是個(gè)HashMapEntry

當(dāng)entry為空時(shí)股耽，此時(shí)調(diào)用 addNewEntryForNullKey 方法根盒，如下

addNewEntryForNullKey()

/**
 * Creates a new entry for the null key, and the given value and
 * inserts it into the hash table. This method is called by put
 * (and indirectly, putAll), and overridden by LinkedHashMap.
 */
void addNewEntryForNullKey(V value) {
    entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}

會新構(gòu)造一個(gè)新的HashMapEntry，傳入value物蝙，其他為null or 0郑象。

當(dāng)entry不為空時(shí)，調(diào)用 preModify 方法茬末，如下

preModify()

/**
 * Give LinkedHashMap a chance to take action when we modify an existing
 * entry.
 *
 * @param e the entry we're about to modify.
 */
void preModify(HashMapEntry<K, V> e) { }// LinkedHashMap實(shí)現(xiàn)

好吧厂榛，就一個(gè)空方法，該方法會在 LinkedHashMap 中實(shí)現(xiàn)丽惭，接下來就是返回 oldValue

當(dāng)key 不為空時(shí)击奶，主要過程已經(jīng)標(biāo)注在了代碼中，這里看一下擴(kuò)容方法 doubleCapacity()

doubleCapacity()

/**
 * Doubles the capacity of the hash table. Existing entries are placed in
 * the correct bucket on the enlarged table. If the current capacity is,
 * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
 * will be new unless we were already at MAXIMUM_CAPACITY.
 */
private HashMapEntry<K, V>[] doubleCapacity() {
    HashMapEntry<K, V>[] oldTable = table;// 原table 標(biāo)記為 oldTable
    int oldCapacity = oldTable.length;// 舊容量
    if (oldCapacity == MAXIMUM_CAPACITY) {// 就容量已經(jīng)是最大值了责掏，就不用擴(kuò)容了（也擴(kuò)不了）
        return oldTable;
    }
    int newCapacity = oldCapacity * 2;// 新容量是舊容量的2倍
    HashMapEntry<K, V>[] newTable = makeTable(newCapacity);// 根據(jù)新容量重新創(chuàng)建一個(gè)
    if (size == 0) {// 如果原來HashMap的size為0柜砾，則直接返回  
        return newTable;
    }

    for (int j = 0; j < oldCapacity; j++) {
        /*
         * Rehash the bucket using the minimum number of field writes.
         * This is the most subtle and delicate code in the class.
         */
        // 代碼注釋都說下面的代碼是非常精妙的了，那就看看咯
        HashMapEntry<K, V> e = oldTable[j];
        if (e == null) {
            continue;
        }

        // 下面這三行换衬，忒抽象痰驱，舉例說明好了
        //oldCapacity假設(shè)為16(00010000)证芭，int highBit = e.hash & oldCapacity能夠得到高位的值，因?yàn)榻?jīng)過與操作過后担映，低位一定是0
        int highBit = e.hash & oldCapacity;
        HashMapEntry<K, V> broken = null;
        // J 在這里是index废士，J 與 高位的值進(jìn)行或操作過后，就能得到在擴(kuò)容后的新的index值蝇完。
        // 設(shè)想一下官硝，理論上我們得到的新的值應(yīng)該是 newValue = hash & (newCapacity - 1) 
        // 與 oldValue = hash & (oldCapacity - 1) 的區(qū)別僅在于高位上。 
        // 因此我們用 J | highBit 就可以得到新的index值短蜕。
        newTable[j | highBit] = e;
        // 下面的操作就是如果當(dāng)前元素下面掛載的還有元素就重新排放
        for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
            //跟上面的類似氢架，以下一個(gè)高位作為排放的依據(jù)
            int nextHighBit = n.hash & oldCapacity;
            if (nextHighBit != highBit) {// 說明位于不同的位置，just存放就可以
                if (broken == null)
                    newTable[j | nextHighBit] = n;
                else
                    broken.next = n;
                broken = e;
                highBit = nextHighBit;
            }// 如果相等說明這兩個(gè)元素肯定還位于數(shù)組的同一位置以鏈表的形式存在朋魔，not care
        }
        if (broken != null)
            broken.next = null;
    }
    return newTable;
}

擴(kuò)容方法講完后岖研，繼續(xù) put 方法的 addNewEntry(key, value, hash, index);

addNewEntry()

/**
 * Creates a new entry for the given key, value, hash, and index and
 * inserts it into the hash table. This method is called by put
 * (and indirectly, putAll), and overridden by LinkedHashMap. The hash
 * must incorporate the secondary hash function.
 */
void addNewEntry(K key, V value, int hash, int index) {
    table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

這個(gè)方法就是將老 Entry 作為新建 Entry 對象的 next 節(jié)點(diǎn)返回給當(dāng)前數(shù)組元素（物理空間上其實(shí)是在鏈表頭部添加新節(jié)點(diǎn)）

put 方法后，就看看 get() 方法

get()

/**
 * Returns the value of the mapping with the specified key.
 *
 * @param key
 *            the key.
 * @return the value of the mapping with the specified key, or {@code null}
 *         if no mapping for the specified key is found.
 */
public V get(Object key) {
    if (key == null) {//取空
        HashMapEntry<K, V> e = entryForNullKey;
        return e == null ? null : e.value;
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
            e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return e.value;
        }
    }
    return null;
}

這個(gè)方法警检，看代碼就應(yīng)該可以理解缎玫，和 put 的操作相反，怎么存的再怎么取出來就ok解滓。

下面看看 containsKey 方法

containsKey()

/**
 * Returns whether this map contains the specified key.
 *
 * @param key
 *            the key to search for.
 * @return {@code true} if this map contains the specified key,
 *         {@code false} otherwise.
 */
@Override public boolean containsKey(Object key) {
    if (key == null) {
        return entryForNullKey != null;
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
            e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return true;
        }
    }
    return false;
}

和 get 方法類似，返回方法不同而已筝家。

看看孿生兄弟 containsValue

containsValue

/**
 * Returns whether this map contains the specified value.
 *
 * @param value
 *            the value to search for.
 * @return {@code true} if this map contains the specified value,
 *         {@code false} otherwise.
 */
@Override public boolean containsValue(Object value) {
    HashMapEntry[] tab = table;
    int len = tab.length;
    if (value == null) {
        for (int i = 0; i < len; i++) {
            for (HashMapEntry e = tab[i]; e != null; e = e.next) {
                if (e.value == null) {
                    return true;
                }
            }
        }
        return entryForNullKey != null && entryForNullKey.value == null;
    }

    // value is non-null
    for (int i = 0; i < len; i++) {
        for (HashMapEntry e = tab[i]; e != null; e = e.next) {
            if (value.equals(e.value)) {
                return true;
            }
        }
    }
    return entryForNullKey != null && value.equals(entryForNullKey.value);
}

這個(gè)是查找是否含有value洼裤，和上面查找是否含有key類似，不過這個(gè)的循環(huán)次數(shù)就比尋找key要多溪王，數(shù)組和鏈表都要查找一遍（沒有辦法啦腮鞍，誰讓 hashMap 是根據(jù) key 來存，偏偏要取 value 莹菱，不得不耗時(shí)咯）移国。

前面有一個(gè)構(gòu)造方法，沒有仔細(xì)看

  /**
 * Constructs a new {@code HashMap} instance containing the mappings from
 * the specified map.
 *
 * @param map
 *            the mappings to add.
 */
public HashMap(Map<? extends K, ? extends V> map) {
    this(capacityForInitSize(map.size()));
    constructorPutAll(map);
}

首先看看 capacityForInitSize 方法

capacityForInitSize()

/**
 * Returns an appropriate capacity for the specified initial size. Does
 * not round the result up to a power of two; the caller must do this!
 * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive).
 */
static int capacityForInitSize(int size) {
    int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth

    // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
    return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY;
}

這個(gè)方法是根據(jù) map 的 size 進(jìn)行合理的擴(kuò)容道伟，擴(kuò)容的大小就是 size 的 1.5 倍迹缀，最后是根據(jù)擴(kuò)容的大小判斷返回值，如果擴(kuò)容的大小大于 1 << 30 則返回 1 << 30 (MAXIMUM_CAPACITY),否則就返回?cái)U(kuò)容后的大小蜜徽。

下面就是 constructorPutAll 方法

constructorPutAll()

/**
 * Inserts all of the elements of map into this HashMap in a manner
 * suitable for use by constructors and pseudo-constructors (i.e., clone,
 * readObject). Also used by LinkedHashMap.
 */
final void constructorPutAll(Map<? extends K, ? extends V> map) {
    if (table == EMPTY_TABLE) {
        doubleCapacity(); // Don't do unchecked puts to a shared table.
    }
    for (Entry<? extends K, ? extends V> e : map.entrySet()) {
        constructorPut(e.getKey(), e.getValue());
    }
}

該方法會把所有的 key 和 value 存儲起來祝懂，利用 constructorPut 方法

constructorPut()

/**
 * This method is just like put, except that it doesn't do things that
 * are inappropriate or unnecessary for constructors and pseudo-constructors
 * (i.e., clone, readObject). In particular, this method does not check to
 * ensure that capacity is sufficient, and does not increment modCount.
 */
private void constructorPut(K key, V value) {
    if (key == null) {
        HashMapEntry<K, V> entry = entryForNullKey;
        if (entry == null) {
            entryForNullKey = constructorNewEntry(null, value, 0, null);
            size++;
        } else {
            entry.value = value;
        }
        return;
    }

    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    HashMapEntry<K, V> first = tab[index];
    for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
        if (e.hash == hash && key.equals(e.key)) {
            e.value = value;
            return;
        }
    }

    // No entry for (non-null) key is present; create one
    tab[index] = constructorNewEntry(key, value, hash, first);
    size++;
}

該方法和 put 方法很類似，但是注釋也講明了二者的區(qū)別拘鞋。

再看 putAll 方法

putAll()

/**
 * Copies all the mappings in the specified map to this map. These mappings
 * will replace all mappings that this map had for any of the keys currently
 * in the given map.
 *
 * @param map
 *            the map to copy mappings from.
 */
@Override public void putAll(Map<? extends K, ? extends V> map) {
    ensureCapacity(map.size());
    super.putAll(map);
}

調(diào)用了 ensureCapacity 方法

ensureCapacity()

/**
 * Ensures that the hash table has sufficient capacity to store the
 * specified number of mappings, with room to grow. If not, it increases the
 * capacity as appropriate. Like doubleCapacity, this method moves existing
 * entries to new buckets as appropriate. Unlike doubleCapacity, this method
 * can grow the table by factors of 2^n for n > 1. Hopefully, a single call
 * to this method will be faster than multiple calls to doubleCapacity.
 *
 *  <p>This method is called only by putAll.
 */
private void ensureCapacity(int numMappings) {
    int newCapacity = Collections.roundUpToPowerOfTwo(capacityForInitSize(numMappings));// 上面講過
    HashMapEntry<K, V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (newCapacity <= oldCapacity) {
        return;
    }
    if (newCapacity == oldCapacity * 2) {// 初始化的空間大小是原來大小2倍
        doubleCapacity();
        return;
    }

    // We're growing by at least 4x, rehash in the obvious way
    HashMapEntry<K, V>[] newTable = makeTable(newCapacity);// 根據(jù)newCapacity初始化新數(shù)組
    if (size != 0) {// 重新掛載
        int newMask = newCapacity - 1;
        for (int i = 0; i < oldCapacity; i++) {
            for (HashMapEntry<K, V> e = oldTable[i]; e != null;) {
                HashMapEntry<K, V> oldNext = e.next;
                int newIndex = e.hash & newMask;
                HashMapEntry<K, V> newNext = newTable[newIndex];
                newTable[newIndex] = e;
                e.next = newNext;
                e = oldNext;
            }
        }
    }
}

接下來就是 remove 方法

remove()

/**
 * Removes the mapping with the specified key from this map.
 *
 * @param key
 *            the key of the mapping to remove.
 * @return the value of the removed mapping or {@code null} if no mapping
 *         for the specified key was found.
 */
@Override public V remove(Object key) {
    if (key == null) {// key 為空就調(diào)用下面方法去除
        return removeNullKey();
    }
    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (HashMapEntry<K, V> e = tab[index], prev = null;
            e != null; prev = e, e = e.next) {// 對鏈表的操作
        if (e.hash == hash && key.equals(e.key)) {
            if (prev == null) {
                tab[index] = e.next;
            } else {
                prev.next = e.next;
            }
            modCount++;// 修改次數(shù) + 1
            size--;// 大小 - 1
            postRemove(e);// 標(biāo)記去除的e
            return e.value;
        }
    }
    return null;
}

private V removeNullKey() {// 針對key 為null 進(jìn)行處理
    HashMapEntry<K, V> e = entryForNullKey;
    if (e == null) {
        return null;
    }
    entryForNullKey = null;
    modCount++;
    size--;
    postRemove(e);
    return e.value;
}

/**
 * Subclass overrides this method to unlink entry.
 */
void postRemove(HashMapEntry<K, V> e) { }// LinkedHashMap實(shí)現(xiàn)

休息一下

還記得 HashMap 的類聲明嗎砚蓬，

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

實(shí)現(xiàn)了 Cloneable 和 Serializable接口,都是兩個(gè)空接口，一個(gè)實(shí)現(xiàn)淺拷貝盆色，一個(gè)實(shí)現(xiàn)序列化

clone()

/**
 * Returns a shallow copy of this map.
 *
 * @return a shallow copy of this map.
 */
@SuppressWarnings("unchecked")
@Override public Object clone() {
    /*
     * This could be made more efficient. It unnecessarily hashes all of
     * the elements in the map.
     */
    HashMap<K, V> result;
    try {
        result = (HashMap<K, V>) super.clone();// here
    } catch (CloneNotSupportedException e) {
        throw new AssertionError(e);
    }

    // Restore clone to empty state, retaining our capacity and threshold
    result.makeTable(table.length);
    result.entryForNullKey = null;
    result.size = 0;
    result.keySet = null;
    result.entrySet = null;
    result.values = null;

    result.init(); // Give subclass a chance to initialize itself
    result.constructorPutAll(this); // Calls method overridden in subclass!!
    return result;
}

HashMap 的迭代器

 private abstract class HashIterator {
    int nextIndex;
    HashMapEntry<K, V> nextEntry = entryForNullKey;
    HashMapEntry<K, V> lastEntryReturned;
    int expectedModCount = modCount;

    HashIterator() {
        if (nextEntry == null) {
            HashMapEntry<K, V>[] tab = table;
            HashMapEntry<K, V> next = null;
            while (next == null && nextIndex < tab.length) {
                next = tab[nextIndex++];
            }
            nextEntry = next;
        }
    }

    public boolean hasNext() {
        return nextEntry != null;
    }

    HashMapEntry<K, V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (nextEntry == null)
            throw new NoSuchElementException();

        HashMapEntry<K, V> entryToReturn = nextEntry;
        HashMapEntry<K, V>[] tab = table;
        HashMapEntry<K, V> next = entryToReturn.next;
        while (next == null && nextIndex < tab.length) {
            next = tab[nextIndex++];
        }
        nextEntry = next;
        return lastEntryReturned = entryToReturn;
    }

    public void remove() {
        if (lastEntryReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        HashMap.this.remove(lastEntryReturned.key);
        lastEntryReturned = null;
        expectedModCount = modCount;
    }
}

上面的是定義在 HashMap 內(nèi)部的迭代器類灰蛙，在迭代的時(shí)候祟剔，外部可以通過調(diào)用 put 和 remove 的方法，來改變正在迭代的對象摩梧。但從設(shè)計(jì)之處物延，HashMap自身就不是線程安全的，因此HashMap在迭代的時(shí)候使用了一種Fast—Fail的實(shí)現(xiàn)方式障本，在 HashIterator 里面維持了一個(gè) expectedModCount 的變量教届，在每次調(diào)用的時(shí)候如果發(fā)現(xiàn) ModCount != expectedModCount，則拋出 ConcurrentModificationException 異常驾霜。但本身這種檢驗(yàn)不能保證在發(fā)生錯(cuò)誤的情況下案训，一定能拋出異常，所以我們需要在使用HashMap的時(shí)候粪糙，心里知道這是「非線程安全」的强霎。

HashMap 的序列化

 private void writeObject(ObjectOutputStream stream) throws IOException {
    // Emulate loadFactor field for other implementations to read
    ObjectOutputStream.PutField fields = stream.putFields();
    fields.put("loadFactor", DEFAULT_LOAD_FACTOR);
    stream.writeFields();
        
    stream.writeInt(table.length); // Capacity 寫入容量
    stream.writeInt(size);// 寫入數(shù)量
    for (Entry<K, V> e : entrySet()) {// 迭代寫入key 和value
        stream.writeObject(e.getKey());
        stream.writeObject(e.getValue());
    }
}

private void readObject(ObjectInputStream stream) throws IOException,
        ClassNotFoundException {
    stream.defaultReadObject();
    int capacity = stream.readInt();
    /**下面的代碼和上面的很類似*/
    if (capacity < 0) {
        throw new InvalidObjectException("Capacity: " + capacity);
    }
    if (capacity < MINIMUM_CAPACITY) {
        capacity = MINIMUM_CAPACITY;
    } else if (capacity > MAXIMUM_CAPACITY) {
        capacity = MAXIMUM_CAPACITY;
    } else {
        capacity = Collections.roundUpToPowerOfTwo(capacity);
    }

    makeTable(capacity);// 根據(jù)容量創(chuàng)建

    int size = stream.readInt();// 獲得size大小
    if (size < 0) {
        throw new InvalidObjectException("Size: " + size);
    }

    init(); // Give subclass (LinkedHashMap) a chance to initialize itself
    for (int i = 0; i < size; i++) {
        @SuppressWarnings("unchecked") K key = (K) stream.readObject();
        @SuppressWarnings("unchecked") V val = (V) stream.readObject();
        constructorPut(key, val); // 前面講到的另一個(gè)類似put的方法
    }
}

涉及序列化，需要了解一個(gè) Java 的關(guān)鍵字 transient 蓉冈，該關(guān)鍵字用來表示一個(gè)域不是該對象串行化的一部分城舞。當(dāng)一個(gè)對象被串行化的時(shí)候，transient 型變量的值不包括在串行化的表示中寞酿，然而非 transient 型的變量是被包括進(jìn)去的家夺。

總結(jié)

至此，HashMap 算是告一段落伐弹，可以看出谷歌處理 HashMap 時(shí)和 Java JDK 里面的方法的不同拉馋。雖然谷歌工程師大牛，但是也存在一些問題

• HashMap的每一次擴(kuò)容都會重新構(gòu)建一個(gè)length是原來兩倍的Entry表惨好，這個(gè)二倍擴(kuò)容的策略很容易造成空間浪費(fèi)煌茴。試想一下，假如我們總共有100萬條數(shù)據(jù)要存放日川，當(dāng)我put到第75萬條時(shí)達(dá)到閾值蔓腐，Hash表會重新構(gòu)建一個(gè)200萬大小的數(shù)組，但是我們最后只放了100萬數(shù)據(jù)龄句，剩下的100萬個(gè)空間將被浪費(fèi)回论。
• HashMap在存儲這些數(shù)據(jù)的過程中需要不斷擴(kuò)容，不斷的構(gòu)建Entry表分歇，不斷的做hash運(yùn)算透葛，會很慢。
• 此外卿樱，HashMap獲取數(shù)據(jù)是通過遍歷Entry鏈表來實(shí)現(xiàn)的僚害，在數(shù)據(jù)量很大時(shí)候會慢上加慢。

在 Android 項(xiàng)目中使用 HashMap，主要針對小數(shù)據(jù)量的任務(wù)比較ok萨蚕。

參考鏈接

HashMap源碼分析

Android HashMap源碼詳解

Java HashMap 源碼解析