數(shù)據(jù)結(jié)構(gòu)中有數(shù)組和鏈表來(lái)實(shí)現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)，但是數(shù)組存儲(chǔ)區(qū)間是連續(xù)的，尋址容易，插入和刪除困難；而鏈表的空間是離散的，因此尋址困難，插入和刪除容易。
因此，綜合了二者的優(yōu)勢(shì)，我們可以設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)——哈希表（hash table），它尋址、插入和刪除都很方便。在java中，哈希表的實(shí)現(xiàn)主要就是HashMap了，可以說(shuō)HashMap是java開(kāi)發(fā)中使用最多的類之一吧。
HashMap的底層其實(shí)就是鏈表的數(shù)組，代碼為
transient Entry[] table;
這里的table其實(shí)就是一個(gè)鏈表的數(shù)組，因?yàn)槲覀兊臄?shù)據(jù)是二元的，因此HashMap定義了一個(gè)內(nèi)部的類Entry，它包含了key和value兩個(gè)屬性。這樣一個(gè)一維的線性數(shù)組就可以存儲(chǔ)兩個(gè)值了。同時(shí)Entry是一個(gè)鏈表，因此還有一個(gè)Entry next屬性，它指向了下一個(gè)節(jié)點(diǎn)。
存儲(chǔ)put時(shí)：
首先計(jì)算出key的hash,然后用table[hash]得到那個(gè)鏈表，再遍歷這個(gè)鏈表，如果鏈表中有一個(gè)key和這個(gè)key是滿足equals的話，則將value替換掉；如果沒(méi)有的話，則插入到鏈表的尾部。
int h = hash(key); Entry e = table[h];
延伸閱讀
學(xué)習(xí)是年輕人改變自己的最好方式