java——HashMap的完成原理，自己完成復雜的HashMap

數據構造中無數組和鏈表來完成對數據的存儲，但是數組存儲區間是延續的，尋址容易，拔出和刪除困難；而鏈表的空間是團圓的，因而尋址困難，拔出和刪除容易。

因而，綜合了二者的優勢，我們可以設計一種數據構造——哈希表（hash table），它尋址、拔出和刪除都很方便。在java中，哈希表的完成次要就是HashMap了，可以說HashMap是java開發中運用最多的類之一吧。

HashMap的底層其實就是鏈表的數組，代碼為

transient Entry[] table;

這裡的table其實就是一個鏈表的數組，由於我們的數據是二元的，因而HashMap定義了一個外部的類Entry，它包括了key和value兩個屬性。這樣一個一維的線性數組就可以存儲兩個值了。同時Entry是一個鏈表，因而還有一個Entry next屬性，它指向了下一個節點。

存儲put時：

首先計算出key的hash,然後用table[hash]失掉那個鏈表，再遍歷這個鏈表，假如鏈表中有一個key和這個key是滿足equals的話，則將value交換掉；假如沒有的話，則拔出到鏈表的尾部。

int h = hash(key);
Entry e = table[h];

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;
            }
        }

在get時，也是以異樣的辦法失掉那個鏈表Entry e；然後遍歷這個鏈表取出元素

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;

HashMap對功能的優化：

HashMap對功能優化，次要是在於增加hash抵觸（不同的key算出異樣的hash），由於hash抵觸越多，從鏈表中需求的尋址時間就越長。

1.經過計算hash值的方式增加hash抵觸：

這個hash辦法無效的增加了hash抵觸：（詳細我的確不懂！大家參考http://zhangshixi.iteye.com/blog/672697）

static int hash(int h) {  
    h ^= (h >>> 20) ^ (h >>> 12);  
    return h ^ (h >>> 7) ^ (h >>> 4);  
}  
static int indexFor(int h, int length) {  
    return h & (length-1);  
}  

我自己寫了一個十分復雜計算hash值的方式，勉強能用：

Math.abs(o==null?0:o.hashCode()) % length

2.自動擴容

當HashMap中的元素越來越多的時分，hash抵觸的幾率也就越來越高，由於數組的長度是固定的。因而，此時就需求對數組停止擴容了。

當HashMap中的元素個數超越數組大小*loadFactor（默許值0.75）時，就會停止數組擴容。這時，需求創立一張新表，將原表的映射到新表中。

擴容時，遍歷每個元素，重新計算其hash值，然後參加新表中。

普通來說，擴容數組的大小為原數組大小的兩倍。而這是一個很耗功能的操作，因而，假如我們曾經預知HashMap中元素的個數，那麼提早設置初始容量將大大提升其功能。

我將我的源碼放到了github上，歡送大家下載交流。

http://pan.baidu.com/s/1dFj2405

https://github.com/xcr1234/my-java 

附上自己完成的功能測試後果，勉強能承受

這篇博文和代碼一定還有很多缺乏的中央，也請各位大神指出！或許fork我的代碼並提出珍貴的建議，謝謝！