map 是個 key-value 的存儲結構，常用的實現(xiàn)有兩種砸逊，HashMap和TreeMap悉罕。
??HashMap 是通過hash方式實現(xiàn)的map赤屋，底層存儲在一個數(shù)組中立镶。hashmap在初始化時，默認會創(chuàng)建一個長度為16的數(shù)組类早。當我們調(diào)用put方法時（例如map.put(2,'hxl')）媚媒，hashmap會獲取key的hash值。將這個hash值與長度進行&操作莺奔，算出的值就是數(shù)據(jù)存在數(shù)組中的下標欣范。
??& 的性能比較高，在和數(shù)組的長度計算時令哟，要求數(shù)組的長度必須是 2^n 2 ，當初始化長度指定長度不是2^n 妨蛹，會將其進行一個轉換屏富。
??Hash碰撞。 如果兩個key算出的下標是同一位置蛙卤，那么就會出現(xiàn)hash碰撞狠半。在JDK8之前，hashmap采用了鏈表的方式解決碰撞問題颤难，也就是說新數(shù)據(jù)會作為一個鏈表的節(jié)點鏈接在前一個節(jié)點中神年。該方法會存在鏈表問題，時間復雜度為 O ( n ) O(n) O(n)行嗤，所以在JDK8之后就把鏈表改成了鏈表+紅黑樹已日。在碰撞數(shù)小于8時，采用的是鏈表栅屏。到8個時會轉換成紅黑樹飘千。另外map的數(shù)組小于64時，不會轉換成數(shù)栈雳，而是進行依次擴容护奈。
??當調(diào)用map的put方法時，hashmap是用equals方法判斷兩個key是否相等哥纫，相等則覆蓋霉旗。因為需要用hash算出key，所以當把對象作為key時蛀骇，需要重寫兩個方法厌秒，一個是equals方法，還有一個是重寫hashcode方法松靡。
??擴容 hashmap的底層是數(shù)組存儲简僧，會涉及到擴容的問題。hashmap計算新數(shù)組長度的方式就是用舊的長度向左移1位雕欺，也就是新數(shù)組是舊數(shù)組的2倍岛马。
??擴容時間 第一種：碰撞數(shù)大于等于8棉姐，且數(shù)組小于64。第二種：當 存儲的數(shù)據(jù)個數(shù) > 數(shù)組長度 ? 0.75 存儲的數(shù)據(jù)個數(shù) > 數(shù)組長度*0.75 存儲的數(shù)據(jù)個數(shù)>數(shù)組長度?0.75 這個0.75是默認的加載因子啦逆。在初始化hashmap的時候就可以進行指定伞矩。
??擴容的方式，就是把舊數(shù)組中的數(shù)據(jù)重新計算hash(rehash)夏志，然后放到新數(shù)組中乃坤，rehash是比較消耗性能的，所以我們要盡量減少rehash的出現(xiàn)沟蔑。
