Java的HashMap非常的常用，本篇研究它的實(shí)現(xiàn)算法，***希望計(jì)算出內(nèi)存占用，性能的量化數(shù)據(jù)，然后得出什么時(shí)候使用HashMap，什么時(shí)候不能濫用的結(jié)論。

HashMap實(shí)際上是一個(gè)數(shù)組，數(shù)組里面的每個(gè)元素都是一個(gè)鏈表。每個(gè)元素在通過put方法放入HashMap中的時(shí)候，要按照如下步驟進(jìn)行：

1.根據(jù)該元素自身提供的hashcode計(jì)算出散列值，該散列值就是數(shù)組的下標(biāo)

2.將新元素放入該數(shù)組位置的鏈表中

先來看一下數(shù)組的定義：

/**  
     * The table, resized as necessary. Length MUST Always be a power of two.  
     */ 
    transient Entry[] table; 

這是一個(gè)數(shù)組，transient關(guān)鍵字告訴我們它不會(huì)參與序列化。既然是一個(gè)數(shù)組，總有數(shù)目上限，也就意味著如果存入HashMap的元素太多，導(dǎo)致數(shù)組大小不能夠存放所有的鏈表的時(shí)候，數(shù)組大小必須要能夠調(diào)整。所以首先來考察一下數(shù)組容量的相關(guān)算法。

***，Entry是什么類型？

static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        Entry<K,V> next;  
        final int hash;  
 
        /**  
         * Creates new entry.  
         */ 
        Entry(int h, K k, V v, Entry<K,V> n) {  
            value = v;  
            next = n;  
            key = k;  
            hash = h;  
        }  
        ....  
        public final boolean equals(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry e = (Map.Entry)o;  
            Object k1 = getKey();  
            Object k2 = e.getKey();  
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
                Object v1 = getValue();  
                Object v2 = e.getValue();  
                if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                    return true;  
            }  
            return false;  
        }  
 
        public final int hashCode() {  
            return (key==null   ? 0 : key.hashCode()) ^  
                   (value==null ? 0 : value.hashCode());  
        }  
        .... 

這是一個(gè)HashMap類的內(nèi)部靜態(tài)類。實(shí)現(xiàn)了Map.Entry接口。接受兩個(gè)模板參數(shù)K和V。key和hash一旦在構(gòu)造函數(shù)中被初始化，就不可改變，并且由于有next的存在，Entry可以構(gòu)成一個(gè)單向鏈表。

比較重要的是equals和hashCode方法。代碼先列出來，后面再解釋。

第二，初始容量的設(shè)定

大多數(shù)都在下面的構(gòu)造函數(shù)里面.用于指定的initialCapacity不準(zhǔn)小于0，也不能超過***值。并且最終的capicity必須是2的n次方。還有如果使用了無參數(shù)的構(gòu)造函數(shù)，默認(rèn)會(huì)創(chuàng)建一個(gè)擁有16個(gè)元素的數(shù)組。

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)(capacity * loadFactor);  
        table = new Entry[capacity];  
        init();  
    } 

第三,什么時(shí)候應(yīng)該調(diào)整數(shù)組的大?。?/strong>

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)  
            resize(2 * table.length);  
    }