Considere la lista humildemente vinculada en un entorno puramente funcional. Sus alabanzas se han cantado desde las cimas de las montañas y se seguirán cantando. Aquí abordaré uno de sus muchos puntos fuertes y la cuestión de cómo se puede extender a la clase más amplia de secuencias puramente funcionales basadas en árboles.
El problema es el siguiente: desea probar la igualdad estructural casi segura en el tiempo O (1) mediante un hashing fuerte. Si la función hash es estructuralmente recursiva, es decir, hash (x: xs) = mix x (hash xs), puede almacenar en caché de forma transparente los valores hash en las listas y actualizarlos en el momento O (1) cuando un elemento se integra en una lista existente . La mayoría de los algoritmos para las listas de hash son estructuralmente recursivos, por lo que este enfoque es eminentemente utilizable en la práctica.
Pero suponga que, en lugar de listas enlazadas individualmente, tiene secuencias basadas en árboles que admiten la concatenación de dos secuencias de longitud O (n) en el tiempo O (log n). Para que el almacenamiento en caché de hash funcione aquí, la función de mezcla de hash debe ser asociativa para respetar los grados de libertad que tiene un árbol para representar la misma secuencia lineal. El mezclador debe tomar los valores hash de los subárboles y calcular el valor hash de todo el árbol.
Aquí es donde estaba hace seis meses cuando pasé un día reflexionando e investigando este problema. Parece no haber recibido atención en la literatura sobre estructuras de datos. Me encontré con el algoritmo de hash Tillich-Zemor de la criptografía. Se basa en la multiplicación de matriz 2x2 (que es asociativa) donde los bits 0 y 1 corresponden a los dos generadores de un subálgebra con entradas en un campo de Galois.
Mi pregunta es, ¿qué me he perdido? Debe haber documentos relevantes tanto en la literatura sobre criptografía como en las estructuras de datos que no pude encontrar en mi búsqueda. Cualquier comentario sobre este problema y posibles lugares para explorar sería muy apreciado.
Editar: Estoy interesado en esta pregunta tanto en los extremos suaves y criptográficamente fuertes del espectro. En el lado más suave, se puede usar para tablas hash donde se deben evitar colisiones pero no son catastróficas. En el lado más fuerte, puede usarse para pruebas de igualdad.
La familia casi universal de funciones hash
fuente
fuente