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

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

Lo que quiero hacer

Quiero poder usar mi estructura ScalarString personalizada como clave en un diccionario. Por ejemplo:

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

Problema

Para hacer eso, ScalarString necesita implementar el Protocolo Hashable . Pensé que sería capaz de 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 Estrategias para implementar el protocolo Hashable en Swift tenía muchas ideas geniales, pero no vi ninguna que pareciera que funcionaría bien en este caso. Específicamente,

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

Aquí hay algunas otras cosas que leo:

  • Implementando el Protocolo Hashable de Swift
  • Protocolos de comparación Swift
  • Función hash perfecta
  • Membresía de objetos personalizados en matrices Swift y diccionarios
  • Cómo implementar Hashable para su clase 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 implique convertir a String y luego utilizar el hashValue String . Todo mi punto para hacer mi propia estructura fue para poder evitar hacer muchas conversiones de String . String obtiene su hashValue de algún lado. Parece que podría obtenerlo usando el mismo método.

Actualización 2: he estado investigando la implementación de algoritmos de códigos hash de cadenas de otros contextos. Sin embargo, estoy teniendo un poco de dificultad para saber qué es lo mejor y expresslo en Swift.

  • Algoritmo hashCode Java
  • Algoritmos C
  • función hash para cadena (preguntas y respuestas SO en C)
  • Tutorial de Hashing (Grupo de investigación de visualización del algoritmo de Virginia Tech)
  • Algoritmos de función hash de propósito general

Actualización 3

Preferiría no importar ningún marco externo a menos que sea la forma recomendada de hacerlo.

Envié una posible solución usando la función 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 clase o estructura personalizada como una clave de diccionario. Para implementar este protocolo, necesita

  1. Implemente el protocolo Equatable (Hashable hereda de Equatable)
  2. Devuelve un hashValue calculado

Estos puntos se derivan del axioma dado en la documentación:

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

donde y son valores de algún tipo.

Implementar el protocolo Equatable

Para implementar el protocolo Equatable, usted define cómo su tipo usa el operador == (equivalencia). En su ejemplo, la equivalencia puede determinarse así:

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

La función == es global, por lo que sale de tu clase o estructura.

Devuelve un hashValue calculado

Su clase o estructura personalizada también debe tener una variable hashValue calculada. Un buen algoritmo hash proporcionará una amplia gama de valores hash. Sin embargo, debe tenerse en cuenta que no necesita garantizar que los valores hash sean únicos. Cuando dos valores diferentes tienen valores hash idénticos, esto se denomina colisión hash. Requiere algo de trabajo extra cuando hay una colisión (por lo que es deseable una buena distribución), pero se esperan algunas colisiones. Según lo entiendo, la función == hace ese trabajo extra. ( Actualización : parece que == puede hacer todo el trabajo ) .

Hay una serie de formas de calcular el valor hash. Por ejemplo, podría hacer algo tan simple como devolver la cantidad de elementos en la matriz.

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

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

Función DJB Hash

Una función hash común que funciona con cadenas es la función hash DJB. Este es el que voy a utilizar, pero echa un vistazo a algunos otros aquí .

Una implementación Swift proporcionada por @MartinR sigue:

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

Esta es una versión mejorada de mi implementación original, pero permítanme también incluir el formulario expandido anterior, que puede ser más legible para personas que no están familiarizadas con reduce . 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 desbordamiento de Int y comienza de nuevo para cadenas largas.

Cuadro grande

Hemos analizado las piezas, pero permítanme ahora mostrar el código de ejemplo completo 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] = [] // 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: ScalarString, right: ScalarString) -> Bool { return left.scalarArray == right.scalarArray } 

Otra lectura útil

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

Créditos

Muchas gracias a Martin R en Code Review. Mi reescritura se basa en gran medida en su respuesta . Si esto le resultó útil, por favor dele un voto favorable.

Actualizar

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

Editar (31 de mayo ’17): consulte la respuesta aceptada. Esta respuesta es simplemente una demostración de cómo usar CommonCrypto Framework

De acuerdo, obtuve y extendí todas las matrices con el protocolo Hashable usando el algoritmo hash SHA-256 del marco CommonCrypto. Tienes que poner

 #import  

en su encabezado de puente para que esto funcione. Es una pena que los punteros tengan que usarse:

 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) -> Void in CC_SHA256(UnsafePointer(ptr.baseAddress), CC_LONG(count * sizeof(Element)), UnsafeMutablePointer(hPtr.baseAddress)) } } return hash[0] } } 

Editar (31 de mayo ’17): No haga esto, aunque SHA256 prácticamente no tiene colisiones hash, es una idea equivocada definir la igualdad mediante la igualdad hash

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

Esto es tan bueno como se consigue con CommonCrypto . Es feo, pero rápido y no hay muchas colisiones de hash sin duda

Editar (15 de julio ’15): Acabo de hacer algunas pruebas de velocidad:

Las matrices Int llenas aleatoriamente de tamaño n tomaron en promedio más de 1000 ejecuciones

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

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

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

Entonces, el modo SHA-256 es aproximadamente 33 veces más rápido que el modo de cuerda. No estoy diciendo que usar una cuerda sea una solución muy buena, pero es la única en la que podemos compararla en este momento

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

 "\(scalarArray)".hashValue 

o

 scalarArray.description.hashValue 

Que solo usa la representación textual como fuente de hash

Una sugerencia: dado que está modelando un String , ¿funcionaría convertir su matriz [UInt32] a String y usar el hashValue String ? Me gusta esto:

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

Eso podría convenientemente permitirle comparar su struct personalizada contra String s también, aunque si eso es una buena idea depende de lo que esté tratando de hacer …

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

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