No entiendo esta explicación que dice que si n es el número de elementos en la tabla hash y m es el número total de cubetas, las tablas hash tienen tiempo de acceso constante en promedio solo si n es proporcional a theta (n). ¿Por qué tiene que ser proporcional?¿Por qué hashtable tiene un tiempo de acceso constante en promedio?
bien en realidad m debe ser proporcional a n. De lo contrario, podría, por ejemplo, tener solo 1 cubo y sería como un conjunto sin clasificar.
Para ser más precisos, si m es proporcional a n, es decir m = c * n, entonces el número de elementos en cada cubo será n/m = 1/c, que es una constante. Ir a cualquier cubo es una operación O (1) (simplemente calcule el código hash) y luego la búsqueda a través del cubo es de orden constante (podría hacer una búsqueda lineal a través de los elementos en el cubo que sería una constante).
Por lo tanto, el orden del algoritmo es O (1), si m = c * n.
Para tomar un ejemplo inverso, supongamos que tenemos una tabla de tamaño fijo tableSize. Entonces, el número esperado de elementos en cada segmento es n/tableSize, que es una función lineal de n. Cualquier tipo de búsqueda a través del cubo es, en el mejor de los casos, O (log (n)) para un árbol (supongo que no se pega otra tabla hash dentro del cubo o tenemos el mismo argumento sobre esa tabla hash), entonces no sería O (1) en este caso.
La probabilidad de colisiones es mayor y, por lo tanto, la incidencia de tener que escanear la lista de elementos con la misma clave hash también es mayor.
El tiempo de acceso es constante porque el acceso se basa en un cálculo de un valor hash y luego en una búsqueda constante para encontrar el depósito apropiado. Asumiendo que la función hash distribuye los artículos de manera uniforme entre los cubos, el tiempo necesario para acceder a cualquier elemento individual será igual al tiempo para acceder a otros elementos, independientemente de n.
Constante no significa necesariamente constantemente bajo. El tiempo de acceso promedio está relacionado con la distribución uniforme de la función de hash y el número de cubetas. Si tiene miles de artículos distribuidos uniformemente entre una pequeña cantidad de cubos, encontrará el cucharón rápidamente pero luego recorrerá muchos artículos en el balde. Si tiene una buena proporción de cubos para artículos pero una mala función hash que coloca muchos más artículos en algunos cubos en lugar de otros, el tiempo de acceso para los artículos en cubos más grandes será más lento que el tiempo de acceso para otros.
Una tabla hash de un tamaño razonable, donde hay suficientes ranuras para cada elemento almacenado y mucho espacio extra, tendrá la función hash haciendo la mayor parte del trabajo eligiendo ranuras y muy pocas colisiones donde diferentes elementos tengan el mismo hash . Una tabla hash muy concurrida tendría muchas colisiones y se degradaría básicamente a una búsqueda lineal, donde casi todas las búsquedas serían un elemento incorrecto que tuviera el mismo hash y tendrías que seguir buscando el correcto (una tabla hash la búsqueda todavía tiene que verificar la clave una vez que elige la primera ranura, porque la clave que está buscando podría haber tenido una colisión cuando se almacenó).
Lo que determina la proporción de colisión de golpe es exactamente la relación de número de elementos a tamaño de hash (es decir, el porcentaje de posibilidades de que se llene una ranura elegida al azar).
Estrictamente hablando, la complejidad del tiempo medio de caso del acceso a la tabla hash es en realidad en Ω (n 1/3). La información no puede viajar más rápido que la velocidad de la luz, que es una constante. Dado que el espacio tiene tres dimensiones, el almacenamiento de n bits de datos requiere que algunos datos se ubiquen a una distancia del orden de n 1/3 desde la CPU.
Más información in my blog.
Para agregar a esta respuesta, el tiempo de acceso constante es alcanzable no solo cuando los dos son proporcionales, sino cuando el número de elementos ('n') es menor o igual que el número de cubos (' m'). De lo contrario, tenemos una situación de 'O (1 + | k |)' donde k es la cantidad de elementos en el k-ésimo cubo. –
Eso es tiempo de acceso constante. O (1 + | k |) = O (1) si k es una constante. –
¿Qué pasa si usamos el direccionamiento abierto para resolver la colisión, en lugar de encadenar como se supone casi todos los análisis de la tabla hash? ¿El tiempo de acceso constante promedio aún se mantiene incluso m es proporcional a n? – sinoTrinity