Hashing universal en la práctica

Una familia $H$ de funciones hash $h: U \rightarrow \{0,\ldots,M-1\}$ es universal si

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

$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$ . Puede encontrar más información sobre hashing universal en este artículo de Wikipedia .

El concepto de hashing universal es ahora una parte estándar de los cursos de pregrado de estructura de datos. Sería bueno poder motivar a los estudiantes sobre la importancia del hashing universal en aplicaciones industriales. Entonces mi pregunta es:

¿Las construcciones de la familia universal de funciones hash son importantes en la práctica? Si la respuesta es sí, ¿podría compartir algunas aplicaciones industriales interesantes que haya visto?

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

Espero que todas las implementaciones de estructuras de hash genéricas que quieran alcanzar un costo de tiempo constante (amortizado / esperado / real) para insertar, buscar y eliminar (que es la única razón por la que nos molestamos en hacer hash en primer lugar) necesiten una forma confiable de construir funciones de hashing "buenas". El hashing universal es un intento (exitoso) de formalizar qué es una función de hashing "buena", y también nos brinda herramientas para generar dichas funciones de manera eficiente para claves arbitrarias. Como no tengo ninguna experiencia en la industria, todo esto es desde un punto de vista teórico, pero espero que sean el camino a seguir.

G. Bach

@ G.Bach Gracias por sus comentarios. Pero sí quiero escuchar opiniones desde un punto de vista industrial.

Dai

@Dai Probablemente este no sea el lugar adecuado para obtener declaraciones de la industria.

Raphael

Hashing universal en la práctica

Respuestas: