Cette réponse a été complètement réécrite après avoir soumis ma réponse originale à l'examen du code .

Comment mettre en œuvre au protocole Hashable

Le protocole Hashable vous permet d'utiliser votre class ou structure personnalisée en tant que key de dictionary. Afin de mettre en œuvre ce protocole, vous devez

1. Implémenter le protocole Equatable (Hashable hérite de Equatable)
2. Renvoie une hashValue calculée

Ces points découlent de l'axiome donné dans la documentation:

x == y implique x.hashValue == y.hashValue

où x et y sont des valeurs de type.

Implémenter le protocole Equatable

Pour implémenter le protocole Equatable, vous définissez comment votre type utilise l'opérateur == (équivalence). Dans votre exemple, l'équivalence peut être déterminée comme ceci:

 func ==(left: ScalarSsortingng, right: ScalarSsortingng) -> Bool { return left.scalarArray == right.scalarArray } 

La fonction == est globale donc elle sort de votre class ou structure.

Renvoie une hashValue calculée

Votre class ou structure personnalisée doit également avoir une variable hashValue calculée. Un bon algorithm de hachage fournira une large gamme de valeurs de hachage. Cependant, il convient de noter que vous n'avez pas besoin de garantir que les valeurs de hachage sont toutes uniques. Lorsque deux valeurs différentes ont des valeurs de hachage identiques, cela s'appelle une collision de hachage. Cela nécessite un travail supplémentaire en cas de collision (c'est pourquoi une bonne dissortingbution est souhaitable), mais certaines collisions sont à prévoir. Si je comprends bien, la fonction == fait ce travail supplémentaire. ( Mise à jour : Il semble que == peut faire tout le travail. )

Il existe plusieurs façons de calculer la valeur de hachage. Par exemple, vous pourriez faire quelque chose d'aussi simple que de returnner le nombre d'éléments dans le tableau.

 var hashValue: Int { return self.scalarArray.count } 

Cela donnerait une collision de hachage chaque fois que deux arrays ont le même nombre d'éléments mais des valeurs différentes. NSArray utilise apparemment cette approche.

Fonction de hachage DJB

Une fonction de hachage commune qui fonctionne avec les strings est la fonction de hachage DJB. C'est celui que je vais utiliser, mais vérifiez d'autres ici .

Une implémentation Swift fournie par @MartinR suit:

 var hashValue: Int { return self.scalarArray.reduce(5381) { ($0 << 5) &+ $0 &+ Int($1) } } 

Ceci est une version améliorée de mon implémentation d'origine, mais permettez-moi d'inclure également le formulaire développé plus ancien, qui peut être plus lisible pour les personnes qui ne connaissent pas reduce . C'est équivalent, je crois:

 var hashValue: Int { // DJB Hash Function var hash = 5381 for(var i = 0; i < self.scalarArray.count; i++) { hash = ((hash << 5) &+ hash) &+ Int(self.scalarArray[i]) } return hash } 

L'opérateur &+ permet à Int de déborder et de recommencer pour les longues strings.

Grande image

Nous avons regardé les pièces, mais laissez-moi maintenant montrer l'set du code d'exemple en ce qui concerne le protocole Hashable. ScalarSsortingng est le type personnalisé de la question. Ce sera différent pour différentes personnes, bien sûr.

 // Include the Hashable keyword after the class/struct name struct ScalarSsortingng: Hashable { private var scalarArray: [UInt32] = [] // required var for the Hashable protocol var hashValue: Int { // DJB hash function return self.scalarArray.reduce(5381) { ($0 << 5) &+ $0 &+ Int($1) } } } // required function for the Equatable protocol, which Hashable inheirits from func ==(left: ScalarSsortingng, right: ScalarSsortingng) -> Bool { return left.scalarArray == right.scalarArray } 

Autre lecture utile

• Quel algorithm de hachage est le meilleur pour l'unicité et la vitesse?
• Opérateurs de débordement
• Pourquoi 5381 et 33 sont-ils si importants dans l'algorithm djb2?
• Comment sont traitées les collisions de hash?

Crédits

Un grand merci à Martin R dans Code Review. Ma réécriture est largement basée sur sa réponse . Si vous avez trouvé cela utile, alors s'il vous plaît lui donner un upvote.

Mettre à jour

Swift est open source maintenant il est donc possible de voir comment hashValue est implémenté pour Ssortingng partir du code source . Cela semble être plus complexe que la réponse que j'ai donnée ici, et je n'ai pas pris le time de l'parsingr complètement. N'hésitez pas à le faire vous-même.

Une suggestion – puisque vous modélisez une Ssortingng , cela fonctionnerait-il pour convertir votre tableau [UInt32] en Ssortingng et utiliser le hashValue ? Comme ça:

 var hashValue : Int { get { return Ssortingng(self.scalarArray.map { UnicodeScalar($0) }).hashValue } } 

Cela pourrait facilement vous permettre de comparer votre struct personnalisée à celle de Ssortingng s, même si cela dépend de ce que vous essayez de faire …

Notez également que, en utilisant cette approche, les instances de ScalarSsortingng auraient la même valeur hashValue si leurs représentations Ssortingng étaient canoniquement équivalentes, ce qui peut être ou ne pas être ce que vous désirez.

Donc je suppose que si vous voulez que hashValue représente une Ssortingng unique, mon approche serait bonne. Si vous voulez que hashValue représente une séquence unique de valeurs UInt32, la réponse de @ Kamesortingxom est la voie à suivre …

Edit (31 mai '17): Veuillez vous référer à la réponse acceptée. Cette réponse est à peu près une démonstration sur l'utilisation de CommonCrypto Framework

D'accord, je suis Hashable l'avant et étendu tous les arrays avec le protocole Hashable en utilisant l'algorithm de hachage SHA-256 de la structure CommonCrypto. Vous devez mettre

 #import <CommonCrypto/CommonDigest.h> 

dans votre en-tête de pontage pour que cela fonctionne. Il est dommage que les pointeurs doivent être utilisés si:

 extension Array : Hashable, Equatable { public var hashValue : Int { var hash = [Int](count: Int(CC_SHA256_DIGEST_LENGTH) / sizeof(Int), repeatedValue: 0) withUnsafeBufferPointer { ptr in hash.withUnsafeMutableBufferPointer { (inout hPtr: UnsafeMutableBufferPointer<Int>) -> Void in CC_SHA256(UnsafePointer<Void>(ptr.baseAddress), CC_LONG(count * sizeof(Element)), UnsafeMutablePointer<UInt8>(hPtr.baseAddress)) } } return hash[0] } } 

Edit (31 mai '17): Ne faites pas cela, même si SHA256 n'a pratiquement pas de collisions de hachage, c'est une mauvaise idée de définir l'égalité par l'égalité de hachage

 public func ==<T>(lhs: [T], rhs: [T]) -> Bool { return lhs.hashValue == rhs.hashValue } 

C'est aussi bon qu'avec CommonCrypto . C'est moche, mais rapide et pas beaucoup de collisions de hachage à peu près à coup sûr

Edit (15 juillet 15): Je viens de faire quelques tests de vitesse:

Les arrays Int de taille n, pris au hasard, ont pris en moyenne plus de 1000 passages

 n -> time 1000 -> 0.000037 s 10000 -> 0.000379 s 100000 -> 0.003402 s 

Alors qu'avec la méthode de hachage de la string:

 n -> time 1000 -> 0.001359 s 10000 -> 0.011036 s 100000 -> 0.122177 s 

Ainsi, la manière SHA-256 est environ 33 fois plus rapide que la manière de la corde. Je ne dis pas que l'utilisation d'une string est une très bonne solution, mais c'est la seule que l'on puisse comparer

Ce n'est pas une solution très élégante mais ça marche bien:

 "\(scalarArray)".hashValue 

ou

 scalarArray.description.hashValue 

Qui utilise simplement la représentation textuelle comme source de hachage