resolucion - ¿Cómo se implementan internamente las tablas hash en lenguajes populares?
tablas hash c++ (7)
El clásico "conjunto de cubos hash" que mencionas se usa en cada implementación que he visto.
Una de las versiones más educativas es la implementación de hash en el lenguaje Tcl, en el archivo tcl/generic/tclHash.c . Más de la mitad de las líneas en el archivo son comentarios que explican todo en detalle: asignación, búsqueda, diferentes tipos de tablas hash, estrategias, etc. Nota: el código que implementa el lenguaje Tcl es realmente legible.
¿Alguien puede aclarar cómo lenguajes populares como Python, Ruby implementa tablas hash internamente para la búsqueda de símbolos? ¿Utilizan el método clásico de "matriz con lista enlazada", o usan un árbol equilibrado?
Necesito un método simple (menos LOC) y rápido para indexar los símbolos en un DSL escrito en C. Me preguntaba qué otros han encontrado más eficientes y prácticos.
Lo que Crashworks quería decir era ...
El propósito de las tablas Hash son la búsqueda, adición y eliminación constantes de tiempo. En términos de algoritmo, la operación para todas las operaciones es O (1) amortizada. Mientras que en el caso de que use el árbol ... el peor tiempo de operación será O (log n) para un árbol equilibrado. N es el número de nodos. Pero, ¿realmente tenemos hash implementado como árbol?
Los árboles equilibrados derrotan el propósito de las tablas hash, ya que una tabla hash puede proporcionar una búsqueda en tiempo constante (amortizado), mientras que la búsqueda promedio en un árbol equilibrado es O (log (n)).
El encadenamiento separado (matriz con lista vinculada) realmente funciona bastante bien si tiene suficientes depósitos, y su implementación de lista vinculada usa un asignador de agrupación en lugar de malloc () que ingresa a cada nodo del montón individualmente. Descubrí que es casi tan eficaz como cualquier otra técnica cuando está correctamente afinada, y es muy fácil y rápido de escribir. Intente comenzar con 1/8 tantos cubos como datos de origen.
También puede utilizar el direccionamiento abierto con sondeo cuadrático o polinómico, como lo hace Python .
Perl usa una matriz con listas vinculadas para contener colisiones. Tiene una heurística simple para duplicar automáticamente el tamaño de la matriz según sea necesario. También hay código para compartir claves entre hashes para ahorrar un poco de memoria. Puede leer sobre el tema en las Actas ilustradas de Perl, pero aún relevantes, en "HV". Si eres realmente aventurero, puedes profundizar en hv.c
El algoritmo de hash solía ser bastante simple, pero probablemente ahora es mucho más complicado con Unicode. Debido a que el algoritmo era predecible, hubo un ataque DoS mediante el cual el atacante generó datos que podrían causar colisiones de hash. Por ejemplo, una enorme lista de claves enviadas a un sitio web como datos POST. El programa Perl probablemente lo dividiría y lo arrojaría en un hash que luego lo metió todo en un cubo. El hash resultante fue O (n) en lugar de O (1). Lanzar una gran cantidad de solicitudes POST en un servidor y puede obstruir la CPU. Como resultado, Perl ahora perturba la función hash con un poco de datos aleatorios.
También es posible que desee ver cómo Parrot implementa hashes básicos, lo que es significativamente menos aterrador que la implementación de Perl 5.
En cuanto a "más eficiente y práctico", use la biblioteca hash de otra persona. Por el amor de Dios, no escriba uno para uso de producción. Ya hay un hojillion robusto y eficiente.
Caos atractivo tiene una comparación de bibliotecas de tablas hash y una update . El código fuente está disponible y está en C y C ++.
Las tablas Lua utilizan una implementación absolutamente ingeniosa que, para las claves arbitrarias, se comporta como ''matriz de cubos'', pero si usa enteros consecutivos como claves, tiene la misma representación y sobrecarga de espacio que una matriz. En la implementación, cada tabla tiene una parte de hash y una parte de matriz .
Creo que esto es genial :-)
Si puede leer Java , es posible que desee revisar el código fuente para sus diversas implementaciones de mapas, en particular HashMap , TreeMap y ConcurrentSkipListMap . Los dos últimos mantienen las llaves ordenadas.
El HashMap de Java utiliza la técnica estándar que mencionas del encadenamiento en cada posición del depósito. Utiliza códigos hash bastante débiles de 32 bits y almacena las claves en la tabla. Los autores de Recetas numéricas también dan un ejemplo (en C) de una tabla hash esencialmente estructurada como la de Java, pero en la que (a) asigna los nodos de las listas de depósitos de una matriz, y (b) usa un hash de 64 bits más fuerte Codificar y prescindir del almacenamiento de claves en la tabla.