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

Question

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

Estoy hablando de la función que devuelve un código hash que luego se utiliza para insertar objetos en hashtables aka diccionarios.

Como __hash__() devuelve un número entero y se utiliza para "agrupar" objetos en hashtables Supongo que los valores del entero devuelto se deben distribuir uniformemente para datos comunes (para minimizar las colisiones). ¿Cuál es una buena práctica para obtener esos valores? ¿Las colisiones son un problema? En mi caso, tengo una pequeña clase que actúa como una clase de contenedor con algunos enteros, algunos flotadores y una cadena.

Answer 1

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

He aquí un ejemplo del uso de una clave de hash y la igualdad:

class A(object): 
    def __key(self): 
     return (self.attr_a, self.attr_b, self.attr_c) 

    def __eq__(x, y): 
     return x.__key() == y.__key() 

    def __hash__(self): 
     return hash(self.__key()) 

Además, el documentation of __hash__ tiene más información, que puede ser valiosa en algunas circunstancias particulares.

Answer 2

Depende del tamaño del valor hash que devuelva. Es simple lógica que si necesitas devolver un int de 32 bits basado en el hash de cuatro entradas de 32 bits, vas a tener colisiones.

Yo preferiría las operaciones de bits. Al igual que, el siguiente código de seudo C:

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

Este sistema podría funcionar para los flotadores también, si simplemente las tomó como su valor de bits en lugar de realmente lo que representa un valor de punto flotante, tal vez mejor.

Para cuerdas, tengo poca/ninguna idea.

Answer 3

Puedo intentar responder la segunda parte de su pregunta.

Las colisiones probablemente no resultarán 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 se resolverían internamente en la colección, y existen muchos métodos para resolver colisiones. El más simple (y el peor) es, dada una entrada para insertar en el índice i, agregue 1 ai hasta que encuentre un lugar vacío e inserte allí. La recuperación funciona de la misma manera. Esto da como resultado recuperaciones ineficaces para algunas entradas, ¡ya que podría tener una entrada que requiera atravesar toda la colección para encontrarla!

Otros métodos de resolución de colisión reducen el tiempo de recuperación moviendo las entradas en la tabla hash cuando se inserta un elemento para separar 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 ramificar diferentes entradas colisionantes para que las entradas se agrupen en un lugar en particular.

Además, si necesita cambiar el tamaño de la colección deberá volver a configurar todo o utilizar un método dinámico de hash.

En resumen, dependiendo de lo que esté usando el código hash, es posible que deba implementar su propio método de resolución de colisión.Si no los está almacenando en una colección, probablemente pueda salirse con la suya con una función hash que solo genera códigos hash en un rango muy amplio. Si es así, puede asegurarse de que su contenedor sea más grande de lo que necesita (cuanto más grande, mejor, por supuesto), según las preocupaciones de su memoria.

Éstos son algunos enlaces si le interesa más:

coalesced hashing on wikipedia

Wikipedia también tiene un summary de diversos métodos de resolución de colisiones:

Además, "File Organization And Processing" de Tharp abarca una gran cantidad de colisiones métodos de resolución extensivamente. IMO es una gran referencia para los algoritmos hash.

Answer 4

Paul Larson de Microsoft Research estudió una amplia variedad de funciones hash. Me dijo que

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

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

Answer 5

John Millikin propuso una solución similar a esto:

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 de esta solución es que el hash(A(a, b, c)) == hash((a, b, c)). En otras palabras, el hash colisiona con el de la tupla de sus miembros clave. Tal vez esto no importa muy a menudo en la práctica?

El Python documentation on __hash__ sugiere combinar los hashes de los subcomponentes utilizando algo así como XOR, lo 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 acaso.

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