?設(shè)想一下，你有一個包含約一千條記錄的數(shù)據(jù)文件,比如一個小企業(yè)的客戶記錄,還有一個程序，它把記錄讀到內(nèi)存中進行處理。每個記錄包含一個唯一的五位數(shù)的客戶ID號、客戶名字、地址、帳戶結(jié)余等等。假設(shè)記錄不是按客戶ID號順序分類的，所以，如果程序要將客戶ID號作為“key”?來查找一個特殊的客戶記錄，唯一的查找方法就是連續(xù)地搜索每個記錄。有時侯，它會很快找到你需要的記錄；但有時侯，在程序找到你需要的記錄前，它幾乎已搜索到了最后一條記錄。如果要在1,000條記錄中搜索，那么查找任何一條記錄都需要程序平均查核500.5?((1000?+?1?)/2)條記錄。如果你常需要查找數(shù)據(jù)，你應(yīng)該需要一個更快的方法來找到一條記錄。

????????一種加快搜索的方法就是把記錄分成幾段，這樣，你就不用搜索一個很大的列表了，而是搜索幾個短的列表。對于我們數(shù)字式的客戶ID號，你可以建10個列表,以0開頭的ID號組成一個列表，以1開頭的ID號組成一個列表，依此類推。那么要查找客戶ID號38016，你只需要搜索以3開頭的列表就行了。如果有1,000條記錄，每個列表的平均長度為100（1,000條記錄被分成10個列表），那么搜索一條記錄的平均比較次數(shù)就降到了約50。?
當然，如果約十分之一的客戶號是以0開頭的，另外十分之一是以1開頭的，等等，那么這種方法會很適合。如果90%的客戶號以0開頭，那么那個列表就會有900條記錄，每次查找平均需要進行450次比較。另外，程序需要執(zhí)行的搜索有90%都是針對以0開頭的號碼的。因此，平均比較數(shù)就大大超過簡單數(shù)學(xué)運算的范圍了。?
???如果我們可以按這樣一種方式在我們的列表中分配記錄，情況就會好一些，即每個列表約有相同條目的記錄，而不管鍵值中數(shù)字的分布。我們需要一種方法能夠把客戶號碼混合到一起并更好地分布結(jié)果。例如，我們可以取號碼中的每位數(shù)，乘以某個大的數(shù)（隨著數(shù)字位置的不同而不同），?然后將結(jié)果相加產(chǎn)生一個總數(shù)，把這個數(shù)除以10，并將余數(shù)作為索引值（index）(除數(shù)相同的分到一組)。當讀入記錄時，程序在客戶號碼上運行這個哈希（hash)?函數(shù)來確定記錄屬于哪個列表。當用戶需要查詢時，將同一個哈希函數(shù)作為一個“key”用于客戶號碼，這樣就可以搜索正確的列表了。?像這樣的一個數(shù)據(jù)結(jié)構(gòu)就稱為一個哈希表（hashtable)。?

總結(jié)

以上是生活随笔為你收集整理的哈希表原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。