algorithm - resolucion - utilizacion de tablas hash

¿Pueden las tablas hash realmente ser O(1)? (6)

Parece ser de conocimiento común que las tablas hash pueden alcanzar O (1), pero eso nunca tuvo sentido para mí. ¿Alguien puede explicarlo? Aquí hay dos situaciones que te vienen a la mente:

A. El valor es un int más pequeño que el tamaño de la tabla hash. Por lo tanto, el valor es su propio hash, por lo que no hay tabla hash. Pero si lo hubiera, sería O (1) y aún sería ineficiente.

B. Tienes que calcular un hash del valor. En esta situación, el orden es O (n) para el tamaño de los datos que se buscan. La búsqueda puede ser O (1) después de hacer O (n) trabajo, pero eso todavía me llega a O (n) en mis ojos.

Y a menos que tenga un hash perfecto o una tabla hash grande, probablemente haya varios artículos por cubo. Por lo tanto, se convierte en una pequeña búsqueda lineal en algún momento de todos modos.

Creo que las tablas hash son increíbles, pero no obtengo la designación O (1) a menos que se suponga que sean teóricas.

El artículo de Wikipedia para tablas hash hace referencia constantemente al tiempo constante de búsqueda e ignora por completo el costo de la función hash. ¿Es realmente una medida justa?

Editar: Para resumir lo que aprendí:

Es técnicamente cierto porque la función hash no es necesaria para usar toda la información en la clave y, por lo tanto, puede ser un tiempo constante, y porque una tabla suficientemente grande puede provocar colisiones casi a tiempo constante.
Es cierto en la práctica porque a lo largo del tiempo simplemente funciona siempre que se elijan la función hash y el tamaño de la tabla para minimizar las colisiones, aunque eso a menudo signifique no utilizar una función hash de tiempo constante.

Tienes que calcular el hash, por lo que el orden es O (n) para el tamaño de los datos que se buscan. La búsqueda puede ser O (1) después de hacer O (n) trabajo, pero eso todavía me llega a O (n) en mis ojos.

¿Qué? Para hash un solo elemento lleva tiempo constante. ¿Por qué sería algo más? Si está insertando n elementos, entonces sí, debe calcular n hashes, y eso lleva tiempo lineal ... buscar un elemento, calcular un solo hash de lo que está buscando y luego encontrar el cubo apropiado con ese. No vuelve a calcular los hash de todo lo que ya está en la tabla hash.

Y a menos que tenga un hash perfecto o una tabla de hash grande, probablemente haya varios elementos por cubo, por lo que se convierte en una pequeña búsqueda lineal en algún punto de todos modos.

No necesariamente. Los depósitos no tienen necesariamente que ser listas o matrices, pueden ser cualquier tipo de contenedor, como una BST equilibrada. Eso significa O(log n) peor caso. Pero esta es la razón por la cual es importante elegir una buena función de hash para evitar poner demasiados elementos en un solo cubo. Como KennyTM señaló, en promedio, todavía obtendrá O(1) vez, incluso si ocasionalmente tiene que escarbar en un cubo.

La compensación de tablas hash es, por supuesto, la complejidad del espacio. Está intercambiando espacio por tiempo, lo que parece ser el caso habitual en informática.

Usted menciona el uso de cadenas como claves en uno de sus otros comentarios. ¿Le preocupa la cantidad de tiempo que lleva computar el hash de una cadena, ya que consta de varios caracteres? Como alguien más señaló nuevamente, no necesariamente necesitas mirar todos los caracteres para calcular el hash, aunque podría producir un mejor hash si lo hicieras. En ese caso, si hay en promedio m caracteres en su clave, y los usó a todos para calcular su hash, entonces supongo que tiene razón, que las búsquedas tomarían O(m) . Si m >> n entonces podría tener un problema. Probablemente sería mejor con un BST en ese caso. O elija una función de hash más económica.

Aquí tiene dos variables, m y n, donde m es la longitud de la entrada yn es la cantidad de elementos en el hash.

El reclamo de rendimiento de búsqueda O (1) hace al menos dos suposiciones:

Sus objetos se pueden comparar en igualdad en O (1) tiempo.
Habrá pocas colisiones hash.

Si sus objetos son de tamaño variable y una verificación de igualdad requiere mirar todos los bits, entonces el rendimiento se convertirá en O (m). Sin embargo, la función hash no tiene que ser O (m) - puede ser O (1). A diferencia de un hash criptográfico, una función hash para usar en un diccionario no tiene que ver cada bit de la entrada para calcular el hash. Las implementaciones son libres de mirar solo una cantidad fija de bits.

Para un número suficiente de elementos, el número de elementos será mayor que el número de hashes posibles y luego se producirán colisiones que causan un aumento del rendimiento por encima de O (1), por ejemplo O (n) para un cruce simple de listas enlazadas (o O (n * m) si ambas suposiciones son falsas).

En la práctica, aunque la afirmación de O (1) es técnicamente falsa, es aproximadamente cierta para muchas situaciones del mundo real, y en particular aquellas situaciones en las que se cumplen las suposiciones anteriores.

El hash es de tamaño fijo: buscar el cubo de hash apropiado es una operación de costo fijo. Esto significa que es O (1).

Calcular el hash no tiene por qué ser una operación particularmente costosa; aquí no estamos hablando de funciones hash criptográficas. Pero eso es por el estilo. El cálculo de la función hash en sí mismo no depende del número n de elementos; aunque podría depender del tamaño de los datos en un elemento, esto no es a lo que n se refiere. Entonces el cálculo del hash no depende de n y también es O (1).

Hashing es O (1) solo si solo hay un número constante de claves en la tabla y se realizan otras suposiciones. Pero en tales casos tiene ventaja.

Si su clave tiene una representación de n bits, su función hash puede usar 1, 2, ... n de estos bits. Pensando en una función hash que usa 1 bit. La evaluación es O (1) con seguridad. Pero solo está dividiendo el espacio clave en 2. Entonces está mapeando hasta 2 ^ (n-1) claves en el mismo contenedor. utilizando la búsqueda BST esto lleva a n-1 pasos para localizar una clave en particular si está casi llena.

Puede extender esto para ver que si su función hash usa K bits, su tamaño de contenedor es 2 ^ (nk).

por lo tanto, función hash K-bit ==> no más de 2 ^ K contenedores eficaces ==> hasta 2 ^ (nK) n bits claves por bin ==> (nK) pasos (BST) para resolver colisiones. En realidad, la mayoría de las funciones hash son mucho menos "efectivas" y necesitan / usan más de K bits para producir 2 ^ k bins. Entonces incluso esto es optimista.

Puede verlo de esta manera: necesitará ~ n pasos para poder distinguir de manera única un par de claves de n bits en el peor de los casos. Realmente no hay forma de evitar el límite de la teoría de la información, la tabla hash o no.

Sin embargo, ¡NO se trata de cómo / cuándo se usa la tabla hash!

El análisis de complejidad asume que para las claves de n bits, podría tener claves O (2 ^ n) en la tabla (por ejemplo, 1/4 de todas las claves posibles). Pero la mayoría, sino todo el tiempo, usamos la tabla hash, solo tenemos un número constante de las claves de n bits en la tabla. Si solo quiere un número constante de claves en la tabla, por ejemplo, C es su número máximo, entonces podría formar una tabla hash de O (C) bins, que garantiza la colisión constante esperada (con una buena función hash); y una función hash que usa ~ logC de los n bits en la clave. Entonces, cada consulta es O (logC) = O (1). Así es como las personas afirman que "el acceso a la tabla hash es O (1)" /

Aquí hay un par de capturas: primero, decir que no necesitas todos los bits solo puede ser un truco de facturación. Primero, no se puede pasar realmente el valor clave a la función hash, porque eso estaría moviendo n bits en la memoria que es O (n). Entonces, debe hacer, por ejemplo, un paso de referencia. Pero aún necesita almacenarlo en algún lugar que ya fuera una operación O (n); simplemente no lo factura al hash; la tarea de cálculo general no puede evitar esto. En segundo lugar, realiza el hashing, encuentra el contenedor y encuentra más de 1 clave; su costo depende de su método de resolución: si hace una comparación (BST o Lista), tendrá la operación O (n) (la clave de recuperación es n-bit); si haces 2nd hash, bueno, tienes el mismo problema si 2nd hash tiene colisión. Por lo tanto, O (1) no está 100% garantizado a menos que no haya una colisión (puede mejorar la posibilidad al tener una tabla con más contenedores que claves, pero aún así).

Considere la alternativa, por ejemplo, BST, en este caso. hay teclas C, por lo que una BST balanceada será O (logC) en profundidad, por lo que una búsqueda toma O (logC) pasos. Sin embargo, la comparación en este caso sería una operación O (n) ... por lo que parece que el hashing es una mejor opción en este caso.

Hay dos configuraciones bajo las cuales puede obtener O (1) veces de peor caso.

Si su configuración es estática, entonces el hash de FKS obtendrá las garantías O (1) más desfavorables. Pero como indicó, su configuración no es estática.
Si usa hash Cuckoo, entonces las consultas y eliminaciones son O (1) el peor de los casos, pero la inserción solo se espera O (1) . La función de hash de cuco funciona bastante bien si tienes un límite superior en el número total de inserciones, y configura el tamaño de la tabla para que sea aproximadamente un 25% más grande.

Copiado desde here

Parece estar basado en la discusión aquí, que si X es el techo de (número de elementos en la tabla / número de contenedores), entonces una mejor respuesta es O (log (X)) suponiendo una implementación eficiente de la búsqueda de contenedores.