首先介紹一下哈希技術(shù)，哈希技術(shù)是在記錄的存儲(chǔ)位置的記錄的key之間建立一個(gè)確定的映射f()，使得每個(gè)key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key)。若查找集合中存在這個(gè)記錄，則必定在f(key)位置上。哈希技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法。
六種哈希函數(shù)f(key)的構(gòu)造方法：
1、直接定址法
哈希地址：f(key)=a*key+b(a,b為常數(shù))
這種方法的優(yōu)點(diǎn)是：簡(jiǎn)單、均勻，不會(huì)產(chǎn)生沖突。但是需要預(yù)先知道key的分布情況，適合查找表較小并且連續(xù)的情況。
2、數(shù)字分析法
比如我們的手機(jī)號(hào)碼“136xxxx5889”，其中前三位是接入號(hào)，一般對(duì)應(yīng)不同運(yùn)營(yíng)公司的子品牌，比如130是聯(lián)通，159是移動(dòng)等等，中間四位表示歸屬地。最后四位才是用戶(hù)號(hào)。
若我們現(xiàn)在要存儲(chǔ)某家公司員工登記表，如果手機(jī)號(hào)碼作為key，那么極有可能前7位是相同的，所以我們選擇后四位作為f(key)就是不錯(cuò)的選擇。
適合處理關(guān)鍵字位數(shù)較大的方法
3、平方取中法
顧名思義，比如key是1234，那么它的平方就是1522756，再抽取中間的三位就是227作為f(key)。
適合不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。
4、折疊法
折疊法是將key從左到右分割成位數(shù)相等的幾個(gè)部分（最后一部分位數(shù)不夠可以短些），然后將這幾部分疊加求和，并按哈希表的表長(zhǎng)，取后幾位作為f(key)。比如我們的key是9876543210，哈希表的表長(zhǎng)為3位，我們將key分為4組，987|654|321|0，然后將他們疊加987+654+321+0=1962，再取后三位即f(key)=962.
適合事先不知道關(guān)鍵字的分布，關(guān)鍵字位數(shù)較多的情況。
5、除留余數(shù)法
哈希地址：f(key)=key mod p (p<=m)m為哈希表長(zhǎng)。這種方法是最常用的哈希函數(shù)構(gòu)造方法，下面的代碼中也使用了這種方法。
6、隨機(jī)數(shù)法
哈希地址：f(key)=random(key)。這里random是隨機(jī)函數(shù)，當(dāng)key長(zhǎng)度不等時(shí)，采用這種方法比較合適。
哈希函數(shù)沖突的兩種解決方法
哈希函數(shù)沖突的情況為key1！=key2但是f(key1)=f(key2)，即發(fā)生沖突
1、開(kāi)放定址法
開(kāi)放定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總是能夠找到，然后將記錄插入。這種方法是最常用的沖突解決方法。下面的代碼中也使用了這種方法。
2、鏈地址法
將所有相同關(guān)鍵字的記錄存儲(chǔ)在一個(gè)單鏈表中，稱(chēng)這種表為同義詞子表，在散列表中只存儲(chǔ)所有同義詞子表的頭指針。
3、再散列函數(shù)法
事先多準(zhǔn)備幾個(gè)散列函數(shù)
示例代碼
package HashSearch;
import java.util.Scanner;
public class HashSearch {
/**
* 哈希查找算法
*/
//初始化哈希表
static int hashLength=7;
static int[] hashTable=new int[hashLength];
//原始數(shù)據(jù)
static int[] list=new int[] {13,29,27,28,26,30,38};
public static void main(String[] args) {
System.out.println("*****************哈希查找*****************");
//創(chuàng)建哈希表
for(int i=0;i<list.length;i++) {
insert(hashTable,list[i]);
}
System.out.println("展示哈希表中的數(shù)據(jù)： "+display(hashTable));
while(true) {
//哈希表查找
System.out.print("請(qǐng)輸入要查找的數(shù)據(jù)：");
int data=new Scanner(System.in).nextInt();
int result=search(hashTable,data);
if(result==-1) {
System.out.println("對(duì)不起，沒(méi)有找到！");
}else {
System.out.println("數(shù)據(jù)的位置是："+result);
}
}
}
/**
* 哈希表插入
* @param hashTable
* @param data
*/
public static void insert(int[] hashTable,int data) {
//哈希函數(shù)，除留余數(shù)法
int hashAddress=hash(hashTable,data);
//如果不為0，則說(shuō)明沖突
while(hashTable[hashAddress]!=0) {
//利用開(kāi)放定址法解決沖突
hashAddress=(++hashAddress)%hashTable.length;
}
//將待插入值存入字典中
hashTable[hashAddress]=data;
}
/**
* 方法：哈希表查找
* @param hashTable
* @param data
* @return
*/
public static int search(int[] hashTable,int data) {
//哈希函數(shù)，除留余數(shù)法
int hashAddress=hash(hashTable, data);
while(hashTable[hashAddress]!=data) {
//利用開(kāi)放定址法解決沖突
hashAddress=(++hashAddress)%hashTable.length;
//查找到開(kāi)放單元 或者循環(huán)到原點(diǎn)，表示查找失敗
if(hashTable[hashAddress]==0 || hashAddress==hash(hashTable, data)) {
return -1;
}
}
//查找成功，返回下標(biāo)
return hashAddress;
}
/*
* 構(gòu)建哈希函數(shù)（除留余數(shù)法）
*/
public static int hash(int[] hashTable,int data) {
return data%hashTable.length;
}
/**
* 展示哈希表
* @param hashTable
*/
public static String display(int[] hashTable) {
StringBuffer stringBuffer=new StringBuffer();
for(int i:hashTable) {
stringBuffer.append(i+" ");
}
return String.valueOf(stringBuffer);
}
}
