create - dictionary comprehension python

¿Cómo puede Python dict tener varias claves con el mismo hash?

Question

Estoy tratando de entender la función de hash python debajo del capó. Creé una clase personalizada donde todas las instancias devuelven el mismo valor hash.

class C(object):
    def __hash__(self):
        return 42

Simplemente asumí que solo una instancia de la clase anterior puede estar en un conjunto en cualquier momento, pero de hecho un conjunto puede tener múltiples elementos con el mismo hash.

c, d = C(), C()
x = {c: ''c'', d: ''d''}
print x
# {<__main__.C object at 0x83e98cc>:''c'', <__main__.C object at 0x83e98ec>:''d''}
# note that the dict has 2 elements

Experimenté un poco más y descubrí que si __eq__ método __eq__ modo que todas las instancias de la clase se comparen iguales, entonces el conjunto solo permite una instancia.

class D(C):
    def __eq__(self, other):
        return hash(self) == hash(other)

p, q = D(), D()
y = {p:''p'', q:''q''}
print y
# {<__main__.D object at 0x8817acc>]: ''q''}
# note that the dict has only 1 element

Entonces, tengo curiosidad por saber cómo puede un dict tener múltiples elementos con el mismo hash. ¡Gracias!

Nota: Editó la pregunta para dar un ejemplo de dict (en lugar de establecer) porque toda la discusión en las respuestas se trata de dicts. Pero lo mismo se aplica a los conjuntos; los conjuntos también pueden tener múltiples elementos con el mismo valor hash.

Answer 1

Aquí está todo sobre los dictados de Python que pude reunir (probablemente más de lo que a nadie le gustaría saber, pero la respuesta es exhaustiva). Un saludo a por señalar que los dictados de Python usan ranuras y me llevan por este agujero de conejo.

• Los diccionarios de Python se implementan como tablas hash .
• Las tablas hash deben permitir las colisiones hash, es decir, incluso si dos claves tienen el mismo valor hash, la implementación de la tabla debe tener una estrategia para insertar y recuperar la clave y los pares de valores sin ambigüedades.
• El dict de Python usa el direccionamiento abierto para resolver colisiones hash (explicado a continuación) (ver dictobject.c:296-297 ).
• La tabla de hash de Python es solo un bloque de memoria contiguo (más o menos como una matriz, por lo que puedes buscar O(1) por índice).
• Cada ranura en la tabla puede almacenar una y solo una entrada. Esto es importante
• Cada entrada en la tabla en realidad es una combinación de los tres valores: . Esto se implementa como una estructura C (ver dictobject.h:51-56 )

• La siguiente figura es una representación lógica de una tabla hash python. En la figura a continuación, 0, 1, ..., i, ... a la izquierda hay índices de las ranuras en la tabla hash (son solo para fines ilustrativos y obviamente no se almacenan junto con la tabla).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+

• Cuando se inicializa una nueva dict, comienza con 8 ranuras . (ver dictobject.h:51-56 )

• Al agregar entradas a la tabla, comenzamos con un espacio, que se basa en el hash de la tecla. CPython usa i = hash(key) & mask iniciales. Donde mask = PyDictMINSIZE - 1 , pero eso no es realmente importante). Solo tenga en cuenta que la ranura inicial, i, que está marcada depende del hash de la tecla.
• Si esa ranura está vacía, la entrada se agrega a la ranura (por entrada, es decir, <hash|key|value> ). Pero ¿y si esa ranura está ocupada? Lo más probable es porque otra entrada tiene el mismo hash (colisión hash!)
• Si la ranura está ocupada, CPython (e incluso PyPy) compara el hash Y la clave (en comparación quiero decir == comparación no is comparación) de la entrada en la ranura contra la clave de la entrada actual que se va a insertar ( dictobject.c:296-297 ). Si ambos coinciden, entonces cree que la entrada ya existe, se da por vencido y pasa a la siguiente entrada para insertar. Si el hash o la tecla no coinciden, comienza la prueba .
• El sondeo solo significa que busca las ranuras por ranura para encontrar un espacio vacío. Técnicamente podríamos ir uno por uno, i + 1, i + 2, ... y usar el primero disponible (eso es un sondeo lineal). Pero por razones explicadas maravillosamente en los comentarios (ver dictobject.c:296-297 ), CPython usa sondeos aleatorios . En una prueba aleatoria, la siguiente ranura se selecciona en un orden pseudo aleatorio. La entrada se agrega a la primera ranura vacía. Para esta discusión, el algoritmo real utilizado para elegir el siguiente espacio no es realmente importante (ver dictobject.c:296-297 para el algoritmo de sondeo). Lo importante es que las ranuras se sondean hasta que se encuentre la primera ranura vacía.
• Lo mismo ocurre con las búsquedas, solo comienza con la ranura inicial i (donde dependo del hash de la tecla). Si el hash y la clave no coinciden con la entrada en la ranura, comienza a sondear, hasta que encuentra una ranura con una coincidencia. Si todas las ranuras están agotadas, informa un error.
• Por cierto, la dict será redimensionada si está llena en dos tercios. Esto evita ralentizar las búsquedas. (ver dictobject.h:51-56 )

¡Aquí tienes! La implementación Python de dict verifica tanto la igualdad hash de dos claves como la igualdad normal ( == ) de las claves al insertar elementos. Entonces, en resumen, si hay dos claves, a y b y hash(a)==hash(b) , pero a!=b , entonces ambas pueden existir armoniosamente en un dict de Python. Pero si hash(a)==hash(b) y a==b , entonces no pueden estar ambos en la misma dicción.

Debido a que tenemos que probar después de cada colisión hash, un efecto secundario de demasiadas colisiones hash es que las búsquedas e inserciones serán muy lentas (como señala Duncan en los comments ).

Supongo que la respuesta corta a mi pregunta es: "Porque así es como se implementa en el código fuente;)"

Si bien es bueno saberlo (¿para los geek points?), No estoy seguro de cómo se puede usar en la vida real. Porque a menos que estés tratando de romper algo de manera explícita, ¿por qué dos objetos que no son iguales tienen el mismo hash?

Answer 2

En el hilo, no vi exactamente qué hace Python con las instancias de las clases definidas por el usuario cuando las ponemos en un diccionario como claves. Leamos un poco de documentación: declara que solo se pueden usar objetos hashable como claves. Hashable son todas las clases incorporadas inmutables y todas las clases definidas por el usuario.

Las clases definidas por el usuario tienen los métodos __cmp __ () y __hash __ () por defecto; con ellos, todos los objetos se comparan desiguales (excepto con ellos mismos) y x .__ hash __ () devuelve un resultado derivado de id (x).

Entonces, si tiene constantemente __hash__ en su clase, pero no proporciona ningún método __cmp__ o __eq__, entonces todas sus instancias son desiguales para el diccionario. Por otro lado, si proporciona cualquier método __cmp__ o __eq__, pero no proporciona __hash__, sus instancias siguen siendo desiguales en términos de diccionario.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

Salida

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}

Answer 3

Las tablas hash, en general, tienen que permitir colisiones hash. Tendrás mala suerte y dos cosas eventualmente se convertirán en lo mismo. Debajo, hay un conjunto de objetos en una lista de elementos que tiene esa misma clave hash. Generalmente, hay una sola cosa en esa lista, pero en este caso, seguirá apilándolas en la misma. La única forma en que sabe que son diferentes es a través del operador de iguales.

Cuando esto sucede, tu rendimiento se degradará con el tiempo, por lo que quieres que tu función hash sea lo más aleatoria posible.

Answer 4

Para obtener una descripción detallada de cómo funciona el hash de Python, vea mi respuesta a ¿Por qué el retorno anticipado es más lento que el resto?

Básicamente usa el hash para elegir una ranura en la mesa. Si hay un valor en la ranura y el hash coincide, compara los elementos para ver si son iguales.

Si el hash no coincide o los elementos no son iguales, entonces prueba otro espacio. Hay una fórmula para elegir esto (que describo en la respuesta a la que se hace referencia), y gradualmente extrae partes no utilizadas del valor hash; pero una vez que los haya usado a todos, eventualmente se abrirá camino en todas las ranuras de la tabla hash. Eso garantiza que eventualmente encontremos un artículo que coincida o un espacio vacío. Cuando la búsqueda encuentra un espacio vacío, inserta el valor o se da por vencido (dependiendo de si estamos agregando u obteniendo un valor).

Lo importante a tener en cuenta es que no hay listas o segmentos: solo hay una tabla hash con un número determinado de espacios y cada hash se utiliza para generar una secuencia de espacios candidatos.

Answer 5

Editar : la respuesta a continuación es una de las posibles maneras de lidiar con las colisiones hash, sin embargo, no es como lo hace Python. La wiki de Python a la que se hace referencia a continuación también es incorrecta. La mejor fuente dada por @Duncan a continuación es la implementación en sí: http://svn.python.org/projects/python/trunk/Objects/dictobject.c Me disculpo por la confusión.

Almacena una lista (o un cubo) de elementos en el hash y luego itera a través de esa lista hasta que encuentra la clave real en esa lista. Una imagen dice más de mil palabras:

Aquí puede ver que John Smith y Sandra Dee hash de 152 . El cubo 152 contiene ambos. Al buscar a Sandra Dee , primero encuentra la lista en el cubo 152 , luego recorre esa lista hasta que encuentra a Sandra Dee y devuelve 521-6955 .

Lo siguiente está mal, solo está aquí para el contexto: en el wiki de Python, ¿puede encontrar (pseudo?) Cómo Python realiza la búsqueda.

En realidad, hay varias soluciones posibles para este problema, eche un vistazo al artículo de Wikipedia para obtener una descripción general agradable: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution