Java三十二篇： 哈希表
平安春運(yùn)
1.概念
哈希表（Hash table，也叫散列表）：
是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
給定表M，存在函數(shù)f(key)，對(duì)任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。
哈希表的本質(zhì)上上一個(gè)數(shù)組（元素是Entry）
這里的 id 是個(gè)key，哈希表就是根據(jù)key值來(lái)通過(guò)哈希函數(shù)計(jì)算得到一個(gè)值，這個(gè)值就是用來(lái)確定這個(gè)Entry要存放在哈希表中的位置的，實(shí)際上這個(gè)值就是一個(gè)下標(biāo)值，來(lái)確定放在數(shù)組的哪個(gè)位置上
比如這里的 id 是001，那么經(jīng)過(guò)哈希函數(shù)的計(jì)算之后得到了1，這個(gè)1就是告訴我們應(yīng)該把這個(gè)Entry放到哪個(gè)位置，這個(gè)1就是數(shù)組的確切位置的下標(biāo)，也就是需要放在數(shù)組中下表為1的位置
Hash Table的查詢速度非常的快，幾乎是O(1)的時(shí)間復(fù)雜度
hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系
散列法：元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法
優(yōu)點(diǎn)：
不論哈希表中有多少數(shù)據(jù)，查找、插入、刪除（有時(shí)包括刪除）時(shí)間接近常量的時(shí)間即0(1）的時(shí)間級(jí)
缺點(diǎn)：
它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展，某些哈希表被基本填滿時(shí)，性能下降得非常嚴(yán)重，所以程序員必須要清楚表中將要存儲(chǔ)多少數(shù)據(jù)
2.哈希函數(shù)的構(gòu)造方法
2.1 直接定制法（不常用）
取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址 即， Ｈ(key) = key H(key) = a * key + b
優(yōu)點(diǎn)：簡(jiǎn)單，均勻，不會(huì)產(chǎn)生沖突 缺點(diǎn)：需要實(shí)現(xiàn)直到關(guān)鍵字的分布情況，適合查找表比較小且連續(xù)的情況
2.2 數(shù)字分析法
數(shù)字分析法用于處理關(guān)鍵字是位數(shù)比較多的數(shù)字，通過(guò)抽取關(guān)鍵字的一部分進(jìn)行操作，計(jì)算哈希存儲(chǔ)位置的方法
例：
身份證號(hào)是有規(guī)律的，現(xiàn)在要存儲(chǔ)一個(gè)班級(jí)學(xué)生的身份證號(hào)碼，假設(shè)這個(gè)班級(jí)的學(xué)生都出生在同一個(gè)地區(qū)，同一年，那么他們的身份證的前面數(shù)位都是相同的，那么我們可以截取后面不同的幾位存儲(chǔ)，假設(shè)有5位不同，那么就用這五位代表地址
適用場(chǎng)景：
處理關(guān)鍵字位數(shù)比較大的情況，事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布均勻
2.3 平方取中法
先對(duì)關(guān)鍵字取平方，然后選取中間幾位為哈希地址，取的位數(shù)由表長(zhǎng)決定
例：key=1234 1234^2=1522756 取227作hash地址 key=4321 4321^2=18671041 取671作hash地址
適用場(chǎng)景：不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況
2.4 折疊法
如果數(shù)字的位數(shù)很多，可以將數(shù)字分割為幾個(gè)部分，取他們的疊加和作為hash地址
例：key=123 456 789 可以存儲(chǔ)在61524，取末三位，存在524的位置
適用場(chǎng)景：關(guān)鍵字位數(shù)很多，而且關(guān)鍵字每一位上數(shù)字分布大致均勻
2.5 除留余數(shù)法（用的較多）
H（key）=key MOD p （p<=m m為表長(zhǎng)）
例：存儲(chǔ)3 6 9，那么p就不能取3 因?yàn)?3 MOD 3 == 6 MOD 3 == 9 MOD 3，地址沖突
一般來(lái)說(shuō)，p應(yīng)為不大于m的質(zhì)數(shù)或是不含20以下的質(zhì)因子的合數(shù)，這樣可以減少地址的重復(fù)（沖突）
2.6 隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值作為他的哈希地址 即，f(key) = random (key)
適合場(chǎng)景：關(guān)鍵字的長(zhǎng)度不等時(shí)。當(dāng)遇到特殊字符的關(guān)鍵字時(shí)，需要將其轉(zhuǎn)換為某種數(shù)字
3.哈希沖突及解決方式
哈希沖突圖例：
3.1 開放尋址法
H（key）的哈希函數(shù)：
H（key1）= H（keyi）
那么 keyi 存儲(chǔ)位置 Hi = (H(key)+di) MOD m ，m為表長(zhǎng)
di 有三種取法：
線性探測(cè)再散列: di = c * i
平方探測(cè)再散列：di = 1^2 , -1 ^2,2 ^2,-2 ^2…
隨機(jī)探測(cè)再散列（雙探測(cè)再散列）：di是一組偽隨機(jī)數(shù)列
簡(jiǎn)單來(lái)說(shuō)就是，既然位置被占了，那就另外再找個(gè)位置，怎么找其他的位置呢？這里其實(shí)也有很多的實(shí)現(xiàn)，我們說(shuō)個(gè)最基本的就是既然當(dāng)前位置被占用了，我們就看看該位置的后一個(gè)位置是否可用，也就是1的位置被占用了，我們就看看2的位置，如果沒(méi)有被占用，那就放到這里唄，當(dāng)然，也有可能2的位置也被占用了，那咱就繼續(xù)往下找，看看3的位置，一次類推，直到找到空位置
3.2 鏈地址法
存儲(chǔ)數(shù)據(jù)后面加一個(gè)指針，指向后面沖突的數(shù)據(jù)
比如：
簡(jiǎn)單來(lái)說(shuō)，Entry還額外的保存了一個(gè)next指針，這個(gè)指針指向數(shù)組外的另外一個(gè)位置，將李四安排在這里，然后張三那個(gè)Entry中的next指針就指向李四的這個(gè)位置，也就是保存的這個(gè)位置的內(nèi)存地址，如果還有沖突，那就把又沖突的那個(gè)Entry放在一個(gè)新位置上，然后李四的Entry中的next指向它，這樣就形成了一個(gè)鏈表。
3.3 再哈希法
Hi = RHi（key） i = 1，2，…，k RHi均是不同的哈希函數(shù)，意思為：當(dāng)繁盛沖突時(shí)，使用不同的哈希函數(shù)計(jì)算地址，直到不沖突為止。這種方法不易產(chǎn)生堆積，但是耗費(fèi)時(shí)間
3.4 公共溢出區(qū)法
即設(shè)立兩個(gè)表：基礎(chǔ)表和溢出表。將所有關(guān)鍵字通過(guò)哈希函數(shù)計(jì)算出相應(yīng)的地址。然后將未發(fā)生沖突的關(guān)鍵字放入相應(yīng)的基礎(chǔ)表中，一旦發(fā)生沖突，就將其依次放入溢出表中即可。
在查找時(shí)，先用給定值通過(guò)哈希函數(shù)計(jì)算出相應(yīng)的散列地址后，首先與基本表的相應(yīng)位置進(jìn)行比較，如果不相等，再到溢出表中順序查找。
此種方法適用于數(shù)據(jù)和沖突較少的情況
4.擴(kuò)容
增長(zhǎng)因子，也叫作負(fù)載因子，簡(jiǎn)單點(diǎn)說(shuō)就是已經(jīng)被占的位置與總位置的一個(gè)百分比。
比如負(fù)載因子是0.7時(shí)，一共十個(gè)位置，現(xiàn)在已經(jīng)占了七個(gè)位置，就觸發(fā)了擴(kuò)容機(jī)制，也就是達(dá)到了總位置的百分之七十就需要擴(kuò)容。
簡(jiǎn)單來(lái)說(shuō)，擴(kuò)容就是新創(chuàng)建一個(gè)數(shù)組是原來(lái)的2倍，然后把原數(shù)組的所有Entry都重新Hash一遍放到新的數(shù)組。
數(shù)組擴(kuò)大了，所以一般哈希函數(shù)也會(huì)有變化，這里的Hash也就是把之前的數(shù)據(jù)通過(guò)新的哈希函數(shù)計(jì)算出新的位置來(lái)存放
代碼的實(shí)際需求
看一個(gè)實(shí)際需求， google 公司的一個(gè)上機(jī)題:
有一個(gè)公司，當(dāng)有新的員工來(lái)報(bào)道時(shí),要求將該員工的信息加入(id, 性別, 年齡, 住址…)，當(dāng)輸入該員工的 id 時(shí)，要求查找到該員工的所有信息
要求：不使用數(shù)據(jù)庫(kù)，盡量節(jié)省內(nèi)存，速度越快越好 => 哈希表(散列)
哈希表編程思路：
先根據(jù)對(duì)象的信息將其散列，得到 hashCode
根據(jù)對(duì)象的 hashCode 值，找到對(duì)應(yīng)的數(shù)組下標(biāo)，其實(shí)就是找到存儲(chǔ)對(duì)象的鏈表
在鏈表中進(jìn)行相應(yīng)的增刪改查操作
代碼實(shí)現(xiàn)
Emp 節(jié)點(diǎn)
//表示一個(gè)雇員
class EmpNode {
publicint id;
public String name;
public EmpNode next; // next 默認(rèn)為 null
public EmpNode(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
Emp 鏈表
head 是首指針（指向真正存放數(shù)據(jù)的節(jié)點(diǎn)），不是頭指針
//創(chuàng)建EmpLinkedList ,表示鏈表
class EmpLinkedList {
// 首指針，指向第一個(gè)EmpNode,因此我們這個(gè)鏈表的head 是直接指向第一個(gè)EmpNode
private EmpNode head; // 默認(rèn)null
// 添加雇員到鏈表
// 說(shuō)明
// 1. 假定，當(dāng)添加雇員時(shí)，id 是自增長(zhǎng)，即id的分配總是從小到大
// 因此我們將該雇員直接加入到本鏈表的最后即可
public void add(EmpNode empNode) {
// 如果是添加第一個(gè)雇員
if (head == null) {
head = empNode;
return;
}
// 如果不是第一個(gè)雇員，則使用一個(gè)輔助的指針，幫助定位到最后
EmpNode curEmp = head;
while (true) {
if (curEmp.next == null) {// 說(shuō)明到鏈表最后
break;
}
curEmp = curEmp.next; // 后移
}
// 退出時(shí)直接將emp 加入鏈表
curEmp.next = empNode;
}
// 遍歷鏈表的雇員信息
public void list(int no) {
if (head == null) { // 說(shuō)明鏈表為空
System.out.println("第 " + (no + 1) + " 鏈表為空");
return;
}
System.out.print("第 " + (no + 1) + " 鏈表的信息為");
EmpNode curEmp = head; // 輔助指針
while (true) {
System.out.printf(" => id=%d name=%s ", curEmp.id, curEmp.name);
if (curEmp.next == null) {// 說(shuō)明curEmp已經(jīng)是最后結(jié)點(diǎn)
break;
}
curEmp = curEmp.next; // 后移，遍歷
}
System.out.println();
}
// 根據(jù)id查找雇員
// 如果查找到，就返回Emp, 如果沒(méi)有找到，就返回null
public EmpNode findEmpById(int id) {
// 判斷鏈表是否為空
if (head == null) {
System.out.println("鏈表為空");
returnnull;
}
// 輔助指針
EmpNode curEmp = head;
while (true) {
if (curEmp.id == id) {// 找到
break;// 這時(shí)curEmp就指向要查找的雇員
}
curEmp = curEmp.next;// 后移
// 退出
if (curEmp == null) {// 說(shuō)明遍歷當(dāng)前鏈表沒(méi)有找到該雇員
break;
}
}
return curEmp;
}
}
Emp 哈希表
//創(chuàng)建HashTab 管理多條鏈表
class HashTab {
private EmpLinkedList[] empLinkedListArray;
privateint size; // 表示有多少條鏈表
// 構(gòu)造器
public HashTab(int size) {
this.size = size;
// 初始化empLinkedListArray
empLinkedListArray = new EmpLinkedList[size];
for (int i = 0; i < size; i++) {
empLinkedListArray[i] = new EmpLinkedList();
}
}
// 添加雇員
public void add(EmpNode empNode) {
// 根據(jù)員工的id ,得到該員工應(yīng)當(dāng)添加到哪條鏈表
int empLinkedListNO = hashFun(empNode.id);
// 將emp 添加到對(duì)應(yīng)的鏈表中
empLinkedListArray[empLinkedListNO].add(empNode);
}
// 遍歷所有的鏈表,遍歷hashtab
public void list() {
for (int i = 0; i < size; i++) {
empLinkedListArray[i].list(i);
}
}
// 根據(jù)輸入的id,查找雇員
public void findEmpById(int id) {
// 使用散列函數(shù)確定到哪條鏈表查找
int empLinkedListNO = hashFun(id);
EmpNode empNode = empLinkedListArray[empLinkedListNO].findEmpById(id);
if (empNode != null) {// 找到
System.out.printf("在第%d條鏈表中找到 雇員 id = %d\n", (empLinkedListNO + 1), id);
} else {
System.out.println("在哈希表中，沒(méi)有找到該雇員~");
}
}
// 編寫散列函數(shù), 使用一個(gè)簡(jiǎn)單取模法
public int hashFun(int id) {
return id % size;
}
}
代碼測(cè)試
publicclass HashTabDemo {
public static void main(String[] args) {
// 創(chuàng)建哈希表
HashTab hashTab = new HashTab(7);
// 寫一個(gè)簡(jiǎn)單的菜單
String key = "";
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.println("add: ?添加雇員");
System.out.println("list: 顯示雇員");
System.out.println("find: 查找雇員");
System.out.println("exit: 退出系統(tǒng)");
System.out.println();
key = scanner.next();
switch (key) {
case"add":
System.out.println("輸入id");
int id = scanner.nextInt();
System.out.println("輸入名字");
String name = scanner.next();
// 創(chuàng)建 雇員
EmpNode empNode = new EmpNode(id, name);
hashTab.add(empNode);
break;
case"list":
hashTab.list();
break;
case"find":
System.out.println("請(qǐng)輸入要查找的id");
id = scanner.nextInt();
hashTab.findEmpById(id);
break;
case"exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}
程序運(yùn)行結(jié)果
add: ?添加雇員
list: 顯示雇員
find: 查找雇員
exit: 退出系統(tǒng)
add
輸入id
1
輸入名字
Heygo
add: ?添加雇員
list: 顯示雇員
find: 查找雇員
exit: 退出系統(tǒng)
list
第 1 鏈表為空
第 2 鏈表的信息為 => id=1 name=Heygo => id=8 name=NiuNiu
第 3 鏈表的信息為 => id=2 name=Oneby
第 4 鏈表為空
第 5 鏈表為空
第 6 鏈表為空
第 7 鏈表為空
add: ?添加雇員
list: 顯示雇員
find: 查找雇員
exit: 退出系統(tǒng)
find
請(qǐng)輸入要查找的id
9
在哈希表中，沒(méi)有找到該雇員~
add: ?添加雇員
list: 顯示雇員
find: 查找雇員
exit: 退出系統(tǒng)
總結(jié)：
哈希表基于數(shù)組，類似于key-value的存儲(chǔ)形式，關(guān)鍵字值通過(guò)哈希函數(shù)映射為數(shù)組的下標(biāo)，如果一個(gè)關(guān)鍵字哈?；揭颜加玫臄?shù)組單元，這種情況稱為沖突。用來(lái)解決沖突的有兩種方法：開放地址法和鏈地址法。在開發(fā)地址法中，把沖突的數(shù)據(jù)項(xiàng)放在數(shù)組的其它位置；在鏈地址法中，每個(gè)單元都包含一個(gè)鏈表，把所有映射到同一數(shù)組下標(biāo)的數(shù)據(jù)項(xiàng)都插入到這個(gè)鏈表中。
?
