p19 散列表結(jié)構(gòu)

?散列表即 HashTable 類，也叫 HashMap 類，是 Dictionary 類的一種散列實現(xiàn)方式。

散列算法的作用是盡可能的在數(shù)據(jù)結(jié)構(gòu)中找到一個值。在以前的系列中，如果要在數(shù)據(jù)

結(jié)構(gòu)中獲取一個值，需要遍歷整個數(shù)據(jù)結(jié)構(gòu)來找到它。如果使用散列函數(shù)，就知道值的

具體位置，因此能夠快速檢索到該值。散列函數(shù)的作用是給定一個鍵值，然后返回值在

表中的位置。有時候一些鍵會有相同的鍵值。不同的的值在散列表中對應(yīng)相同位置的時

候，我們稱其為沖突。此時，當我們通過相同的散列值去取屬性值的時候會出現(xiàn)相互覆

蓋、數(shù)據(jù)丟失的情況。處理沖突有幾種方法：分離鏈接，線性探查和雙散列法，這里說

下分離鏈接法。在鏈接法中，把散列到同一個槽的元素都放在一個鏈表中，該槽中存放

鏈表的頭指針，如果不存在這樣的鏈表，則該槽為NULL。槽中的鏈表既可以是單鏈表，

也可以是雙鏈表。