在使用數(shù)組的時(shí)候，下標(biāo)作為關(guān)鍵字為我們提供了操作的便捷性，此時(shí)關(guān)鍵字是連續(xù)的奈附。在需要統(tǒng)計(jì)一串?dāng)?shù)字中每個(gè)數(shù)字各出現(xiàn)多少次時(shí)筷弦，若數(shù)字取值范圍較小，可以這樣處理:
int a[11]; //數(shù)字取值范圍1~10
while(cin>>x)
a[x]++;
但如果取值范圍是1~100000或者更大呢域醇？在數(shù)字總數(shù)不大的情況下不必建立一個(gè)可以儲(chǔ)存1000000個(gè)整數(shù)的數(shù)組，而是將有限的關(guān)鍵字（數(shù)字）進(jìn)行散列的儲(chǔ)存：
map<int,int>m;
while(cin>>x)
m[x]++;
map把關(guān)鍵字和實(shí)際需要儲(chǔ)存的數(shù)據(jù)進(jìn)行映射譬挚，這樣需要的儲(chǔ)存空間就小得多。
散列方式
在直接尋址方式下减宣，具有關(guān)鍵字k的元素被存放在槽k中。在散列方式下漆腌，該元素在槽h(k)中。h是散列函數(shù)闷尿，它決定關(guān)鍵字k的槽的位置。但不同的關(guān)鍵字可以由散列函數(shù)分配到同一個(gè)槽中填具，造成沖突。解決辦法有：
鏈接法(chaining)把散列在同一個(gè)槽中的元素都放在一個(gè)鏈表中灌旧，散列表中保存這些鏈表的頭指針绰筛。
在進(jìn)行數(shù)據(jù)查找、增加铝噩、刪除等操作時(shí)時(shí)間復(fù)雜度只取決于鏈表長(zhǎng)度，因此若所有關(guān)鍵字都被分配至同一個(gè)槽中（最壞情況），時(shí)間復(fù)雜度為O(n)毛甲。但一般情況下操作只需O(1)。
開放尋址法(open addressing)將所有元素直接儲(chǔ)存在散列表中玻募。由于元素沒有和地址的映射關(guān)系，在操作者需要查找某元素時(shí)需要檢查整個(gè)散列表七咧。檢查的順序依賴于探查序列，它是散列函數(shù)的擴(kuò)充艾栋。
完全散列(perfect hashing)的查詢操作在對(duì)壞情況也能達(dá)到O(1)，十分適合靜態(tài)儲(chǔ)存蝗砾。它采用兩級(jí)散列，在最初的散列表中存放數(shù)個(gè)二次散列表悼粮，并且選用合適二次散列表空間防止沖突，選用合適的第一級(jí)散列函數(shù)使整體儲(chǔ)存空間不會(huì)過大扣猫。
散列函數(shù)
散列函數(shù)應(yīng)該使關(guān)鍵字的散列盡可能均勻，使散列值盡可能獨(dú)立于數(shù)據(jù)的模式苞笨。多數(shù)散列函數(shù)先將關(guān)鍵字都轉(zhuǎn)化為數(shù)字，再進(jìn)行散列瀑凝。
除法散列法 取關(guān)鍵字的余數(shù)作為結(jié)果，需要都除數(shù)進(jìn)行合理設(shè)計(jì)粤咪。
乘法散列法使關(guān)鍵字乘一個(gè)常數(shù)，取他們乘積的小數(shù)部分乘另一個(gè)常數(shù)寥枝，再向下取整。
全域散列法先設(shè)定一組散列函數(shù)囊拜，然后在處理關(guān)鍵字時(shí)隨機(jī)選用函數(shù)。無論關(guān)鍵字是怎樣的都能保證散列較平均冠跷。
