No entiendo muy bien cómo funciona el hashing universal. Por ejemplo, cuando inserto un elemento en mi tabla hash, tengo que elegir una función aleatoria de mi familia universal de funciones hash. Ahora quiero recuperar dicho artículo. ¿Cómo sabrá mi tabla hash qué función debe usar para calcular el hash?Hashing universal
Porque usará la misma función hash para todos los elementos de la tabla.
¿Quiere decir que la elección (aleatoria) de la función hash se realiza en el momento de la construcción, no en cada operación de inserción? –
@iuliux: Correcto. La sal, si se usa, puede diferir (y se almacenará con el inserto), pero el algoritmo será el mismo. –
todavía no entiendo cómo recuperar el número que hasteamos con una función hash aleatoria. – user65165
Qué función hash se usa es aleatoria solo en el sentido de que no son predecibles por un adversario pero la elección es una función de la clave. Hay una buena escritura en http://www.cs.ucsb.edu/~suri/cs130a/Hashing.txt El método de la matriz es más fácil de entender que otros métodos ...
¿Algún enlace más reciente? Está roto ahora. –
¿Qué idioma está utilizando? – Gerben
@Gerben: ninguna. Esta es una pregunta conceptual. – ryyst