Quiero implementar una tabla hash usando árboles de búsqueda binarios para reducir la complejidad de búsqueda en el proceso de encadenamiento separado de O (n) (usando la lista vinculada) a O (log n) (usando BST). ¿Se puede hacer esto y, en caso afirmativo, cómo? Sería más fácil de entender si la solución es paso a paso, la implementación de la lógica.
Quiero reducir el tiempo de búsqueda en la tabla hash (compilación usando un encadenamiento separado), pero al mismo tiempo no quiero que aumente el tiempo de inserción. Para mi proyecto, no puedo cambiar la función hash para reducir las colisiones. Pero debido a la escalabilidad, están ocurriendo colisiones. Estoy tratando de encontrar una solución, de modo que pueda trabajar de alguna manera con el mejor acceso e insertar el tiempo en caso de que ocurra una colisión ... es decir, administrar el estado actual de las cosas que reestructurar todo el algoritmo. Si no funciona, entonces tendrá que reestructurarse. Entonces, ¿alguna idea?
Respuestas:
Lo que está pidiendo es posible dadas sus limitaciones.
Análisis
La fuerza de una tabla hash es su rápida búsqueda y velocidad de inserción. Para obtener esa velocidad, uno debe abandonar cualquier apariencia de orden en la tabla: es decir, todas las entradas están mezcladas. Una lista es aceptable para usar como entrada de la tabla porque, mientras que el recorrido es O (n), las listas tienden a ser cortas suponiendo que la tabla hash es lo suficientemente grande y los objetos almacenados en la tabla se combinan utilizando un algoritmo de hash de buena calidad.
Un árbol de búsqueda binario (BST) tiene una inserción y búsqueda rápidas en O (log 2 n). También impone una restricción a los elementos que almacena: debe haber alguna forma de ordenar los elementos. Dados dos elementos A y B almacenados en el árbol, debe ser posible determinar si A viene antes que B o si tienen un orden equivalente.
Una tabla hash no impone tal restricción: los elementos en una tabla hash deben tener dos propiedades. Primero, debe haber una manera de determinar si son equivalentes; segundo, debe haber una manera de calcular un código hash determinista. El orden no es un requisito.
Si los elementos de su tabla hash tienen un orden, puede usar un BST como entrada de la tabla hash para contener objetos con el mismo código hash (colisiones). Sin embargo, debido a que BST tiene búsqueda e inserción de O (log 2 n), eso significa que el peor de los casos para toda la estructura (tabla hash más BST) es técnicamente mejor que usar una lista como entrada de tabla. Dependiendo de la implementación de BST, requerirá más almacenamiento que una lista, pero probablemente no mucho más.
Tenga en cuenta que normalmente la sobrecarga y el comportamiento de un BST no aporta nada a la mesa en situaciones del mundo real como cubos de tabla hash, por lo que el pobre rendimiento teórico de una lista es aceptable. En otras palabras, la tabla hash compensa la debilidad de la lista al colocar menos elementos en cada lista (depósito). Sin embargo : el problema indicó específicamente que la tabla hash no puede aumentar de tamaño, y las colisiones son más frecuentes de lo que es típico en una tabla hash.
Implementación
No voy a poner código aquí porque, sinceramente, no es realmente necesario y de todos modos no dio un idioma.
Lo que haría es simplemente copiar cualquier tabla hash estándar que contenga la biblioteca estándar de su idioma en una nueva clase, luego cambiar el tipo de cubo de tabla de una lista a un árbol. Dependiendo del idioma y su biblioteca estándar, esto puede ser algo muy trivial.
Normalmente no recomendaría copiar y pegar codificaciones como esta. Sin embargo, es una manera fácil de obtener una estructura de datos probada en batalla muy rápidamente.
fuente
El uso de un árbol binario para el manejo de colisiones en una tabla hash no solo es posible, se ha hecho.
Walter Bright es mejor conocido como el inventor del lenguaje de programación D , pero también escribió una variante ECMAScript llamada DMDScript . En el pasado, un reclamo principal de DMDScript (o posiblemente un antepasado, creo recordar el nombre DScript) era que sus tablas hash tendían a superar a las de muchos idiomas similares. La razón: manejo de colisiones utilizando árboles binarios.
No recuerdo exactamente de dónde es esto, pero los árboles utilizados eran árboles binarios ingenuos, sin un esquema de equilibrio parcial (no AVL, rojo-negro o lo que sea) lo que tiene sentido ya que suponiendo que la propia tabla hash se redimensiona cuando se llena demasiado. no obtienes tasas absurdamente improbables de colisiones de hash, los árboles binarios siempre deben ser pequeños. Básicamente, el peor de los casos sigue siendo el mismo que usar una lista vinculada para el manejo de colisiones (excepto que paga el precio de dos punteros por nodo en lugar de uno), pero el caso promedio reduce la cantidad de búsqueda dentro de cada cubo de hash.
fuente