對集合S的完美散列函式 是一個將S的每個元素映射到一系列無衝突的整數的 哈希函式。一個完美散列函式的套用與其他哈希函式的套用基本一致，但不需要任何衝突解決方案。在數學術語中，這是一個完全單射函式。
基本介紹
- 中文名：完美散列
- 外文名：Perfect hash function
- 學科：計算機科學
特性及使用,最小完美散列函式,
特性及使用
對於特定集合S的完美散列函式能在常數時間中被計算出，其映射值在一個相對小的範圍內，能被一個隨機化算法發現，該算法的操作次數與S的大小成正比。任何適合在哈希表中使用的完美散列函式需要至少與S的大小成正比的位數。
一個值的位數被限定範圍的完美散列函式能套用於高效查找操作中：假定查找鍵(key)與集合S（或與集合S關聯的值）對應，然後將完美散列函式套用於查找鍵，得到哈希值（一個整數），然後在查找表中取出該整數對應的值。在集合S極少更新且查詢頻率非常多的情況下，使用完美hash函式是非常有效的。對集合S更新頻率的限定是由於對任何集合S的修改，都將導致該完美散列函式退化為非完美散列函式。每次集合S被修改後自動更新hash函式的解決方案被稱為dynamic perfect hashing，但這類方法非常複雜，難以實現。一個簡單的允許動態更新集合S的完美散列函式的替代品叫cuckoo hashing。
最小完美散列函式
最小完美散列函式是一個能將n個鍵（key）映射到n個連續的整數的完美散列函式。 產生的值通常為 [0..n−1] 或 [1..n]。正式表述如下：設j和k是有限集合K的兩個元素。F是一個最小完美散列函式
只在j=k的情況下成立(單射)；並且存在整數a，使得F的範圍為a~a+|K|−1。已經在數學上證明，通用的完美hash函式至少需要每個鍵（key）1.44 比特（bit）。而當前已知的最小完美hash散列函式每個鍵需要2.6 比特。
對一個最小完美散列函式F，若鍵以a1,a2, ...,an次序給出，對任意鍵
和
，意味著
。我們稱該最小完美散列函式F是保序的。
若對一個最小完美散列函式F，其套用變換後得到的值保持了鍵（key）的字典序，我們稱該最小完美散列函式F為單調的。在此情況下，函式產生的值就是輸入的鍵在所有可能的有序鍵序列中的位置。若被hash的鍵被存儲於有序數組中，已實現一種策略，對每個鍵存儲少量附加位（bits），以取得更快計算hash值的優勢。
