Universelles Hashing in der Praxis

$H$ $h: U \rightarrow \{0,\ldots,M-1\}$

\forall x, y \in U, x \neq y \Rightarrow \underset{h \in H}{Pr} [h (x) = h (y)] \leq \frac{1}{M}

$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$

Das Konzept des universellen Hashings ist heute ein Standardbestandteil von Grundstudiengängen zur Datenstruktur. Es wäre schön, die Schüler für die Bedeutung von Universal-Hashing in industriellen Anwendungen motivieren zu können. Meine Frage lautet also:

Sind Konstruktionen der universellen Familie von Hash-Funktionen in der Praxis wichtig? Wenn die Antwort ja ist, würden Sie bitte einige interessante industrielle Anwendungen teilen, die Sie gesehen haben?

data-structures education hash-tables applied-theory Dai
quelle

Ich erwarte, dass alle Implementierungen von generischen Hash-Strukturen, die konstante Zeitkosten für das Einfügen, Nachschlagen und Entfernen (was der einzige Grund ist, warum wir uns überhaupt mit dem Hash beschäftigen) erreichen (amortisiert / erwartet / real) wollen, einen zuverlässigen Weg benötigen, dies zu tun konstruiere "gute" Hashing-Funktionen. Universal-Hashing ist ein (erfolgreicher) Versuch, zu formalisieren, was eine "gute" Hashing-Funktion ist, und es gibt uns auch Werkzeuge, um solche Funktionen effizient für beliebige Schlüssel zu generieren. Da ich keine Branchenerfahrung habe, ist dies alles aus theoretischer Sicht, aber ich erwarte sehr, dass sie der richtige Weg sind.

G. Bach

@ G.Bach Danke für deine Kommentare. Aber ich möchte Meinungen aus industrieller Sicht hören.

Dai

@Dai Dies ist wahrscheinlich nicht der richtige Ort, um Aussagen aus der Industrie zu erhalten.

Raphael

Universelles Hashing in der Praxis

Antworten: