現(xiàn)在，有了hash code,來考慮如何計算放入數(shù)組的位置。hash code值通常會很大，但是數(shù)組的大小有限，默認(rèn)只有16，大的也不能超過2的30次方。所以，用模運(yùn)算來保證在數(shù)組大小范圍內(nèi)是合理的，比如:index = hash code % array size.不過這有點(diǎn)慢，JDK采用了更快的算法。這個更快的算法源于一個數(shù)學(xué)規(guī)律，就是如果size是2的N次方，那么數(shù)X對size的模運(yùn)算結(jié)果等價于X和size-1的按位與運(yùn)算，也就是 X % size <=> X & (size -1).按位與只消耗一個CPU周期，當(dāng)然快多了。現(xiàn)在就可理解為什么要故意把數(shù)組大小弄成2的N次方了。再回頭看一開始計算數(shù)組大小的代碼，完全理解了。

int capacity = 1;  
        while (capacity < initialCapacity)  
            capacity <<= 1; 

比如size=16，二進(jìn)制表示如下：（32位）

0000000000000000000000000010000

size-1=15，表示如下：

0000000000000000000000000001111

假如hash code=4

0000000000000000000000000000100

4 & 15 結(jié)果為：

0000000000000000000000000000100

假如hash code=6

0000000000000000000000000000101

6 & 15 結(jié)果為：

0000000000000000000000000000101

假如hash code=38

0000000000000000000000000100110

38 & 15 結(jié)果為：

0000000000000000000000000000110

通過觀察這三個例子，又可以發(fā)現(xiàn)一個特點(diǎn)，也就是X & size-1 的結(jié)果受到了size的階數(shù)的限制，這里size=16,階數(shù)為4.結(jié)果就是只用低4位的1和X按位與，而X的高位沒有用到。這會導(dǎo)致重復(fù)率相當(dāng)高。如果用一個算法將X的低位重新計算，比如根據(jù)所有位的值進(jìn)行重新計算，就可以使得hash值分布更均勻。下面的代碼揭示了在真正按位與之前，調(diào)用了hash函數(shù)，進(jìn)行了一堆位運(yùn)算。至于為什么用這個算法，我也不知道其來歷。

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value);  
        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;  
            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;  
    }  
 
    static int hash(int h) {  
        // This function ensures that hashCodes that differ only by  
        // constant multiples at each bit position have a bounded  
        // number of collisions (approximately 8 at default load factor).  
        h ^= (h >>> 20) ^ (h >>> 12);  
        return h ^ (h >>> 7) ^ (h >>> 4);  
    }  
 
    static int indexFor(int h, int length) {  
        return h & (length-1);  
    }  
 
    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);  
    } 

上面的for循環(huán)是查找并替換符合條件的對象，如果找不到，則添加新的對象。查找到的條件（必須都滿足）是：

1.hash值相等

2.key的引用相同或者key的值相等。

原文鏈接：http://blog.csdn.net/sheismylife/article/details/7355282

【編輯推薦】

1. Java HashMap分析之二：Hash code
2. Java HashMap分析之一：基本結(jié)構(gòu)
3. Java集合框架總結(jié)：Set接口的使用
4. Java的位移運(yùn)算巧方法
5. Java7的一個新類JLayer：裝飾的Swing組件