Manejo de colisiones en una matriz asociativa implementada utilizando un árbol de equilibrio de sí mismo

Question

¿Cómo se manejan las colisiones en matrices asociativas implementadas utilizando un árbol auto-equilibrado? Si dos objetos tienen el mismo hash, ¿están almacenados en una lista vinculada adjunta a un nodo de árbol o se crean dos nodos? En su primera, entonces cómo es O(log n) Y si es último, ¿cómo el árbol de búsqueda binario puede manejar las mismas claves (hashes)?

Answer 1

Los árboles de búsqueda definitivamente no pueden manejar dos nodos con la misma clave, por lo que debe almacenar las entradas con claves de colisionamiento en una estructura de datos separada (generalmente, como dice, una lista vinculada conectada a un nodo de árbol). De hecho, no tendrá la peor complejidad de O (log n), al igual que una matriz asociativa implementada como una tabla hash no tendrá operaciones en el peor de los casos O (1).

Como señala Epitaph, una cosa que debe probar es aumentar la longitud de sus claves hash, para no obtener colisiones. Sin embargo, no puede garantizar que no lo hará, y debe hacer algún tipo de provisión para dos objetos con el mismo hash. Sin embargo, si elige su algoritmo de hash correctamente, este debería ser un caso raro y su promedio La complejidad del tiempo para las búsquedas será O (log n), a pesar de que puede degradarse a o (n) en el caso degenerado de todo lo que tiene la misma clave hash.