Map用來存儲key-value鍵值對，是最常用的數(shù)據(jù)結(jié)構(gòu)之一。
HashMap
-
HashMap存儲數(shù)據(jù)時將要存入key的數(shù)據(jù)進行hash運算，大多數(shù)情況下可以快速定位應當放到哪里，因此HashMap的訪問速度是很快的，但是遍歷順序是不確定的，不能保證是放入時的順序。
在java7時的底層實現(xiàn)是數(shù)組+鏈表，如下圖所示：
- 當出現(xiàn)hash碰撞時，會在同一個位置使用鏈表鏈接。因此當鏈表長度較長時，查詢的時間復雜度是比較高的。HashMap在擴容時總是擴容至原來的兩倍，有一個核心參數(shù)叫負載因子0.75，這個是衡量在何時擴容的參數(shù)。擴容的閾值=容量*負載因子。
-
java8中底層實現(xiàn)上進行了優(yōu)化，如下圖所示：
和之前相比最大的不同在于底層實現(xiàn)上使用了數(shù)組+鏈表+紅黑樹；紅黑樹的引入當鏈表長度超過8時，會自動轉(zhuǎn)換為紅黑樹，這樣時間復雜度由O(N)降低為O(logN)。
