La sección CFDictionary del Collections Programming Topics for Core Foundation (que usted debe mirar en si usted quiere saber más) afirma:
un diccionario un objeto de la CFDictionary tipo es un colección basada en hash cuyas claves para acceder a sus valores son arbitrarios, datos definidos por programa (o punteros a datos). Aunque la clave es por lo general una cadena (o, en Fundación Core, un objeto CFString), que puede ser cualquier cosa que pueda caber en el tamaño de un puntero en forma de un entero, una referencia a un objeto de infraestructura de núcleo, incluso un puntero a una estructura de datos (por improbable que pueda ser).
Esto es lo que Wikipedia tiene que decir acerca de las tablas hash:
Idealmente, la función hash debe asignar cada posible clave para un índice de ranura única , pero este ideal rara vez es alcanzable en la práctica (a menos las claves hash son fijas, es decir, las nuevas entradas nunca se agregan a la tabla después de crearse). En cambio, la mayoría de los diseños de tabla de hash asumen que de hash-colisiones diferentes claves que se correlacionan con el hash mismo valor-voluntad se producen y deben ser acomodados de alguna manera. En una tabla hash bien dimensionada, el costo promedio (número de instrucciones) para cada búsqueda es independiente del número de elementos almacenados en la tabla. Muchos de hash diseños de mesa también permiten inserciones arbitrarias y deleciones de pares de valores clave, en promedio constante (de hecho, amortizados) costo por operación.
Por lo tanto, el rendimiento depende de la calidad del hash. Si es bueno, entonces el acceso a los elementos debe ser una operación O (1) (es decir, no depende de la cantidad de elementos).
EDIT:
De hecho después de leer aún más las colecciones de programación Los temas de la Fundación Core, manzana da una respuesta a su pregunta:
El tiempo de acceso para un valor en un objeto CFDictionary se garantiza que en el peor de los casos O (log N) para cualquier implementación, pero a menudo es O (1) (tiempo constante). Las operaciones de inserción o eliminación generalmente están en el tiempo constante también, pero son O (N * log N) en el peor de los casos. Es más rápido acceder a los valores a través de una clave que acceder a ellos directamente. Los diccionarios tienden a utilizar significativamente más memoria que una matriz con el mismo número de valores.
es esencialmente una estructura de tabla hash, por lo tanto, Big-O para la búsqueda es O (1). Sin embargo, para evitar reasignaciones (y para lograr la complejidad de O (1)) debe usar dictionaryWithCapacity: para crear un nuevo diccionario con el tamaño apropiado con respecto al tamaño de su conjunto de datos.
El uso de dictionaryWithCapacity en el caso normal proporcionará un aumento mínimo o nulo del rendimiento. De hecho, los documentos de Apple dicen que es solo una pista. He comparado con tamaños de NSArray entre 10 y 10,000,000 y no encontré ninguna ventaja significativa. La principal desventaja es el gasto de tiempo y pensamiento en el cálculo que es mejor spendt – zaph
No puede garantizar que no habrá colisiones en la tabla, independientemente del tamaño de la tabla. –
¡despejado! ¡Gracias! ;) –
El hecho de que muestre O (log N) u O (1) hace que me pregunte si tienen una implementación de árbol negro rojo, o si el registro N da cuenta del encadenamiento duplicado. –
@JustinMeiners El peor caso es para las colisiones hash – JustSid