一直以來似乎都有一個錯覺，認為map跟其他的集合類一樣繼承自Collection，其實不然，Map和Collection在結構層次上是沒有任何關系的，通過查看源碼可以發現map所有操作都是基於key-value對，而不是單獨的元素。
下面以HashMap為例子，深入對Map的實現機制進行瞭解，在這個過程中，請打開jdk源碼。
Hash算法
HashMap使用Hash算法，所以在解剖HashMap之間，需要先簡單的瞭解Hash算法，Hash算法一般也成為散列算法，通過散列算法將任意的值轉化成固定的長度輸出，該輸出就是散列值，這是一種壓縮映射，也就是，散列值的空間遠遠小於輸入的值空間。
簡單的說，hash算法的意義在於提供瞭一種快速存取數據的方法,它用一種算法建立鍵值與真實值之間的對應關系,(每一個真實值隻能有一個鍵值,但是一個鍵值可以對應多個真實值),這樣可以快速在數組等裡面存取數據。
下面我們建立一個HashMap,然後往裡面放入12對key-value，這個HashMap的默認數組長度為16，我們的key分別存放在該數組的格子中，每個格子下面存放的元素又是以鏈表的方式存放元素。
public static void main(String[] args) { Map map = new HashMap(); map.put( ” What ” , ” chenyz ” ); map.put( ” You ” , ” chenyz ” ); map.put( ” Dont ” , ” chenyz ” ); map.put( ” Know ” , ” chenyz ” ); map.put( ” About ” , ” chenyz ” ); map.put( ” Geo ” , ” chenyz ” ); map.put( ” APIs ” , ” chenyz ” ); map.put( ” Cant ” , ” chenyz ” ); map.put( ” Hurt ” , ” chenyz ” ); map.put( ” you ” , ” chenyz ” ); map.put( ” google ” , ” chenyz ” ); map.put( ” map ” , ” chenyz ” ); map.put( ” hello ” , ” chenyz ” ); } 當我們新添加一個元素時，首先我們通過Hash算法計算出這個元素的Hash值的hashcode，通過這個hashcode的值，我們就可以計算出這個新元素應該存放在這個hash表的哪個格子裡面，如果這個格子中已經存在元素，那麼就把新的元素加入到已經存在格子元素的鏈表中。
運行上面的程序，我們對HashMap源碼進行一點修改，打印出每個key對象的hash值
What–>hash值：8
You–>hash值：3
Dont–>hash值：7
Know–>hash值：13
About–>hash值：11
Geo–>hash值：12
APIs–>hash值：1
Cant–>hash值：7
Hurt–>hash值：1
you–>hash值：10
google–>hash值：3
map–>hash值：8
hello–>hash值：0
計算出來的Hash值分別代表該key應該存放在Hash表中對應數字的格子中，如果該格子已經有元素存在，那麼該key就以鏈表的方式依次放入格子中
從上表可以看出，Hash表是線性表和鏈表的綜合所得，根據數據結構的定義，可以得出粗劣的結論，Hash算法的存取速度要比數組差一些，但是比起單純的鏈表，在查找和存取方面卻要好多。
如果要查找一個元素時，同樣的方式，通過Hash函數計算出這個元素的Hash值hashcode，然後通過這個hashcode值，直接找到跟這個hash值相對應的線性格子，進如該格子後，對這個格子存放的鏈表元素逐個進行比較，直到找到對應的hash值。
在簡單瞭解完Hash算法後，我們打開HashMap源碼
初始化HashMap
下面我們看看Map map = new HashMap();這段代碼究竟做瞭什麼，發生瞭什麼數據結構的變化。
HashMap中幾個重要的屬性
transient Entry[] table;
用來保存key-value的對象Entry數組，也就是Hash表
transient int size;
返回HashMap的鍵值對個數
final float loadFactor;
負載因子，用來決定Entry數組是否擴容的因子，HashMap默認是0.75f
int threshold;
重構因子，(capacity * load factor)負載因子與Entry[]數組容積的乘值
public class HashMap < K,V > extends AbstractMap < K,V > implements Map < K,V > , Cloneable, Serializable { int threshold; final float loadFactor; transient Entry[] table; static final float DEFAULT_LOAD_FACTOR = 0.75f ; static final int DEFAULT_INITIAL_CAPACITY = 16 ; 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(); } 以public HashMap(int initialCapacity, float loadFactor)構造函數為例，另外兩個構造函數實際上也是以同種方式來構建HashMap.
首先是要確定hashMap的初始化的長度，這裡使用的策略是循環查出一個大於initialCapacity的2的次方的數，例如 initialCapacity的值是10，那麼大於10的數是2的4次方，也就是16
capacity的值被賦予瞭16，那麼實際上table數組的長度是16，之所以采用這樣的策略來構建Hash表的長度，是因為2的次方運算對於計算機來說是有相當的效率。
loadFactor，