HashMap的本質(zhì)依然是數(shù)組叼风，而且是一個(gè)不定長的多維數(shù)組。
1无宿、簡單介紹
HashMap中的數(shù)組保存鏈表的頭節(jié)點(diǎn)枢里。
保存數(shù)據(jù)：
計(jì)算key的hashCode，再與數(shù)組長度進(jìn)行求余運(yùn)算得到數(shù)組下標(biāo)(鏈表頭節(jié)點(diǎn))栏豺。
如果該位置為空，生成一個(gè)新的鏈表節(jié)點(diǎn)并保存到該數(shù)組巷疼。
如果該位置非空溉卓，循環(huán)比對鏈表的每一個(gè)節(jié)點(diǎn)：已經(jīng)存在key相同的節(jié)點(diǎn)搬泥，覆蓋舊節(jié)點(diǎn)；不存在key相同的節(jié)點(diǎn)忿檩，將新節(jié)點(diǎn)作為鏈表的尾節(jié)點(diǎn)（注：查看JDK1.8中的源碼爆阶，新節(jié)點(diǎn)總是加入到鏈表末尾燥透，而不是如JDK1.6一般作為鏈表頭節(jié)點(diǎn)）
查找數(shù)據(jù)：
計(jì)算key的hashCode辨图，再與數(shù)組長度進(jìn)行求余運(yùn)算得到數(shù)組下標(biāo)(鏈表頭節(jié)點(diǎn))。如果鏈表不為空吱韭，先比對首節(jié)點(diǎn)鱼的，如果首節(jié)點(diǎn)key相同（hashCode相同且equals為true）理盆，直接返回首節(jié)點(diǎn)的value凑阶；首節(jié)點(diǎn)key不同則順序遍歷比對鏈表其它節(jié)點(diǎn)，返回key相同的節(jié)點(diǎn)的value（未找到key相同的節(jié)點(diǎn)則返回null）姨俩。
注意事項(xiàng)：
如果所有key的hashcode相同师郑，假定均為0环葵，則0%4 = 0宝冕，所有元素就會(huì)都保存到鏈表0，保存和查找每一個(gè)數(shù)據(jù)都需要遍歷鏈表0。那么先誉，此時(shí)的HashMap實(shí)質(zhì)上已經(jīng)退化成了鏈表，時(shí)間復(fù)雜度也從設(shè)計(jì)的O(1)上升到了O(n/2)褐耳。
為了盡可能地讓HashMap的查找和保存的時(shí)間復(fù)雜度保持在O(1),就需要讓元素均勻地分布在每一個(gè)鏈表，也就是每一個(gè)鏈表只保存一個(gè)元素雅镊。
那么影響因素有哪些襟雷？
一是key的hashcode不能重復(fù)仁烹，如果重復(fù)就肯定會(huì)有鏈表保存至少2個(gè)元素；
二是哈希函數(shù)設(shè)計(jì)卓缰，如果只是簡單的求余，那么余數(shù)會(huì)有大量重復(fù)捌显；
三是鏈表的大小总寒，如果100個(gè)元素要分布在長度為10的數(shù)組扶歪，無論怎么計(jì)算都會(huì)導(dǎo)致其中有鏈表保存多個(gè)元素摄闸，最好的情況是每個(gè)鏈表保存10個(gè)；
