java.util.HashMap源碼分析

我剛開始找工作的時候，刷面試題磕谅，刷到最多的锅减，同時確實也是面試官最喜歡的考察的一個知識點就是什么是HashMap扫尖，或者與Hashtable的區(qū)別等一系列相關(guān)的面試題。然而事實上這道題更多的還是考察對HashMap這個數(shù)據(jù)結(jié)構(gòu)的知識點禀综，那這個數(shù)據(jù)結(jié)構(gòu)就是hash table简烘。hash table是一個非常重要的數(shù)據(jù)結(jié)構(gòu)苔严，在日常coding中我們也會經(jīng)常使用這樣的數(shù)據(jù)結(jié)構(gòu)，java中有HashMap孤澎，python中有字典届氢，都是通過hash table實現(xiàn)的，所以學(xué)習(xí)hash table很重要亥至。

本篇主要從什么是hash table悼沈？如何實現(xiàn)一個工業(yè)級別的hashtable？以及hashtable的應(yīng)用場景等方面討論姐扮。

什么是hash table絮供？

Hash table是通過一個hash函數(shù)來計算數(shù)據(jù)存儲位置的數(shù)據(jù)結(jié)構(gòu)，是一個鍵值對類型的數(shù)據(jù)結(jié)構(gòu)茶敏，(key, value)壤靶。通常支持如下操作：

• put(Key Value)： 插入鍵值對(key,value)
• get(key):如果存在鍵為key的鍵值對則返回其value，否則返回空值惊搏。
• delete(key):刪除鍵為key的鍵值對贮乳。

hash table屬于線性表，由一個直接尋址表和一個hash函數(shù)組成恬惯。hash函數(shù)hash(key)將key做為自變量向拆，返回元素的存儲下標(biāo)，也就是直接尋址表的下標(biāo)酪耳。

我們回過頭來浓恳，回想一下動態(tài)數(shù)組（列表）的插入，一般情況下咱都是直接調(diào)用list.add(value)方法實現(xiàn)的碗暗，所以都是追加到末尾的一種方式颈将，那如果我們把key按照列表的方式插入，那就是直接插入到末尾言疗，如果我們想要獲取key晴圾，那也要從頭開始遍歷一遍，一個個key值比較噪奄，時間復(fù)雜度是O(n)死姚，即使這個key是數(shù)字，也插入的時候是有序插入的勤篮，使用二分查找算法都毒，也需要O(logn)的時間復(fù)雜度。那有沒有辦法再進一步優(yōu)化get(key)的時間復(fù)雜度呢叙谨？

1. 直接尋址表

   當(dāng)關(guān)鍵字的全域u比較小時温鸽，直接尋址時一種簡單而有效的方法。

hash-table-直接尋址表.png

假設(shè)u的域為[0,9]，那我們就建立一個長度為10的數(shù)組T涤垫。此時我們需要插入的key有(2,3,5,8)姑尺，那我們就直接在下標(biāo)為2，3蝠猬，5切蟋，8里插入對應(yīng)的key值即可。如果想獲取key = 5的元素榆芦，只要返回T(5)的值即可柄粹，如果想要刪除key = 8的元素，只要將T(8)置為空即可匆绣。

直接尋址表的優(yōu)點：

實際上數(shù)組的優(yōu)點就是直接尋址表的優(yōu)點（其實也是hash table的優(yōu)點）驻右。

• 根據(jù)key查找的時間復(fù)雜度為O(1)

缺點：

• 當(dāng)U很大的時候，需要消耗大量的內(nèi)存崎淳，很不實際堪夭。如果u的是一個[0, 100W]的域，但是key卻只有很少的一部分拣凹，就會造成大量的空間被浪費森爽。
• 如果key不是數(shù)字，也不能使用直接尋址表嚣镜。直接尋址表就是當(dāng)key = k的時候爬迟，咱就直接把對應(yīng)的value放入T(k)。

2. 散列表

   直接尋址表是根據(jù)關(guān)鍵字k找到槽(k)菊匿，并存入對應(yīng)的對應(yīng)的值付呕。而散列表是根據(jù)關(guān)鍵字k通過一個hash函數(shù)(記為h(k))計算出槽的位置。這里的函數(shù)h將關(guān)鍵字的全域u映射到散列表的槽位上捧请，那h(k)就是關(guān)鍵字k的散列值凡涩。

   假設(shè)u的域是[0,6]棒搜，一個長度為7的數(shù)組≌铗龋現(xiàn)需要插入的key有（2，14力麸，19可款，24）。hash(key) = key%7克蚂。這樣就是2對應(yīng)的位置就是下標(biāo)為2的位置闺鲸，14對應(yīng)的位置就是下標(biāo)為0的位置，19對應(yīng)的位置是下標(biāo)為5埃叭，24對應(yīng)的位置就是下標(biāo)為3的位置摸恍。

hash-table-散列表.png

3. Hash函數(shù)

   散列表中關(guān)鍵的第一步就是根據(jù)hash函數(shù)，找出對應(yīng)的槽位，那如何設(shè)計一個hash函數(shù)呢立镶？本小節(jié)主要討論就是如何設(shè)計一個hash函數(shù)壁袄。

   根據(jù)維基百科的定義：散列函數(shù)（英語：Hash function）又稱散列算法、哈希函數(shù)媚媒，是一種從任何一種數(shù)據(jù)中創(chuàng)建小的數(shù)字“指紋”的方法嗜逻。散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小缭召，將數(shù)據(jù)的格式固定下來栈顷。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個叫做散列值（hash values嵌巷，hash codes萄凤，hash sums，或hashes）的指紋搪哪。散列值通常用一個短的隨機字母和數(shù)字組成的字符串來代表蛙卤。那對于hash table來說，我們需要通過hash函數(shù)找到對應(yīng)的槽位噩死，所以這里的hash函數(shù)需要返回的散列值是一個自然數(shù)颤难，即假設(shè)hash table的全域是一個自然數(shù)集（0，1已维，2行嗤，3，4垛耳，栅屏。。堂鲜。栈雳。）

   設(shè)計hash函數(shù)的三個基本要求：

   1. 散列函數(shù)計算出來的散列值是一個自然數(shù)。
   2. 如果key1 == key2,則hash(key1) == hash(key2)缔莲。
   3. 如果key1 != key2,則hash(key1) != hash(key2)哥纫。

   分享幾種常見的hash函數(shù)設(shè)計方法：

   1. 取模：h(k) = k mod m，比如上述案例就是通過取模散列痴奏，h(k) = k % 7蛀骇。我們在選取m的值的時候需要注意盡量不要選擇2或者靠近2的整數(shù)冪的素數(shù)。比如我們需要存儲大約2000個字符串读拆，散列函數(shù)可以設(shè)置為h(k) = k % 701擅憔。
   2. 乘法hash法：h(k) = floor(m*(A*key%1))。用關(guān)鍵字k乘上常數(shù)A(0<A<1),并提取kA的小數(shù)部分檐晕，第二步暑诸，用m*這個值，再向下取整。
   3. 全域hash法：h(k) = ((a * key + b) mod p) mod m a,b = 1,2,....,p-1

4. Hash沖突

   我們知道hash table都有一個全域u个榕，這個全域可以看成是一個數(shù)組啦逆，數(shù)組的存儲空間是有限的，然而我們需要存儲的內(nèi)容卻是無限的笛洛。那這樣就有可能會發(fā)生這樣的情況夏志，就是兩個(多個)相同的key可能會被映射到同一個槽里，這種情形我們稱之為hash沖突苛让。在討論hash函數(shù)的設(shè)計三要素的時候沟蔑，第三點確實是很難完全保證，但是我們需要盡量保證狱杰，然而hash沖突確實無法完全避免瘦材，現(xiàn)業(yè)界里也是有方案去解決hash沖突的問題。

   解決方案：

   • 開放尋址法：如果hash函數(shù)返回的位置上已經(jīng)有值仿畸，則可以向后探查新的位置來存儲這個值食棕。

     • 線性探查：如果位置i被占用，則探查i+1, i+2, ......错沽，如果發(fā)現(xiàn)到數(shù)組的最后一位還沒找到可以存儲的位置簿晓，就從下標(biāo)為0的位置上，繼續(xù)尋找千埃，直到找到為止憔儿。
     • 二次探查：如果位置i被占用，則探查i+1^2, i-1^2,i+2^2, i-2^2,....
     • 二度hash：有n個hash函數(shù)放可，當(dāng)使用第一個hash函數(shù)發(fā)生沖突時谒臼，則嘗試使用第二個hash。

     不管采用哪種探測方法耀里，當(dāng)散列表中空閑位置不多的時候蜈缤，散列沖突的概率就會大大提高。為了盡可能保證散列表的操作效率冯挎，一般情況下底哥，我們會盡可能保證散列表中有一定比例的空閑槽位。我們用裝載因子來表示空位的多少织堂。

     裝載因子的計算公式是：

     loadFactor = 填入表中的元素個數(shù) / 散列表的長度

     裝載因子越大叠艳，說明散列表中的元素越多奶陈，空閑位置越少易阳，散列沖突的概率就越大。不僅插入數(shù)據(jù)的過程要多次尋址或者拉很長的鏈表吃粒，查找的過程也會因此變得很慢潦俺。

     優(yōu)點：

     1. 不需要像鏈表法一樣，需要拉很多鏈表。
     2. 散列表中的數(shù)據(jù)都存儲在數(shù)組中事示，可以有效地利用cpu緩存加快查詢速度早像。
     3. 序列化簡單

     缺點：

     1. 刪除數(shù)據(jù)的時候比較麻煩，需要特殊標(biāo)記已經(jīng)刪除的數(shù)據(jù)
     2. 比起拉鏈法更浪費內(nèi)存空間肖爵，沖突的代價更高卢鹦，裝載因子的上限不能太大。

     當(dāng)數(shù)據(jù)量比較小劝堪，裝載因子小的時候冀自，適合采用開放尋址法。

   • 拉鏈法：在散列表中秒啦，每個槽會對應(yīng)一條鏈表熬粗，所有散列值相同的元素我們都放到相同槽位對應(yīng)的鏈表中。當(dāng)插入的時候余境，我們只需要通過散列函數(shù)計算出對應(yīng)的散列槽位驻呐，將其插入到對應(yīng)鏈表中即可，所以插入的時間復(fù)雜度是o(1)芳来。當(dāng)查找含末，刪除一個元素的時候，我們同樣通過散列函數(shù)計算出對應(yīng)的槽即舌，然后遍歷鏈表查找或者刪除答渔，時間復(fù)雜度與鏈表的長度k成正比，也就是o(K)侥涵。

     基于鏈表的散列沖突處理方法比較適合存儲大對象沼撕，大數(shù)據(jù)量的散列表，靈活芜飘，支持更多的優(yōu)化策略务豺，比如使用紅黑樹，跳表等數(shù)據(jù)結(jié)構(gòu)替換鏈表嗦明。

如何實現(xiàn)一個hashtable笼沥？

針對散列表，當(dāng)裝載因子過大時娶牌，我們也可以進行動態(tài)擴容奔浅，重新申請一個更大的散列表，將數(shù)據(jù)搬移到這個新散列表中诗良。每次擴容我們都申請一個原來散列表大小兩倍的空間汹桦。如果原來散列表的裝載因子時0.8，經(jīng)過擴容以后就是0.4鉴裹。擴容的時候需要注意舞骆，因為散列表的大小變了钥弯，數(shù)據(jù)的存儲位置也變了，所以我們需要通過散列函數(shù)重新計算每個數(shù)據(jù)的存儲位置督禽。

我們首先來分析一下java.util.HashMap的代碼實現(xiàn)脆霎。

1. 初始化大小：HashMap的默認初始大小時16，也可以自己設(shè)置初始大小狈惫，如果事先知道大概的數(shù)據(jù)量大小睛蛛，可以通過修改初始大小，減少動態(tài)擴容的次數(shù)胧谈，這樣會大大提高HashMap的性能玖院。

2. 裝載因子和動態(tài)擴容：裝載因子默認是0.75，當(dāng)HashMap中元素個數(shù)超過0.75*capacity(capacity表示散列表的容量)的時候第岖，就會啟動擴容难菌，每次擴容都會擴容外原來的兩倍大小。

3. 鏈表法解決沖突：不管裝載因子和散列函數(shù)設(shè)計的再合理蔑滓，也免不了會出現(xiàn)鏈表過長的情況郊酒，一旦鏈表過長還是會影響性能。在jdk1.8引入紅黑樹，當(dāng)鏈表的長度默認超過8時，鏈表就會轉(zhuǎn)換為紅黑樹爪喘，當(dāng)紅黑樹的結(jié)點個數(shù)少于8時，會退化為鏈表褐健。

4. hash函數(shù)：

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

設(shè)計一個散列表需要具備哪些特性？

1. 支持快速地查詢澜汤，插入蚜迅，刪除操作；
2. 內(nèi)存占用合理俊抵，不能浪費過多的內(nèi)存空間谁不；
3. 性能穩(wěn)定，極端情況下徽诲，散列表的性能也不會退化到無法接受的情況刹帕。

如何實現(xiàn)？

1. 設(shè)計一個合理的hash函數(shù)谎替；
2. 定義裝載因子偷溺，并且設(shè)計動態(tài)擴容策略；
3. 選擇合適的散列沖突解決方法钱贯。

show me the code:仿java.util.HashMap

public interface Map<K, V> {

  V put(K k, V v);

  V get(K k);

  Entry[] entry();

  interface Entry<K, V>{
    K getKey();
    V getValue();

    Entry<K, V> next();
  }

}

public class HashMap<K, V> implements Map<K, V> {

  // 默認的初始化大小
  private static final int DEFAULT_CAPACITY = 1 << 4;

  // 默認的裝載因子
  private static final float DEFAULT_LOAD_FACTOR = 0.75f;

  private Node<K, V>[] table;

  // 實際元素大小
  private int size;

  private int use;

  private int capacity;

  private float loadFactor;

  public HashMap() {
    this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
  }

  public HashMap(int capacity, float loadFactor) {
    if (capacity < 0) {
      throw new IllegalArgumentException("Illegal capacity: " + capacity);
    }
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
      throw new IllegalArgumentException("Illegal loadFactor: " + loadFactor);
    }
    this.capacity = capacity;
    this.loadFactor = loadFactor;
    table = new Node[capacity];
  }

  @Override
  public V put(K k, V v) {
    V oldValue = null;
    // 判斷是否需要擴容?
    if (use >= capacity * loadFactor) {
      resize();
    }
    int index = hash(k);
    if (table[index] == null) { 
      table[index] = new Node<>(k, v, null);
    } else {
      Node<K, V> entry = table[index];
      Node<K, V> e = entry;
      while (e != null) {
        if (k == e.getKey() || k.equals(e.getKey())) {
          oldValue = e.value;
          e.value = v;
          return oldValue;
        }
        e = e.next;
      }
      table[index] = new Node<>(k, v, entry);
    }
    ++use;
    ++size;
    return oldValue;
  }

  private void resize() {
    capacity = capacity << 1;
    Node<K, V>[] newTable = new Node[capacity];
    use = 0;
    size = 0;
    rehash(newTable);
  }

  private void rehash(Node<K, V>[] newTable) {
    List<Node<K, V>> entryList = new ArrayList<Node<K, V>>();
    for (Node<K, V> entry : table) {
      if (entry != null) {
        do {
          entryList.add(entry);
          entry = entry.next;
        } while (entry != null);
      }
    }

    if (newTable.length > 0) {
      table = newTable;
    }

    for (Node<K, V> entry : entryList) {
      put(entry.getKey(), entry.getValue());
    }
  }

  @Override
  public V get(K k) {
    int index = hash(k);
    if (table[index] == null) {
      return null;
    } else {
      Entry<K, V> entry = table[index];
      do {
        if (k == entry.getKey() || k.equals(entry.getKey())) {
          return entry.getValue();
        }
        entry = entry.next();
      } while (entry != null);
    }
    return null;
  }

  @Override
  public Entry[] entry() {
    Node<K, V>[] tmp = new Node[size];
    int j = 0;
    for (int i = 0; i < capacity; i++) {
      if (table[i] != null) {
        tmp[j++] = table[i];
        if(j == size){
          break;
        }
      }
    }
    return tmp;
  }

  private static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  static class Node<K, V> implements Entry<K, V> {

    K key;

    V value;

    Node<K, V> next;

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

    @Override
    public K getKey() {
      return key;
    }

    @Override
    public V getValue() {
      return value;
    }

    @Override
    public Entry<K, V> next() {
      return next;
    }
  }
}

hashtable的應(yīng)用場景

1. 利用hashtable減少遍歷層數(shù)挫掏，提高算法的時間復(fù)雜度。例如leetcode第一題two sum喷舀。
2. hashtable可以做為cache或者存儲砍濒，hashtable + linkedlist可以實現(xiàn)LRU Cache淋肾。
3. 可以表示為弱對象硫麻。