ios - delegados - delegate swift

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

Question

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

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 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 valor 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ían bien en este caso. Específicamente,

• Propiedad del objeto (la matriz no tiene hashValue )
• Propiedad de ID (no estoy seguro de cómo se podría implementar esto bien)
• Fórmula (parece que cualquier fórmula para una cadena de enteros de 32 bits sería un procesador pesado y tendría mucho 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 rápida
• Función hash perfecta
• Membresía de objetos personalizados en matrices y diccionarios Swift
• Cómo implementar Hashable para tu clase personalizada
• Escribir una buena implementación Hashable en Swift

Pregunta

Las cadenas hashValue tienen una propiedad hashValue , por lo 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 usar el hashValue String . Todo mi punto para crear mi propia estructura era para poder evitar hacer muchas conversiones de String . String obtiene su hashValue de alguna parte. 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, me cuesta un poco saber cuál es el mejor y expresarlos en Swift.

• Algoritmo de hashCode Java
• Algoritmos C
• función hash para cadena (SO pregunta y respuestas en C)
• Tutorial de hash (Grupo de investigación de visualización de algoritmos tecnológicos de Virginia)
• Algoritmos de función hash de uso general

Actualización 3

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

Envié una posible solución usando la función DJB Hash.

Answer 1

Actualizar

Martin R writes :

A partir de Swift 4.1 , el compilador puede sintetizar Equatable y Hashable para la conformidad de tipos automáticamente, si todos los miembros se ajustan a Equatable / Hashable (SE0185). Y a partir de Swift 4.2 , un combinador de hash de alta calidad está integrado en la biblioteca estándar de Swift (SE-0206).

Por lo tanto, ya no es necesario definir su propia función de hashing, basta con declarar la conformidad:

struct ScalarString: Hashable, ... {

    private var scalarArray: [UInt32] = []

    // ... }

Por lo tanto, la respuesta a continuación debe reescribirse (una vez más). Hasta que eso suceda, consulte la respuesta de Martin R desde el enlace de arriba.

Vieja respuesta:

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

Cómo implementar el protocolo Hashable

El protocolo Hashable le permite usar su clase o estructura personalizada como clave de diccionario. Para implementar este protocolo necesita

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

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

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

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

Implementar el protocolo equitativo

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

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

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

Devuelve un valor hashValue calculado

Su clase o estructura personalizada también debe tener una variable calculada hashValue . 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 un poco de trabajo adicional cuando hay una colisión (por lo que es deseable una buena distribución), pero es de esperar que se produzcan algunas colisiones. Según tengo entendido, la función == hace ese trabajo extra. ( Actualización : Parece que == puede hacer todo el trabajo ) .

Hay varias formas de calcular el valor 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 hash cada vez que dos matrices tuvieran el mismo número de elementos pero valores diferentes. NSArray aparentemente usa este enfoque.

DJB Hash Function

Una función hash común que funciona con cadenas es la función hash DJB. Este es el que usaré, pero mira algunos otros aquí .

A continuación se presenta una implementación Swift writes :

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 la forma expandida anterior, que puede ser más legible para las personas que no están familiarizadas con la 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 que Int desborde y comience nuevamente para cadenas largas.

Cuadro grande

Hemos examinado las piezas, pero permítanme mostrar ahora el código de ejemplo completo en relación con el 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 unicidad y la velocidad?
• Operadores de desbordamiento
• ¿Por qué son tan importantes 5381 y 33 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 writes . Si esto le resultó útil, por favor, denle un voto positivo.

Actualizar

Swift ahora es de código abierto, 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 me he tomado el tiempo para analizarlo completamente. Siéntase libre de hacerlo usted mismo.

Answer 2

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 hash

Answer 3

Una sugerencia: dado que está modelando una String , ¿funcionaría convertir su matriz [UInt32] en una String y utilizar el valor hashValue la hashValue ? Me gusta esto:

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

Eso podría permitirle comparar convenientemente su struct personalizada con String s, aunque si esa es una buena idea depende de lo que intente hacer ...

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

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

Answer 4

Editar (31 de mayo ''17): consulte la respuesta aceptada. Esta respuesta es prácticamente solo una demostración de cómo usar CommonCrypto Framework

De acuerdo, Hashable y extendí todos los arreglos con el protocolo Hashable usando el algoritmo de hash 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 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<Int>) -> Void in
                CC_SHA256(UnsafePointer<Void>(ptr.baseAddress), CC_LONG(count * sizeof(Element)), UnsafeMutablePointer<UInt8>(hPtr.baseAddress))
            }
        }

        return hash[0]
    }
}

Editar (31 de mayo de ''17): no hagas esto, aunque SHA256 prácticamente no tiene colisiones hash, es una idea equivocada definir igualdad por hash igualdad

public func ==<T>(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 hash con seguridad.

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

Las matrices Int llenadas al azar 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 cadenas:

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 cadena. No estoy diciendo que usar una cadena sea una muy buena solución, pero es la única con la que podemos compararlo en este momento.