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

Question

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

En el wiki, la búsqueda y la eliminación son O (n) (pensé que el objetivo de las tablas hash era tener una búsqueda constante, entonces, ¿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 uso tablas hash estándar en un lenguaje como C++ o Java, ¿qué puedo esperar que sea la complejidad del tiempo?

Answer 1

Hash tables son O(1)media y amortized complejidad del caso, sin embargo, sufre de O(n)peor de los casos tiempo de complejidad.[Y creo que esto es donde la confusión es]

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

1. Si hay demasiados elementos fueron ordenada en la misma tecla: mirar dentro de esta clave puede tomar O(n) vez.
2. Una vez que una tabla hash ha pasado su load balance - 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) media y el caso se amortizan porque:

1. Es muy raro que muchos artículos serán hash a la misma tecla [si elige una buena función hash y se no tiene un balance de carga demasiado grande
2. La operación de repetición, que es O(n), puede a lo sumo a pasar después de n/2 ops, que son todos asumió O(1): Por lo tanto, cuando usted resume el tiempo promedio por OP, que se obtiene: (n*O(1) + O(n))/n) = O(1)

Nota debido a la refrito problema: las aplicaciones en tiempo real y las aplicaciones que necesitan baja latency - no deben usar una tabla hash como su estructura de datos.

EDIT: Annother problema con tablas hash: cache
Otro problema por el que es posible que vea una pérdida de rendimiento en grandes tablas hash se debe al rendimiento de la caché. Las tablas hash adolecen de un mal rendimiento de caché y, por lo tanto, para una gran colección: el tiempo de acceso puede llevar más tiempo, ya que necesita volver a cargar la parte relevante de la tabla de la memoria en la caché.

Answer 2

Depende del hash modo en que implementa, en el peor de los casos se puede ir a O (n), en el mejor de los casos es 0 (1) (por lo general se puede lograr si tu DS no es tan grande fácilmente)

Answer 3

¿Quizás estabas mirando la complejidad del espacio? Eso es O (n). Las otras complejidades son las esperadas en la entrada hash table. 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 4

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

Por ejemplo, imaginar las cadenas "era el mejor de los casos era el peor de los tiempos" y "Green Eggs and Ham" tanto como resultado un valor hash de 123.

Cuando se inserta la primera cuerda, se coloca en la cuchara 123. Cuando se inserta la segunda cuerda, verá que ya existe un valor para la cuchara 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.

¿Tiene sentido?

Answer 5

Algunas tablas hash (hash de cuco) han garantizado O (1) consulta de