python - ¿Cuál es una forma correcta y buena de implementar__hash__()?
hashtable hashcode (5)
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. 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);
Tal sistema también podría funcionar para flotadores, si simplemente los toma como su valor de bit en lugar de representar realmente un valor de coma flotante, quizás sea mejor.
Para cuerdas, tengo poca / ninguna idea.
¿Cuál es una forma correcta y buena de implementar __hash__() ?
Estoy hablando de la función que devuelve un hashcode que luego se usa para insertar objetos en hashtables aka dictionaries.
Como __hash__() devuelve un número entero y se utiliza para "agrupar" objetos en hashtables, supongo que los valores del entero devuelto deben distribuirse uniformemente para los 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 clase pequeña que actúa como una clase de contenedor con algunos enteros, algunos flotadores y una cadena.
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 colisiona 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 hash de los subcomponentes usando algo 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)))
Bonificación: __eq__ más robusto arrojado allí por si __eq__ .
Actualización: como señala Blckknght, cambiar el orden de a, byc 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 procesando. Este ^ hash(...) final ^ hash(...) 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.).
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)
funcionó sorprendentemente bien para una amplia variedad de cadenas. Descubrí que las 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 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án internamente por 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 al mover 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, puede que tenga que 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.
Aquí hay algunos enlaces si le interesa más:
hashing combinado en wikipedia
Wikipedia también tiene un summary de varios métodos de resolución de colisiones:
Además, la " Organización y procesamiento de archivos " de Tharp abarca muchos métodos de resolución de colisiones. IMO es una gran referencia para los algoritmos hash.
Una forma fácil y correcta de implementar __hash__() es usar una tupla de tecla. No será tan rápido como un hash especializado, pero si lo necesita, entonces probablemente debería implementar el tipo en C.
Aquí hay un ejemplo del uso de una clave para hash e 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, la documentación de __hash__ tiene más información, que puede ser valiosa en algunas circunstancias particulares.