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