HashMap簡介： HashMap在日常的開發中應用的非常之廣泛，它是基於Hash表，實現了Map介面，以鍵值對(key-value)形式進行數據存儲，HashMap在數據結構上使用的是數組+鏈表。允許null鍵和null值，不保證鍵值對的順序。 HashMap檢索數據的大致流程： 當我們使用Ha ...
HashMap簡介：
HashMap在日常的開發中應用的非常之廣泛，它是基於Hash表，實現了Map介面，以鍵值對(key-value)形式進行數據存儲，HashMap在數據結構上使用的是數組+鏈表。允許null鍵和null值，不保證鍵值對的順序。
HashMap檢索數據的大致流程：
當我們使用HashMap搜索key所對應的value時，HashMap會根據Hash演算法對key進行計算，得到一個key的hash值，再根據hash值算出該key在數組中存儲的位置index，然後獲取數組在index位置的鍵值對e,再使用鏈表對e進行遍歷，查找遍歷的元素是否和給定的key相符合，若有符合的，則返回其value值。
自己手動畫了一個HashMap的數據結構圖：
HashMap源碼分析：
HashMap是存儲鍵值對的集合，實現了Map介面,下麵我們看一下Map介面的定義：
/** *映射key到value的頂級介面，不能包含重覆的key，一個key最多可以映射到一個value,鍵和值均可為null */ public interface Map<K,V> { //返回該map包含的鍵值對的個數，如果鍵值對的個數超過了Integer.MAX_VALUE,則返會Integer.MAX_VALUE int size(); //如果該Map沒有包含鍵值對，則返回true，否則返回false boolean isEmpty(); //判斷該map是否包含指定的key所對應的鍵值對，key可以為null boolean containsKey(Object key); //判斷該map是否包含指定的value所對應的鍵值對,若map中包含有一個及以上的key,對應指定的value,則返回true，value可以為null boolean containsValue(Object value); //返回指定的key所對應的value，若key不存在，則返回null;但是返回null的key,不代表key在map中不存在，有可能是key所對應的value為null V get(Object key); //將指定的key和value映射為一個鍵值對，放入map中；若之前該map中包含了指定的Key,則該key所對應的老的值oldValue將會被替換為value V put(K key, V value); //刪除指定的key所對應的鍵值對，並返回該key對應的value V remove(Object key); //將指定的map中的鍵值對複製到當前map中 void putAll(Map<? extends K, ? extends V> m); //清除map中所有的鍵值對，該操作完成後，該map就是空的了 void clear(); //將map中所有的key返回，由於map中的key是不能重覆的，所以用Set集合的方式裝載所有的key Set<K> keySet(); //將map中所有的value返回，由於map中的value是可重覆的，所以用Collection集合的方式裝載所有的value Collection<V> values(); //將map中所有的鍵值對Entry返回，由於map中的鍵值對是不可重覆的（key不可重覆），所以用Set集合的方式裝載所有的value Set<Map.Entry<K, V>> entrySet(); //Map中承載鍵值對的數據結構Entry interface Entry<K,V> { //返回鍵值對的鍵值key K getKey(); //返回鍵值對的value值 V getValue(); //將當前鍵值對的value值 替換為指定的value值 V setValue(V value); //判斷指定的對象和當前鍵值對是否equals相等，若相等，則代表是同一個鍵值對； boolean equals(Object o); //返回當前鍵值對的hashCode值 int hashCode(); } //判斷指定對象和當前Map的equals是否相等 boolean equals(Object o); //返回當前Map的hashCode int hashCode(); }
下麵我們具體的看一下HashMap：
//HashMap是基於hash表來實現Map介面的，HashMap維護了下麵幾個變數： //HashMap預設的初始化大小為16 static final int DEFAULT_INITIAL_CAPACITY = 16; //HashMap包含鍵值對的最大容量為2^30,HashMap的容量一定要是2的整數次冪 static final int MAXIMUM_CAPACITY = 1 << 30; //預設的載入因數為0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //裝載鍵值對的內部容器Entry數組，長度一定得是2的冪 transient Entry[] table; //HashMap中包含的鍵值對的個數 transient int size; //HashMap的極限 當鍵值對的個數達到threshold時，數組table要擴容的 int threshold; //載入因數 final float loadFactor; //HashMap結構上被改變的次數，結構上的改變包括：鍵值對的大小的改變，修改HashMap的內部結構（比較進行了rehash操作），此屬性用來保持fail-fast transient volatile int modCount;
接下來我們看一下HashMap的構造函數：
/** *根據指定的容量initialCapacity和載入因數loadFactor構造HashMap */ public HashMap(int initialCapacity, float loadFactor) { //對initialCapacity進行參數校驗，若小於0，則拋出IllegalArgumentException異常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //若initialCapacity大於MAXIMUM_CAPACITY(2^30),則將MAXIMUM_CAPACITY賦值給initialCapacity if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //對參數loadFactor進行有效性校驗，不能<=0,不能非數字，否則拋出IllegalArgumentException異常 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity 找到一個2的冪的數capacity，使其不小於參數initialCapacity int capacity = 1; //若capacity小於initialCapacity,則將capacity擴大一倍 while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; //設置極限，大小為 capacity * loadFactor,即(容量*負載因數) threshold = (int)(capacity * loadFactor); //創建一個大小為capacity的Entry數組table,用來保存鍵值對 table = new Entry[capacity]; //調用方法init(),進行額外的初始化操作 init(); } //init方法是空的，如果你定製額外的初始化操作，可以繼承HashMap，覆蓋init()方法 void init() { } //通過指定的容量initialCapacity來構造HashMap，這裡使用了預設的載入因數DEFAULT_LOAD_FACTOR 0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //無參的構造函數 載入因數為DEFAULT_LOAD_FACTOR 0.75，容量為預設的DEFAULT_INITIAL_CAPACITY 16，極限為 16*0.75=12 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
下麵我們看一下HashMap中承載鍵值對的數據結構Entry的實現,Entry<K,V>是HashMap的一個靜態內部類
/** *Entry是HashMap裡面承載鍵值對數據的數據結構，實現了Map介面裡面的Entry介面，除了方法recordAccess(HashMap<K,V> m),recordRemoval(HashMap<K,V> m)外，其他方法均為final方法，表示即使是子類也不能覆寫這些方法。 */ static class Entry<K,V> implements Map.Entry<K,V> { //鍵值,被final修飾，表明一旦賦值，不可修改 final K key; //value值 V value; //下一個鍵值對的引用 Entry<K,V> next; //當前鍵值對中鍵值的hash值 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 K getKey() { return key; } public final V getValue() { return value; } //設置value值，返回原來的value值 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //比較鍵值對是否equals相等，只有鍵、值都相等的情況下，才equals相等 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(); //若k1 == k2(k1,k2引用同一個對象),或者k1.equals(k2)為true時，進而判斷value值是否相等 if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); //若v1 == v2(v1,v2引用同一個對象),或者v1.equals(v2)為true時，此時才能說當前的鍵值對和指定的的對象equals相等 if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } //其他均為false return false; } public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } //此方法只有在key已存在的時候調用m.put(key,value)方法時，才會被調用，即覆蓋原來key所對應的value值時被調用 void recordAccess(HashMap<K,V> m) { } //此方法在當前鍵值對被remove時調用 void recordRemoval(HashMap<K,V> m) { } }
下麵是Hash的put方法的實現：
/** *將指定的鍵key,值value放到HashMap中 */ public V put(K key, V value) { //首先判斷鍵key是否為null,若為null,則調用putForNullKey(V v)方法完成put if (key == null) return putForNullKey(value); //程式走到這，說明key不為null了，先調用hash(int)方法，計算key.hashCode的hash值 int hash = hash(key.hashCode()); //再調用indexFor(int,int)方法求出此hash值對應在table數組的哪個下標i上 (bucket桶) int i = indexFor(hash, table.length); //遍歷bucket桶上面的鏈表元素，找出HashMap中是否有相同的key存在，若存在，則替換其value值，返回原來的value值 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //若元素e.hash值和上面計算的hash值相等，並且(e.key == 入參key,或者入參key equals 相等 e.key)，則說明HashMap中存在了和入參相同的key了，執行替換操作 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; //在執行替換操作的時候，調用Entry對象的recordAccess(HashMap<K,V> m)方法，這個上面說過了 e.recordAccess(this); return oldValue; } } //程式走到這，說明原來HashMap中不存在key,則直接將鍵值對插入即可，由於插入元素，修改了HashMap的結構，因此將modeCount+1 modCount++; //調用addEntry(int,K,V,int)方法進行鍵值對的插入 addEntry(hash, key, value, i); //由於原來HashMap中不存在key，則不存在替換value值問題，因此返回null return null; }
當key為null時，HashMap是這樣進行數據插入的：
//先看看HashMap中原先是否有key為null的鍵值對存在，若存在，則替換原來的value值；若不存在，則將key為null的鍵值對插入到Entry數組的第一個位置table[0] private V putForNullKey(V value) { //獲取Entry數組的第一個元素:table[0],然後通過e.next進行鏈表的遍歷，若遍歷過程中有元素e.key為null,則替換該元素的值 for (Entry<K,V> e = table[0]; e != null; e = e.next) { //說明原來之前HashMap中就已經存在key問null的鍵值對了，現在又插入了一個key為null的新元素，則替換掉原來的key為null的value值 if (e.key == null) { V oldValue = e.value; e.value = value; //在執行替換操作的時候，調用Entry對象的recordAccess(HashMap<K,V> m)方法，這個上面說過了 e.recordAccess(this); return oldValue; } } //程式走到這，說明HashMap中原來沒有key為null的鍵值對，需要直接插入元素，由於插入元素，修改了HashMap的結構，因此將modeCount+1 modCount++; //調用addEntry(int,K,V,int)方法進行鍵值對的插入,這裡將入參hash設置為0，K為null,插入的位置index也為0，說明key為null的元素插入在bucket[0]第一個桶上 addEntry(0, null, value, 0); return null; }
HashMap在插入數據之前，要根據key值和hash演算法來計算key所對應的hash值
//根據key的hashCode值，來計算key的hash值 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); }
/** *在HashMap中要找到某個元素，需要根據key的hash值來求得對應數組中的位置,如何計算這個位置就是hash演算法. *HashMap的數據結構是數組和鏈表的結合,所以我們當然希望這個HashMap裡面的元素位置儘量的分佈均勻些，儘量使得每個位置上的元素數量只有一個, *那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表. *所以我們首先想到的就是把hashcode對數組長度取模運算，這樣一來，元素的分佈相對來說是比較均勻的,但是，“模”運算的消耗還是比較大的， *能不能找一種更快速，消耗更小的方式那？java中時這樣做的 :將hash值和數組長度按照位與&來運算 */ static int indexFor(int h, int length) { return h & (length-1); }
下麵我們看一看實際進行數據添加的操作addEntry方法
/** *將指定的key,value,hash,bucketIndex 插入鍵值對，若此時size 大於極限threshold,則將Entry數組table擴容到原來容量的兩倍 */ void addEntry(int hash, K key, V value, int bucketIndex) { //取出原來bucketIndex處的鍵值對e Entry<K,V> e = table[bucketIndex]; //創建一個新的鍵值對，使用給定的hash、key、value,並將新鍵值對的next屬性指向e,最後將新鍵值對放在bucketIndex處 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //將size+1,若此時size 大於極限threshold,則將Entry數組table擴容到原來容量的兩倍 if (size++ >= threshold) //調用resize(int)方法，進行數組的擴容 resize(2 * table.length); }
我們知道HashMap採用的數組+鏈表來實現的，當HashMap中元素的個數size大於極限threshold時，會進行數組的擴容操作，這個操作使用resize(int newCapacity)方法實現的：
/** *將HashMap中Entry數組table的容量擴容至新容量newCapacity,數組的擴容不但涉及到數組元素的複製，還要將原數組中的元素rehash到新的數組中，很耗時;如果能預估到放入HashMap中元素的大小，最好使用new HashMap(size)方式創建足夠容量的HashMap，避免不必要的數組擴容(rehash操作)，提高效率 */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果原數組的大小已經為允許的最大值MAXIMUM_CAPACITY了，則不能進行擴容了，這裡僅僅將極限threshold設置為Integer.MAX_VALUE，然後返回 if (oldCapacity == MAXIMUM_CAPACITY) { //將極限threshold設置為Integer.MAX_VALUE threshold = Integer.MAX_VALUE; return; } //程式走到這，說明可以進行擴容，先創建容量為newCapacity的新Entry數組newTable Entry[] newTable = new Entry[newCapacity]; //調用tranfer(Entry[] newTable)方法，進行數組元素的移動和rehashing transfer(newTable); //將新數組newTable賦值給table table = newTable; //計算極限threshold的最新值 threshold = (int)(newCapacity * loadFactor); } //將原Entry數組table中的所有鍵值對遷移到新Entry數組newTable上 void transfer(Entry[] newTable) { //原數組賦值給src Entry[] src = table; //新數組長度為newCapacity int newCapacity = newTable.length; //遍歷原數組 for (int j = 0; j < src.length; j++) { //獲取原數組中的元素(鍵值對),賦值給e Entry<K,V> e = src[j]; //若元素e不為null if (e != null) { //將當前元素設值為null src[j] = null; //遍歷元素e所對應的bucket桶內的所有元素 do { //獲取下一個元素next Entry<K,V> next = e.next; //重新計算鍵值對e在新數組newTable中的bucketIndex位置(即rehash操作) int i = indexFor(e.hash, newCapacity); //這步操作，說實話，沒看懂，有清楚的，請不吝賜教 e.next = newTable[i]; //將當前元素e放入新數組的i位置 newTable[i] = e; //將下一個元素next賦值給當前元素，以便完成遍歷 e = next; } while (e != null); } } }
下麵我們看一下HashMap檢索數據的操作：
//獲取指定key所對應的value值 public V get(Object key) { //若key==null,則直接調用getForNullKey()方法 if (key == null) return getForNullKey(); //到這說明key != null,先獲取key的hash值 int hash = hash(key.hashCode()); //在indexFor(int hash,int length)獲取key落在Entry數組的哪個bucket桶上，獲取該bucket桶上的元素e,進而遍歷e的鏈表，找相對應的key,若找到則返回key所對應的value值，找不到則返回null for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若元素e.hash == 上面計算的hash值，並且(e.key 和入參key是同一個對象的引用，或者e.key和入參key equals相等)， //則認為入參key和當前遍歷的元素e的key是同一個,返回e的value值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } //上面遍歷了一遍也沒有找到，則返回null return null; } //獲取key為null的value值，由上面putForNullKey方法可知，key為null的鍵值對，被放在了Entry數組table的第一個bucket桶(table[0]) private V getForNullKey() { //獲取Entry數組table的第一個元素e,從e開始往下遍歷，若找到元素e.key 為null的，則直接返回該元素e.value值 for (Entry<K,V> e = table[0]; e != null; e = e.next) { //找到元素e.key 為null的，則直接返回該元素e.value值 if (e.key == null) return e.value; } //從table[0]開始，遍歷鏈表一遍，沒有找到key為null的，則返回null return null; } //獲取指定key所對應的鍵值對Entry,先獲取key的hash值，再獲取該hash值應放入哪個hash桶，然後遍歷該桶中的鍵值對，若有則返回該鍵值對；若沒有則返回null final Entry<K,V> getEntry(Object key) { //若key為null,則hash值為0；若key != null,則利用hash(int)計算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); //獲取該hash值應放入哪個hash桶,並遍歷該hash桶 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //若元素e.hash == hash,並且(e.key == key，或者 key.equals(e.key)為true)，則認為入參key和當前遍歷的元素e.key是同一個，返回該元素e if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } //若沒有則返回null return null; }
//判斷HashMap中是否含有指定key的鍵值對，內部用getEntry(Object key)來實現 public boolean containsKey(Object key) { return getEntry(key) != null; }
//將指定Map中的所有元素(鍵值對)拷貝到當前HashMap中，對於當前HashMap中存在的key,則進行value值的替換 public void putAll(Map<? extends K, ? extends V> m) { //若指定的Map中沒有元素，則直接返回 int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; //若必要，則進行數組的擴容 if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; //計算新的容量 int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; //若新容量大於目前數組的長度，則調用resize(int)進行擴容 if (newCapacity > table.length) resize(newCapacity); } //獲取指定Map的迭代器，迴圈調用put(K k,V v)方法，進行鍵值對的插入 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); put(e.getKey(), e.getValue()); } }
下麵看下HashMap的remove操作：
/** * 刪除指定key所對應的元素 */ public V remove(Object key) { //調用方法reomveEntryForKey(Object key)來刪除並獲取指定的entry Entry<K,V> e = removeEntryForKey(key); //若entry為null，則返回null；否則返回entry的value值 return (e == null ? null : e.value); } /** *移除並返回指定key所關聯的鍵值對entry,若HashMap中沒有鍵值對和指定的key相關聯，則返回null */ final Entry<K,V> removeEntryForKey(Object key) { //若key為null,則hash值為0；若key != null,則利用hash(int)計算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); //獲取key應放入的在數組中的位置索引i int i = indexFor(hash, table.length); //標識前一個元素 Entry<K,V> prev = table[i]; //標識遍歷過程中的當前元素 Entry<K,V> e = prev; //遍歷bucket桶table[i]中的元素，尋找對應的key while (e != null) { //當前元素的下一個元素 Entry<K,V> next = e.next; Object k; //元素e.hash和上面計算的hash值相等，並且(key == e.key 或者key.equals(e.key) 為true)，說明找到了指定key所對應的鍵值對 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { //由於刪除了一個元素，修改了HashMap的結構，因此將modCount+1 modCount++; //將size-1 size--; //若待查找的元素為桶內的第一個元素，則當前元素的下一個元素next放入數組中位置i中 if (prev == e) table[i] = next; //否則將上一個元素的next屬性指向 當前元素的next else prev.next = next; //當元素被remove時，調用Entry對象的recordRemove(Map<K,V> m)方法 e.recordRemoval(this); //返回找到的當前元素 return e; } //程式走到這，說明當前元素不是要查找的元素；則將當前元素賦值給上一個元素，將下一個元素賦值給當前元素，以完成遍歷 prev = e; e = next; } return e; }
//判斷HashMap中是否包含指定的對象value public boolean containsValue(Object value) { //若value為null，則調用containsNullValue()方法處理 if (value == null) return containsNullValue(); //將數組table賦值給tab Entry[] tab = table; //遍曆數組tab的每個索引位置(此層迴圈對應數組結構) for (int i = 0; i < tab.length ; i++) //對應指定的索引位置i,遍歷在索引位置i上的元素(此層迴圈對應鏈表結構) for (Entry e = tab[i] ; e != null ; e = e.next) //若某個元素e.value和指定的value equals相等，則返回true if (value.equals(e.value)) return true; //遍歷完成沒有找到對應的value值，返回false return false; } //判斷HashMap是否包含value為null的元素 private boolean containsNullValue() { //將數組table賦值給tab Entry[] tab = table; //遍曆數組tab的每個索引位置(此層迴圈對應數組結構) for (int i = 0; i < tab.length ; i++) //對應指定的索引位置i,遍歷在索引位置i上的元素(此層迴圈對應鏈表結構) for (Entry e = tab[i] ; e != null ; e = e.next) //若某個元素e.value == null，則返回true if (e.value == null) return true; //沒有找到value值為null的，返回false return false; }
//清除HashMap中所有的鍵值對，此操作過後，HashMap就是空的了 public void clear() { //要刪除所有的元素，肯定會對HashMap的結構造成改變，因此modCount+1 modCount++; Entry[] tab = table; //遍曆數組，將數組中每個索引位置的設置為null for (int i = 0; i < tab.length; i++) tab[i] = null; //將size 修改為0 size = 0; }
現在看一下上面沒有講的一個構造函數:
//構造一個新的HashMap，以承載指定Map中所有的鍵值對，使用預設的載入因數DEFAULT_LOAD_FACTOR public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); //調用putAllForCreate(Map<? extends K, ? extends V>)方法完成元素的遷移 putAllForCreate(m); } private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); //在迭代器迴圈中調用putForCreate(K k,V v)來實現元素的創建 putForCreate(e.getKey(), e.getValue()); } } //該方法和put方法不同，它不會進行數組的擴容resize,和對modCount的檢查 private void putForCreate(K key, V value) { //若key為null,則hash值為0；若key != null,則利用hash(int)計算key的hash值 int hash = (key == null) ? 0 : hash(key.hashCode()); //求key應該放入哪個hash桶(bucket)內 int i = indexFor(hash, table.length); //遍歷鏈表，若key之前在Map中已經有了，則直接返回 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } //調用createEntry(int hash,K k,V v,int bucketIndex)方法完成鍵值對的創建並加入到鏈表中 createEntry(hash, key, value, i); } void createEntry(int hash, K key, V value, int bucketIndex) { //將bucketIndex位置的元素取出來 Entry<K,V> e = table[bucketIndex]; //創建一個新的鍵值對，使用給定的hash、key、value,並將新鍵值對next指向e,最後將新鍵值對放在bucketIndex處 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //將數組大小size + 1 size++; }
下麵我們講下HashMap的負載因數loadfactor, 所謂負載因數就是散列表的實際元素數目(n)/散列表的容量(m), 它衡量的是一個散列表的空間的使用程度，預設情況下loadfactor是0.75，它的作用是當HashMap中元素的個數size 大於(HashMap的容量capacity * 負載因數loadfactor)時，該HashMap便會進行擴容resize。
我們先說下hash衝突：
當利用HashMap存數據的時候，先根據key的hashcode值來計算key的hash值(利用hash函數)，再根據hash值來計算該key在數組table中的位置index（hash & (length-1)）,比如我們要存兩個鍵值對key1-value1和key2-value2,
如果key1、key2分別通過hash函數計算的hash值hash1、hash值hash2 相等，那key1和key2一定會落在數組table的同一個位置上，這就產生了衝突，這個衝突是由不同的key值但是卻相同的hash值引起的，稱之為hash衝突。HashMap解決hash衝突的方式就是鏈表，雖然key1-value1和key2-value2這兩個鍵值對落在了數組table的同一個位置上，但是它們是鏈表的方式連接在一起，當HashMap查找key1時，就需要遍歷這個鏈表了。
當負載因數越大的時候，出現hash衝突的可能性越大，這意味著數組table中某個具體的桶bucket上不止有一個元素（此時就構成了鏈表了）可能性增大，在檢索數據的時候需要遍歷鏈表的可能性增大，因此檢索的效率就比較低（耗時長），但是空間的利用率越高。
當負載因數越小的時候，出現hash衝突的可能性越小，這意味著數組table中某個具體的桶bucket上不止有一個元素（此時就構成了鏈表了）可能性減小了，在檢索數據的數據需要遍歷鏈表的可能性減小，因此檢索的效率就比較高，但是空間利用率越低。
上面的源碼解析了提到了HashMap的容量一定得是2的整數此冪(2^n),這又是問什麼呢？
通過上面的源碼我們知道：根據hash值求該hash值在數組中的位置的實現是： hash & (length-1)，當數組table的長度length為2的整數次冪的時候，那（length-1）二進位表示形式從低位開始一定都是1，直到為0，如果length依次為2,4,8,16,32，64，則(length-1)一次為1,3,7,15,31,63，那(length-1)的二進位形式依次為1,11,111,1111,11111，我們知道二進位的與運算&，當一方位數全是1的時候，進行&運算的結果完全取決於另外一方。
比如從0開始到15,依次和15進行&運算，看
