Java HashMap 分析之一:基本結構

　　Java的HashMap非常的常用,本篇研究它的實現演算法,最后希望計算出內存佔用,性能的量化數據,然後得出什麼時候使用HashMap,什麼時候不能濫用的結論.

　　HashMap實際上是一個數組,數組裡面的每個元素都是一個鏈表.每個元素在通過put方法放入HashMap中的時候,要按照如下步驟進行：1.根據該元素自身提供的hashcode計算出散列值,該散列值就是數組的下標2.將新元素放入該數組位置的鏈表中先來看一下數組的定義：[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<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（））；}……

　　這是一個HashMap類的內部靜態類.實現了Map.Entry介面.接受兩個模板參數K和V.key和hash一旦在構造函數中被初始化,就不可改變,並且由於有next的存在,Entry可以構成一個單向鏈表.

　　比較重要的是equals和hashCode方法.代碼先列出來,後面再解釋.

　　第二,初始容量的設定大多數都在下面的構造函數裡面.用於指定的initialCapacity不準小於0,也不能超過最大值.並且最終的capicity必須是2的n次方.還有如果使用了無參數的構造函數,默認會創建一個擁有16個元素的數組.

　　[java] view plaincopy 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（）；}

　　第三,什麼時候應該調整數組的大小？

　　演算法是這樣,有一個變數size保存了實際數組已經使用了多少個元素,並且如果size的值達到了變數threshold的值,就必須擴充數組的容量.threshold=capicity*loadFactor.capicity是數組最大的容納元素個數,loadFactor可以在構造函數中制定,否則採用默認值0.75f.capicity的最大值是1<<30（也就是2的30次方,1073741824）.由此我們可以看到HashMap最多存放10億多個鏈表.

　　第四,如何調整數組大小？

　　答案是2倍,很像C 裡面的vector的分配策略.

　　[java] view plaincopy 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）；}

　　第五,為什麼數組大小必須是2的倍數？

　　在後面介紹散列值演算法的時候會回答.