El rasgo Hash fue diseñado para soportar colecciones basadas en hashes como HashMap y HashSet. La biblioteca estándar de Rust exige que cualquier tipo que implemente Eq también implemente Hash de tal manera que si k1 == k2, entonces hash(k1) == hash(k2). Esta invariante asegura que las tablas hash resuelvan correctamente las colisiones.
El problema surge cuando dos instancias distintas se comparan como iguales (según Eq) pero producen digestos de hash diferentes. En este escenario, un HashMap podría colocar estas claves "iguales" en diferentes cubos. Busquedas posteriores podrían fallar en encontrar entradas existentes, o inserciones podrían crear duplicados, violando el contrato semántico del mapa de claves únicas.
La solución requiere mantener la sincronización a nivel de bits entre la lógica de igualdad y hashing. Al personalizar PartialEq y Eq para ignorar ciertos campos (por ejemplo, marcas de tiempo o hashes en caché), debes excluir esos campos de la implementación de Hash. Esto asegura que valores lógicos equivalentes siempre se asignen a códigos hash idénticos, preservando la integridad de la colección.
Considera un programador de tareas distribuido donde las estructuras Task sirven como claves en un HashMap que rastrea el estado de finalización. Cada Task contiene un id: Uuid, payload: Vec<u8>, y timestamp: Instant. Inicialmente, tanto Hash como Eq se derivan automáticamente. Sin embargo, los requisitos cambian: las tareas deben considerarse iguales si su id coincide, independientemente de payload o timestamp.
La primera solución considerada fue derivar ambos rasgos automáticamente a través de #[derive]. Este enfoque mantenía la consistencia estructural entre el hashing y la igualdad al incluir todos los campos, pero causó errores funcionales en la lógica empresarial. Específicamente, tareas con IDs idénticos pero diferentes marcas de tiempo se trataron como claves distintas, impidiendo actualizaciones de estado para tareas existentes y causando que el mapa se inflara con entradas obsoletas.
La segunda solución involucró implementar manualmente Eq para ignorar timestamp mientras se mantenía el Hash derivado. Esto parecía eficiente pero introdujo un error crítico. Dos tareas iguales por ID hashían diferente si sus marcas de tiempo divergían, causando que el HashMap las dispersara en cubos no relacionados:
impl PartialEq for Task { fn eq(&self, other: &Self) -> bool { self.id == other.id // Ignora la marca de tiempo } } // #[derive(Hash)] todavía hashía todos los campos incluyendo la marca de tiempo
Las búsquedas de estado de tarea fallarían aleatoriamente en encontrar entradas existentes, lo que llevaría a la ejecución duplicada de tareas y agotamiento de recursos.
La solución elegida fue la implementación manual de ambos Hash y Eq, asegurando que ambos consideraran solo el campo id:
impl Hash for Task { fn hash<H: Hasher>(&self, state: &mut H) { self.id.hash(state); // Solo hashía ID } }
Esto garantizó que tareas lógicamente equivalentes siempre colisionaran en el mismo cubo, permitiendo que HashMap identificara correctamente duplicados mediante chequeos de igualdad después de la colisión de hash.
El resultado fue un sistema estable donde la deduplicación de tareas funcionaba correctamente, eliminando la ejecución doble y manteniendo tiempos de búsqueda promedio de O(1). Este enfoque aseguró que el programador de tareas distribuido pudiera rastrear de manera confiable la finalización de tareas sin filtraciones de memoria o inconsistencias lógicas. La solución requirió pruebas cuidadosas para verificar que las colisiones de hash entre diferentes IDs se manejaban correctamente mediante la verificación de igualdad, confirmando que la lógica de igualdad parcial se integrara sin problemas con la implementación de la tabla hash de la biblioteca estándar.
¿Por qué debe Hash ser consistente con Eq pero no necesariamente con Ord?
La consistencia con Eq es obligatoria porque HashMap utiliza el hash para localizar un cubo y luego utiliza la igualdad (==) para resolver colisiones dentro de ese cubo. Si los elementos iguales hashían diferente, ocuparían cubos diferentes, haciendo que la verificación de igualdad fuera irrelevante durante la búsqueda y rompiendo la invariante de unicidad. Ord, sin embargo, define un orden total para colecciones ordenadas como BTreeMap, que no depende del hashing sino de árboles de comparación; así, Ord y Hash no tienen una relación contractual, y un tipo puede ser ordenable de una manera inconsistente con su hash sin comprometer la seguridad de memoria o la semántica de la colección.
¿Qué sucede si el método hash entra en pánico durante la inserción en un HashMap?
Si Hash entra en pánico, el HashMap queda en un estado intermedio donde la clave ha sido procesada parcialmente pero no completamente insertada. A diferencia de Mutex, HashMap no implementa envenenamiento. Sin embargo, la asignación de memoria subyacente para la entrada podría haber ocurrido sin que el valor estuviera completamente inicializado o vinculado a la cadena de la tabla. Esto puede llevar a filtraciones de memoria o, en casos extremos, comportamientos indefinidos si el pánico ocurre durante una operación de rehash donde la tabla se está redimensionando. La biblioteca estándar mitiga esto mediante el uso de guardias de eliminación y una gestión cuidadosa del estado, pero el código del usuario debe asegurar que las implementaciones de Hash estén libres de pánicos para garantizar la consistencia de la colección.
¿Cómo previene BuildHasher ataques HashDoS, y por qué es SipHasher el valor predeterminado?
BuildHasher abstrae la creación de instancias de Hasher, permitiendo que HashMap instancie un nuevo hasher con claves aleatorias para cada instancia de mapa. El valor predeterminado RandomState utiliza SipHasher-1-3 (o una variante similar) con claves generadas a partir de la fuente de entropía del sistema operativo. Esta aleatorización previene ataques HashDoS donde un atacante crea entradas que todos hashían al mismo cubo, degradando la búsqueda a O(n). Al sembrar cada mapa de manera diferente, se elimina la superficie de ataque porque el atacante no puede predecir qué entradas colisionarán. SipHasher fue elegido por su equilibrio entre seguridad criptográfica (previniendo la recuperación de claves) y velocidad, a diferencia de algoritmos más rápidos pero vulnerables como MurmurHash o hashes criptográficos más lentos como SHA-3.