HashMap工作原理

相信大家不管是在Java還是安卓面試過程中，或多或少都會被問及HashMap的工作原理，小編今天大概看了一下Android中HashMap的源碼，將結果整理如下，如有不對之處請批評指正：

一、HashMap的數據結構

其實HashMap的存儲數據結構是一個散列數組+鏈表的數據結構，如圖：

HashMap的存儲數據結構

我們都知道往HashMap里存儲值時會傳入key和value，HashMap首先會拿到key相對應的hash值，

接著通過hash值計算存放數組的下標，再將value值存放在數組對應下標下的鏈表里。

接下來我們就根據源碼看看HashMap的存取實現。

二、HashMap的存取實現

1） put（key，value）

@Override 
public V put(K key, V value) {    
    if (key == null) {        
        return putValueForNullKey(value);    
    }    

    int hash = Collections.secondaryHash(key);    
    HashMapEntry<K, V>[] tab = table;    
    int index = hash & (tab.length - 1);    
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {        
         if (e.hash == hash && key.equals(e.key)) {            
             preModify(e);            
             V oldValue = e.value;            
             e.value = value;            
             return oldValue;        
         }    
     }    

     // No entry for (non-null) key is present; create one    
     modCount++;    
     if (size++ > threshold) {        
         tab = doubleCapacity();        
         index = hash & (tab.length - 1);    
     }    
     addNewEntry(key, value, hash, index);    
     return null;
}

由源碼可以看出，程序首先會檢測key值是否為空，如果為空則做空值處理（null key總是存放在entryForNullKey對象中）；接著對key的hashCode()做hash，然后再計算index；接著在Entry[index]下的鏈表里查找是否存在hash和key值與插入key的一樣的HashMapEntry對象，如果有的話，則將舊值替換成value，并返回舊值；否則通過addNewEntry插入新的HashMapEntry對象，源碼如下：

void addNewEntry(K key, V value, int hash, int index) {    
    table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {    
    this.key = key;    
    this.value = value;    
    this.hash = hash;    
    this.next = next;
}

由方法可知，插入方法是將新的HashMapEntry對象當成table[index]下鏈表的頭結點，而用新的HashMapEntry對象的next指向原table[index]下鏈表的頭結點，以達成插入鏈表頭結點的目的。

2） get（key）

public V get(Object key) {    
    if (key == null) {        
        HashMapEntry<K, V> e = entryForNullKey;        
        return e == null ? null : e.value;    
    }    

    int hash = Collections.secondaryHash(key);    
    HashMapEntry<K, V>[] tab = table;    
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
          e != null; e = e.next) {        
          K eKey = e.key;        
          if (eKey == key || (e.hash == hash && key.equals(eKey))) {            
              return e.value;        
          }    
     }    
     return null;
}

由源碼可以看出，程序首先會判斷key值是否為空，如果為空，則檢查entryForNullKey有沒有存放值，有的話則返回；接著對key的hashCode()做hash，然后再計算index；接著在Entry[index]下的鏈表里查找是否存在hash和key值與插入key的一樣的HashMapEntry對象，有的話則返回。

三、HashMap的大小問題

• 如果沒有設置初始大小，即直接new HashMap()，size為MINIMUM_CAPACITY 的二分之一

  /** * An empty table shared by all zero-capacity maps (typically from default
  * constructor). It is never written to, and replaced on first put. Its size
  * is set to half the minimum, so that the first resize will create a 
  * minimum-sized table. 
  */
  private static final Entry[] EMPTY_TABLE        
      = new HashMapEntry[MINIMUM_CAPACITY >>> 1];
  public HashMap() {    
      table = (HashMapEntry<K, V>[]) EMPTY_TABLE;    
      threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
  }

• 如果有設置初始大小，即調用new HashMap(capacity)， 注意table初始大小并不是構造函數中的initialCapacity！！而是 >= initialCapacity并且是2的n次冪的整數！！！！

  public HashMap(int capacity) {    
     if (capacity < 0) {        
         throw new IllegalArgumentException("Capacity: " + capacity);    
     }    
  
     if (capacity == 0) {        
         @SuppressWarnings("unchecked")        
         HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;        
         table = tab;        
         threshold = -1; // Forces first put() to replace EMPTY_TABLE        
         return;    
     }    
  
     if (capacity < MINIMUM_CAPACITY) {        
         capacity = MINIMUM_CAPACITY;    
     } else if (capacity > MAXIMUM_CAPACITY) {        
         capacity = MAXIMUM_CAPACITY;    
     } else {        
         capacity = Collections.roundUpToPowerOfTwo(capacity);    
     }    
     makeTable(capacity);
  }

  其中Collections的roundUpToPowerOfTwo方法，就是獲取大于等于 某個整數 并且是 2 的冪數的整數

• 再散列 rehash ：當哈希表的容量超過默認容量時，doubleCapacity會調整table的為原來的2倍。這時，需要創建一張新表，將原表的映射到新表中。

  private HashMapEntry<K, V>[] doubleCapacity() {    
      HashMapEntry<K, V>[] oldTable = table;    
      int oldCapacity = oldTable.length;    
      if (oldCapacity == MAXIMUM_CAPACITY) {        
          return oldTable;    
      }    
      int newCapacity = oldCapacity * 2;    
      HashMapEntry<K, V>[] newTable = makeTable(newCapacity);    
      if (size == 0) {        
          return newTable;    
      }    
      for (int j = 0; j < oldCapacity; j++) {       
           /*         
           * Rehash the bucket using the minimum number of field writes.         
           * This is the most subtle and delicate code in the class.         
           */        
           HashMapEntry<K, V> e = oldTable[j];        
           if (e == null) {            
               continue;        
           }        
           int highBit = e.hash & oldCapacity;        
           HashMapEntry<K, V> broken = null;        
           newTable[j | highBit] = e;        
           for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {            
                int nextHighBit = n.hash & oldCapacity;            
                if (nextHighBit != highBit) {                
                    if (broken == null)                    
                        newTable[j | nextHighBit] = n;                
                    else                    
                        broken.next = n;                
                        broken = e;                
                        highBit = nextHighBit;            
                 }        
           }        
           if (broken != null)            
           broken.next = null;    
       }    
       return newTable;
  }

來自：http://www.jianshu.com/p/142aac8232e2