Perfektes Hashing

Für das statische dictionary problem (nur Access() ) können wir definieren:

• Eine Hash-Funktion h ist ``perfekt`` für $S\subset U$ gdw. für alle Paare von verschiedenen Schlüssel, also $\forall k_1,k_2\in S$ gilt: $\delta_h(k_1,k_2) = 0$, also $h(k_1) \neq h(k_2)$.
• Eine minimale perfekte Hash-Funktion braucht nur den Platz m=|S|=n.
• Für $m \geq 3n$ kann man in Zeit $\mathcal{O}(nN)$ eine perfekte Hash-Funktion für $S\subset U$ finden, die in $\mathcal{O}(1)$ Zeit auszuwerten ist (durch ein Programm der Größe $\mathcal{O}(n \log{N}))$ Bits.
  
  Bisher bestes Resultat:
  Programmgröße $\mathcal{O}(n \log \log n + \log \log N)$
  (untere Schranke: $\Omega \left(\frac{n^2}{m} + \log \log N\right)$ )