HashMap容器O(1)的查找時間復雜度只是其理想的狀態(tài)，而這種理想狀態(tài)需要由java設計者去保證。

在由設計者保證了鏈表長度盡可能短的前提下，由于利用了數(shù)組結構，使得key的查找在O(1)時間內完成。

可以將 HashMap分成兩部分來看待，hash和map。map只是實現(xiàn)了鍵值對的存儲。而其整個O(1)的查找復雜度很大程度上是由hash來保證的。

HashMap對hash的使用體現(xiàn)出一些設計哲學，如：通過key.hashCode()將普通的object對象轉換為int值，從而可以將其視為數(shù)組下標，利用數(shù)組O(1)的查找性能。

OK，下面我們來看看HashMap中新增元素的時間復雜度。

put操作的流程：

第一步：key.hashcode()，時間復雜度O(1)。

第二步：找到桶以后，判斷桶里是否有元素，如果沒有，直接new一個entey節(jié)點插入到數(shù)組中。時間復雜度O(1)。

第三步：如果桶里有元素，并且元素個數(shù)小于6，則調用equals方法，比較是否存在相同名字的key，不存在則new一個entry插入都鏈表尾部。時間復雜度O(1)+O(n)=O(n)。

第四步：如果桶里有元素，并且元素個數(shù)大于6，則調用equals方法，比較是否存在相同名字的key，不存在則new一個entry插入都鏈表尾部。時間復雜度O(1)+O(logn)=O(logn)。紅黑樹查詢的時間復雜度是logn。

通過上面的分析，我們可以得出結論，HashMap新增元素的時間復雜度是不固定的，可能的值有O(1)、O(logn)、O(n)。

二，hash碰撞問題

HashMap在put元素時，首先會計算key的hashcode，這時候不會去調用equals方法。為什么呢？因為equals方法的時間復雜度是O(n)。但是HashMap存在hash碰撞問題，最壞的情況下，所有的key都被分配到了同一個桶，這時map的put和get時間復雜度都是O(n)。

所以HashMap的設計者必須要考慮的一個問題就是減少hash碰撞。

HashMap解決哈希沖突采用的是哪種方式呢？

答：HashMap解決哈希沖突采用的是鏈地址法。說白了就是把沖突的key連接起來，放到桶里。當桶中的元素個數(shù)不超過6個時，以單鏈表的形式串起來，當桶中的元素個數(shù)超過6個時，以紅黑樹的形式串起來。

通過上面的分析，我們可以得出結論，HashMap的hash操作的時間復雜度是O(1)，HashMap的equals操作的時間復雜度是O(n)。