Hashing

Quiz

Haben 2 Teilnehmer am gleichen Tag Geburtstag?

Antwort

Wahrscheinlichkeit: 59.8%

Es gibt tatsächlich 2 Personen.

Hash-Funktion

  • h : Daten → Zahl
  • h(a) ≠ h(b) ⇒ a ≠ b
  • Perfekte Hash-Funktion: h(b) ≠ h(n) ⇔ a ≠ b

Zahl hat fixe Grösse, z.B. 32 oder 64 Bit.

Gute Hash-Funktionen?

  • hsum(c1c2c3…cn) = c1 + c2 + … + cn
  • hprod(c1c2c3…cn) = c1 ⋅ c2⋯cn
  • h2(c1c2c3…cn) = c1 + 2c2 + … + 2n − 1cn
  • hp(c1c2c3…cn) = c1 + pc2 + … + pn − 1cn

Wieso sind das keine Hash-Funktionen?

Gute Hash-Funktionen?

  • hsum(c1c2c3…cn) = (c1 + c2 + … + cn) mod M
  • hprod(c1c2c3…cn) = (c1 ⋅ c2⋯cn) mod M
  • h2(c1c2c3…cn) = (c1 + 2c2 + … + 2n − 1cn) mod M
  • hp(c1c2c3…cn) = (c1 + pc2 + … + pn − 1cn) mod M = ((((c1 mod M) + p ⋅ c2) mod M) + … + pn − 1cn) mod M

Geburtstagsparadoxon

Falls jeder Hashwert gleich häufig:

Bits 0.1% 1% 25% 50% 75%
32 2900 9300 50′000 77′000 110′000
64 1.9 ⋅ 108 6.1 ⋅ 108 3.3 ⋅ 109 5.1 ⋅ 109 7.2 ⋅ 109

Lese: Um bei 32-Bit-Hashes mit 50% Wahrscheinlichkeit herbeizurufen benötigt man etwa 77'000 Einträge.

Hash-Tables

  • Array der Grösse C (Capacity).
  • Element x wird an Index h(x) mod C gespeichert.
  • Bei Kollision:
    1. Verlinkte Liste anlegen
    2. In h(x) + 1 mod C abspeichern.
    Variante 1 unterstützt Löschen, Variante 2 ist schneller.

Laufzeit Hash-Tables

Einfügen hat gleiche Laufzeit wie Suchen.

Falls k Kollisionen: O(k).

  • Durchschnittliche Anzahl Elemente: C/N
  • Durchschnittliche Anzahl Kollisionen: C/N
  • Zufällige Hashfunktion  ⇒  erwartete Anzahl Kollisionen
  • Laufzeit O(1) (O(1 + C/N) mit C > N)
  • image

Rehashing

Falls beliebige Anzahl Einfügeoperationen ist C nicht im Voraus bekannt.

Einfach mit C = 2 beginnen und falls C = N verdoppeln.

Hash-Tables (C++)

#include <unordered_map>
unordered_map<string, int> words;
for (string s; cin >> s;)
  words[s]++;
for (auto& w : words)
  cout << w.first << ": " << w.second;

Polynomial Hashing

hp(c1c2c3…cn) = (c1 + pc2 + … + pn − 1cn) mod M

  • p und M müssen teilerfremd sein
  • p > max(ci) und p < M
  • M = 264 ist beliebt (da modulo automatisch), aber es ist leicht, unabhängig von p Kollisionen zu erzwingen.

Rolling Hash

Vorteil vom Polynomial Hash: Einfach updaten.

hp(c1c2c3…cn) = (c1 + pc2 + … + pn − 1cn) mod M                         = (c1 mod M + (p(c2 + pc3 + … + pn − 2cn)) mod M) mod M        = (c1 + p(c2c3…cn)) mod M

hp(c1c2c3…cn) = ((c1 + pc2 + … + pn − 1cn) + (pn − 1cn)) mod M    = (hp(c1c2…cn − 1) + pn − 1cn) mod M

Rolling Hash

Sei hp(c1c2c3…cn) sowie p − 1 und pn bekannt.

Dann ist:

hp(c2c2c3…cncn + 1) = (p − 1(hp(c1c2c3…cn) − c1) + pn) mod M

Rolling Hash gedreht

Definiere den umgekehrten Polynomial Hash:

h′p(c1c2…cn − 1cn) = (pn − 1c1 + pn − 2c2 + … + pcn − 1 + cn) mod M

Dann ist:

h′p(c2c3…cncn + 1) = (h′p(c1c2…cn − 1cn) − pnc1 + cn + 1) mod M

Rabin–Karp

Gegeben String str und pat, finde pat in str.

const uint64_t p, p_n, m; // bekannt
uint64_t pattern_hash = hash(pat);
uint64_t hash = 0;
queue<char> buffer;
for (char& c : s) {
  if (buffer.size() >= p.size()) {
    hash = (m - p_n*buffer.front())%m;
    buffer.pop();
  }
  buffer.push(c);
  hash = (hash + c)%m;
  if (hash == pattern_hash && buffer.size() == p)
    // found
}

Rabin-Karp in 2D

Hash von jedem Substring

Beispiel 1

  • Wie viele Palindrome sind in str?
  • Hashs von allen Substrings generieren und überprüfen
  • Binary-Search von jedem Zeichen aus

Beispiel 2

  • Was ist der längste Substring, der mindestens zwei mal vorkommt?
  • Binary-Search über Länge.

Beispiel 3

  • Gegeben ein String str und Indices from1, to1, from2, to2, ist der Substring von from1 bis to1 oder der von from2 bis to2 kleiner?
  • Binary-Search über Länge des gemeinsamen Präfix.

Beispiel 4

  • Gegeben ein String aus 0 und 1. Ein String ist antisymmetrisch, wenn alle 0 mit 1 vertauscht wurden und er umgedreht ist. Wie viele antysymmetrische Substrings gibt es in str?
  • Hashs für str und das antisymmetrische str ausrechnen. Dann von jedem Index aus Binary-Search über die Länge.
  • Aufgabe stammt aus der 17. Polnischen Informatikolympiade.

Zusammenfassung

  • Hashing ermöglicht sehr kurze und effiziente Implementierungen von String-Aufgaben.
  • Nur zu hoher Wahrscheinlichkeit korrekt (aber kein Problem bei Full-Feedback).