一、完美散列

簡介

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

特性及使用

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

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

延伸閱讀：

二、完美哈希

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

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