hashtable - utilizacion - La complejidad del tiempo de la tabla Hash
utilizacion de tablas hash (3)
Es imposible saber de antemano cuántas colisiones obtendrá 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.
Estoy confundido acerca de la complejidad del tiempo de la tabla hash. Muchos artículos dicen que están "amortizados O (1)" y no es cierto. 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)?
Para algunos usos de las tablas hash, es imposible crearlas con el tamaño "correcto" de antemano, ya que no se sabe cuántos elementos deberán mantenerse simultáneamente durante la vida útil 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 hacer con la mínima frecuencia de 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.
Insertar un valor en una tabla hash toma, en el caso promedio, O (1) tiempo . La función hash se calcula, el bucked 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 se debe atravesar toda la lista del cubo o, en el caso del direccionamiento abierto, se debe sondear toda la tabla hasta que se encuentre un punto vacío. Por lo tanto, en el peor de los casos, la inserción demora O (n)
remítase a: http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf (Sección Hash Table)