Cómo implementar el protocolo Hashable en Swift para una matriz Int (una estructura de cadena personalizada)

Estoy creando una estructura que actúa como una String , excepto que solo trata los valores escalares Unicode UTF-32. Por lo tanto, es una matriz de UInt32 . (Consulte esta pregunta para get más información).

Lo que quiero hacer

Quiero poder usar mi struct ScalarString personalizada como key en un dictionary. Por ejemplo:

 var suffixDictionary = [ScalarString: ScalarString]() // Unicode key, rendenetworking glyph value // populate dictionary suffixDictionary[keyScalarString] = valueScalarString // ... // check if dictionary contains Unicode scalar string key if let rendenetworkingSuffix = suffixDictionary[unicodeScalarString] { // do something with value } 

Problema

Para hacer eso, ScalarString necesita implementar el Protocolo Hashable . Pensé que podría hacer algo como esto:

 struct ScalarString: Hashable { private var scalarArray: [UInt32] = [] var hashValue : Int { get { return self.scalarArray.hashValue // error } } } func ==(left: ScalarString, right: ScalarString) -> Bool { return left.hashValue == right.hashValue } 

pero luego descubrí que las matrices Swift no tienen un hashValue .

Lo que leo

El artículo Strategies for Implementing the Hashable Protocol en Swift tenía muchas buenas ideas, pero no vi ninguna que pareciera que funcionaría bien en este caso. Específicamente,

  • Propiedad del object (array is no tiene hashValue )
  • Propiedad ID (no estoy seguro de cómo esto podría implementarse bien)
  • Fórmula (parece que cualquier fórmula para una cadena de integers de 32 bits sería un procesador pesado y tiene un montón de desbordamiento de integers)
  • ObjectIdentifier (estoy usando una estructura, no una class)
  • Henetworkingando desde NSObject (estoy usando una estructura, no una class)

Aquí hay algunas otras cosas que leí:

  • Implementación del protocolo Hashable de Swift
  • Protocolos de comparación rápida
  • Perfecta function hash
  • Membresía de objects personalizados en matrices y dictionarys Swift
  • Cómo implementar Hashable para tu class personalizada
  • Escribir una buena implementación Hashable en Swift

Pregunta

Swift Strings tiene una propiedad hashValue , así que sé que es posible hacerlo.

¿Cómo crearía un hashValue para mi estructura personalizada?

Actualizaciones

Actualización 1: Me gustaría hacer algo que no involucre convertir a String y luego usar hashValue String . Todo mi punto de hacer mi propia estructura fue para que pudiera evitar hacer muchas conversiones de String . String obtiene su hashValue desde alguna parte. Parece que podría getlo usando el mismo método.

Actualización 2: He estado investigando la implementación de algorithms hash de códigos de cadenas desde otros contexts. Estoy teniendo un poco de dificultad para saber cuál es mejor y expresslas en Swift, sin embargo.

  • Java hashCode algorithm
  • Algoritmos C
  • function hash para cadena (pregunta SO y respuestas en C)
  • Tutorial de Hashing (Virginia Tech Algorithm Visualization Research Group)
  • Algoritmos de function hash de uso general

Actualización 3

Preferiría no importar ningún marco externo a less que esa sea la forma recomendada de search estas cosas.

Presenté una posible solución con la function DJB Hash.

Esta respuesta ha sido completamente reescrita después de enviar mi respuesta original a la revisión del código .

Cómo implementar el protocolo Hashable

El protocolo Hashable le permite usar su class personalizada o struct como una key de dictionary. Para implementar este protocolo, debe

  1. Implementar el protocolo Equatable (Hashable henetworkinga de Equatable)
  2. Devuelve un hashValue calculado

Estos puntos se derivan del axioma dado en la documentation:

x == y implica x.hashValue == y.hashValue

donde x e y son valores de algún tipo.

Implementar el protocolo Equatable

Para implementar el protocolo Equatable, define cómo su tipo utiliza el operador == (equivalencia). En su ejemplo, la equivalencia se puede determinar de la siguiente manera:

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

La function == es global por lo que se sale de tu class o struct.

Devuelve un hashValue calculado hashValue

Su class personalizada o struct también debe tener una variable hashValue calculada. Un buen algorithm de hash proporcionará una amplia gama de valores de hash. Sin embargo, se debe tener en count que no es necesario garantizar que los valores de hash sean únicos. Cuando dos valores diferentes tienen valores hash idénticos, esto se denomina colisión hash. Requiere un trabajo adicional cuando hay una colisión (por lo que es deseable una buena distribución), pero se deben esperar algunas colisiones. Según lo entiendo, la function == hace ese trabajo adicional. ( Actualización : Parece que == puede hacer todo el trabajo ) .

Hay varias forms de calcular el valor de hash. Por ejemplo, podría hacer algo tan simple como devolver el número de elementos en la matriz.

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

Esto daría una colisión de hash cada vez que dos arreglos tuvieran el mismo número de elementos pero diferentes valores. NSArray aparentemente usa este enfoque.

DJB Hash Function

Una function hash común que funciona con cadenas es la function hash de DJB. Este es el que voy a usar, pero mira algunos otros aquí .

A continuación se muestra una implementación rápida proporcionada por @MartinR :

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

Esta es una versión mejorada de mi implementación original, pero permítanme include también la forma expandida más antigua, que puede ser más legible para las personas que no están familiarizadas con networkinguce . Esto es equivalente, creo:

 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 } 

El operador &+ permite que Int desborde y comience de nuevo para cadenas largas.

Cuadro grande

Hemos visto las piezas, pero permítanme ahora mostrar todo el código de ejemplo en lo que se refiere al protocolo Hashable. ScalarString es el tipo personalizado de la pregunta. Esto será diferente para diferentes personas, por supuesto.

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

Otra lectura útil

  • ¿Qué algorithm de hash es mejor para la singularidad y la velocidad?
  • Operadores de desbordamiento
  • ¿Por qué son 5381 y 33 tan importantes en el algorithm djb2?
  • ¿Cómo se manejan las colisiones de hash?

Créditos

Muchas gracias a Martin R en Review Code. Mi reescritura se basa principalmente en su respuesta . Si consideras que esto es útil, entonces dale una respuesta.

Actualizar

Swift es de código abierto ahora, por lo que es posible ver cómo se implementa hashValue para String desde el código fuente . Parece ser más complejo que la respuesta que he dado aquí, y no he tomado el time para analizarlo por completo. Siéntete libre de hacerlo tú mismo.

Una sugerencia, ya que está modelando una String , ¿podría funcionar para convertir su matriz [UInt32] a una String y usar el hashValue la hashValue ? Me gusta esto:

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

Eso podría convenientemente permitirle comparar su struct personalizada también con String , aunque sea o no una buena idea depende de lo que esté intentando hacer …

Tenga en count también que, con este enfoque, las instancias de ScalarString tendrían el mismo hashValue si sus representaciones de String eran canónicamente equivalentes, lo que puede o no ser lo que desea.

Entonces, supongo que si quieres que hashValue represente una String única, mi enfoque sería bueno. Si quiere que hashValue represente una secuencia única de valores UInt32 , la respuesta de @ Kametrixom es el path a seguir …

Editar (31 de mayo de 17): consulte la respuesta aceptada. Esta respuesta es más que una simple demostración de cómo usar CommonCrypto Framework

De acuerdo, Hashable y extendí todos los arreglos con el protocolo Hashable utilizando el algorithm de hashing SHA-256 del marco CommonCrypto. Tienes que poner

 #import <CommonCrypto/CommonDigest.h> 

en su encabezado de puente para que esto funcione. Sin embargo, es una lástima que se utilicen pointers:

 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] } } 

Edición (31 de mayo de 17): No hagas esto, aunque SHA256 tiene casi ninguna colisión hash, es una idea equivocada definir la igualdad por igualdad hash

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

Esto es tan bueno como lo hace con CommonCrypto . Es feo, pero rápido y no muchas, casi no hay colisiones hash, seguro

Edición (15 de julio de 15): acabo de hacer algunas testings de velocidad:

Las matrices Int aleatorias de tamaño n tomaron en promedio más de 1000 tiradas

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

Mientras que con el método de cadena de hashing:

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

Entonces, la forma SHA-256 es aproximadamente 33 veces más rápida que la forma de la cadena. No digo que usar una cadena sea una buena solución, pero es la única en la que podemos compararlo ahora mismo.

No es una solución muy elegante pero funciona muy bien:

 "\(scalarArray)".hashValue 

o

 scalarArray.description.hashValue 

Que simplemente usa la representación textual como una fuente hash