查找----散列查找

1、散列函數

    把任意長的輸入消息串變化成固定長的輸出串的一種函數。這個輸出串稱為該消息的雜湊值。一般用于産生消息摘要，密鑰加密等。常見的散列函數構造方法如下：

  （1）直接定址法

　 例如：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。

  （2）數字分析法

　　有學生的生日資料如下：

　　年.月.日

　　75.10.03

　　75.11.23

　　76.03.02

　　76.07.12

　　75.04.21

　　76.02.15

    　...

　　經分析，第一位，第二位，第三位重複的可能性大，取這三位造成沖突的機會增加，是以盡量不取前三位，取後三位比較好。

   （3）平方取中法

　　取關鍵字平方後的中間幾位為哈希位址。

  （4）折疊法

　　将關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（舍去進位）作為哈希位址，這方法稱為折疊法。

　　例如：每一種西文圖書都有一個國際标準圖書編号，它是一個10位的十進制數字，若要以它作關鍵字建立一個哈希表，當館藏書種類不到10,000時，可采用此法構造一個四位數的哈希函數。

  （5）除留取餘法

　　取關鍵字被某個不大于哈希表表長m的數p除後所得餘數為哈希位址。 H(key)=key MOD p (p<=m)

   （6）随機數法

　　選擇一個随機函數，取關鍵字的随機函數值為它的哈希位址，即 H(key)=random(key），其中random為随機函數。通常用于關鍵字長度不等時采用此法。

　　若已知哈希函數及沖突處理方法，哈希表的建立步驟如下：

　　Step1.　取出一個資料元素的關鍵字key，計算其則哈希表中的存儲位址D=H(key）。若存儲位址為D的存儲空間還沒有被占用，則将該資料元素存入；否則發生沖突，執行Step2。

　　Step2.　根據規定的沖突處理方法，計算關鍵字為key的資料元素之下一個存儲位址。若該存儲位址的存儲空間沒有被占用，則存入；否則繼續執行Step2，直到找出一個存儲空間沒有被占用的存儲位址為止。

2、沖突處理

    無論哈希函數設計有多麼精細，都會産生沖突現象，也就是2個關鍵字處理函數的結果映射在了同一位置上，是以，有一些方法可以避免沖突。

  （1）拉鍊法

　　拉出一個動态連結清單代替靜态順序存儲結構，可以避免哈希函數的沖突，不過缺點就是連結清單的設計過于麻煩，增加了程式設計複雜度。此法可以完全避免哈希函數的沖突。

  （2）再哈希法

　　設計二種甚至多種哈希函數，可以避免沖突，但是沖突幾率還是有的，函數設計的越好或越多都可以将幾率降到最低（除非人品太差，否則幾乎不可能沖突）。

  （3）開放定址法

　　開放位址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1） 。其中，m為哈希表的表長。di 是産生沖突的時候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。 如果di取1，則每次沖突之後，向後移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2） 。稱二次探測再散列。如果di取值可能為僞随機數列。稱僞随機探測再散列。

  （4）建域法

#define MAX 10
        
//連結清單資料結構
typedef struct list  
{
	int data;
	list *next;
}*pList;

list hashtable[MAX];  ///鍊式法解決位址沖突，MAX個帶頭節點的hash連結清單

//除留取餘法
int hashFunc(int n)   
{
	return n%MAX;
}

//建立hash連結清單
void createhash(int *array,int n)  
{
	pList p,pNew;
	for (int i=0;i<n;i++)
	{
		pNew=new list;
		pNew->data=array[i];
		pNew->next=NULL;
		
		int pos=hashFunc(array[i]);
		p=hashtable[pos].next;
		
		if (p!=NULL)         //将新的節點插入到頭結點的後面
		{
			pNew->next=p;
			hashtable[pos].next=pNew;
		} 
		else
		{
			hashtable[pos].next=pNew;
		}
	}
}

//hash查找
bool SearchHash(int val)   
{
	int pos=hashFunc(val);        //找出在哪個hash連結清單
	pList p=hashtable[pos].next;  //周遊對應的連結清單
	while(p!=NULL)
	{
		if(p->data==val)
			return true;
		p=p->next;
	}
	
	return false;
}

//周遊hashtable
void TraverseHashtable()
{
	for (int m=0;m<MAX;m++) //一次周遊每個連結清單裡面的内容
	{
		pList p1=hashtable[m].next;
		while(p1!=NULL)
		{
			cout<<p1->data<<" ";
			p1=p1->next;
		}
	}
	cout<<endl;
}