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

在由設計者保證了(le)鏈表長(cháng)度盡可(kě)能短的(de)前提下(xià)，由于利用(yòng)了(le)數組結構，使得(de)key的(de)查找在O(1)時(shí)間内完成。

可(kě)以将 HashMap分(fēn)成兩部分(fēn)來(lái)看待，hash和(hé)map。map隻是實現了(le)鍵值對(duì)的(de)存儲。而其整個(gè)O(1)的(de)查找複雜(zá)度很大(dà)程度上是由hash來(lái)保證的(de)。

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

OK，下(xià)面我們來(lái)看看HashMap中新增元素的(de)時(shí)間複雜(zá)度。

put操作的(de)流程：

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

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

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

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

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

二，hash碰撞問題

HashMap在put元素時(shí)，首先會計算(suàn)key的(de)hashcode，這(zhè)時(shí)候不會去調用(yòng)equals方法。爲什(shén)麽呢(ne)？因爲equals方法的(de)時(shí)間複雜(zá)度是O(n)。但是HashMap存在hash碰撞問題，最壞的(de)情況下(xià)，所有的(de)key都被分(fēn)配到了(le)同一個(gè)桶，這(zhè)時(shí)map的(de)put和(hé)get時(shí)間複雜(zá)度都是O(n)。

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

HashMap解決哈希沖突采用(yòng)的(de)是哪種方式呢(ne)？

答(dá)：HashMap解決哈希沖突采用(yòng)的(de)是鏈地址法。說白了(le)就是把沖突的(de)key連接起來(lái)，放到桶裏。當桶中的(de)元素個(gè)數不超過6個(gè)時(shí)，以單鏈表的(de)形式串起來(lái)，當桶中的(de)元素個(gè)數超過6個(gè)時(shí)，以紅黑(hēi)樹的(de)形式串起來(lái)。

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

如您有微信小程序開發、外賣、社區(qū)團購(gòu)、分(fēn)銷商城(chéng)、分(fēn)銷系統、量身定制開發、原生android定制、opencv人(rén)臉識别項目、網站建設等業務，可(kě)聯系閃端，專業團隊爲您排優解難！