- 全域哈希
- 完全哈希
普通哈希的一個(gè)缺點(diǎn)：
對(duì)任意的hash函數(shù)h省艳，總存在一組keys，讓他們都映射到同一個(gè)槽里面塌忽，這樣效率拍埠，就跟離鏈表差不多了
解決的思想就是：
獨(dú)立于鍵值失驶，隨機(jī)的選擇hash 函數(shù)土居。這就跟快排中為避免最差情況時(shí)隨機(jī)化版本差不多。但是選取hash function的全局域是不能亂定的嬉探，否則也打不到理想的性能擦耀。
全域哈希
設(shè)U是key的全局域， 設(shè)H是哈希函數(shù)的有限集合涩堤，H函數(shù)將U映射到{0,1,..,m-1}眷蜓，即table的槽內(nèi)。 如果對(duì)所有不等的鍵值對(duì)x,y∈U胎围，將他們映射到同一個(gè)位置的概率是H/m
從另一個(gè)角度看吁系，如果函數(shù)h是從H中隨機(jī)選出的，x和y發(fā)生碰撞的概率是1/m
用一張圖來(lái)理解白魂，當(dāng)我隨機(jī)選一個(gè)哈希函數(shù)時(shí)汽纤，就像在上圖區(qū)域亂扔一個(gè)飛鏢，落在下面紅色區(qū)域中就會(huì)發(fā)生沖突福荸，這個(gè)概率是1/m
下面給一個(gè)定理蕴坪，說(shuō)明為什么全域函數(shù)就是好的
設(shè)h是從哈希函數(shù)全域集H中隨機(jī)選出的函數(shù)h，h被用作把任意n個(gè)鍵映射到表T的m個(gè)槽中，對(duì)給定鍵值x背传，E[#collision with x]<n/m | 發(fā)生碰撞的期望次數(shù)小于n/m呆瞻，即裝載因子α
證明
設(shè)Cx是表示與key x沖突的鍵值數(shù)量的隨機(jī)變量，設(shè)Cxy是指示變量
Cxy = 1 if h(x) = h(y) and 0 otherwise
根據(jù)定理 E[Cxy]=1/m
Cx=∑Cxy | y∈T?{x}
=》 E[Cx] = E[ ∑Cxy ] | y∈T?{x}
= ∑ E[Cxy] | y∈T?{x}
= ∑ 1/m | y∈T?{x}
= n-1 / m
這個(gè)定理想要說(shuō)明的是径玖，這種全域哈希的隨機(jī)化選擇可以達(dá)到哈希表理想的效果
構(gòu)造一個(gè)全域哈希
首先選擇一個(gè)足夠大的質(zhì)數(shù)m痴脾，把key k分解為r+1位，可以把k=<k_0挺狰、k_1 ...k_r> | k_i > 0明郭，即把k轉(zhuǎn)換成m進(jìn)制數(shù)
然后引入隨機(jī)化策略，隨機(jī)的選擇一個(gè)數(shù)a丰泊，a=<a_0薯定、a_1 ...a_r>，a同樣是m進(jìn)制數(shù)瞳购，a_i∈[0, m-1]话侄，對(duì)于a的每一位，對(duì)應(yīng)一個(gè)不同的哈希函數(shù)学赛，用隨機(jī)數(shù)a表示隨機(jī)哈希函數(shù)
最后定義哈希函數(shù)年堆，ha(k) = ∑ ai·ki mod m | i = 0 <- r
書上給出的全域哈希
首先選擇一個(gè)足夠大的質(zhì)數(shù)p,使得所有的鍵值都在0-p-1之間
Zp={0,1,...,p-1}，Z?p={1,2,..,p-1}
對(duì)于任意的a∈Zp*和b∈Zp盏浇，定義散列函數(shù)
Ha,b(k) = ((ak + b) mod p) mod m
所有這樣的哈希函數(shù)構(gòu)成的函數(shù)集
Hp.m={ha,b | a∈Zp*,b∈Zp}变丧，共p(p-1)個(gè)散列函數(shù)
現(xiàn)有p=17，m=6 計(jì)算h3,4(8)=5
完全哈希
當(dāng)鍵值是static(即固定不變)的時(shí)候绢掰，我們可以涉及方案使得最差情況下的查詢性能也很出色痒蓬，這就是完美哈希
完全哈希可以在最壞情況下以O(shè)(1)復(fù)雜度查找滴劲，性能非常出色的攻晒。完美哈希的思想就是采用兩級(jí)的框架，每一級(jí)上都用全域哈希
完全哈希的結(jié)構(gòu)如圖
第一級(jí)和帶鏈表的哈希非常的相似班挖，只是第一級(jí)發(fā)生沖突后后面接
的不是鏈表鲁捏，而是一個(gè)新的哈希表。后面那個(gè)哈希結(jié)構(gòu)萧芙，我們可以看到前端存儲(chǔ)了一些哈希表的基本性質(zhì)：m 哈希表槽數(shù)给梅；a,b 全域哈希函數(shù)要確定的兩個(gè)值(一般是隨機(jī)選然后確定下來(lái)的)，后面跟著哈希表双揪。新的哈希表通過(guò)選取哈希函數(shù)卻表二次哈希不出現(xiàn)碰撞
為了保證不沖突动羽，每個(gè)二級(jí)哈希表的數(shù)量是第一級(jí)映射到這個(gè)槽中元素個(gè)數(shù)的平方，這樣可以保證整個(gè)哈希表非常的稀疏盟榴。下面給出一個(gè)定理曹质，能更清楚的看到設(shè)置m=n2的作用
設(shè)H是一類全域哈希函數(shù)，哈希表的槽數(shù)m=n2. 那么，如果我們用一個(gè)隨機(jī)函數(shù)h∈H把n個(gè)keys映射到表中羽德。沖突次數(shù)的期望最多是1/2
