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

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

A. El valor es un int menor que el tamaño de la tabla hash. Por lo tanto, el valor es su propio hash, por lo que no hay una 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 podría ser O (1) después de que hagas el trabajo de O (n), pero eso todavía me sale a O (n).

Y a menos que tenga un hash perfecto o una tabla de hash grande, probablemente haya varios elementos 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 sea teórico.

El artículo de Wikipedia sobre tablas hash hace referencia constantemente al tiempo de búsqueda constante 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 no se requiere que la función hash utilice toda la información en la clave y, por lo tanto, podría ser un tiempo constante, y porque una tabla lo suficientemente grande puede reducir las colisiones a un tiempo casi constante.

• Es cierto en la práctica porque con el tiempo funciona siempre que se elijan la función hash y el tamaño de la tabla para minimizar las colisiones, aunque eso a menudo significa no usar una función hash de tiempo constante.

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

La afirmación de rendimiento de búsqueda de O (1) hace al menos dos suposiciones:

• Sus objetos pueden ser iguales comparados en O (1) tiempo.
• Habrá pocas colisiones de hash.

Si sus objetos son de tamaño variable y una verificación de igualdad requiere mirar todos los bits, 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 mirar cada bit en la entrada para calcular el hash. Las implementaciones son libres de mirar solo un número fijo de bits.

Para un número suficiente de elementos, el número de elementos será mayor que el número de posibles hashes y luego se producirán colisiones que harán que el rendimiento aumente por encima de O (1), por ejemplo, O (n) para un recorrido de lista enlazado simple (o O (n * m) si ambos supuestos son falsos).

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

Debe calcular el hash, por lo que el orden es O (n) para el tamaño de los datos que se buscan. La búsqueda podría ser O (1) después de que hagas el trabajo de O (n), pero eso todavía me sale a O (n).

¿Qué? Hacer hash de un solo elemento lleva un tiempo constante. ¿Por qué sería otra cosa? Si está insertando nelementos, entonces sí, tiene que calcular nhashes, y eso lleva un tiempo lineal ... para buscar un elemento, calcula un solo hash de lo que está buscando, luego encuentra el cubo apropiado con ese . No vuelve a calcular los valores 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 de todos modos se convierte en una pequeña búsqueda lineal en algún momento.

No necesariamente. Los depósitos no necesariamente tienen que ser listas o matrices, pueden ser de cualquier tipo de contenedor, como un BST equilibrado. Eso significa el O(log n)peor de los casos. Pero esta es la razón por la que es importante elegir una buena función hash para evitar poner demasiados elementos en un cubo. Como señaló Kenny TM, en promedio, todavía tendrá O(1)tiempo, incluso si ocasionalmente tiene que excavar en un cubo.

La compensación de las tablas hash es, por supuesto, la complejidad del espacio. Estás intercambiando espacio por tiempo, que parece ser el caso habitual en la ciencia de la computación.

Mencionas el uso de cadenas como claves en uno de tus otros comentarios. ¿Le preocupa la cantidad de tiempo que se tarda en calcular el hash de una cadena porque consta de varios caracteres? Como otra persona señaló nuevamente, no es necesario que mire todos los caracteres para calcular el hash, aunque podría producir un mejor hash si lo hiciera. En ese caso, si hay un promedio de mcaracteres en su clave, y los usó todos para calcular su hash, entonces supongo que tiene razón, esas búsquedas tomarían O(m). Sim >> n es posible que tenga un problema. Probablemente estaría mejor con un BST en ese caso. O elija una función hash más barata.

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 de hash criptográficas. Pero eso es por cierto. El cálculo de la función hash en sí no depende del número n de elementos; si bien puede depender del tamaño de los datos en un elemento, esto no es a lo que se refiere n . Entonces, el cálculo del hash no depende de ny también es O (1).

El hash es O (1) solo si solo hay un número constante de claves en la tabla y se hacen algunas 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) seguro. Pero solo está dividiendo el espacio de claves en 2. Por lo tanto, está mapeando hasta 2 ^ (n-1) claves en el mismo contenedor. al usar la búsqueda BST, se necesitan hasta n-1 pasos para localizar una tecla en particular si está casi llena.

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

entonces la función hash de K-bit ==> no más de 2 ^ K contenedores efectivos ==> hasta 2 ^ (nK) claves de n bits por contenedor ==> (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. Así que incluso esto es optimista.

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

Sin embargo, ¡así NO es cómo / cuándo usa la tabla hash!

El análisis de complejidad asume que para 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 de las veces, si no todo, usamos la tabla hash, solo tenemos un número constante de claves de n bits en la tabla. Si solo desea un número constante de claves en la tabla, digamos que 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 usando ~ logC de los n bits en la clave. Entonces, cada consulta es O (logC) = O (1). Así es como la gente afirma que "el acceso a la tabla hash es O (1)" /

Aquí hay un par de trampas: primero, decir que no necesita todos los bits puede ser solo un truco de facturación. Primero, realmente no puede pasar el valor de la clave a la función hash, porque eso sería mover n bits en la memoria, que es O (n). Entonces necesitas hacer, por ejemplo, un pase de referencia. Pero aún necesita almacenarlo en algún lugar que ya fue una operación O (n); simplemente no lo factura al hash; su tarea de cálculo general no puede evitar esto. En segundo lugar, realiza el hash, busca el contenedor y encuentra más de 1 claves; su costo depende de su método de resolución: si realiza una comparación (BST o Lista), tendrá la operación O (n) (la clave de recuperación es de n bits); si hace el segundo hash, bueno, tiene el mismo problema si el segundo hash tiene colisión.

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

TL; DR: Las tablas hash garantizan el O(1)peor tiempo esperado si elige su función hash de manera uniforme al azar de una familia universal de funciones hash. El peor caso esperado no es el mismo que el caso promedio.

Descargo de responsabilidad: no pruebo formalmente que las tablas hash lo sean O(1), para eso eche un vistazo a este video de coursera [ 1 ]. Tampoco hablo de lo amortizado aspectos de las tablas hash. Eso es ortogonal a la discusión sobre hash y colisiones.

Veo una gran confusión en torno a este tema en otras respuestas y comentarios, e intentaré rectificar algunos de ellos en esta larga respuesta.

Razonamiento sobre el peor de los casos

Hay diferentes tipos de análisis del peor de los casos. El análisis que la mayoría de las respuestas han hecho aquí hasta ahora no es el peor de los casos, sino un caso promedio [ 2 ]. El análisis de casos promedio tiende a ser más práctico. Tal vez su algoritmo tenga una entrada en el peor de los casos, pero en realidad funciona bien para todas las demás entradas posibles. La conclusión es que su tiempo de ejecución depende del conjunto de datos en el que se está ejecutando.

Considere el siguiente pseudocódigo del getmétodo de una tabla hash. Aquí supongo que manejamos la colisión mediante el encadenamiento, por lo que cada entrada de la tabla es una lista vinculada de (key,value)pares. También asumimos que el número de cubos mes fijo pero esO(n) , donde nes el número de elementos en la entrada.

function get(a: Table with m buckets, k: Key being looked up)
  bucket <- compute hash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Como han señalado otras respuestas, esto O(1)ocurre en promedio y en el peor de los casos O(n). Podemos hacer un pequeño bosquejo de una prueba por desafío aquí. El desafío es el siguiente:

(1) Le da su algoritmo de tabla hash a un adversario.

(2) El adversario puede estudiarlo y prepararse todo el tiempo que quiera.

(3) Finalmente, el adversario te da una entrada de tamaño. n para que la inserte en su tabla.

La pregunta es: ¿qué tan rápido es su tabla hash en la entrada del adversario?

Desde el paso (1) el adversario conoce su función hash; durante el paso (2) el adversario puede elaborar una lista de nelementos con los mismos hash modulo m, por ejemplo, calculando aleatoriamente el hash de un grupo de elementos; y luego en (3) te pueden dar esa lista. Pero he aquí, dado que todos los nelementos se transfieren al mismo grupo, su algoritmo tardará O(n)en recorrer la lista vinculada en ese grupo. No importa cuántas veces volvamos a intentar el desafío, el adversario siempre gana, y así de malo es su algoritmo, en el peor de los casos O(n).

¿Por qué el hash es O (1)?

Lo que nos desconcertó en el desafío anterior fue que el adversario conocía muy bien nuestra función hash y podía usar ese conocimiento para elaborar la peor entrada posible. ¿Qué pasa si en lugar de usar siempre una función hash fija, en realidad tuviéramos un conjunto de funciones hash H, que el algoritmo puede elegir aleatoriamente en tiempo de ejecución? En caso de que tenga curiosidad, Hse denomina familia universal de funciones hash [ 3 ]. Muy bien, intentemos agregar algo de aleatoriedad a esto.

Primero, suponga que nuestra tabla hash también incluye una semilla ry rse le asigna un número aleatorio en el momento de la construcción. Lo asignamos una vez y luego se corrige para esa instancia de tabla hash. Ahora revisemos nuestro pseudocódigo.

function get(a: Table with m buckets and seed r, k: Key being looked up)
  rHash <- H[r]
  bucket <- compute rHash(k) modulo m
  for each (key,value) in a[bucket]
    return value if k == key
  return not_found

Si intentamos el desafío una vez más: desde el paso (1) el adversario puede conocer todas las funciones hash que tenemos en H, pero ahora depende de la función hash específica que usemos r. El valor de res privado para nuestra estructura, el adversario no puede inspeccionarlo en tiempo de ejecución ni predecirlo con anticipación, por lo que no puede elaborar una lista que siempre sea mala para nosotros. Vamos a suponer que en el paso (2) adversario elige una función hashen Hal azar, entonces la artesanía en una lista de ncolisiones menores hash modulo m, y manda que para la etapa (3), cruzando los dedos para que en tiempo de ejecución H[r]serán los mismos hashque eligieron.

Esta es una apuesta seria para el adversario, la lista que elaboró ​​colisiona debajo hash, pero solo será una entrada aleatoria en cualquier otra función hash en H. Si gana esta apuesta, nuestro tiempo de ejecución será el peor de los casos, O(n)como antes, pero si pierde, entonces solo nos están dando una entrada aleatoria que toma el O(1)tiempo promedio . Y de hecho, la mayoría de las veces el adversario perderá, solo ganará una vez en cada |H|desafío, y podemos hacer que |H|sea ​​muy grande.

Compare este resultado con el algoritmo anterior donde el adversario siempre ganaba el desafío. Agitando un poco la mano aquí, pero dado que la mayoría de las veces el adversario fallará, y esto es cierto para todas las estrategias posibles que el adversario puede probar, se deduce que aunque el peor de los casos es O(n), el peor de los casos esperado es de hecho O(1).

Nuevamente, esta no es una prueba formal. La garantía que obtenemos de este análisis esperado del peor de los casos es que nuestro tiempo de ejecución ahora es independiente de cualquier entrada específica . Esta es una garantía verdaderamente aleatoria, a diferencia del análisis de casos promedio en el que mostramos que un adversario motivado podría fácilmente crear malas entradas.

Hay dos configuraciones bajo las cuales puede obtener O (1) tiempos en el peor de los casos.

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

Copiado de aquí

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

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

Este es un caso en el que podría mapear trivialmente las claves a distintos depósitos, por lo que una matriz parece una mejor opción de estructura de datos que una tabla hash. Aún así, las ineficiencias no aumentan con el tamaño de la mesa.

(Es posible que aún use una tabla hash porque no confía en que los enteros permanezcan más pequeños que el tamaño de la tabla a medida que el programa evoluciona, desea hacer que el código sea potencialmente reutilizable cuando esa relación no se cumple, o simplemente no lo hace quieren que las personas que leen / mantienen el código tengan que desperdiciar su esfuerzo mental en comprender y mantener la relación).

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 podría ser O (1) después de que hagas el trabajo de O (n), pero eso todavía me sale a O (n).

Necesitamos distinguir entre el tamaño de la clave (por ejemplo, en bytes) y el tamaño del número de claves que se almacenan en la tabla hash. Las afirmaciones de que las tablas hash proporcionan operaciones O (1) significan que las operaciones (insertar / borrar / buscar) no tienden a ralentizarse más a medida que la cantidad de claves aumenta de cientos a miles a millones a miles de millones (al menos no si todos los datos se accede / actualiza en un almacenamiento igualmente rápido, ya sea RAM o disco, los efectos de caché pueden entrar en juego, pero incluso el costo de una falla de caché en el peor de los casos tiende a ser un múltiplo constante del golpe en el mejor de los casos).

Considere una guía telefónica: puede tener nombres que sean bastante largos, pero ya sea que el libro tenga 100 nombres o 10 millones, la longitud promedio del nombre será bastante consistente y el peor de los casos en la historia ...

El récord mundial Guinness para el nombre más largo usado por alguien fue establecido por Adolph Blaine Charles David Earl Frederick Gerald Hubert Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Senior

... wcme dice que es 215 caracteres - Eso no es una fuerza superior, unidos a la longitud de la clave, pero no tiene que preocuparse acerca de que hay masivamente más.

Eso es válido para la mayoría de las tablas hash del mundo real: la longitud promedio de la clave no tiende a crecer con la cantidad de claves en uso. Hay excepciones, por ejemplo, una rutina de creación de claves puede devolver cadenas que incorporan números enteros en aumento, pero incluso entonces, cada vez que aumenta el número de claves en un orden de magnitud, solo aumenta la longitud de la clave en 1 carácter: no es significativo.

También es posible crear un hash a partir de una cantidad de datos clave de tamaño fijo. Por ejemplo, Visual C ++ de Microsoft se envía con una implementación de biblioteca estándar std::hash<std::string>que crea un hash que incorpora solo diez bytes espaciados uniformemente a lo largo de la cadena, por lo que si las cadenas solo varían en otros índices, obtendrá colisiones (y, por lo tanto, en la práctica, comportamientos no O (1) en el lado de la búsqueda posterior a la colisión), pero el tiempo para crear el hash tiene un límite superior difícil.

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

Generalmente es cierto, pero lo asombroso de las tablas hash es que la cantidad de claves visitadas durante esas "pequeñas búsquedas lineales" es, para el enfoque de encadenamiento separado para las colisiones, una función del factor de carga de la tabla hash (relación de claves a cubos).

Por ejemplo, con un factor de carga de 1.0, hay un promedio de ~ 1.58 para la duración de esas búsquedas lineales, independientemente del número de claves (vea mi respuesta aquí ). El hash cerrado es un poco más complicado, pero no mucho peor cuando el factor de carga no es demasiado alto.

Es técnicamente cierto porque no se requiere que la función hash utilice toda la información en la clave y, por lo tanto, podría ser un tiempo constante, y porque una tabla lo suficientemente grande puede reducir las colisiones a un tiempo casi constante.

Este tipo de pierde el punto. En última instancia, cualquier tipo de estructura de datos asociativa tiene que realizar operaciones en todas las partes de la clave a veces (la desigualdad a veces se puede determinar a partir de solo una parte de la clave, pero la igualdad generalmente requiere que se considere cada bit). Como mínimo, puede aplicar hash a la clave una vez y almacenar el valor hash, y si utiliza una función hash lo suficientemente fuerte, por ejemplo, MD5 de 64 bits, prácticamente podría ignorar incluso la posibilidad de que dos claves tengan el mismo valor (una empresa Trabajé para hacer exactamente eso para la base de datos distribuida: el tiempo de generación de hash aún era insignificante en comparación con las transmisiones de red en toda la WAN). Por lo tanto, no tiene mucho sentido obsesionarse con el costo de procesar la clave: eso es inherente al almacenamiento de claves independientemente de la estructura de datos y, como se dijo anteriormente, no lo hace.

En cuanto a tablas hash lo suficientemente grandes que reducen las colisiones, eso también está perdiendo el sentido. Para el encadenamiento por separado, todavía tiene una longitud de cadena de colisión promedio constante en cualquier factor de carga dado; es más alta cuando el factor de carga es más alto y esa relación no es lineal. El usuario de SO Hans comenta mi respuesta también enlazada arriba :

la longitud promedio del cucharón condicionada a cucharones no vacíos es una mejor medida de eficiencia. Es a / (1-e ^ {- a}) [donde a es el factor de carga, e es 2.71828 ...]

Por lo tanto, el factor de carga por sí solo determina la cantidad promedio de claves que colisionan en las que debe buscar durante las operaciones de inserción / borrado / búsqueda. Para el encadenamiento separado, no se trata solo de ser constante cuando el factor de carga es bajo, siempre es constante. Para el direccionamiento abierto, aunque su reclamo tiene cierta validez: algunos elementos en colisión se redirigen a depósitos alternativos y luego pueden interferir con las operaciones en otras claves, por lo que con factores de carga más altos (especialmente> .8 o .9), la longitud de la cadena de colisión empeora drásticamente.

Es cierto en la práctica porque con el tiempo funciona siempre que se elijan la función hash y el tamaño de la tabla para minimizar las colisiones, aunque eso a menudo significa no usar una función hash de tiempo constante.

Bueno, el tamaño de la tabla debería resultar en un factor de carga sensato dada la opción de hash cercano o encadenamiento separado, pero también si la función hash es un poco débil y las claves no son muy aleatorias, tener un número primo de cubos a menudo ayuda a reducir las colisiones también ( hash-value % table-sizeluego se envuelve de tal manera que los cambios solo en un bit de orden superior o dos en el valor hash aún se resuelven en cubos distribuidos pseudoaleatoriamente en diferentes partes de la tabla hash).