1.了解哈希表
線上性表、樹等資料結構中，存儲元素的位置是随機的，和元素本身不存在确定的關系，是以在查找元素時，需要進行比較，在這種比較的查找機制中，結果有大于、等于和小于，查找效率依賴于過程中比較的次數。
在理想的情況下不需要進行比較，一次存取便能得到所查元素。是以，需要在元素和元素存儲位置之間建立一個确定的對應關系F，使得對于每一個元素K，有相應的存儲位置F（K）對應，稱這個對應關系F為哈希函數。
設定哈希函數Hash(Key)和處理沖突的方法将一組元素映像到一個連續的位址空間，以Hash(Key)作為Key在表中的存儲位置，這種表是哈希表，這一過為哈希構造表或散列，所得存儲位置為哈希位址或散列位址。
要點：
- 哈希函數的構造靈活，隻要元素的哈希值在表長的範圍内即可。
- 對不同元素得到同一哈希值，這種現象為沖突，沖突隻能減少，不能完全避免。
2.哈希函數的構造方法
若對于元素映像到位址空間中的任意位址的機率是相等的，則稱均勻的哈希函數。
直接定值法
取元素本身或元素的線性函數值為哈希位址：
Hash(key)=key
Hash(key)=a*key+b
其中a,b為常數。
數字分析法
取關鍵字的若幹位數組成哈希位址，盡量選擇随機數。
平方取中法
取元素平方後的中間幾位作為哈希值，比較常用。
除留餘數法
取元素被不大于哈希表表長m的數p除後所得的餘數作為哈希位址：
Hash（key)=key MOD p (p<=m)
一般情況下可選擇p為素數。
折疊法
将元素分解成位數相同的幾部分（最後一部分可以不同），然後取這幾部分的疊加和（舍去進位）作為哈希位址。當元素位數較多，而且每一位上數字分布大緻均勻時，可以使用折疊法。
随機數法
選擇一個随機函數，取元素的随機函數值作為哈希位址，即Hash(key)=random(key)。當關鍵字長度不等時，可采用此法構造哈希函數。
3.處理沖突的方法
沖突是指目前元素計算的哈希位址的位置上已經存有記錄，而“處理沖突”就是為該元素找到另一個空的哈希位址。
開放定址法
=( H(key) +
) MOD m
其中：
（1）
=1,2,3,...,m-1 【線性探測再散列】
（2）
=
,
,
,
,...,
( k<=m/2) 【二次探測再散列】
鍊位址法
将所有元素的同義詞的記錄存儲在同一線性連結清單中。假設哈希函數産生的哈希位址空間為[0,m-1],設定一個存儲連結清單的數組，即
T Chain[m]
每個分量的初始狀态為空，哈希位址為 i 的元素插入到Chain[ i ]連結清單中。
建立一個公共溢出區
若哈希函數的值域為[0,m-1]，建立一個基本表HashTable[0...m-1],每個分量存放一個記錄，再建立一個溢出表OverFlowTable[n],若是同義詞的記錄，一旦發生沖突，将其填入溢出表。