¿Cómo Puedo Elegir Entre una Tabla Hash y un Trie (Árbol de Prefijos)?

Todo depende del problema que estés tratando de resolver. Si todo lo que necesita hacer son inserciones y búsquedas, vaya con una tabla hash. Si necesita resolver problemas más complejos, como consultas relacionadas con prefijos, entonces un trie podría ser la mejor solución.

Todo el mundo conoce la tabla hash y sus usos , pero no es exactamente constante buscar tiempo , depende de qué tan grande es la tabla hash, la complejidad computacional de la función hash.

Crear enormes tablas hash para una búsqueda eficiente no es una solución elegante en la mayoría de los escenarios industriales donde incluso la pequeña latencia/escalabilidad importa (por ejemplo, el comercio de alta frecuencia). También debe preocuparse por las estructuras de datos para optimizarlas para el espacio que ocupa en la memoria para reducir la caché perder.

Un muy buen ejemplo donde trie se adapta mejor a los requisitos es el middleware de mensajería . Usted tiene un millón de suscriptores y editores de mensajes a varias categorías (en términos JMS - Temas o intercambios) , en tales casos si desea filtrar los mensajes basados en temas (que en realidad son cadenas) , definitivamente no desea crear una tabla hash para el millón de suscripciones con millones de temas . Un mejor enfoque es almacenar los temas en trie, por lo que cuando se realiza el filtrado basado en coincidencia de tema, su complejidad es independiente del número de temas / suscripciones / editores (solo depende de la longitud de la cadena). Me gusta porque puede ser creativo con esta estructura de datos para optimizar los requisitos de espacio y, por lo tanto, tener una menor pérdida de caché.

Utilice un árbol:

1. Si necesita la función de autocompletar
2. Encuentra todas las palabras que comienzan con 'a' o 'axe', etc.
3. Un árbol sufijo es una forma especial de un árbol. Los árboles de sufijos tienen toda una lista de ventajas que el hash no puede cubrir.

Hay algo que no he visto a nadie mencionar explícitamente que creo que es importante tener en cuenta. Tanto las tablas hash como los intentos de varios tipos típicamente tendrán operaciones O(k), donde k es la longitud de la cadena en bits (o equivalentemente en caracteres).

Esto es asumiendo que tienes una buena función hash. Si no desea que" farm "y" farm animals "tengan el mismo valor, entonces la función hash tendrá que usar todos los bits de la clave, y así hashing" farm animals" debería tomar aproximadamente el doble de tiempo que "farm" (a menos que esté en algún tipo de escenario de hash continuo, pero también hay escenarios de ahorro de operaciones similares con intentos). Y con un intento de vainilla, está claro por qué insertar "animales de granja" tomará aproximadamente el doble de tiempo que solo "granja". A la larga, también es cierto con los intentos comprimidos.

HashTable implementation is space efficient as compared to basic Trie implementation. Pero con las cadenas, ordenar es necesario en la mayoría de las aplicaciones prácticas. Pero HashTable perturba totalmente el orden lexográfico. Ahora, si su aplicación está haciendo operaciones basadas en el orden lexográfico (como búsqueda parcial, todas las cadenas con prefijo dado, todas las palabras en orden ordenado), debe usar Tries. Para solo buscar, se debe usar HashTable (como podría decirse, da un mínimo tiempo de búsqueda).

P.d.: Aparte de estos, Los Árboles de Búsqueda Ternaria (TSTs) serían una excelente opción. Su tiempo de búsqueda es más que HashTable, pero es eficiente en el tiempo en todas las demás operaciones. Además, su espacio más eficiente que tries.

La inserción y búsqueda en un trie es lineal con la longitud de la cadena de entrada O(s).

Un hash le dará una O(1) para la búsqueda y la inserción, pero primero debe calcular el hash basado en la cadena de entrada que nuevamente es O(s).

Conclussion, la complejidad asintótica del tiempo es lineal en ambos casos.

El trie tiene algo más de sobrecarga desde la perspectiva de los datos, pero puede elegir un trie comprimido que lo pondrá de nuevo, más o menos en un empate con el hash tabla.

Para romper el empate hágase esta pregunta: ¿Necesito buscar solo palabras completas? ¿O tengo que devolver todas las palabras que coincidan con un prefijo? (Como en un sistema predictivo de entrada de texto). Para el primer caso, ir a por un hachís. Es un código más simple y limpio. Más fácil de probar y mantener. Para un caso de uso más elaborado donde los prefijos o sufijos importan, vaya por un trie.

Y si lo haces solo por diversión, implementar un trie le daría un buen uso a una tarde de domingo.

Algunas aplicaciones (generalmente incrustadas, en tiempo real) requieren que el tiempo de procesamiento sea independiente de los datos. En ese caso, una tabla hash puede garantizar un tiempo de ejecución conocido, mientras que un trie varía en función de los datos.