¿Cómo funcionan las búsquedas de hash de diccionario de Python?

Question

¿Cómo funcionan internamente los algoritmos de búsqueda del diccionario Python?

mydi['foo'] 

Si el diccionario tiene 1,000,000 de términos, ¿se ejecuta una búsqueda en árbol? ¿Esperaría el rendimiento en términos de la longitud de la cadena clave o el tamaño del diccionario? Tal vez meter todo en un diccionario es tan bueno como escribir un índice de búsqueda de árbol para cadenas de tamaño 5 millones.

Answer 1

Aquí hay un pseudocódigo más cercano a lo que realmente sucede. Imagine que el diccionario tiene un atributo data que contiene la clave, pares de valores y un size que es el número de celdas asignadas.

def lookup(d, key): 
    perturb = j = hash(key) 
    while True: 
     cell = d.data[j % d.size] 
     if cell.key is EMPTY: 
      raise IndexError 
     if cell.key is not DELETED and (cell.key is key or cell.key == key): 
      return cell.value 
     j = (5 * j) + 1 + perturb 
     perturb >>= PERTURB 

El valor perturb se asegura de que todos los bits del código hash se utilizan finalmente en la resolución de conflictos de hash pero una vez que se ha degradado a 0 el (5*j)+1 será finalmente tocar todas las celdas de la tabla.

size es siempre mucho más grande que el número de celdas realmente utilizadas, por lo que se garantiza que el hash eventualmente golpeará una celda vacía cuando la clave no exista (y normalmente debería golpear una bastante rápidamente). También hay un valor eliminado para que una tecla indique una celda que no debe terminar la búsqueda pero que no está actualmente en uso.

En cuanto a su pregunta sobre la longitud de la cadena de clave, hashing una cadena verá todos los caracteres de la cadena, pero una cadena también tiene un campo utilizado para almacenar el hash calculado. Por lo tanto, si utiliza cadenas diferentes cada vez para realizar la búsqueda, la longitud de la cadena puede tener un rumbo, pero si tiene un conjunto fijo de claves y vuelve a utilizar las mismas cadenas, el hash no se volverá a calcular después de la primera vez que se usa . Python obtiene un beneficio de esto ya que la mayoría de las búsquedas de nombres involucran diccionarios y una sola copia de cada variable o nombre de atributo se almacena internamente, por lo que cada vez que accede a un atributo x.y hay una búsqueda en el diccionario pero no una llamada a una función hash.

Answer 2

Como mencionaste en tu título, los dicts son tablas hash. No se usa búsqueda en árbol. Buscar una clave es una operación de tiempo casi constante, independientemente del tamaño del dict.

que podrían encontrar las respuestas a esta pregunta útil: búsquedas de How are Python's Built In Dictionaries Implemented

Answer 3

Hash no utilizan árboles. Usan una tabla hash y realizan búsquedas constantes. Tomarán más espacio (en promedio, creo que el doble) que un árbol, pero los tiempos de búsqueda e inserción son satisfactorios.

simplificar en exceso, tomar un MD5 de su clave, y mod que con el número de direcciones que tiene, y que es donde se guarda o mira para recuperar una clave. No importa cuán grande sea el conjunto, siempre llevará la misma cantidad de tiempo siempre que no tenga una colisión importante, lo cual evitará un buen hash.

Answer 4

Aquí hay una buena explicación: http://wiki.python.org/moin/DictionaryKeys

Pseudocódigo desde arriba enlace:

def lookup(d, key): 
    '''dictionary lookup is done in three steps: 
     1. A hash value of the key is computed using a hash function. 

     2. The hash value addresses a location in d.data which is 
      supposed to be an array of "buckets" or "collision lists" 
      which contain the (key,value) pairs. 

     3. The collision list addressed by the hash value is searched 
      sequentially until a pair is found with pair[0] == key. The 
      return value of the lookup is then pair[1]. 
    ''' 
    h = hash(key)     # step 1 
    cl = d.data[h]     # step 2 
    for pair in cl:    # step 3 
     if key == pair[0]: 
      return pair[1] 
    else: 
     raise KeyError, "Key %s not found." % key 

Answer 5

Respuesta 1: trabajo interno se explica en este video

Respuesta 2: No, un árbol de búsqueda no se hace si tiene un millón de registros en un diccionario.

Respuesta 3: Como puede haber colisiones clave que se espera que el rendimiento en términos del tamaño del diccionario, y no en términos de la longitud de la cadena de clave.

Respuesta 4: Considere el diccionario como una matriz (ubicaciones de memoria contigua), pero puede haber bloques dentro de la matriz que no se utilizan. Por lo tanto, los diccionarios tienden a perder mucho espacio de memoria en comparación con los árboles. Pero, para un mejor rendimiento, los diccionarios de rendimiento podrían ser mejores que los árboles. Las colisiones clave en ocasiones pueden degradar el rendimiento. Deberías leer acerca de Hashing constante.