HashMap容器O(1)的查找時間複雜(zá)度隻是(shì)其理想的狀态，而這種理想狀态需要由java設計者去(qù)保證。

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

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

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

OK，下面我們來看看HashMap中新增元素的時間複雜(zá)度。

put操作的流程：

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

第二步：找到桶以後，判斷桶裏是(shì)否有元素，如果沒有，直接new一個entey節點插入到數組中。時間複雜(zá)度O(1)。

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

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

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

二，hash碰撞問題

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

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

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

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

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

如您有微信小程序開發、外賣、社區團購、分銷商城、分銷系統、量身定制開發、原生android定制、opencv人臉識别項目、網站建設等業務，可聯系閃端，專業團隊爲您排優解難！