¿Cuál es una forma correcta y buena de implementar __hash __ ()?

¿Cuál es una forma correcta y buena de implementar __hash__() ?

Me refiero a la función que devuelve un código hash que luego se usa para insertar objetos en tablas hash, también como diccionarios.

Como __hash__() devuelve un entero y se usa para “agrupar” objetos en tablas hash, asumo que los valores del entero devuelto deberían distribuirse uniformemente para datos comunes (para minimizar las colisiones). ¿Cuál es una buena práctica para obtener tales valores? ¿Son las colisiones un problema? En mi caso, tengo una clase pequeña que actúa como una clase contenedora que contiene algunas entradas, algunas carrozas y una cuerda.

Una forma fácil y correcta de implementar __hash__() es usar una tupla de claves. No será tan rápido como un hash especializado, pero si lo necesita, probablemente debería implementar el tipo en C.

Aquí hay un ejemplo del uso de una clave para el hash y la igualdad:

 class A: def __key(self): return (self.attr_a, self.attr_b, self.attr_c) def __hash__(self): return hash(self.__key()) def __eq__(self, other): return isinstance(self, type(other)) and self.__key() == other.__key() 

Además, la documentación de __hash__ tiene más información, que puede ser valiosa en algunas circunstancias particulares.

John Millikin propuso una solución similar a esta:

 class A(object): def __init__(self, a, b, c): self._a = a self._b = b self._c = c def __eq__(self, othr): return ((self._a, self._b, self._c) == (othr._a, othr._b, othr._c)) def __hash__(self): return hash((self._a, self._b, self._c)) 

El problema con esta solución es que el hash(A(a, b, c)) == hash((a, b, c)) . En otras palabras, el hash choca con el de la tupla de sus miembros clave. Tal vez esto no importa muy a menudo en la práctica?

La documentación de Python en __hash__ sugiere combinar los hashes de los subcomponentes utilizando algo como XOR, que nos da esto:

 class B(object): def __init__(self, a, b, c): self._a = a self._b = b self._c = c def __eq__(self, othr): return (isinstance(othr, type(self)) and (self._a, self._b, self._c) == (othr._a, othr._b, othr._c)) def __hash__(self): return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^ hash((self._a, self._b, self._c))) 

Bono: más robusto __eq__ arrojado allí por si __eq__ .

Actualización: como señala Blckknght, cambiar el orden de a, b y c podría causar problemas. ^ hash((self._a, self._b, self._c)) un ^ hash((self._a, self._b, self._c)) adicional ^ hash((self._a, self._b, self._c)) para capturar el orden de los valores que se están copiando. Este ^ hash(...) final ^ hash(...) se puede eliminar si los valores que se combinan no se pueden reorganizar (por ejemplo, si tienen diferentes tipos y, por lo tanto, el valor de _a nunca se asignará a _b o _c , etc.).

Paul Larson, de Microsoft Research, estudió una amplia variedad de funciones hash. Él me dijo eso

 for c in some_string: hash = 101 * hash + ord(c) 

Trabajó sorprendentemente bien para una amplia variedad de cuerdas. Descubrí que técnicas polinomiales similares funcionan bien para calcular un hash de subcampos dispares.

Puedo intentar responder la segunda parte de tu pregunta.

Las colisiones probablemente resultarán no del código hash en sí, sino de la asignación del código hash a un índice en una colección. Entonces, por ejemplo, su función hash podría devolver valores aleatorios de 1 a 10000, pero si su tabla hash solo tiene 32 entradas, obtendrá colisiones en la inserción.

Además, creo que las colisiones serían resueltas por la colección internamente, y hay muchos métodos para resolver las colisiones. Lo más simple (y lo peor) es que, dada una entrada para insertar en el índice i, agregue 1 a i hasta que encuentre un lugar vacío e inserte allí. La recuperación funciona de la misma manera. ¡Esto da como resultado recuperaciones ineficientes para algunas entradas, ya que podría tener una entrada que requiera recorrer toda la colección para encontrar!

Otros métodos de resolución de colisiones reducen el tiempo de recuperación moviendo las entradas en la tabla hash cuando se inserta un elemento para distribuir las cosas. Esto aumenta el tiempo de inserción pero supone que lee más de lo que inserta. También hay métodos que intentan y ramifican diferentes entradas en conflicto para que las entradas se agrupen en un lugar en particular.

Además, si necesita cambiar el tamaño de la colección, deberá repetir todo o usar un método de hashing dynamic.

En resumen, dependiendo de lo que esté usando el código hash, tendrá que implementar su propio método de resolución de colisiones. Si no los almacena en una colección, probablemente pueda salirse con una función de hash que solo genera códigos hash en un rango muy grande. Si es así, puede asegurarse de que su contenedor sea más grande de lo que debe ser (cuanto más grande mejor, por supuesto) dependiendo de sus preocupaciones con respecto a la memoria.

Aquí hay algunos enlaces si te interesa más:

hashing fusionado en wikipedia

Wikipedia también tiene un resumen de varios métodos de resolución de colisiones:

Además, ” Organización y procesamiento de archivos ” de Tharp cubre muchos de los métodos de resolución de colisiones ampliamente. OMI es una gran referencia para los algoritmos de hash.

Depende del tamaño del valor hash que devuelva. Es una lógica simple que si necesitas devolver un int de 32 bits basado en el hash de cuatro ints de 32 bits, obtendrás colisiones.

Yo preferiría las operaciones de bits. Como, el siguiente pseudo código C:

 int a; int b; int c; int d; int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F); 

Un sistema así también podría funcionar para flotadores, si simplemente los tomara como su valor de bit en lugar de representar un valor de punto flotante, tal vez sea mejor.

Para cuerdas, tengo poca / ninguna idea.