Hashable / Hasher

Cuando pides cita para la Genius Bar en una Apple Store, te indican que acudas a un día y hora determinados para ser atendido por un encargado. Después de indicarte que tomes asiento, el encargado te añade a la cola y hace unos apuntes para poder identificarte.

De acuerdo a unos informes anónimos de antiguos empleados, hay reglas estrictas acerca de cómo puede describirse un cliente. No puede usarse ningún dato relativo a su aspecto físico: edad, género, etnia, altura… ni siquiera el color del pelo. En su lugar, los clientes se describen de acuerdo a su ropa, del modo «Persona con jersey negro de cuello alto, vaqueros y gafas».

Esta práctica de describir clientes tiene mucho en común con las funciones de hashing en programación. Cualquier función hash buena es consistente, fácil de computar y se puede usar para encontrar lo que (o a quien) estás buscando. ¡Mucho mejor que una cola!

El tema de esta semana es Hashable y su tipo relacionado, Hasher. Juntos, forman parte de la funcionalidad subyacente de dos de las clases más queridas de Swift: Diccionary y Set.

---

Imagina que tienes una lista de objetos que pueden compararse por igualdad. Para encontrar un objeto en concreto de esa lista, iteras todos los elementos hasta encontrar una coincidencia. A medida que añades más elementos a la lista, la cantidad media de tiempo necesario para encontrar un objeto aumenta linealmente (O(n)).

En cambio, si almacenas esos objetos en un set (conjunto), puedes encontrar teóricamente cualquier objeto en un tiempo constante (O(1)). Es decir, una búsqueda en un set de 10 elementos tarda lo mismo que una búsqueda en uno de 10000^*. ¿Cómo es posible? En lugar de almacenar objetos secuencialmente, un set usa un hash como índice, basado en el contenido del objeto. Cuando realizas una búsqueda en un set, usas la función para calcular el hash y buscar el objeto allí.

^* Dos objetos producen una colisión de hashes si tienen el mismo valor de hash pero no son iguales. Cuando ocurre una colisión en una inserción, se almacenan en una lista en esa dirección. Cuanto mayor sea la tasa de colisión entre objetos, más lineal será el rendimiento de la colección de hashes.

Hashable

En Swift, la clase Array es la interfaz estándar para listas, y Set para sets. Para que un objeto pueda guardarse en un Set, su tipo debe conformar Hashable (y, por extensión, Equatable). La interfaz estándar de mapas, Dictionary, requiere lo mismo en su tipo clave (Key).

En versiones anteriores del lenguaje, se requería un poco de código repetitivo a la hora de satisfacer los requisitos para almacenar un tipo personalizado en un Set o Dictionary.

Considera el siguiente tipo Color, el cual usa valores de 8-bits para representar la intensidad del rojo, verde y azul:

struct Color {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
}

Para conformar Equatable, tenías que proveer una implementación del operador ==. Y para conformar Hashable, tenías que proveer una implementación de la propiedad computada hashValue:

// Swift < 4.1
extension Color: Equatable {
    static func ==(lhs: Color, rhs: Color) -> Bool {
        return lhs.red == rhs.red &&
               lhs.green == rhs.green &&
               lhs.blue == rhs.blue
    }
}

extension Color: Hashable {
    var hashValue: Int {
        return self.red.hashValue ^
               self.green.hashValue ^
               self.blue.hashValue
    }
}

La mayoría de desarrolladores se quitaban rápidamente de encima la implementación de Hashable haciendo un XOR de todas las propiedades del tipo.

Pero un inconveniente de este método es su alta tasa de colisiones de hashes. Como XOR es conmutativo, colores tan dispares como el cian y el amarillo producen colisiones:

// Swift < 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)

cyan.hashValue == yellow.hashValue // true, colisión

Esto no es un problema en la mayoría de ocasiones; las computadoras modernas son tan potentes que tienes que meter mucho la pata en detalles de implementación para notar una bajada del rendimiento.

Pero eso no quiere decir que los detalles no importen; a menudo importan inmensamente. Veremos más sobre esto después.

Conformando Hashable automáticamente

A partir de Swift 4.1, el compilador sintetiza y conforma los protocolos Equatable y Hashable automáticamente para tipos que adopten dichos protocolos en su declaración si sus miembros también los conforman.

A parte de ser un enorme empujón en la productividad del desarrollador, esto puede reducir drásticamente la cantidad de código del proyecto. Por ejemplo, nuestro tipo Color de antes es ahora ⅓ de su tamaño original:

// Swift >= 4.1
struct Color: Hashable {
    let red: UInt8
    let green: UInt8
    let blue: UInt8
}

Pero a pesar de estas mejoras inequívocas en el lenguaje, todavía quedaba en el aire una cuestión sobre algunos detalles de implementación.

En esta propuesta de evolución de Swift SE-0185: Synthesizing Equatable and Hashable conformance, Tony Allevato escribió esta nota acerca de funciones hash:

La elección de la función hash se deja como detalle de implementación, no como parte fija del diseño; por lo que los usuarios no deberían depender de características específicas de su comportamiento. La implementación más probable llamaría a la función mixInt, de la librería estándar, para el hash de cada miembro y los combinaría luego con un XOR (^), que es como se hace actualmente para los tipos Collection.

Afortunadamente, Swift no tardó en establecer una función hash. Tuvimos respuesta en la siguiente versión:

Hasher

Swift 4.2 refina Hashable aún más introduciendo el tipo Hasher y adoptando una nueva función hash universal.

En la propuesta de evolución de Swift SE-0206: Hashable Enhancements, vemos:

Con una buena función hash, búsquedas simples, inserciones y extracciones toman un tiempo medio constante. Sin embargo, cuando la funcion hash no se escoge cuidadosamente para ajustarse a la naturaleza de los datos, el tiempo esperado de tales operaciones puede llegar a ser proporcional al número de elementos almacenados en la tabla.

Como Karoy Lorentey y Vincent Esche indican, el principal atractivo de colecciones basadas en hashes, como Set y Dictionary, es la capacidad de buscar valores en tiempo constante. Si la función hash no produce una distribución uniforme de valores, estas colecciones se comportan como listas enlazadas.

Swift 4.2 implementa hashing basado en la familia de funciones pseudo-aleatorias SipHash, concretamente SipHash-1-3 y SipHash-2-4, con 1 o 2 rondas de hashing por bloque de mensaje y 3 o 4 rondas de finalización, respectivamente.

Si quieres personalizar la forma en la que tu tipo implementa Hashable, puedes sobreescribir el método hash(into:) en lugar de hashValue. El método hash(into:) pasa un objeto Hasher por referencia, con el cual llamas a combine(_:) para añadir información de estado importante de tu tipo.

// Swift >= 4.2
struct Color: Hashable {
    let red: UInt8
    let green: UInt8
    let blue: UInt8

    // Sintetizado por el compilador
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.red)
        hasher.combine(self.green)
        hasher.combine(self.blue)
    }

    // Implementación por defecto de la extensión del protocolo
    var hashValue: Int {
        var hasher = Hasher()
        self.hash(into: &hasher)
        return hasher.finalize()
    }
}

Los desarrolladores aprovechan esta funcionalidad incorporada en Swift para abstraerse de manipular bits a bajo nivel, lo cual tiene el beneficio extra de evitar las colisiones que teníamos en la implementación basada en XOR:

// Swift >= 4.2
let cyan = Color(red: 0x00, green: 0xFF, blue: 0xFF)
let yellow = Color(red: 0xFF, green: 0xFF, blue: 0x00)

cyan.hashValue == yellow.hashValue // false, sin colisión

Personalizando la función hash

Por defecto, Swift usa una función hash universal que reduce una secuencia de bytes a un único entero.

Sin embargo, puedes mejorar esto adaptando la función hash a tu dominio. Por ejemplo, si fueras a escribir un programa de juego de tablero como el ajedrez o el go, podrías implementar el Zobrist hashing para almacenar el estado del juego.

Protegiéndote contra Hash-Flooding

Elegir un algoritmo criptográfico como SipHash ayuda a proteger contra ataques de tipo hash-flooding DoS, los cuales intentan generar colisiones de hashes deliberadamente en un intento de ralentizar y detener el programa. Esto causó gran cantidad de problemas al inicio de la década de 2010.

Para hacer las cosas aún más seguras, Hasher genera semillas aleatorias cada vez que se lanza una app, haciendo que los valores hash sean incluso menos predecibles.

No deberías depender de valores hash específicos ni preservarlos entre ejecuciones. En el hipotético caso de que necesites comportamiento determinista, puedes activar el flag SWIFT_DETERMINISTIC_HASHING para desactivar las semillas hash aleatorias. No deberías depender de valores consistentes, pero podrías usar el determinismo con fines de prueba.

---

El problema de hacer analogías con la programación es que se normaliza comportamiento antisocial a través de edge cases.

Como ingenieros de software, destacamos a la hora de ver todas las formas en las que un atacante puede aprovecharse, con fines maliciosos, de un comportamiento en particular; como en el caso de los ataques hash-flooding DoS. Pero si nos aprovecharnos de esto fuera del teclado nos arriesgamos a fallar como personas.

Así que no te estoy animando, querido lector, a coordinar esfuerzos con tus amigos para sembrar la confusión y la discordia entre los encargados de la Genius Bar la próxima vez que visites una Apple Store.

Por favor, no lo hagas.

En cambio, míralo de esta manera:

Si estás esperando en la Genius Bar, mantente lejos de cualquiera que lleve una camiseta del mismo color que la tuya. Facilitará mucho las cosas.