查找算法06-哈希查找

• • 6、哈希查找
  • • 6-1實作代碼
    • 6-2測試
    • 6-3方法解析

知識分享： 熱門部落格

6、哈希查找

（1）概述

在哈希表中,若出現key1≠key2,而f(key1)=f(key2),則這種現象稱為位址沖突key1和key2對哈希函數f來說是同義詞。根據設定的哈希函數f=H(key)和處理沖突的方法，将一組關鍵字映射到一個有限的連續的位址集上，并以關鍵字在位址集中的“象作為記錄中的存儲位置，這一映射過程為構造哈希表(散清單)。

　　好的哈希函數應該使一組關鍵字的哈希位址均勻分布在整個哈希表中，進而減少沖突，常用的構造哈希函數的方法有：

• 直接位址法（直接尋址法）：

  ① 公式：f(key)=a*key+b （a,b都是常數）。

  ②适合查找表較小且連續的情況。

  ③優點：簡單、均勻，不會産生沖突。

  ④缺點：需要知道關鍵字的分布，現實中不常用。

• 數字分析法：

  ①方法：抽取關鍵字中的一部分來計算存儲位置。

  ②适用于關鍵詞較長的情況。

• 平方取中法：

  ① 方法：将關鍵字先平方，然後截取中間x位作為存儲位置。

  ②适合用于不知道關鍵詞分布，且位數不長的情況。

• 除留餘數法：

  ① 方法：f(key)=key mod p (p<=m)，m是散清單表長。

  ②p取小于等于m的最小質數或者不包含小于20質因子的合數，以減少沖突的情況。

• 折疊法：

  ① 方法：将關鍵字拆分成若幹部分後累加起來，根據散清單表長取總和的後若幹位作為存儲位置。

  ②适用于不知道關鍵字分布，且位數較長的情況。

• 随機數法：

  ① 方法：f(key)=random(key)。

  ②注意random的随機種子需要是固定的，以便查詢的時候能夠根據key重新找到存儲位置。

  ③适用于關鍵字長度不等的情況。

（2）常用沖突處理方法

采用均勻的哈希函數可以減少位址沖突，但是不能避免沖突，是以，必須有良好的法來處理沖突，通常，處理位址沖突的方法有以下兩種:

• 開放位址法
• 拉鍊法（鍊位址法）
• 再散列函數法
• 公共溢出區法

6-1實作代碼

• Java實作方式一：

public static int searchHash(int[] hash,int hashLength,int key) {
		int index=key%hashLength;
		while(hash[index]!=0&&hash[index]!=key) {
			index=(++index)%hashLength;
		}
		if(hash[index]==0)
			return -1;
		return index;
	}
	public static void insertHash(int[] hash,int data) { 
		int index=data%hash.length;
		while(hash[index]!=0) {
			index+=(++index)%hash.length;
		}
		hash[index]=data;
	}
           

6-2測試

int[] array= {1,2,3,4,5,6,7,8,9,10};
		int hashLength=20;  //設定的值應該大于數組中元素的個數
		int[] hash=new int[hashLength];
		for(int i=0;i<array.length;i++) {
			insertHash(hash,array[i]);
		}
		for(int i=0;i<50;i++) {
			int index=searchHash(hash,hashLength,i);
			if(index!=-1) {
				System.out.println("數組中有"+i+"元素");
			}
		}
           

輸出結果：

6-3方法解析

• 方法中的hashLength的長度不能小于原數組的長度，否則會出現死循環。其中searchHash函數傳回的是資料在hash數組中存放的下标，不是原數組的下标。
• 當然上面代碼也有缺點，就是原數組中不能包含0，因為hash數組沒賦初值，預設值也是0，是以解決方式就是給hash數組中每一個元素都賦一個原數組中不可能出現的初值。

上篇博文：查找算法05-分塊查找