Uniwersalne mieszanie w praktyce

Rodzina funkcji skrótu jest uniwersalna, jeśli $H$ $h: U \rightarrow \{0,\ldots,M-1\}$ Więcej informacji o uniwersalnym haszowaniu można znaleźć w tymartykule naWikipedii.

\forall x, y \in U, x \neq y \Rightarrow \underset{h \in H.}{Par} [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}$

Koncepcja uniwersalnego mieszania jest obecnie standardową częścią kursów struktury danych licencjackich. Byłoby miło móc motywować studentów do znaczenia uniwersalnego mieszania w zastosowaniach przemysłowych. Więc moje pytanie brzmi:

Czy konstrukcje uniwersalnej rodziny funkcji mieszających są ważne w praktyce? Jeśli odpowiedź brzmi „tak”, czy mógłbyś podzielić się interesującymi aplikacjami przemysłowymi, które widziałeś?

data-structures education hash-tables applied-theory Dai
źródło

Oczekuję, że wszystkie implementacje ogólnych struktur mieszających, które chcą osiągnąć (zamortyzowany / oczekiwany / rzeczywisty) stały koszt wstawiania, wyszukiwania i usuwania (jest to jedyny powód, dla którego zawracamy sobie głowę hashowaniem), potrzebują niezawodnego sposobu na konstruować „dobre” funkcje haszujące. Uniwersalny skrót to (udana) próba sformalizowania, czym jest „dobra” funkcja skrótu, a także daje nam narzędzia do wydajnego generowania takich funkcji dla dowolnych kluczy. Ponieważ nie mam doświadczenia w branży, wszystko to z teoretycznego punktu widzenia, ale bardzo liczę na to, że będą one najlepszym rozwiązaniem.

G. Bach,

@ G.Bach Dzięki za komentarze. Ale chcę usłyszeć opinie z przemysłowego punktu widzenia.

Dai

@Dai Prawdopodobnie nie jest to odpowiednie miejsce na otrzymywanie oświadczeń z branży.

Raphael

Uniwersalne mieszanie w praktyce

Odpowiedzi: