Hashing Universal na Prática

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

\forall x, y \in você, 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}$

O conceito de hash universal agora faz parte padrão dos cursos de graduação em estrutura de dados. Seria bom poder motivar os alunos sobre a importância do hash universal em aplicações industriais. Então, minha pergunta é:

As construções da família universal de funções hash são importantes na prática? Se a resposta for sim, você poderia compartilhar algumas aplicações industriais interessantes que você já viu?

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

Espero que todas as implementações de estruturas de hash genéricas que queiram atingir o custo de tempo constante (amortizado / esperado / real) para inserção, pesquisa e remoção (que é a única razão pela qual nos preocupamos com o hash em primeiro lugar) precisam de uma maneira confiável de construir funções de hash "boas". O hash universal é uma tentativa (bem-sucedida) de formalizar o que é uma função de hash "boa" e também fornece ferramentas para gerar essas funções com eficiência para chaves arbitrárias. Como não tenho nenhuma experiência no setor, tudo isso é do ponto de vista teórico, mas espero que eles sejam o caminho a seguir.

G. Bach

@ G.Bach Obrigado por seus comentários. Mas eu quero ouvir opiniões do ponto de vista industrial.

Dai #

@Dai Este provavelmente não é o lugar certo para obter declarações da indústria.

Raphael

Hashing Universal na Prática

Respostas: