背景：之前介紹了《軟考路之線性表》，在順序表和樹表中查找資料元素要進行一系列的鍵值比較過程。為了使資料元素的存儲位置和鍵值之間建立某種聯系，以減少比較次數，現在介紹用散清單技術實作動态查找表。
一、散清單
資料元素的鍵值和存儲位置之間建立的對應關系H稱為散列函數，用鍵值通過散列函數擷取存儲位置的這種存儲方式構造的存儲結構稱為散清單（Hash Table），這一映射過程稱為散列。
如果標明了某種散列函數H及相應的散清單L，則對每個資料元素X，函數值H（X.key）就是X在散清單L中的存儲位置，這個存儲位置也稱為散列位址。
散列檔案是一種計算尋址檔案。
二、常用散列法
1、數字分析法
又稱為數字選擇法，其方法是收集所有可能出現的鍵值，排列在一起，對鍵值的每一位進行分析，選擇分布較均勻的若幹位組成散列位址。
所取的位數取決與散清單的表長，見表長為100，則取2位即可。
假定已知可能出現的所有鍵值如下：
對所有的鍵值分析不能看出，左起前三位都是“7 1 2”，第五位隻能取1、4，第七位隻能取6、7、8、，故這五位都不可取。剩下的第4、6、8、9位都是分布比較均勻的，可考慮将它們或它們中的幾位組織起來作為散列位址。
2、除數餘數法
是一種簡單有效且常用的構造方法，其方法是選擇一個不大于散清單長n的正整數p,以鍵值除以p所得的餘數作為散列位址，即
H（key）=key mod p (p<=n)
mod是取餘數運算，在C語言中，這一運算符是“%”。值得注意的是這一方法的關鍵在于p的選取。
如果選p為偶數，則所得的散列函數總是将奇數鍵值映射成奇數位址，偶數鍵值映射為偶數位址，因而增加了沖突的機會。通常選p為小于散清單長度n的素數。
3、平均取中法
以鍵值平方的中間幾位作為散列位址。
通常在標明散列函數時不一定能知道鍵值的分布情況。取其中哪幾位也不一定合适，而一個數平方的中間幾位與這個數的每一位都有關，所得散列位址比較均勻。
4、基數轉換法
将鍵值看成另一種進制的數再轉換成原來進制的數，然後選其中幾位作為散列位址。例：
對于十進制鍵值443730，先把它看成是十三進制的數再轉換為十進制數：
然後，根據散清單的長度從中選取幾位作為散列位址。
三、散清單的實作
1、線性探測法
對于任何鍵值key，設H（key）= d ，設散清單的容量為m ，則線性探測法生成的後繼散列位址序列為：
d+1,d+2,d+3,...,m-1,0,1,...,d-1
例：表長為13，其散列函數為H（key）= key mod 13,在下列的散清單中插入29
從上面可以看出，用線性探測法生成後繼散列位址計算簡單，但由于探測的是一個連續的位址序列，這也引出新的問題。表中30和29本來不是同義詞，但是發生了沖突，這種非同義詞之間對同一個散列位址的争奪現象稱為“堆積”。為了減少堆積的機會，應設法使後繼散列位址盡量均勻地分散在整個散清單中。
2、二分探測法
基本思想：生成的後繼散列位址不是連續的，而是跳躍的，以便為後繼資料元素留下空間進而減少堆積。
鍵值為key的散列位址序列為：
d(0)=H(key)
d(i)=(d(0)+i) mod m
m為散清單的表長，i=1^2,-1^2,2^2,-2^2,...±k^2(k≤m/2)
二次探測法的缺點是不易探測到整個散清單的所有空間，也就是說，上述後繼散列位址可能難以包括散清單的所有存儲位置。
3、鍊位址法
是對每一個同義詞都建一個單連結清單來解決沖突。
設標明的散列函數為H，H的值域（即散列位址的範圍）為0~（n-1）。設定一個指針向量“Pointer HP[n]”,其中的每個指針HP[i]指向一個單連結清單，該單連結清單用于存儲所有散列位址為i的資料元素。
每一個這樣的單連結清單稱為一個同義詞子表。例：
4、多重散列法
此法要求設立多個散列函數H（i）,i=1,...,k。當給定值key與散清單中的某個鍵值是相對于某個散列函數H（i）的同義詞而發生沖突時，繼續計算這個給定值key在下一個散列函數H（i+1）下的散列位址，直到不再産生沖突為止。
這種方法的優點時不易産生“堆積”，缺點是計算量較大。
5、公共溢出區法
按照這種方法，散清單由兩個一維數組組成。一個稱為基本表，它實際上就是上面所說的散清單，另一個稱為溢出表。插入首先在基本表上進行，假如發生沖突，則将同義詞存入溢出表，這樣，基本表不可能發生“堆積”。
四、學習心得
本來很簡單的東西，自己從心裡恐懼，就會造成知識沒學到，心情變得糟糕，為了考試不得不再次複習此處的内容，再次感到很難，恐懼.....于是乎，掉入了惡性循環中，不可自拔。
每每遇到一個新的事物。首先我們做的就是從心裡面認為它很簡單，這樣，讓自己有了信心，才有動力去解決它，自此，一位“學霸”就誕生了，學什麼會什麼，會什麼精通什麼，心情變好了，人自然就變漂亮了，變帥了，嘿嘿......
自信，是每個人不可缺少的東西。是成功的第一秘訣。