c# - ¿Por qué acceder a un elemento de un diccionario con la tecla O(1) aunque la función hash no sea O(1)?

dictionary hashtable (8)

el HashFunc sí tiene muchas operaciones detrás de escena

Eso es ciertamente cierto. Sin embargo, el número de estas operaciones depende del tamaño de la clave , no del tamaño de la tabla hash en la que se inserta la clave: el número de operaciones para calcular la función hash es el mismo para una clave en una tabla con diez o con diez mil entradas.

Es por eso que la llamada de la función hash a menudo se considera O (1). Esto funciona bien para claves de tamaño fijo (valores integrales y cadenas de longitud fija). También proporciona una aproximación decente para teclas de tamaño variable con un límite superior práctico.

En general, sin embargo, el tiempo de acceso de una tabla hash es O (k), donde k es el límite superior del tamaño de la clave hash.

Veo cómo puede acceder a su colección por clave. Sin embargo, la función hash en sí misma tiene muchas operaciones detrás de escena, ¿no?

Suponiendo que tiene una buena función hash que es muy eficiente, aún puede requerir muchas operaciones.

¿Se puede explicar esto?

Si un diccionario / mapa se implementa como un HashMap , tiene una mejor complejidad de caso de O(1) , ya que en el mejor de los casos requiere exactamente el cálculo del código hash del elemento clave para la recuperación, si no hay colisiones clave .

Un mapa hash puede tener una complejidad de tiempo de ejecución en el peor de los casos de O(n) si tiene muchas colisiones de teclas o una función hash muy mala, ya que en este caso se degrada a un escaneo lineal de toda la matriz que contiene los datos .

Además, O(1) no significa instantáneamente , significa que tiene una cantidad constante . Por lo tanto, elegir la implementación correcta para un diccionario también puede depender de la cantidad de elementos en la colección, ya que tener un costo constante muy alto para la función será mucho peor si solo hay unas pocas entradas.

Es por eso que los diccionarios / mapas se implementan de manera diferente para diferentes escenarios. Para Java, existen múltiples implementaciones diferentes, C ++ usa árboles rojos / negros, etc. Usted los elige en función de la cantidad de datos y de su mejor / promedio / peor tiempo de ejecución.

Significa que no importa el tamaño de su colección, aún le llevará casi la misma cantidad de tiempo recuperar a cualquiera de sus miembros.

En otras palabras, un diccionario con 5 miembros podríamos decir que podría tomar alrededor de 0.002 ms para acceder a uno de ellos, así como un diccionario de 25 miembros debería tomar algo similar. Big O significa complejidad algorítmica sobre el tamaño de la colección en lugar de declaraciones o funciones reales ejecutadas

Teóricamente sigue siendo O (n), porque en el peor de los casos, todos sus datos pueden terminar teniendo un hash idéntico y agruparse, en cuyo caso tendrá que pasarlos linealmente.

Una vez que se tiene en cuenta el hecho de que los diccionarios cada vez más grandes ocupan más memoria, descienden más allá de la jerarquía de caché y eventualmente reducen el espacio de intercambio en el disco, es difícil argumentar que realmente es O (1). El rendimiento del diccionario será más lento a medida que se haga más grande, lo que probablemente le otorgue complejidad de tiempo O (log N). No me creas Pruébelo usted mismo con 1, 100, 1000, 10000, etc., elementos de diccionario, hasta 100 mil millones, y mida cuánto tiempo lleva en la práctica buscar un elemento.

Sin embargo, si hace la suposición simplificadora de que toda la memoria de su sistema es memoria de acceso aleatorio y se puede acceder a ella en tiempo constante, puede afirmar que el diccionario es O (1). Esta suposición es común, aunque no es realmente cierta para ninguna máquina con espacio de intercambio de disco, y todavía es bastante discutible en cualquier caso, dados los diversos niveles de caché de la CPU.

Ver publicación ¿Qué significa "O (1) tiempo de acceso"?

El número de operaciones en una función hash es irrelevante siempre que lleve la misma cantidad de tiempo (constante) para CADA elemento de la colección. Por ejemplo, acceder a un elemento en una colección de 2 elementos toma .001 ms, pero también acceder a un elemento en una colección de 2,000,000,000 elementos toma .001 ms. Aunque la función hash puede contener cientos de sentencias if y cálculos múltiples.

de los documentos:

Recuperar un valor utilizando su clave es muy rápido, cercano a O (1), porque la clase T: System.Collections.Generic.Dictionary`2 se implementa como una tabla hash.

Por lo tanto, puede ser O (1) pero puede ser más lento. Aquí puede encontrar otro hilo sobre el rendimiento de la tabla hash: Hash table: ¿por qué es más rápido que las matrices?

O(1) no significa instantáneo. O(1) significa constante sin tener en cuenta el tamaño de los datos . La función hash toma una cierta cantidad de tiempo, pero esa cantidad de tiempo no se escala con el tamaño de la colección.