詳解HashMap數據結構實現

　　HashMap的設計是由數組加鏈表的符合數據結構，在這裡用自己的語言以及結合源碼去總結一下，如果有不對的地方希望評論指正，先拱手謝謝。

　　HashMap是日常中非常常用的一種數據結構，我們要想深入瞭解學習任何一門技術，都是要先應用，再深入。深入就要瞭解實現的原理，在java語言中，最基本的結構是數組以及類變數(引用),HashMap是兩者的結合，更明確的說，HashMap是數組以及鏈表的結合。

public class HashMap<K, V>
  extends AbstractMap<K, V>
  implements Map<K, V>, Cloneable, Serializable
{
  private static final long serialVersionUID = 362498820763181265L;
  static final int DEFAULT_INITIAL_CAPACITY = 16;
  static final int MAXIMUM_CAPACITY = 1073741824;
  static final float DEFAULT_LOAD_FACTOR = 0.75F;
  static final int TREEIFY_THRESHOLD = 8;
  static final int UNTREEIFY_THRESHOLD = 6;
  static final int MIN_TREEIFY_CAPACITY = 64;
  transient Node<K, V>[] table;
  transient Set<Map.Entry<K, V>> entrySet;
  transient int size;
  transient int modCount;
  int threshold;
  final float loadFactor;
...
}

　　我們可以看到HashMap維護了一個Node<K,V>數組，在這裡我們再看Node的實現

 static class Node<K, V>
    implements Map.Entry<K, V>
  {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
.....
}

Node維護了四個屬性，Key,Value,Hash碼,以及關鍵的：Node<K,V> next，每一個Node持有下一個Node，形成了鏈表。

　　在這裡奉上一張HashMap的導圖,當我們插入一個值時，即插入了一個Node，通過Node的key的hashcode與Node<K,V> table 數組的長度來計算出這個Node在數組中的位置，也就是下標。計算的方法就是hash演算法，當我們插入一個Node的時候，Key是唯一的，但是不同的key求出的hashcode