Java HashMap深度剖析

一、首先再簡單重復一下Hash算法
簡單的說就是一種將任意內容的輸入轉換成相同長度輸出（有個范圍，假設10位的數字，用一個稱之為HashTable的容器來存放）的加密方式------hash
如（假設）：
“a”---10位數1
123---10位數2
…
注意：任意內容的輸入，范圍是無窮無盡，肯定比相同長度輸出（如10位數）要大很多，那麼就會造成不同的輸入，會得到相同的輸出（值）----hash沖突
HashMap當然也無法避免沖突問題

二、HashMap源碼片段
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;//負載因子，默認0.75
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
//使用的是Entry數組
        init();
}

public V put(K key, V value) {
        if (key == null)//空的情況，允許存空
            return putForNullKey(value);
        int hash = hash(key.hashCode());//根據key的hashCode再來計算一個hash值----根據hash沖突可以知道不同的key對應的hashCode可能一樣（如果不被重寫的話，Object的hashCode()生成的hashCode存放在java底層的一個大的HashTable上，不過我想JDK應該已經做過沖突處理，不會使用這麼簡單的hash算法，除非自己重寫hashCode(),否則應該不會有沖突，真的發生沖突估計要內存溢出了）
//就算hashCode不同，通過hash()出來的hash值也可能沖突(後面會講到)
        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))) {//該位置已經有了，且key也完全是同一個，就覆蓋，否則也是走下面的新開(後面會有例子)
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }//已經存在的情況
//以下是新增的情況
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

/**
為給定的hashCode增加一個hash方法，用於抵消低質量的hash函數。這是很關鍵的，因為HashMap使用power-of-two長度的hash表，否則遇到沖突的hashCode無法區分    
     */
    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);
    }

//根據hashCode及table的長度計算index
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];//先取原有的元素作為next，index沖突的時候用，形成一個“鏈條”
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存放自己的下一個
        final int hash;
...
}

//------再看一下get方法
public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
//根據key的hashCode計算出“鏈條”在table中的index，再到“鏈條”中查找符合自己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.equals(k)))
                return e.value;
        }
        return null;
  }