1 散清單查找定義
散列技術是在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系，使得每個關鍵字key對應一個存儲位置。
存儲位置=f(關鍵字)
對應關系稱為散列函數，又稱為哈希（Hash）函數。
采用散列技術将記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或哈希表。散列技術既是一種存儲方法，也是一種查找方法。
散列函數可能會把兩個或兩個以上的不同關鍵字映射到同一位址，稱這些情況為沖突，這些發生碰撞的不同關鍵字稱為同義詞。
2 散列函數的構造方法
3.1 直接定址法
對于下圖所示的0-100歲的人口數字統計表，對年齡這個關鍵字就可以直接用年齡的數字作為位址，此時
f(key)=key
。
如果我們要統計的是1980年後出生年份的人口數，如下圖所示，我們對出生年份這個關鍵字可以用年份減去1980來作為位址。此時
f(key)=key-1980
。
直接去關鍵字的某個線性函數值為散列位址，散列函數為：
直接定址法的散列函數的優點是簡單、均勻，也不會産生沖突，但是需要提前知道關鍵字的分布情況，适合查找表較小且連續的情況。
3.2 除留餘數法
除留餘數法是最常用的構造散列函數的方法，假設散清單表長為m，取一個不大于m但最接近或等于m的質數p，散列函數為：
假設我們有12個記錄的關鍵字構造散清單時，就用了的方法，比如，是以它存儲在下标為5的位置。
根據經驗，若散清單表長為m，通常p為小于或等于表長（最好接近m）的最小質數或不包含小于20質因子的合數。
3 處理散列沖突的方法
3.1 開放位址法
3.1.1 線性探測法
開放定址法就是一旦發生了沖突，就去尋找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将記錄存入。
公式是：
一個簡單的案例，我們的關鍵字集合為，表長為12.我們用散列函數。
當計算前5個數，都是沒有沖突的散列位址，直接存入，如下圖所示。
計算key=37時，發現，此時就與25所在的位置沖突，于是再次進行計算，于是将37存入下标為2的位置，如圖所示。
到了key=48，我們計算得到，與12所在的0位置沖突了，繼續計算，與25所在的位置沖突，于是一直到，才有空位，如圖所示。
這種解決沖突的開放定址法稱為線性探測法。
3.1.2 二次探測
當時，稱為二次探測法。增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域。
公式如下：
3.1.3 僞随機探測
在沖突時，對于位移量 采用随機函數計算得到，我們稱為随機探測法。
3.2 鍊址法
為了避免非同義詞發生沖突，把所有的同義詞存儲在一個線性連結清單，如圖所示。
鍊址法對于可能會造成很多沖突的散列函數來說，提供了絕不會出現找不到位址的保障。
4 散清單的查找
散清單查找取決于三個因素：散列函數、處理沖突的方法和裝填因子。
裝填因子表中記錄數散清單長度。
散清單的平均查找長度依賴于散清單的裝填因子，不直接依賴于或。
越大，表示裝填的越滿，發生沖突的可能性就越大。
4.1 散清單查找算法實作
散清單的結構定義如下：
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /* 定義散清單長為數組的長度 */
#define NULLKEY -32768
typedef int Status; /* Status是函數的類型,其值是函數結果狀态代碼，如OK等 */
typedef struct
{
int *elem; /* 資料元素存儲基址，動态配置設定數組 */
int count; /* 目前資料元素個數 */
}HashTable;
int m=0; /* 散清單表長，全局變量 */ 散清單初始化：
/* 初始化散清單 */
Status InitHashTable(HashTable *H)
{
int i;
m=HASHSIZE;
H->count=m;
H->elem=(int *)malloc(m*sizeof(int));
for(i=0;i<m;i++)
H->elem[i]=NULLKEY;
return OK;
} 除留餘數法作為散列函數：
/* 散列函數 */
int Hash(int key)
{
return key % m; /* 除留餘數法 */
} 散清單插入算法：
/* 插入關鍵字進散清單 */
void InsertHash(HashTable *H,int key)
{
int addr = Hash(key); /* 求散列位址 */
while (H->elem[addr] != NULLKEY) /* 如果不為空，則沖突 */
{
addr = (addr+1) % m; /* 開放定址法的線性探測 */
}
H->elem[addr] = key; /* 直到有空位後插入關鍵字 */
} 代碼中插入關鍵字時，首先算出散列位址，如果目前位址不為空關鍵字，則說明有沖突。此時我們應用開放定址法的線性探測進行重新尋址，此處也可更改為鍊位址法等其他解決沖突的辦法。
/* 散清單查找關鍵字 */
Status SearchHash(HashTable H,int key,int *addr)
{
*addr = Hash(key); /* 求散列位址 */
while(H.elem[*addr] != key) /* 如果不為空，則沖突 */
{
*addr = (*addr+1) % m; /* 開放定址法的線性探測 */
if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循環回到原點 */
return UNSUCCESS; /* 則說明關鍵字不存在 */
}
return SUCCESS;
}