c++ - utilizacion - Complejidad del tiempo de ejecución de la tabla hash(insertar, buscar y eliminar)

utilizacion de tablas hash

Question

¿Por qué sigo viendo diferentes complejidades de tiempo de ejecución para estas funciones en una tabla hash?

En wiki, la búsqueda y la eliminación son O (n) (pensé que el punto de las tablas hash era tener una búsqueda constante, así que ¿cuál es el punto si la búsqueda es O (n)).

En algunas notas del curso de hace un tiempo, veo una amplia gama de complejidades que dependen de ciertos detalles, incluido uno con todos los O (1). ¿Por qué se usaría cualquier otra implementación si puedo obtener todo O (1)?

Si estoy usando tablas hash estándar en un lenguaje como C ++ o Java, ¿qué puedo esperar que sea la complejidad del tiempo?

Answer 1

Algunas tablas hash (hashing de cuco) tienen una O (1) búsqueda garantizada

Answer 2

Depende de cómo implemente hashing, en el peor de los casos puede ir a O (n), en el mejor de los casos es 0 (1) (generalmente puede lograrlo si su DS no es tan grande fácilmente)

Answer 3

Idealmente, una tabla hash es O(1) . El problema es si dos claves no son iguales, sin embargo, producen el mismo hash.

Por ejemplo, imagine las cuerdas "fue la mejor de las veces que fue la peor de las veces" y "Huevos verdes y jamón" resultaron en un valor hash de 123 .

Cuando se inserta la primera cadena, se coloca en la categoría 123. Cuando se inserta la segunda cadena, verá que ya existe un valor para la categoría 123 . Luego compararía el nuevo valor con el valor existente y vería que no son iguales. En este caso, se crea una matriz o lista vinculada para esa clave. En este punto, la recuperación de este valor se convierte en O(n) ya que la tabla hash necesita iterar a través de cada valor en ese depósito para encontrar el deseado.

Por esta razón, cuando se usa una tabla hash, es importante usar una clave con una función hash realmente buena que sea rápida y no resulte en valores duplicados para diferentes objetos.

¿Tener sentido?

Answer 4

Tal vez estabas mirando la complejidad del espacio? Eso es O (n). Las otras complejidades son las esperadas en la entrada de la tabla hash . La complejidad de búsqueda se aproxima a O (1) a medida que aumenta el número de segmentos. Si en el peor de los casos tiene solo un contenedor en la tabla hash, entonces la complejidad de búsqueda es O (n).

Editar en respuesta al comentario No creo que sea correcto decir que O (1) es el caso promedio. Realmente es (como dice la página de wikipedia) O (1 + n / k) donde K es el tamaño de la tabla hash. Si K es lo suficientemente grande, entonces el resultado es efectivamente O (1). Pero supongamos que K es 10 y N es 100. En ese caso, cada cubo tendrá un promedio de 10 entradas, por lo que el tiempo de búsqueda definitivamente no es O (1); es una búsqueda lineal hasta con 10 entradas.

Answer 5

Las tablas hash son O(1) complejidad de caso promedio y amortized , sin embargo, sufre de O(n) peor complejidad de tiempo de caso . [Y creo que aquí es donde está tu confusión]

Las tablas Hash sufren de O(n) peor complejidad de tiempo debido a dos razones:

1. Si demasiados elementos se convirtieron en hash en la misma clave: mirar dentro de esta clave puede tomar O(n) tiempo.
2. Una vez que una tabla hash ha superado su balance de carga , tiene que volver a generar [crear una nueva tabla más grande, y volver a insertar cada elemento en la tabla].

Sin embargo, se dice que es O(1) promedio y amortizado porque:

1. Es muy raro que muchos elementos se mezclen con la misma clave [si eliges una buena función hash y no tienes un balance de carga demasiado grande.
2. La operación de repetición, que es O(n) , puede suceder a lo sumo después de n/2 operaciones, todas asumidas O(1) : de esta forma, cuando sumas el tiempo promedio por operación, obtienes: (n*O(1) + O(n)) / n) = O(1)

Tenga en cuenta que debido al problema del reaprovisionamiento, las aplicaciones en tiempo real y las aplicaciones que necesitan baja latency , no deben usar una tabla hash como su estructura de datos.

EDITAR: Otro problema con las tablas hash: cache
Otro problema donde puede ver una pérdida de rendimiento en grandes tablas hash se debe al rendimiento de la memoria caché. Las tablas hash adolecen de un mal rendimiento de la memoria caché y, por lo tanto, de una gran recopilación: el tiempo de acceso puede llevar más tiempo, ya que debe volver a cargar la parte relevante de la tabla de la memoria en la memoria caché.