¿Cómo tiene hash un tiempo de búsqueda o (1)? [duplicate]

4 minutos de lectura

avatar de usuario
algo-geeks

Cuando usamos un HashTable para almacenar datos, se dice que la búsqueda lleva o(1) tiempo. Estoy confundido, ¿alguien puede explicarme?

  • El costo de búsqueda en hashTable es una constante amortizada O (1): la mayoría de las veces solo hacemos un trabajo constante, pero de vez en cuando (donde hay colisiones) hacemos algunas comparaciones directas que nuevamente pueden ser una búsqueda binaria o lineal.

    – RBT

    19 de noviembre de 2016 a las 2:42

Bueno, es un poco un poco de mentira, puede tomar más tiempo que eso, pero por lo general no lo hace.

Básicamente, una tabla hash es una matriz que contiene todas las claves para buscar. La posición de cada tecla en la matriz está determinada por la función hash, que puede ser cualquier función que siempre asigne la misma entrada a la misma salida. Supondremos que la función hash es O(1).

Entonces, cuando insertamos algo en la tabla hash, usamos la función hash (llamémosla h) para encontrar la ubicación donde colocarlo y colocarlo allí. Ahora insertamos otra cosa, hashing y almacenamiento. Y otro. Cada vez que insertamos datos, se tarda O(1) en insertarlos (ya que la función hash es O(1).

Buscar datos es lo mismo. Si queremos encontrar un valor, Xsolo tenemos que averiguar h(x), que nos dice dónde X se encuentra en la tabla hash. Entonces podemos buscar cualquier valor hash en O(1) también.

Ahora a la mentira: lo anterior es una muy buena teoría con un problema: ¿qué pasa si insertamos datos y ya hay algo en esa posición de la matriz? No hay nada que garantice que la función hash no producirá el mismo resultado para dos entradas diferentes (a menos que tenga un función hash perfecta, pero son difíciles de producir). Por lo tanto, cuando insertamos necesitamos tomar una de dos estrategias:

  • Almacene múltiples valores en cada punto de la matriz (digamos, cada ranura de la matriz tiene una lista vinculada). Ahora, cuando realiza una búsqueda, todavía es O (1) para llegar al lugar correcto en la matriz, pero potencialmente una búsqueda lineal en una lista enlazada (con suerte corta). Esto se llama “encadenamiento separado”.
  • Si encuentra que algo ya está allí, vuelva a hacer hash y busque otra ubicación. Repita hasta que encuentre un lugar vacío y colóquelo allí. El procedimiento de búsqueda puede seguir las mismas reglas para encontrar los datos. Ahora todavía es O (1) para llegar a la primera ubicación, pero hay una búsqueda lineal potencial (con suerte corta) para rebotar alrededor de la tabla hasta que encuentre los datos que está buscando. Esto se llama “direccionamiento abierto”.

Básicamente, ambos enfoques siguen siendo principalmente O(1) pero con una secuencia lineal con suerte corta. Podemos suponer para la mayoría de los propósitos que es O(1). Si la tabla hash se está llenando demasiado, esas búsquedas lineales pueden volverse más y más largas, y entonces es hora de “volver a hacer hash”, lo que significa crear una nueva tabla hash de un tamaño mucho más grande e insertar todos los datos nuevamente en ella. .

  • muchas gracias por la explicacion..

    – algo-geeks

    6 de diciembre de 2010 a las 5:50

  • +1: para explicarlo bellamente, también existen otras técnicas para evitar colisiones como “Encadenamiento utilizado básicamente por Dictionary, Double Hashing, etc.”.

    – TalentTuner

    6 de diciembre de 2010 a las 5:53


  • @ usuario531802 No hay problema. Si está satisfecho con esta respuesta, ¿podría marcar la casilla de verificación “respuesta aceptada”?

    – mgiuca

    6 de diciembre de 2010 a las 6:25

  • whoa — entonces el hash es la matriz índicey no un índice de búsqueda lineal?

    – Simón Kuang

    17 de julio de 2014 a las 17:46

  • para bien explicar sobre esto – the hash table is getting too full, those linear searches can become longer and longer, and then it is time to "re-hash" which means to create a new hash table of a much bigger size mira esto – stackoverflow.com/questions/2369467/…

    – RBT

    19 de noviembre de 2016 a las 2:49

avatar de usuario
TalentTuner

La búsqueda lleva un tiempo O(1) si no hay colisiones en la tabla hash, por lo que es incorrecto afirmar que la búsqueda en una tabla hash lleva O(1) o un tiempo constante.

¿Ves cómo funciona Hashtable en MSDN?

EDITAR

mgiuca lo explica maravillosamente y solo estoy agregando una técnica más para evitar colisiones que se llama Encadenamiento.

En esta técnica, mantenemos una lista de enlaces de valores en cada ubicación, de modo que cuando tenga una colisión, su valor se agregará a la lista de enlaces en esa posición, de modo que cuando esté buscando un valor, puede haber un escenario en el que necesite buscar el valor. en toda la lista de enlaces, por lo que en ese caso la búsqueda no será una operación O (1).

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad