Wiederverwendung von 5-unabhängigen Hash-Funktionen für die lineare Abtastung

In Hash-Tabellen, die Kollisionen durch lineares Abtasten auflösen , ist es sowohl erforderlich als auch ausreichend, dass die Hash-Funktion aus einer 5-unabhängigen Familie stammt, um die erwartete Leistung von sicherzustellen . (Suffizienz: "Lineares Testen mit konstanter Unabhängigkeit", Pagh et al. , Notwendigkeit: "Zur k-Unabhängigkeit, die für lineares Testen und min. Unabhängigkeit erforderlich ist", Pătraşcu und Thorup )$O(1)$

Nach meinem Verständnis verwenden die schnellsten bekannten fünf unabhängigen Familien die Tabellierung. Die Auswahl einer Funktion aus einer solchen Familie kann teuer sein. Daher möchte ich die Häufigkeit meiner Angriffe minimieren und dennoch Angriffe auf algorithmische Komplexität verhindern, wie in Crosby und Wallachs "Denial of Service via Algorithmic Complexity Attacks" beschrieben . Ich mache mir weniger Sorgen über Timing-Angriffe (dh Gegner mit Stoppuhren). Welche Konsequenzen hat die Wiederverwendung derselben Funktion:

1. Wenn eine Hash-Tabelle wächst, die zu voll ist?
2. Wenn Sie eine Hash-Tabelle verkleinern, die nicht voll genug ist?
3. Beim Neuerstellen einer Hash-Tabelle, bei der zu viele "gelöschte" Bits gesetzt sind?
4. In verschiedenen Hash-Tabellen, die einige gemeinsame Schlüssel enthalten können?$k$
5. In verschiedenen Hash-Tabellen, die keine gemeinsamen Schlüssel enthalten?$k$

$1/2$

• https://issues.cloudera.org/browse/IMPALA-2653
• https://github.com/rust-lang/rust/issues/36481