¿Qué algoritmo hash utiliza el mapeo del diccionario de Python?

Estaba jugando con la creación de un analizador de línea de comandos y me preguntaba qué tipo de algoritmo hash usaría python dict?¿Qué algoritmo hash utiliza el mapeo del diccionario de Python?

La forma en que lo tengo configurado, tengo un algoritmo de coincidencia de patrones que coincide con secuencias de entrada tokenizadas con una clave de diccionario. Algunas de las claves son relativamente largas (longitud 5 o 6 tuplas de cadenas de 6 a 7 caracteres). Me preguntaba si había un punto en el cual las claves largas del diccionario reducen significativamente la eficiencia de la recuperación de claves.

Fuente

2012-01-25 Joel Cornett

Echa un vistazo a [Objects/dictnotes.txt] (http://hg.python.org/cpython/file/2.7/Objects/dictnotes.txt) – jfs

Eche un vistazo a [esta pregunta] (http://stackoverflow.com/questions/ 2070276/where-can-i-find-source-or-algorithm-of-pythons-hash-function). Tiene un enlace a [esta página] (http://effbot.org/zone/python-hash.htm) que describe cómo python hashes algunos tipos diferentes y podría ser útil para usted. – srgerg

El hash que utiliza depende del objeto que se utiliza como clave: cada clase puede definir su propio método __hash __() y el valor que devuelve para una instancia particular es el que se utiliza para el diccionario.

Python proporciona la implementación de hash para los tipos str y tuple. Una rápida mirada a la fuente debería revelar el algoritmo exacto para esos.

El hash de una tupla se basa en los hashes de su contenido. El algoritmo es esencialmente esto (simplificado un poco):

def hash(tuple): 
    mult = 1000003 
    x = 0x345678 
    for index, item in enumerate(tuple): 
     x = ((x^hash(item)) * mult) & (1<<32) 
     mult += (82520 + (len(tuple)-index)*2) 
    return x + 97531

Para las cadenas, el intérprete también itera sobre cada personaje, combinándolos con esto (de nuevo, ligeramente simplificada) algoritmo:

def hash(string): 
    x = string[0] << 7 
    for chr in string[1:]: 
     x = ((1000003 * x)^chr) & (1<<32) 
    return x

Un problema más grande preocuparse es evitar las colisiones hash. Las claves hash de colisión provocarán una búsqueda lineal a medida que el diccionario intente encontrar un lugar para almacenar el nuevo objeto (esto ahora se reconoce como un problema de seguridad, y el comportamiento puede estar cambiando en las próximas versiones de python)

Fuente

2012-01-25 04:56:28

Oh, está bien. Por alguna razón, asumí que Python acababa de utilizar un algoritmo genérico de hash bytecode para todos los tipos de datos. En cuanto a las claves hash colisionantes, no creo que eso vaya a ser un problema, ya que la cantidad de claves que tendré es (relativamente) pequeña, probablemente de miles. Disculpe mi ingnorancia, pero ¿cómo los hashes colisionantes y las búsquedas lineales se convierten en un problema de seguridad? –

@Joel Cornett: Este es un problema de seguridad porque las tablas hash usan cubos para almacenar claves, y las claves con el mismo código hash se procesan en el mismo depósito, obligando a la tabla hash a hacer una búsqueda lineal cada vez que busca una clave, que puede ser muy ineficiente (e incluso puede causar denegación de servicio) si el número de claves es grande. Los ataques de denegación de servicio pueden producirse si un programa encuentra una tabla hash con claves distintas que comparten el mismo código hash. –

Si un atacante puede controlar las claves que se usan en su diccionario, entonces es posible que puedan insertar cientos o miles de claves colisionantes, haciendo que las operaciones de inserción sean muy lentas. En algunos casos, esto podría causar que una máquina deje de responder, o que una base de datos quede inutilizable: un ataque Dos –

¿Qué algoritmo hash utiliza el mapeo del diccionario de Python?

Respuesta

Cuestiones relacionadas