在java8發布以前，HashMap的實現簡單來說就是一個Node數組，通過hash算法盡可能的分散了元素的位置，當一個位置有超過一個元素時，用鏈表的形式將元素進行連接。在java8中HashMap的實現形式有了一些改動，其中比較重要的一點就是鏈表的阈值，當鏈表的長度大於等於7時，會將這個位置的鏈表轉換為紅黑樹的形式，如下圖。
在來說說hash算法，HashMap中使用的算法如下
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這個hash先將key右移了16位，然後與key進行異或，這裡還涉及到後面put方法中的另一次&操作，
tab[i = (n - 1) & hash]
tab既是table，n是map集合的容量大小，hash是上面方法的返回值。因為通常聲明map集合時不會指定大小，或者初始化的時候就創建一個容量很大的map對象，所以這個通過容量大小與key值進行hash的算法在開始的時候只會對低位進行計算，雖然容量的2進制高位一開始都是0，但是key的2進制高位通常是有值的，因此先在hash方法中將key的hashCode右移16位在與自身異或，使得高位也可以參與hash，更大程度上減少了碰撞率。
