作者：nnngu
GitHub：https://github.com/nnngu
博客園：http://www.cnblogs.com/nnngu
簡書：http://www.reibang.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
前面的幾篇文章分別總結(jié)了：順序查找腐巢、二分查找冯勉、索引查找、二叉排序樹此迅。這一篇文章要總結(jié)的是五大查找的最后一個：哈希查找（也稱為散列查找）。提起哈希，我的第一印象就是java中的Hashtable類，它是由 key/value 的鍵值對組成的集合，它就是應(yīng)用了哈希技術(shù)钦无。
那什么是哈希查找呢？在弄清楚什么是哈希查找之前盖袭，我們要弄清楚哈希技術(shù)失暂，哈希技術(shù)是在記錄的存儲位置和記錄的 key 之間建立一個確定的映射 f()，使得每個 key 對應(yīng)一個存儲位置 f(key)苍凛。若查找集合中存在這個記錄趣席，則必定在 f(key) 的位置上。哈希技術(shù)既是一種存儲方法醇蝴，也是一種查找方法宣肚。
六種哈希函數(shù) f(key) 的構(gòu)造方法：
1、直接定址法
哈希地址：f(key) = a*key+b (a,b為常數(shù))
這種方法的優(yōu)點是：簡單悠栓，均勻霉涨，不會產(chǎn)生沖突。但是需要事先知道 key 的分布情況惭适，適合查找表較小并且連續(xù)的情況笙瑟。
2、數(shù)字分析法
比如我們的11位手機(jī)號碼“136xxxx5889”癞志，其中前三位是接入號往枷，一般對應(yīng)不同運營公司的子品牌，如130是聯(lián)通如意通凄杯，136是移動神州行等等错洁。中間四位表示歸屬地。最后四位才是用戶號戒突。
若我們現(xiàn)在要存儲某家公司員工登記表屯碴，如果用手機(jī)號碼作為 key，那么極有可能前7位都是相同的膊存，所以我們選擇最后四位作為 f(key) 就是不錯的選擇导而。
3、平方取中法
故名思義隔崎，比如 key 是1234今艺，那么它的平方就是1522756，再抽取中間的3位就是227作為 f(key) 爵卒。
4虚缎、折疊法
折疊法是將 key 從左到右分割成位數(shù)相等的幾個部分(最后一部分位數(shù)不夠可以短些)，然后將這幾部分疊加求和技潘，并按哈希表的表長遥巴，取后幾位作為 f(key) 。
比如我們的 key 是 9876543210享幽，哈希表的表長為3位铲掐，我們將 key 分為4組，987|654|321|0 值桩，然后將它們疊加求和 987+654+321+0=1962摆霉，再取后3位即得到 f(key) = 962 。
5奔坟、除留余數(shù)法
哈希地址：f(key) = key mod p (p<=m) m為哈希表表長携栋。
這種方法是最常用的哈希函數(shù)構(gòu)造方法。下面的代碼中也使用了這種方法咳秉。
6婉支、隨機(jī)數(shù)法
哈希地址：f(key) = random(key)
這里 random 是隨機(jī)函數(shù)，當(dāng) key 的長度不等時澜建，采用這種方法比較合適向挖。
哈希函數(shù)沖突的兩種解決方法：
我們設(shè)計得再好的哈希函數(shù)也不可能完全避免沖突，當(dāng)我們使用哈希函數(shù)后發(fā)現(xiàn)有 key1 != key2炕舵，但卻有 f(key1) = f(key2) 何之，即發(fā)生沖突。
1咽筋、開放定址法：
開放定址法就是一旦發(fā)生了沖突溶推，就去尋找下一個空的哈希地址，只要哈希表足夠大奸攻，空的哈希地址總是能找到蒜危，然后將記錄插入。這種方法是最常用的解決沖突的方法舞箍。下面的代碼中也使用了這種方法舰褪。
2、鏈地址法：
鏈地址法不做詳細(xì)展開疏橄。
代碼：
HashSearch.java
import java.io.IOException;
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) throws IOException {
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("請輸入要查找的數(shù)據(jù)：");
int data = new Scanner(System.in).nextInt();
int result = search(hashTable, data);
if (result == -1) {
System.out.println("對不起占拍，沒有找到！");
} else {
System.out.println("數(shù)據(jù)的位置是：" + result);
}
}
}
/**
* 方法：哈希表插入
*/
public static void insert(int[] hashTable, int data) {
// 哈希函數(shù)捎迫，除留余數(shù)法
int hashAddress = hash(hashTable, data);
// 如果不為0晃酒，則說明發(fā)生沖突
while (hashTable[hashAddress] != 0) {
// 利用 開放定址法 解決沖突
hashAddress = (++hashAddress) % hashTable.length;
}
// 將待插入值存入字典中
hashTable[hashAddress] = data;
}
/**
* 方法：哈希表查找
*/
public static int search(int[] hashTable, int data) {
// 哈希函數(shù)，除留余數(shù)法
int hashAddress = hash(hashTable, data);
while (hashTable[hashAddress] != data) {
// 利用 開放定址法 解決沖突
hashAddress = (++hashAddress) % hashTable.length;
// 查找到開放單元 或者 循環(huán)回到原點窄绒，表示查找失敗
if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, data)) {
return -1;
}
}
// 查找成功贝次，返回下標(biāo)
return hashAddress;
}
/**
* 方法：構(gòu)建哈希函數(shù)（除留余數(shù)法）
*
* @param hashTable
* @param data
* @return
*/
public static int hash(int[] hashTable, int data) {
return data % hashTable.length;
}
/**
* 方法：展示哈希表
*/
public static String display(int[] hashTable) {
StringBuffer stringBuffer = new StringBuffer();
for (int i : hashTable) {
stringBuffer = stringBuffer.append(i + " ");
}
return String.valueOf(stringBuffer);
}
}
運行結(jié)果：
