Java的HashMap非常的常用本篇研究它的實現算法最後希望計算出內存占用性能的量化數據然後得出什麼時候使用HashMap什麼時候不能濫用的結論
HashMap實際上是一個數組數組裡面的每個元素都是一個鏈表每個元素在通過put方法放入HashMap中的時候要按照如下步驟進行根據該元素自身提供的hashcode計算出散列值該散列值就是數組的下標將新元素放入該數組位置的鏈表中先來看一下數組的定義[java] view plaincopy /** * The table resized as necessary Length MUST Always be a power of two */ transient Entry[] table
這是一個數組transient關鍵字告訴我們它不會參與序列化既然是一個數組總有數目上限也就意味著如果存入HashMap的元素太多導致數組大小不能夠存放所有的鏈表的時候數組大小必須要能夠調整所以首先來考察一下數組容量的相關算法
第一Entry是什麼類型？
[java] view plaincopy static class Entry<KV> implements MapEntry<KV> { final K keyV valueEntry<KV> nextfinal int hash
/** * Creates new entry */ Entry（int h K k V v Entry<KV> n） { value = vnext = nkey = khash = h}……
public final boolean equals（Object o） { if （！（o instanceof MapEntry））
return falseMapEntry e = （MapEntry）oObject k = getKey（）Object k = egetKey（）if （k == k || （k ！= null && kequals（k））） { Object v = getValue（）Object v = egetValue（）if （v == v || （v ！= null && vequals（v）））
return true} return false}
public final int hashCode（） { return （key==null ？ keyhashCode（）） ^（value==null ？ valuehashCode（））}……
這是一個HashMap類的內部靜態類實現了MapEntry接口接受兩個模板參數K和Vkey和hash一旦在構造函數中被初始化就不可改變並且由於有next的存在Entry可以構成一個單向鏈表
比較重要的是equals和hashCode方法代碼先列出來後面再解釋
第二初始容量的設定大多數都在下面的構造函數裡面用於指定的initialCapacity不准小於也不能超過最大值並且最終的capicity必須是的n次方還有如果使用了無參數的構造函數默認會創建一個擁有個元素的數組
[java] view plaincopy public HashMap（int initialCapacity float loadFactor） { if （initialCapacity < ）
throw new IllegalArgumentException（Illegal initial capacity + initialCapacity）if （initialCapacity > MAXIMUM_CAPACITY）
initialCapacity = MAXIMUM_CAPACITYif （loadFactor <= || FloatisNaN（loadFactor））
throw new IllegalArgumentException（Illegal load factor + loadFactor）
// Find a power of >= initialCapacity int capacity = while （capacity < initialCapacity）
capacity <<=
thisloadFactor = loadFactorthreshold = （int）（capacity * loadFactor）table = new Entry[capacity]init（）}
第三什麼時候應該調整數組的大小？
算法是這樣有一個變量size保存了實際數組已經使用了多少個元素並且如果size的值達到了變量threshold的值就必須擴充數組的容量threshold=capicity*loadFactorcapicity是數組最大的容納元素個數loadFactor可以在構造函數中制定否則采用默認值fcapicity的最大值是<<（也就是的次方）由此我們可以看到HashMap最多存放億多個鏈表
第四如何調整數組大小？
答案是倍很像C++裡面的vector的分配策略
[java] view plaincopy void addEntry（int hash K key V value int bucketIndex） { Entry<KV> e = table[bucketIndex]table[bucketIndex] = new Entry<KV>（hash key value e）if （size++ >= threshold）
resize（ * tablelength）}
第五為什麼數組大小必須是的倍數？
在後面介紹散列值算法的時候會回答
From:http://tw.wingwit.com/Article/program/Java/hx/201311/25781.html
