java - tries - Hash Array Mapped Trie(HAMT)

trie significado

Question

Estoy tratando de entender los detalles de un HAMT . Hubiera implementado uno en Java solo para entender. Estoy familiarizado con Tries y creo que entiendo el concepto principal de HAMT.

Básicamente,

Dos tipos de nodos:

Valor clave

Key Value Node:
K key
V value

Índice

Index Node:
int bitmap (32 bits)
Node[] table (max length of 32)

1. Genera un hash de 32 bits para un objeto.
2. Paso a paso por el hash de 5 bits a la vez. (0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) nota: el último paso (7mo) es solo 2 bits.
3. En cada paso, busca la posición de ese entero de 5 bits en el mapa de bits. por ejemplo, integer==5 bitmap==00001
   1. Si el bit es un 1, entonces esa parte del hash existe.
   2. Si el bit es un 0, la clave no existe.
4. Si la clave existe, encuentre su índice en la tabla contando el número de 1 en el mapa de bits entre 0 y la posición. por ejemplo, integer==6 bitmap==0101010101 index==3
   1. Si la tabla apunta a un nodo clave / valor, entonces compare las claves.
   2. Si la tabla apunta a un nodo índice, vaya a 2 avanzando un paso.

La parte que no entiendo del todo es la detección y mitigación de colisiones. En el documento vinculado lo alude:

La clave existente luego se inserta en la nueva tabla sub-hash y se agrega la nueva clave. Cada vez que se usan 5 bits más de hash, la probabilidad de una colisión se reduce en un factor de 1/32. Ocasionalmente, se puede consumir un hash completo de 32 bits y se debe calcular uno nuevo para diferenciar las dos claves.

Si tuviera que calcular un hash "nuevo" y almacenar el objeto en ese nuevo hash; ¿cómo podrías buscar el objeto en la estructura? Al realizar una búsqueda, ¿no generaría el hash "inicial" y no el "hash recalculado"?

Debo estar perdiendo algo.....

Por cierto: HAMT funciona bastante bien, se ubica entre un mapa hash y un mapa de árbol en mis pruebas.

Data Structure Add time Remove time Sorted add time Sorted remove time Lookup time Size
Java''s Hash Map 38.67 ms 18 ms 30 ms 15 ms 16.33 ms 8.19 MB
HAMT 68.67 ms 30 ms 57.33 ms 35.33 ms 33 ms 10.18 MB
Java''s Tree Map 86.33 ms 78 ms 75 ms 39.33 ms 76 ms 8.79 MB
Java''s Skip List Map 111.33 ms 106 ms 72 ms 41 ms 72.33 ms 9.19 MB

Answer 1

Si tuviera que calcular un hash "nuevo" y almacenar el objeto en ese nuevo hash; ¿cómo podrías buscar el objeto en la estructura? Al realizar una búsqueda, ¿no generaría el hash "inicial" y no el "hash recalculado"?

Al hacer una búsqueda, se usa el hash inicial. Cuando se agotan los bits en el hash inicial, cualquiera de las siguientes condiciones es verdadera:

1. terminamos con un nodo clave / valor - devuélvelo
2. terminamos con un nodo índice: esta es la sugerencia de que tenemos que profundizar volviendo a calcular un nuevo hash.

La clave aquí es el agotamiento de los bits hash.

Answer 2

HAMT es una estructura excelente y de alto rendimiento, especialmente cuando se necesitan objetos inmutables, es decir, cada vez que se realiza una modificación, se crea una nueva copia de una estructura de datos.

En cuanto a su pregunta sobre colisiones hash, encontré una implementación de implementation C # (que ahora funciona mal) que muestra cómo funciona: en cada colisión hash la clave se vuelve a generar y la búsqueda se vuelve a intentar recursivamente hasta que se alcanza el límite máximo de iteraciones.

Actualmente también estoy explorando HAMP en el contexto de programación funcional y aprendiendo el código existente. Hay varias implementaciones de referencia de HAMT en Haskell como Data.HshMap y en Clojure como PersistenceHashMap .

Existen algunas otras implementaciones más simples en la web que no se ocupan de las colisiones, pero que son útiles para comprender el concepto. Aquí están en Haskell y OCaml

He encontrado un artículo de artículo de resumen agradable que describe HAMT con imágenes y enlaces a papers research originales de Phil Bagwell.

Puntos relacionados:

Al implementar HAMT en F #, he notado que la implementación de la función popCount que se describe here realmente importa y da un 10-15% en comparación con la implementación ingenua que se describe en las siguientes respuestas en el enlace. No es genial, pero es un almuerzo gratis.

Las estructuras de IntMap relacionadas ( Haskell y su puerto a F # ) son muy buenas cuando la clave podría ser un número entero e implementan PATRICIA/Radix trie .

Creo que todas estas implementaciones son muy buenas para aprender sobre estos ejemplos ejemplos de una estructura de datos inmutable e idiomas funcionales eficientes en toda su belleza. ¡Realmente brillan juntos!

Answer 3

Hay dos secciones del documento que creo que podrías haber perdido. El primero es el bit que precede inmediatamente al bit que citó:

O la clave colisionará con una existente. En este caso, la clave existente debe reemplazarse con una tabla sub-hash y la siguiente operación hash de 5 bits de la clave existente calculada. Si todavía hay una colisión, este proceso se repite hasta que no se produce una colisión.

Entonces, si tiene el objeto A en la tabla y agrega el objeto B que choca, la celda en la que chocaron sus teclas será un puntero a otra subtabla (donde no chocan).

A continuación, la Sección 3.7 del documento que vinculó describe el método para generar un hash nuevo cuando se ejecuta al final de sus primeros 32 bits:

La función hash fue diseñada para dar un hash de 32 bits. El algoritmo requiere que el hash se pueda extender a un número arbitrario de bits. Esto se logró volviendo a colocar la clave combinada con un número entero que representa el nivel trie, siendo cero la raíz. Por lo tanto, si dos teclas dan el mismo hash inicial, entonces la repetición tiene una probabilidad de 1 en 2 ^ 32 de una nueva colisión.

Si esto no parece explicar nada, diga y ampliaré esta respuesta con más detalle.

Answer 4

La probabilidad de colisión es presumiblemente muy baja, y generalmente solo problemática para árboles enormes. Dado esto, es mejor que simplemente guardes las colisiones en una matriz en la hoja y lo busques linealmente ( lo hago en mi C # HAMT ).