Estoy confundido acerca de la complejidad de tiempo de la tabla hash muchos artículos dicen que están "amortizados O (1)" no verdadero orden O (1) qué significa esto en aplicaciones reales. ¿Cuál es la complejidad de tiempo promedio de las operaciones en una tabla hash, en la implementación real no en teoría, y por qué las operaciones no son verdaderas O (1)?Complejidad del tiempo de la tabla hash
Para algunos usos de tablas hash, es imposible crearlos del tamaño "correcto" de antemano, porque no se sabe cuántos elementos deberán mantenerse simultáneamente durante el tiempo de vida de la tabla. Si desea mantener un acceso rápido, necesita cambiar el tamaño de la tabla de vez en cuando a medida que crece el número de elementos. Este redimensionamiento lleva tiempo lineal con respecto al número de elementos que ya están en la tabla, y generalmente se realiza en una inserción, cuando los elementos numéricos pasan un umbral.
Estas operaciones de cambio de tamaño se pueden realizar con poca frecuencia para que el costo amortizado de la inserción sea constante (siguiendo una progresión geométrica del tamaño de la tabla, por ejemplo duplicando el tamaño cada vez que se redimensiona). Pero una inserción de vez en cuando toma O (n) tiempo porque desencadena un cambio de tamaño.
En la práctica, esto no es un problema a menos que esté creando aplicaciones duras en tiempo real.
No es solo el tamaño lo que se considera, sino también las colisiones hash. Hay diferentes formas de tratar con ellos, pero hagas lo que hagas no sucederá en O (1) vez. El caso promedio todavía está cerca de O (1) en la práctica, a menos que la tabla hash se llene completamente – Jords
@Jords. No sé qué significa "cerca de O (1)".Además, estoy bastante seguro de que el "O (1) amortizado" que se encuentra en la literatura corresponde a hipótesis sobre la función hash donde la profundidad del cubo permanece por debajo de un límite fijo, por lo tanto, tiempo constante. Porque si la búsqueda sin cambiar el tamaño no era un tiempo constante, la búsqueda amortizada tampoco sería un tiempo constante. –
Es imposible saber de antemano cuántas colisiones tendrá con su función de hash, así como cosas como la necesidad de cambiar el tamaño. Esto puede agregar un elemento de impredecibilidad al rendimiento de una tabla hash, por lo que no es verdadero O (1). Sin embargo, prácticamente todas las implementaciones de tablas hash ofrecen O (1) en la gran mayoría de las inserciones. Esto es lo mismo que insertar una matriz: es O (1) a menos que necesite cambiar el tamaño, en cuyo caso es O (n), más la incertidumbre de colisión.
En realidad, las colisiones hash son muy raras y la única condición en la que tendría que preocuparse por estos detalles es cuando su código específico tiene una ventana de tiempo muy apretada en la que debe ejecutarse. Para prácticamente todos los casos de uso, las tablas hash son O (1). Más impresionante que la inserción de O (1) es O (1) búsqueda.
bueno, O (1) búsqueda también es cierto para matrices –
Inserción un valor en una tabla Hash toma, en el caso medio, O (1) Tiempo de. La función hash es calculada, la respuesta se elige de la tabla hash y luego se inserta el elemento. En el peor de los casos, todos los elementos tendrán hash al mismo valor, lo que significa que toda la lista del cubo debe estar atravesada o, en el caso del direccionamiento abierto, toda la tabla debe probarse hasta un lugar vacío es encontrado. Por lo tanto, en el peor de los casos, la inserción se lleva tiempo O (n)
refieren: http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf (Hash Tabla Sección)
Esto está relacionado, aunque no exactamente la misma pregunta: http://stackoverflow.com/ questions/2369467/why-are-hash-table-expansions-usually-done-by-doubling-the-size –
Esto ayuda a responder a la inserción pero no explica nada sobre las otras operaciones, estoy más interesado en una explicación sobre la complejidad del tiempo de búsqueda en una tabla hash – marme
Bajo algunas hipótesis sobre la función hash, la búsqueda es real O (1) tiempo para la mayoría de las implementaciones de la tabla hash. De hecho, en algunas implementaciones con profundidad de cuchara delimitada, es constante por diseño. –