一、完美散列

簡(jiǎn)介

對(duì)集合S的完美散列函數(shù) 是一個(gè)將S的每個(gè)元素映射到一系列無(wú)沖突的整數(shù)的 哈希函數(shù)。一個(gè)完美散列函數(shù)的應(yīng)用與其他哈希函數(shù)的應(yīng)用基本一致，但不需要任何沖突解決方案。在數(shù)學(xué)術(shù)語(yǔ)中，這是一個(gè)完全單射函數(shù)。

特性及使用

對(duì)于特定集合S的完美散列函數(shù)能在常數(shù)時(shí)間中被計(jì)算出，其映射值在一個(gè)相對(duì)小的范圍內(nèi)，能被一個(gè)隨機(jī)化算法發(fā)現(xiàn)，該算法的操作次數(shù)與S的大小成正比。任何適合在哈希表中使用的完美散列函數(shù)需要至少與S的大小成正比的位數(shù)。

一個(gè)值的位數(shù)被限定范圍的完美散列函數(shù)能應(yīng)用于高效查找操作中：假定查找鍵(key)與集合S（或與集合S關(guān)聯(lián)的值）對(duì)應(yīng)，然后將完美散列函數(shù)應(yīng)用于查找鍵，得到哈希值（一個(gè)整數(shù)），然后在查找表中取出該整數(shù)對(duì)應(yīng)的值。在集合S極少更新且查詢頻率非常多的情況下，使用完美hash函數(shù)是非常有效的。對(duì)集合S更新頻率的限定是由于對(duì)任何集合S的修改，都將導(dǎo)致該完美散列函數(shù)退化為非完美散列函數(shù)。每次集合S被修改后自動(dòng)更新hash函數(shù)的解決方案被稱為dynamic perfect hashing，但這類方法非常復(fù)雜，難以實(shí)現(xiàn)。一個(gè)簡(jiǎn)單的允許動(dòng)態(tài)更新集合S的完美散列函數(shù)的替代品叫cuckoo hashing。

延伸閱讀：

二、完美哈希

從性能角度可以這樣定義：當(dāng)關(guān)鍵字的集合是一個(gè)不變的靜態(tài)集合時(shí)，哈希技術(shù)還可以用來(lái)獲取出色的最壞情況性能。如果某一種哈希技術(shù)在進(jìn)行查找時(shí)，其最壞情況的內(nèi)存訪問(wèn)次數(shù)為O(1)時(shí)，則稱其為完美哈希（Perfect Hashing）。

完美哈希函數(shù)是靜態(tài)的，就意味著事前必須知道需要哈希哪些數(shù)據(jù)。同時(shí)生成的算法比較復(fù)雜，需要很長(zhǎng)的時(shí)間來(lái)建立索引。沒(méi)有辦法實(shí)時(shí)添加更新。給他的應(yīng)用范圍提了個(gè)極大的限制。