HashMap內(nèi)部實(shí)現(xiàn)原理
HashMap表面上是由key-value對(duì)組成的,key具有唯一性.
而HashMap在內(nèi)部實(shí)現(xiàn)時(shí)運(yùn)用了數(shù)組以及鏈表.
初始數(shù)組長(zhǎng)度為16.
[ 0 ]——>{k-v}->{k-v}->{k-v}
[ 1 ]——>{k-v}->{k-v}
[ 2 ]
[ 3 ]
[ 4 ]——>{k-v}
[ 5 ]
[ 6 ]——>{k-v}->{k-v}->{k-v}
[ 7 ]
[ 8 ]——>{k-v}->{k-v}
[ 9 ]
[ 10]
[ 11]——>{k-v}->{k-v}->{k-v}
[ 12]
[ 13]——>{k-v}
[ 14]
[ 15]——>{k-v}
其中,
數(shù)組[ ]叫做table.
{k-v}->{k-v}叫做鏈表.
{k-v}在鏈表中叫做Node,在Map中叫做Entry.
那么,如何將一個(gè)鍵值對(duì)加入這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)椿胯？
1.如果鍵為null,加入[0]號(hào)鏈表,如果鏈表中里有該鍵,覆蓋其value,否則直接加入鏈表.
2.如果鍵不為null,進(jìn)行hashcode(key),并將這個(gè)數(shù)與這個(gè)數(shù)無符號(hào)右移16位進(jìn)行異或(保證所有位參與運(yùn)算,更加離散)
3.將異或得到的數(shù)與0xF相與,得到4bit有效值,用來表示0～15.來確定鍵值對(duì)所加入的鏈表.
4.如果所加入的鏈表為空,直接加入鏈表,如果鏈表中有該鍵,覆蓋其value.
這樣即保證了散列性,又保證了鍵的唯一性豹缀。
