2018-08-13-hashable.md

title	author	translator	category	excerpt	status
Hashable / Hasher	Mattt	Vincent Pradeilles	Swift	Notre sujet de cette semaine est le protocol `Hashable` et le nouveau type qui lui est lié : `Hasher`. À eux deux, ils comprennent les fonctionnalités sous-jacentes à deux des collections les plus appréciées de Swift : `Dictionnary` et `Set`.	swift 4.2

Lorsque vous prenez un rendez-vous au Genius Bar d'un Apple Store, il vous est demandé de venir à une certaine heure et de vous annoncer auprès de l'accueil. Après vous avoir dirigé vers un tabouret libre, le préposé vous ajoute à la file d'attente, et remplit un formulaire qui indique comment vous reconnaître.

D'après les témoignages anonymes d'anciens employés, il existe des consignes strictes sur les termes utilisables pour décrire un client. Rien relevant de leur apparence physique ne peut être employé : âge, sexe, origine ethnique, taille --- pas même la couleur des cheveux. À la place, les clients sont décrits d'après leurs habits, tel que : "Personne portant un col roulé noir, un jean et des lunettes".

Cette technique pour décrire un client a beaucoup de traits communs avec les fonctions de hachage que l'on rencontre en programmation. Comme toute bonne fonction de hachage, elle est cohérente, facile à réaliser, et permet de rapidement identifier un élément, ou, ici, un individu. Bien plus efficace qu'une file d'attente, n'est-ce pas ?

Notre sujet de cette semaine est le protocol Hashable et le nouveau type qui lui est lié : Hasher. À eux deux, ils comprennent les fonctionnalités sous-jacentes à deux des collections les plus appréciées de Swift : Dictionnary et Set.

---

Imaginons que vous ayez une liste d'objets dont l'égalité peut être testée deux-à-deux. Pour identifier un objet particulier de cette liste, vous itérez sur ses éléments jusqu'à trouver une correspondance. Au fur et à mesure que des éléments viennent s'ajouter à la liste, le temps moyen nécessaire à identifier l'un d'entre-eux augmente linéairement (O(n)).

Alors que, si ces mêmes objets avaient été stockés dans un ensemble, il aurait été théoriquement possible d'y identifier un élément en un temps constant (O(1)) --- c'est à dire qu'une recherche dans un ensemble de 10 éléments nécessiterait autant de temps que dans un ensemble qui en compterait 10 000^*. Comment cela fonctionne-t-il ? Au lieu de stocker des objets séquentiellement, un ensemble utilise une fonction de hachage pour calculer une empreinte de chaque objet, à partir de son contenu. Lorsque l'on recherche un objet dans un ensemble, la même fonction de hachage est mise en oeuvre pour calculer l'empreinte de l'objet recherché, et la comparer à celles contenues dans l'ensemble.

^* Deux objets produisent une collision lorsque qu'ils possèdent la même empreinte alors que leurs contenus diffèrent. Lorsqu'une collision a lieu lors d'une insertion, les deux objets sont stockés dans une liste, identifiée par leur empreinte commune. Plus le taux de collision sera haut, plus la performance de la collection deviendra linéaire.

Hashable

En Swift, le type Array fourni l'interface nécessaire à une liste, et le type Set celle nécessaire à un ensemble. Pour qu'un objet puisse être stocké dans un Set, son type doit implémenter le protocole Hashable, (ainsi que, de fait, Equatable). Swift propose également le type Dictionary, qui implémente l'interface d'un tableau associatif, et ce dernier impose la même contrainte à son paramètre générique Key.

Dans des versions précédentes du langage, une bonne dose de code boilerplate était requise pour permettre à un type d'être stocké dans un Set ou un Dictionary./

Considérons le type Color ci-dessous, qui représente une couleur via trois valeurs sur 8 bits, indiquant la quantité de rouge, vert et bleu :

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

Pour se conformer à Equatable, il fallait définir une implémentation de l'opérateur ==. Pour se conformer à Hashable, il faillait définir une implémentation de la propriété calculée 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
    }
}

Pour une majorité de développeurs, devoir implementer Hashable était une source de ralentissement dans la bonne marche de leur travail, alors ils se contentaient de faire un OU exclusif entre toutes les propriétés d'un objet, et n'allaient pas plus loin.

Un inconvénient de cette approche est qu'elle génère un fort taux de collisions. Étant donné que la fonction OU exclusif est commutative, des couleurs aussi différentes que le cyan et le jaune produisent une collision :

// 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, collision

Dans la plupart des cas, cela ne pose pas de réel problème. Les ordinateurs modernes sont tellement puissants qu'il faudrait un grand nombre d'erreurs de ce type avant de pouvoir remarquer une baisse de performances.

Mais cela ne veut pas dire que de tels détails peuvent être négligés --- bien souvent ils revêtent une importance capitale. Nous y reviendrons plus loin.

Se Conformer Automatiquement à Hashable

Depuis Swift 4.1, le compilateur est capable d'automatiquement générer le code nécessaire pour adopter les protocoles Equatable et Hashable. Il suffit pour cela que les protocoles soient adoptés lors de la déclaration du type (et non via une extension) et que leurs propriétés implémentent également ces mêmes protocoles.

En plus d'améliorer significativement la vitesse de développement, cela permet de réduire drastiquement la taille du code source. Par exemple, notre type Color évoqué plus haut, voit sa taille réduite de deux tiers :

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

Malgré ces améliorations indéniables du langage, quelques questions restent tout de même en suspend quant aux détails d'implémentations.

Dans cette proposition d'évolution de Swift SE-0185: Synthesizing Equatable and Hashable conformance, Tony Allevato faisait l'observation suivante à propos des fonctions de hachage :

Le choix d'une fonction de hachage est laissé comme un détail d'implémentation et non un comme élément défini par les spécifications. Ainsi, les utilisateurs ne devraient pas dépendre des caractéristiques de son comportement. L'implémentation la plus probable appliquerait la fonction _mixInt de la librairie standard à la hashValue de chaque propriété, puis combinerait ces résultats via un OU exclusif (^). Il s'agit de la manière dont, à ce jour, les différentes Collections sont hachées.

Heureusement, il n'aura pas fallu longtemps à Swift pour se choisir une fonction de hachage. La réponse est arrivée avec la version suivante :

Hasher

Swift 4.2 continue dans l'amélioration de Hashable en introduisant le nouveau type Hasher, et en adoptant une nouvelle fonction universelle de hachage.

La proposition d'évolution SE-0206: Hashable Enhancements indique :

Avec une bonne fonction de hachage, les recherches simples, insertions et suppressions s'exécutent, en moyenne, en un temps constant. Cependant, lorsque la fonction de hachage choisie n'est pas adaptée aux données sur lesquelles elle opère, la durée de ces opérations peut devenir proportionnelle au nombre d'éléments stockés dans la table.

Comme le remarquent Karoy Lorentey et Vincent Esche, tout l'intérêt de type comme Set et Dictionary réside dans leur capacité à y rechercher une valeur en un temps constant. Si la fonction de hachage ne distribue pas ses valeurs de façon uniforme, ces types deviennent aussi peu efficace qu'une liste chainée.

Swift 4.2 implémente le mécanisme de hachage en s'appuyant sur la famille de fonctions pseudo-aléatoires SipHash, plus précisément SipHash-1-3 et SipHash-2-4, avec respectivement 1 à 2 cycles de hachage par bloc de message et 3 à 4 cycles de finalisation.

Désormais, si vous souhaitez customiser la façon dont un type implémente Hashable, vous pouvez redéfinir la méthode hash(into:), au lieu de la propriété hashValue. La méthode hash(into:) reçoit un paramètre inout sur lequel la méthode combine(_:) doit être appelée, avec comme paramètre chacune des propriétés que vous souhaitez prendre en compte dans le calcul de l'empreinte.

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

    // Synthesized by compiler
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.red)
        hasher.combine(self.green)
        hasher.combine(self.blue)
    }

    // Default implementation from protocol extension
    var hashValue: Int {
        var hasher = Hasher()
        self.hash(into: &hasher)
        return hasher.finalize()
    }
}

En encapsulant les problématiques de bas niveau, les développeurs sont maintenant capable de facilement exploiter les possibilités de la fonction de hachage fournie par Swift, avec l'avantage appréciable de ne plus aboutir aux situations de collision que nous rencontrions avec notre implémentation à base de OU exclusifs :

// 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, no collision

Customiser une Fonction de Hachage

Par défaut, Swift utilise une fonction universelle de hachage qui transforme une séquence d'octets en un seul nombre entier.

Toutefois, vous pouvez améliorer ce comportement en utilisant une fonction de hachage plus appropriée aux données que vous manipulez. Par exemple, si vous écrivez un programme permettant de jouer à un jeu de plateau, tel que les échecs ou le go, vous pourriez implémenter un hachage de Zobrist, pour stocker plus rapidement l'état du plateau.

Se Prémunir Contre un Hash-Flooding

Le choix d'un algorithme cryptographique tel que SipHash permet de se protéger contre une attaque de type hash-flooding DoS, qui essaye de délibérément générer des collisions dans le but provoquer volontairement une baisse de performance. Cette vulnérabilité est responsable de tout un tas de problèmes sur le web du début des années 2010.

Pour rendre les choses plus sûres, Hasher initialise son générateur de valeurs aléatoires avec une graine différente à chaque fois qu'une app est lancée, de manière à rendre les empreintes encore plus difficiles à prédire.

{% info do %}

Votre code ne devrait pas supposer qu'une empreinte sera la même d'une exécution à l'autre. Dans les rares cas où vous auriez besoin de ce comportement déterministe, le paramètre SWIFT_DETERMINISTIC_HASHING peut être ajouté aux options de compilation pour désactiver l'utilisation de graines aléatoires.

{% endinfo %}

---

Toute la difficulté des métaphores informatiques est qu'elles tendent à normaliser les comportements antisociaux que leurs cas limites impliquent.

Nous accomplissions avec succès notre travail d'ingénieurs logiciel lorsque nous sommes capable d'anticiper toutes les manières dont un attaquant peut s'appuyer sur un comportement particulier pour atteindre un but néfaste --- comme dans le cas d'une attaque hash-flooding DoS. Mais en faisant cela, nous risquons d'échouer en tant qu'humains si nous appliquons ce savoir à la vie réelle.

Tout cela pour dire... Nous ne vous encourageons pas, cher lecteur, lors de votre prochaine visite dans votre Apple Store, à coordonner votre habillement avec celui de vos amis, afin de répandre la confusion et le trouble chez les Genius.

Ne faites pas cela.

A la place, considérez plutôt cette remarque :

Si vous êtes entrain d'attendre au Genius Bar, éloignez vous de toute personne qui porte une chemise de la même couleur que la votre. Cela simplifiera la vie de tout le monde.